md5.c

   1 /*@ S-nail - a mail user agent derived from Berkeley Mail.
   2  *@ MD5 / HMAC-MD5 algorithm implementation.
   3  *
   4  * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
   5  * Copyright (c) 2012 - 2013 Steffen "Daode" Nurpmeso <sdaoden@users.sf.net>.
   6  */
   7 /*
   8  * The MD5_CTX algorithm is derived from RFC 1321:
   9  */
  10 /* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
  11  */
  12 /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
  13 rights reserved.
  14
  15 License to copy and use this software is granted provided that it
  16 is identified as the "RSA Data Security, Inc. MD5 Message-Digest
  17 Algorithm" in all material mentioning or referencing this software
  18 or this function.
  19
  20 License is also granted to make and use derivative works provided
  21 that such works are identified as "derived from the RSA Data
  22 Security, Inc. MD5 Message-Digest Algorithm" in all material
  23 mentioning or referencing the derived work.
  24
  25 RSA Data Security, Inc. makes no representations concerning either
  26 the merchantability of this software or the suitability of this
  27 software for any particular purpose. It is provided "as is"
  28 without express or implied warranty of any kind.
  29
  30 These notices must be retained in any copies of any part of this
  31 documentation and/or software.
  32  */
  33
  34 /* hmac_md5() is derived from:
  35
  36 Network Working Group                                       H. Krawczyk
  37 Request for Comments: 2104                                          IBM
  38 Category: Informational                                      M. Bellare
  39                                                                    UCSD
  40                                                              R. Canetti
  41                                                                     IBM
  42                                                           February 1997
  43
  44
  45              HMAC: Keyed-Hashing for Message Authentication
  46
  47 Status of This Memo
  48
  49    This memo provides information for the Internet community.  This memo
  50    does not specify an Internet standard of any kind.  Distribution of
  51    this memo is unlimited.
  52
  53 Appendix -- Sample Code
  54
  55    For the sake of illustration we provide the following sample code for
  56    the implementation of HMAC-MD5 as well as some corresponding test
  57    vectors (the code is based on MD5 code as described in [MD5]).
  58 */
  59
  60 #include "config.h"
  61
  62 #ifndef HAVE_MD5
  63 typedef int avoid_empty_file_compiler_warning;
  64 #else
  65 #include <string.h>
  66
  67 #include "md5.h"
  68
  69 #define UINT4B_MAX      0xFFFFFFFFul
  70
  71 /*
  72  * Constants for MD5Transform routine.
  73  */
  74 #define S11 7
  75 #define S12 12
  76 #define S13 17
  77 #define S14 22
  78 #define S21 5
  79 #define S22 9
  80 #define S23 14
  81 #define S24 20
  82 #define S31 4
  83 #define S32 11
  84 #define S33 16
  85 #define S34 23
  86 #define S41 6
  87 #define S42 10
  88 #define S43 15
  89 #define S44 21
  90
  91 static unsigned char PADDING[64] = {
  92   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  93   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  94   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  95 };
  96
  97 /*
  98 #define F(x,y,z)        (((x) & (y))  |  ((~(x)) & (z)))
  99 #define G(x,y,z)        (((x) & (z))  |  ((y) & (~(z))))
 100 */
 101
 102 /* As pointed out by Wei Dai <weidai@eskimo.com>, the above can be
 103  * simplified to the code below.  Wei attributes these optimizations
 104  * to Peter Gutmann's SHS code, and he attributes it to Rich Schroeppel.
 105  */
 106 #define F(b,c,d)        ((((c) ^ (d)) & (b)) ^ (d))
 107 #define G(b,c,d)        ((((b) ^ (c)) & (d)) ^ (c))
 108 #define H(b,c,d)        ((b) ^ (c) ^ (d))
 109 #define I(b,c,d)        (((~(d) & UINT4B_MAX) | (b)) ^ (c))
 110
 111 /*
 112  * ROTATE_LEFT rotates x left n bits.
 113  */
 114 #define ROTATE_LEFT(x, n) ((((x) << (n)) & UINT4B_MAX) | ((x) >> (32 - (n))))
 115
 116 /*
 117  * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
 118  * Rotation is separate from addition to prevent recomputation.
 119  */
 120 #define FF(a, b, c, d, x, s, ac) { \
 121         (a) = ((a) + F(b, c, d) + (x) + ((ac) & UINT4B_MAX)) & UINT4B_MAX; \
 122         (a) = ROTATE_LEFT((a), (s)); \
 123         (a) = ((a) + (b)) & UINT4B_MAX; \
 124 }
 125
 126 #define GG(a, b, c, d, x, s, ac) { \
 127         (a) = ((a) + G(b, c, d) + (x) + ((ac) & UINT4B_MAX)) & UINT4B_MAX; \
 128         (a) = ROTATE_LEFT((a), (s)); \
 129         (a) = ((a) + (b)) & UINT4B_MAX; \
 130 }
 131
 132 #define HH(a, b, c, d, x, s, ac) { \
 133         (a) = ((a) + H(b, c, d) + (x) + ((ac) & UINT4B_MAX)) & UINT4B_MAX; \
 134         (a) = ROTATE_LEFT((a), (s)); \
 135         (a) = ((a) + (b)) & UINT4B_MAX; \
 136 }
 137
 138 #define II(a, b, c, d, x, s, ac) { \
 139         (a) = ((a) + I(b, c, d) + (x) + ((ac) & UINT4B_MAX)) & UINT4B_MAX; \
 140         (a) = ROTATE_LEFT((a), (s)); \
 141         (a) = ((a) + (b)) & UINT4B_MAX; \
 142 }
 143
 144 static void * ( *volatile _volatile_memset)(void*, int, size_t) = &(memset);
 145
 146 static void Encode(unsigned char *output, md5_type *input, unsigned int len);
 147 static void Decode(md5_type *output, unsigned char *input, unsigned int len);
 148 static void MD5Transform(md5_type state[], unsigned char block[]);
 149
 150 /*
 151  * Encodes input (md5_type) into output (unsigned char). Assumes len is
 152  * a multiple of 4.
 153  */
 154 static void
 155 Encode(unsigned char *output, md5_type *input, unsigned int len)
 156 {
 157         unsigned int i, j;
 158
 159         for (i = 0, j = 0; j < len; i++, j += 4) {
 160                 output[j] = input[i] & 0xff;
 161                 output[j+1] = (input[i] >> 8) & 0xff;
 162                 output[j+2] = (input[i] >> 16) & 0xff;
 163                 output[j+3] = (input[i] >> 24) & 0xff;
 164         }
 165 }
 166
 167 /*
 168  * Decodes input (unsigned char) into output (md5_type). Assumes len is
 169  * a multiple of 4.
 170  */
 171 static void
 172 Decode(md5_type *output, unsigned char *input, unsigned int len)
 173 {
 174         unsigned int    i, j;
 175
 176         for (i = 0, j = 0; j < len; i++, j += 4)
 177                 output[i] = ((md5_type)input[j] |
 178                         (md5_type)input[j+1] << 8 |
 179                         (md5_type)input[j+2] << 16 |
 180                         (md5_type)input[j+3] << 24) & UINT4B_MAX;
 181 }
 182
 183 /* MD5 basic transformation. Transforms state based on block. */
 184 static void
 185 MD5Transform(md5_type state[4], unsigned char block[64])
 186 {
 187         md5_type a = state[0], b = state[1], c = state[2], d = state[3],
 188                 x[16];
 189
 190         Decode(x, block, 64);
 191
 192         /* Round 1 */
 193         FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
 194         FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
 195         FF(c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
 196         FF(b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
 197         FF(a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
 198         FF(d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
 199         FF(c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
 200         FF(b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
 201         FF(a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
 202         FF(d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
 203         FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
 204         FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
 205         FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
 206         FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
 207         FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
 208         FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
 209
 210         /* Round 2 */
 211         GG(a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
 212         GG(d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
 213         GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
 214         GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
 215         GG(a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
 216         GG(d, a, b, c, x[10], S22,  0x2441453); /* 22 */
 217         GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
 218         GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
 219         GG(a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
 220         GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
 221         GG(c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
 222         GG(b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
 223         GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
 224         GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
 225         GG(c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
 226         GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
 227
 228         /* Round 3 */
 229         HH(a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
 230         HH(d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
 231         HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
 232         HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
 233         HH(a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
 234         HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
 235         HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
 236         HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
 237         HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
 238         HH(d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
 239         HH(c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
 240         HH(b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
 241         HH(a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
 242         HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
 243         HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
 244         HH(b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
 245
 246         /* Round 4 */
 247         II(a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
 248         II(d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
 249         II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
 250         II(b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
 251         II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
 252         II(d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
 253         II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
 254         II(b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
 255         II(a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
 256         II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
 257         II(c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
 258         II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
 259         II(a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
 260         II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
 261         II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
 262         II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
 263
 264         state[0] = (state[0] + a) & UINT4B_MAX;
 265         state[1] = (state[1] + b) & UINT4B_MAX;
 266         state[2] = (state[2] + c) & UINT4B_MAX;
 267         state[3] = (state[3] + d) & UINT4B_MAX;
 268
 269         /*
 270          * Zeroize sensitive information.
 271          */
 272         (*_volatile_memset)(x, 0, sizeof x);
 273 }
 274
 275 /*
 276  * MD5 initialization. Begins an MD5 operation, writing a new context.
 277  */
 278 void
 279 MD5Init (
 280     MD5_CTX *context    /* context */
 281 )
 282 {
 283         context->count[0] = context->count[1] = 0;
 284         /*
 285          * Load magic initialization constants.
 286          */
 287         context->state[0] = 0x67452301;
 288         context->state[1] = 0xefcdab89;
 289         context->state[2] = 0x98badcfe;
 290         context->state[3] = 0x10325476;
 291 }
 292
 293 /*
 294  * MD5 block update operation. Continues an MD5 message-digest
 295  * operation, processing another message block, and updating the
 296  * context.
 297  */
 298 void
 299 MD5Update (
 300     MD5_CTX *context,           /* context */
 301     unsigned char *input,               /* input block */
 302     unsigned int inputLen               /* length of input block */
 303 )
 304 {
 305         unsigned int i, idx, partLen;
 306
 307         /* Compute number of bytes mod 64 */
 308         idx = context->count[0]>>3 & 0x3F;
 309
 310         /* Update number of bits */
 311         if ((context->count[0] = (context->count[0] + (inputLen<<3)) &
 312                                         UINT4B_MAX)
 313                         < ((inputLen << 3) & UINT4B_MAX))
 314         context->count[1] = (context->count[1] + 1) & UINT4B_MAX;
 315         context->count[1] = (context->count[1] + (inputLen >> 29)) & UINT4B_MAX;
 316
 317         partLen = 64 - idx;
 318
 319         /*
 320          * Transform as many times as possible.
 321          */
 322         if (inputLen >= partLen) {
 323                 memcpy(&context->buffer[idx], input, partLen);
 324                 MD5Transform(context->state, context->buffer);
 325
 326                 for (i = partLen; i + 63 < inputLen; i += 64)
 327                         MD5Transform(context->state, &input[i]);
 328
 329                 idx = 0;
 330         } else
 331                 i = 0;
 332
 333         /* Buffer remaining input */
 334         memcpy(&context->buffer[idx], &input[i], inputLen-i);
 335 }
 336
 337 /*
 338  * MD5 finalization. Ends an MD5 message-digest operation, writing the
 339  * the message digest and zeroizing the context.
 340  */
 341 void
 342 MD5Final (
 343     unsigned char digest[16],   /* message digest */
 344     MD5_CTX *context            /* context */
 345 )
 346 {
 347         unsigned char   bits[8];
 348         unsigned int    idx, padLen;
 349
 350         /* Save number of bits */
 351         Encode(bits, context->count, 8);
 352
 353         /*
 354          * Pad out to 56 mod 64.
 355          */
 356         idx = context->count[0]>>3 & 0x3f;
 357         padLen = idx < 56 ? 56 - idx : 120 - idx;
 358         MD5Update(context, PADDING, padLen);
 359
 360         /* Append length (before padding) */
 361         MD5Update(context, bits, 8);
 362         /* Store state in digest */
 363         Encode(digest, context->state, 16);
 364
 365         /*
 366          * Zeroize sensitive information.
 367          */
 368         (*_volatile_memset)(context, 0, sizeof *context);
 369 }
 370
 371 void
 372 hmac_md5 (
 373     unsigned char *text,        /* pointer to data stream */
 374     int text_len,               /* length of data stream */
 375     unsigned char *key,         /* pointer to authentication key */
 376     int key_len,                /* length of authentication key */
 377     void *digest                /* caller digest to be filled in */
 378 )
 379 {
 380         MD5_CTX context;
 381         unsigned char k_ipad[65];    /* inner padding -
 382                                       * key XORd with ipad
 383                                       */
 384         unsigned char k_opad[65];    /* outer padding -
 385                                       * key XORd with opad
 386                                       */
 387         unsigned char tk[16];
 388         int i;
 389         /* if key is longer than 64 bytes reset it to key=MD5(key) */
 390         if (key_len > 64) {
 391
 392                 MD5_CTX      tctx;
 393
 394                 MD5Init(&tctx);
 395                 MD5Update(&tctx, key, key_len);
 396                 MD5Final(tk, &tctx);
 397
 398                 key = tk;
 399                 key_len = 16;
 400         }
 401
 402         /*
 403          * the HMAC_MD5 transform looks like:
 404          *
 405          * MD5(K XOR opad, MD5(K XOR ipad, text))
 406          *
 407          * where K is an n byte key
 408          * ipad is the byte 0x36 repeated 64 times
 409          * opad is the byte 0x5c repeated 64 times
 410          * and text is the data being protected
 411          */
 412
 413         /* start out by storing key in pads */
 414         memset(k_ipad, 0, sizeof k_ipad);
 415         memset(k_opad, 0, sizeof k_opad);
 416         memcpy(k_ipad, key, key_len);
 417         memcpy(k_opad, key, key_len);
 418
 419         /* XOR key with ipad and opad values */
 420         for (i=0; i<64; i++) {
 421                 k_ipad[i] ^= 0x36;
 422                 k_opad[i] ^= 0x5c;
 423         }
 424         /*
 425          * perform inner MD5
 426          */
 427         MD5Init(&context);                   /* init context for 1st
 428                                               * pass */
 429         MD5Update(&context, k_ipad, 64);             /* start with inner pad */
 430         MD5Update(&context, text, text_len); /* then text of datagram */
 431         MD5Final(digest, &context);          /* finish up 1st pass */
 432         /*
 433          * perform outer MD5
 434          */
 435         MD5Init(&context);                   /* init context for 2nd
 436                                               * pass */
 437         MD5Update(&context, k_opad, 64);     /* start with outer pad */
 438         MD5Update(&context, digest, 16);     /* then results of 1st
 439                                               * hash */
 440         MD5Final(digest, &context);          /* finish up 2nd pass */
 441 }
 442 #endif /* HAVE_MD5 */