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