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