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