lib/md5.c

   1 /* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
   2  */
   3
   4 /* Function names changed to avoid namespace collisions: Rob Siemborski */
   5
   6 /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
   7 rights reserved.
   8
   9 License to copy and use this software is granted provided that it
  10 is identified as the "RSA Data Security, Inc. MD5 Message-Digest
  11 Algorithm" in all material mentioning or referencing this software
  12 or this function.
  13
  14 License is also granted to make and use derivative works provided
  15 that such works are identified as "derived from the RSA Data
  16 Security, Inc. MD5 Message-Digest Algorithm" in all material
  17 mentioning or referencing the derived work.
  18
  19 RSA Data Security, Inc. makes no representations concerning either
  20 the merchantability of this software or the suitability of this
  21 software for any particular purpose. It is provided "as is"
  22 without express or implied warranty of any kind.
  23
  24 These notices must be retained in any copies of any part of this
  25 documentation and/or software.
  26 */
  27
  28 #include <config.h>
  29 #include "md5global.h"
  30 #include "md5.h"
  31 #include "hmac-md5.h"
  32
  33 #ifndef WIN32
  34 # include <arpa/inet.h>
  35 #endif
  36
  37 /* Constants for MD5Transform routine.
  38 */
  39
  40 #define S11 7
  41 #define S12 12
  42 #define S13 17
  43 #define S14 22
  44 #define S21 5
  45 #define S22 9
  46 #define S23 14
  47 #define S24 20
  48 #define S31 4
  49 #define S32 11
  50 #define S33 16
  51 #define S34 23
  52 #define S41 6
  53 #define S42 10
  54 #define S43 15
  55 #define S44 21
  56
  57 static void MD5Transform PROTO_LIST ((UINT4 [4], const unsigned char [64]));
  58 static void Encode PROTO_LIST
  59        ((unsigned char *, UINT4 *, unsigned int));
  60 static void Decode PROTO_LIST
  61        ((UINT4 *, const unsigned char *, unsigned int));
  62 static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
  63 static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));
  64
  65 static unsigned char PADDING[64] = {
  66        0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  67        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  68 };
  69
  70 /* F, G, H and I are basic MD5 functions.
  71
  72         */
  73 #ifdef I
  74 /* This might be defined via NANA */
  75 #undef I
  76 #endif
  77
  78 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  79 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
  80 #define H(x, y, z) ((x) ^ (y) ^ (z))
  81 #define I(x, y, z) ((y) ^ ((x) | (~z)))
  82
  83 /* ROTATE_LEFT rotates x left n bits.
  84
  85         */
  86
  87 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  88
  89 /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
  90 Rotation is separate from addition to prevent recomputation.
  91 */
  92
  93 #define FF(a, b, c, d, x, s, ac) { (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
  94 #define GG(a, b, c, d, x, s, ac) {        (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);         }
  95 #define HH(a, b, c, d, x, s, ac) {        (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
  96 #define II(a, b, c, d, x, s, ac) {        (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac);        (a) = ROTATE_LEFT ((a), (s));        (a) += (b);        }
  97
  98 /* MD5 initialization. Begins an MD5 operation, writing a new context.
  99 */
 100
 101 void _sasl_MD5Init (context)
 102 MD5_CTX *context; /* context */
 103 {
 104        context->count[0] = context->count[1] = 0;
 105
 106        /* Load magic initialization constants. */
 107        context->state[0] = 0x67452301;
 108        context->state[1] = 0xefcdab89;
 109        context->state[2] = 0x98badcfe;
 110        context->state[3] = 0x10325476;
 111 }
 112
 113 /* MD5 block update operation. Continues an MD5 message-digest
 114        operation, processing another message block, and updating the context.
 115 */
 116
 117 void _sasl_MD5Update (context, input, inputLen)
 118 MD5_CTX *context; /* context */
 119 const unsigned char *input; /* input block */
 120 unsigned int inputLen; /* length of input block */
 121 {
 122        unsigned int i, index, partLen;
 123
 124          /* Compute number of bytes mod 64 */
 125          index = (unsigned int)((context->count[0] >> 3) & 0x3F);
 126
 127          /* Update number of bits */
 128          if ((context->count[0] += ((UINT4)inputLen << 3))
 129           < ((UINT4)inputLen << 3))
 130         context->count[1]++;
 131          context->count[1] += ((UINT4)inputLen >> 29);
 132
 133        partLen = 64 - index;
 134
 135          /* Transform as many times as possible.
 136
 137 */
 138        if (inputLen >= partLen) {
 139        MD5_memcpy
 140        ((POINTER)&context->buffer[index], (POINTER)input, partLen); MD5Transform
 141        (context->state, context->buffer);
 142
 143        for (i = partLen; i + 63 < inputLen; i += 64)
 144        MD5Transform (context->state, &input[i]);
 145
 146        index = 0;
 147        }
 148        else
 149        i = 0;
 150
 151          /* Buffer remaining input */
 152          MD5_memcpy
 153         ((POINTER)&context->buffer[index], (POINTER)&input[i],
 154          inputLen-i);
 155
 156 }
 157
 158 /* MD5 finalization. Ends an MD5 message-digest operation, writing the
 159        the message digest and zeroizing the context.
 160 */
 161
 162 void _sasl_MD5Final (digest, context)
 163 unsigned char digest[16]; /* message digest */
 164 MD5_CTX *context; /* context */
 165 {
 166        unsigned char bits[8];
 167        unsigned int index, padLen;
 168
 169          /* Save number of bits */
 170          Encode (bits, context->count, 8);
 171
 172          /* Pad out to 56 mod 64. */
 173          index = (unsigned int)((context->count[0] >> 3) & 0x3f);
 174          padLen = (index < 56) ? (56 - index) : (120 - index);
 175          _sasl_MD5Update (context, PADDING, padLen);
 176
 177          /* Append length (before padding) */
 178          _sasl_MD5Update (context, bits, 8);
 179
 180          /* Store state in digest */
 181          Encode (digest, context->state, 16);
 182
 183          /* Zeroize sensitive information. */
 184        MD5_memset ((POINTER)context, 0, sizeof (*context));
 185 }
 186
 187 /* MD5 basic transformation. Transforms state based on block. */
 188
 189 static void MD5Transform (state, block)
 190 UINT4 state[4];
 191 const unsigned char block[64];
 192 {
 193        UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
 194
 195        Decode (x, block, 64);
 196
 197          /* Round 1 */
 198          FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
 199          FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
 200          FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
 201          FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
 202          FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
 203          FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
 204          FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
 205          FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
 206          FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
 207          FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
 208          FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
 209          FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
 210          FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
 211          FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
 212          FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
 213          FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
 214
 215         /* Round 2 */
 216          GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
 217          GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
 218          GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
 219          GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
 220          GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
 221          GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
 222          GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
 223          GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
 224          GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
 225          GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
 226          GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
 227          GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
 228          GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
 229          GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
 230          GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
 231          GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
 232
 233          /* Round 3 */
 234          HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
 235          HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
 236          HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
 237          HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
 238          HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
 239          HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
 240          HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
 241          HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
 242          HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
 243          HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
 244          HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
 245          HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
 246          HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
 247          HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
 248          HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
 249          HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
 250
 251          /* Round 4 */
 252          II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
 253          II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
 254          II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
 255          II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
 256          II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
 257          II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
 258          II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
 259          II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
 260          II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
 261          II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
 262          II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
 263          II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
 264          II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
 265          II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
 266          II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
 267          II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
 268
 269        state[0] += a;
 270        state[1] += b;
 271        state[2] += c;
 272        state[3] += d;
 273
 274          /* Zeroize sensitive information.
 275          */
 276        MD5_memset ((POINTER)x, 0, sizeof (x));
 277 }
 278
 279 /* Encodes input (UINT4) into output (unsigned char). Assumes len is
 280        a multiple of 4.
 281
 282         */
 283
 284 static void Encode (output, input, len)
 285 unsigned char *output;
 286 UINT4 *input;
 287 unsigned int len;
 288 {
 289        unsigned int i, j;
 290
 291        for (i = 0, j = 0; j < len; i++, j += 4) {
 292        output[j] = (unsigned char)(input[i] & 0xff);
 293        output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
 294        output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
 295        output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
 296        }
 297 }
 298
 299 /* Decodes input (unsigned char) into output (UINT4). Assumes len is
 300        a multiple of 4.
 301
 302         */
 303
 304 static void Decode (output, input, len)
 305 UINT4 *output;
 306 const unsigned char *input;
 307 unsigned int len;
 308 {
 309        unsigned int i, j;
 310
 311        for (i = 0, j = 0; j < len; i++, j += 4)
 312        output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) | (((UINT4)input[j+2]) << 16)
 313        | (((UINT4)input[j+3]) << 24);
 314 }
 315
 316 /* Note: Replace "for loop" with standard memcpy if possible.
 317
 318         */
 319
 320 static void MD5_memcpy (output, input, len)
 321 POINTER output;
 322 POINTER input;
 323 unsigned int len;
 324 {
 325        unsigned int i;
 326
 327        for (i = 0; i < len; i++)
 328               output[i] = input[i];
 329 }
 330
 331 /* Note: Replace "for loop" with standard memset if possible.
 332 */
 333
 334 static void MD5_memset (output, value, len)
 335 POINTER output;
 336 int value;
 337 unsigned int len;
 338 {
 339        unsigned int i;
 340
 341        for (i = 0; i < len; i++)
 342        ((char *)output)[i] = (char)value;
 343 }
 344
 345 void _sasl_hmac_md5_init(HMAC_MD5_CTX *hmac,
 346                          const unsigned char *key,
 347                          int key_len)
 348 {
 349   unsigned char k_ipad[65];    /* inner padding -
 350                                 * key XORd with ipad
 351                                 */
 352   unsigned char k_opad[65];    /* outer padding -
 353                                 * key XORd with opad
 354                                 */
 355   unsigned char tk[16];
 356   int i;
 357   /* if key is longer than 64 bytes reset it to key=MD5(key) */
 358   if (key_len > 64) {
 359
 360     MD5_CTX      tctx;
 361
 362     _sasl_MD5Init(&tctx);
 363     _sasl_MD5Update(&tctx, key, key_len);
 364     _sasl_MD5Final(tk, &tctx);
 365
 366     key = tk;
 367     key_len = 16;
 368   }
 369
 370   /*
 371    * the HMAC_MD5 transform looks like:
 372    *
 373    * MD5(K XOR opad, MD5(K XOR ipad, text))
 374    *
 375    * where K is an n byte key
 376    * ipad is the byte 0x36 repeated 64 times
 377    * opad is the byte 0x5c repeated 64 times
 378    * and text is the data being protected
 379    */
 380
 381   /* start out by storing key in pads */
 382   MD5_memset((POINTER)k_ipad, '\0', sizeof k_ipad);
 383   MD5_memset((POINTER)k_opad, '\0', sizeof k_opad);
 384   MD5_memcpy( k_ipad, (POINTER)key, key_len);
 385   MD5_memcpy( k_opad, (POINTER)key, key_len);
 386
 387   /* XOR key with ipad and opad values */
 388   for (i=0; i<64; i++) {
 389     k_ipad[i] ^= 0x36;
 390     k_opad[i] ^= 0x5c;
 391   }
 392
 393   _sasl_MD5Init(&hmac->ictx);                   /* init inner context */
 394   _sasl_MD5Update(&hmac->ictx, k_ipad, 64);     /* apply inner pad */
 395
 396   _sasl_MD5Init(&hmac->octx);                   /* init outer context */
 397   _sasl_MD5Update(&hmac->octx, k_opad, 64);     /* apply outer pad */
 398
 399   /* scrub the pads and key context (if used) */
 400   MD5_memset((POINTER)&k_ipad, 0, sizeof(k_ipad));
 401   MD5_memset((POINTER)&k_opad, 0, sizeof(k_opad));
 402   MD5_memset((POINTER)&tk, 0, sizeof(tk));
 403
 404   /* and we're done. */
 405 }
 406
 407 /* The precalc and import routines here rely on the fact that we pad
 408  * the key out to 64 bytes and use that to initialize the md5
 409  * contexts, and that updating an md5 context with 64 bytes of data
 410  * leaves nothing left over; all of the interesting state is contained
 411  * in the state field, and none of it is left over in the count and
 412  * buffer fields.  So all we have to do is save the state field; we
 413  * can zero the others when we reload it.  Which is why the decision
 414  * was made to pad the key out to 64 bytes in the first place. */
 415 void _sasl_hmac_md5_precalc(HMAC_MD5_STATE *state,
 416                             const unsigned char *key,
 417                             int key_len)
 418 {
 419   HMAC_MD5_CTX hmac;
 420   unsigned lupe;
 421
 422   _sasl_hmac_md5_init(&hmac, key, key_len);
 423   for (lupe = 0; lupe < 4; lupe++) {
 424     state->istate[lupe] = htonl(hmac.ictx.state[lupe]);
 425     state->ostate[lupe] = htonl(hmac.octx.state[lupe]);
 426   }
 427   MD5_memset((POINTER)&hmac, 0, sizeof(hmac));
 428 }
 429
 430
 431 void _sasl_hmac_md5_import(HMAC_MD5_CTX *hmac,
 432                      HMAC_MD5_STATE *state)
 433 {
 434   unsigned lupe;
 435   MD5_memset((POINTER)hmac, 0, sizeof(HMAC_MD5_CTX));
 436   for (lupe = 0; lupe < 4; lupe++) {
 437     hmac->ictx.state[lupe] = ntohl(state->istate[lupe]);
 438     hmac->octx.state[lupe] = ntohl(state->ostate[lupe]);
 439   }
 440   /* Init the counts to account for our having applied
 441    * 64 bytes of key; this works out to 0x200 (64 << 3; see
 442    * MD5Update above...) */
 443   hmac->ictx.count[0] = hmac->octx.count[0] = 0x200;
 444 }
 445
 446 void _sasl_hmac_md5_final(unsigned char digest[HMAC_MD5_SIZE],
 447                           HMAC_MD5_CTX *hmac)
 448 {
 449   _sasl_MD5Final(digest, &hmac->ictx);  /* Finalize inner md5 */
 450   _sasl_MD5Update(&hmac->octx, digest, 16); /* Update outer ctx */
 451   _sasl_MD5Final(digest, &hmac->octx); /* Finalize outer md5 */
 452 }
 453
 454
 455 void _sasl_hmac_md5(text, text_len, key, key_len, digest)
 456 const unsigned char* text; /* pointer to data stream */
 457 int text_len; /* length of data stream */
 458 const unsigned char* key; /* pointer to authentication key */
 459 int key_len; /* length of authentication key */
 460 unsigned char *digest; /* caller digest to be filled in */
 461 {
 462   MD5_CTX context;
 463
 464   unsigned char k_ipad[65];    /* inner padding -
 465                                 * key XORd with ipad
 466                                 */
 467   unsigned char k_opad[65];    /* outer padding -
 468                                 * key XORd with opad
 469                                 */
 470   unsigned char tk[16];
 471   int i;
 472   /* if key is longer than 64 bytes reset it to key=MD5(key) */
 473   if (key_len > 64) {
 474
 475     MD5_CTX      tctx;
 476
 477     _sasl_MD5Init(&tctx);
 478     _sasl_MD5Update(&tctx, key, key_len);
 479     _sasl_MD5Final(tk, &tctx);
 480
 481     key = tk;
 482     key_len = 16;
 483   }
 484
 485   /*
 486    * the HMAC_MD5 transform looks like:
 487    *
 488    * MD5(K XOR opad, MD5(K XOR ipad, text))
 489    *
 490    * where K is an n byte key
 491    * ipad is the byte 0x36 repeated 64 times
 492    * opad is the byte 0x5c repeated 64 times
 493    * and text is the data being protected
 494    */
 495
 496   /* start out by storing key in pads */
 497   MD5_memset(k_ipad, '\0', sizeof k_ipad);
 498   MD5_memset(k_opad, '\0', sizeof k_opad);
 499   MD5_memcpy( k_ipad, (POINTER)key, key_len);
 500   MD5_memcpy( k_opad, (POINTER)key, key_len);
 501
 502   /* XOR key with ipad and opad values */
 503   for (i=0; i<64; i++) {
 504     k_ipad[i] ^= 0x36;
 505     k_opad[i] ^= 0x5c;
 506   }
 507   /*
 508    * perform inner MD5
 509    */
 510
 511   _sasl_MD5Init(&context);                   /* init context for 1st
 512                                                * pass */
 513   _sasl_MD5Update(&context, k_ipad, 64);      /* start with inner pad */
 514   _sasl_MD5Update(&context, text, text_len); /* then text of datagram */
 515   _sasl_MD5Final(digest, &context);          /* finish up 1st pass */
 516
 517   /*
 518    * perform outer MD5
 519    */
 520   _sasl_MD5Init(&context);                   /* init context for 2nd
 521                                         * pass */
 522   _sasl_MD5Update(&context, k_opad, 64);     /* start with outer pad */
 523   _sasl_MD5Update(&context, digest, 16);     /* then results of 1st
 524                                         * hash */
 525   _sasl_MD5Final(digest, &context);          /* finish up 2nd pass */
 526
 527 }