2 * MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
4 * Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
7 * License to copy and use this software is granted provided that it
8 * is identified as the "RSA Data Security, Inc. MD5 Message-Digest
9 * Algorithm" in all material mentioning or referencing this software
12 * License is also granted to make and use derivative works provided
13 * that such works are identified as "derived from the RSA Data
14 * Security, Inc. MD5 Message-Digest Algorithm" in all material
15 * mentioning or referencing the derived work.
17 * RSA Data Security, Inc. makes no representations concerning either
18 * the merchantability of this software or the suitability of this
19 * software for any particular purpose. It is provided "as is"
20 * without express or implied warranty of any kind.
22 * These notices must be retained in any copies of any part of this
23 * documentation and/or software.
25 * $FreeBSD: src/lib/libmd/md5c.c,v 1.9.2.1 1999/08/29 14:57:12 peter Exp $
27 * This code is the same as the code published by RSA Inc. It has been
28 * edited for clarity and style only.
30 * ----------------------------------------------------------------------------
31 * The md5_crypt() function was taken from freeBSD's libcrypt and contains
33 * "THE BEER-WARE LICENSE" (Revision 42):
34 * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you
35 * can do whatever you want with this stuff. If we meet some day, and you think
36 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
38 * $FreeBSD: src/lib/libcrypt/crypt.c,v 1.7.2.1 1999/08/29 14:56:33 peter Exp $
40 * ----------------------------------------------------------------------------
41 * On April 19th, 2001 md5_crypt() was modified to make it reentrant
42 * by Erik Andersen <andersen@uclibc.org>
45 * June 28, 2001 Manuel Novoa III
47 * "Un-inlined" code using loops and static const tables in order to
48 * reduce generated code size (on i386 from approx 4k to approx 2.5k).
50 * June 29, 2001 Manuel Novoa III
52 * Completely removed static PADDING array.
54 * Reintroduced the loop unrolling in MD5_Transform and added the
55 * MD5_SIZE_OVER_SPEED option for configurability. Define below as:
56 * 0 fully unrolled loops
57 * 1 partially unrolled (4 ops per loop)
58 * 2 no unrolling -- introduces the need to swap 4 variables (slow)
59 * 3 no unrolling and all 4 loops merged into one with switch
60 * in each loop (glacial)
61 * On i386, sizes are roughly (-Os -fno-builtin):
62 * 0: 3k 1: 2.5k 2: 2.2k 3: 2k
65 * Since SuSv3 does not require crypt_r, modified again August 7, 2002
66 * by Erik Andersen to remove reentrance stuff...
70 * Valid values are 1 (fastest/largest) to 3 (smallest/slowest).
72 #define MD5_SIZE_OVER_SPEED 3
74 /**********************************************************************/
78 uint32_t state[4]; /* state (ABCD) */
79 uint32_t count[2]; /* number of bits, modulo 2^64 (lsb first) */
80 unsigned char buffer[64]; /* input buffer */
83 static void __md5_Init(struct MD5Context *);
84 static void __md5_Update(struct MD5Context *, const unsigned char *, unsigned int);
85 static void __md5_Pad(struct MD5Context *);
86 static void __md5_Final(unsigned char [16], struct MD5Context *);
87 static void __md5_Transform(uint32_t [4], const unsigned char [64]);
90 #define MD5_MAGIC_STR "$1$"
91 #define MD5_MAGIC_LEN (sizeof(MD5_MAGIC_STR) - 1)
92 static const unsigned char __md5__magic[] = MD5_MAGIC_STR;
96 #define __md5_Encode memcpy
97 #define __md5_Decode memcpy
101 * __md5_Encodes input (uint32_t) into output (unsigned char). Assumes len is
105 __md5_Encode(unsigned char *output, uint32_t *input, unsigned int len)
109 for (i = 0, j = 0; j < len; i++, j += 4) {
110 output[j] = input[i];
111 output[j+1] = (input[i] >> 8);
112 output[j+2] = (input[i] >> 16);
113 output[j+3] = (input[i] >> 24);
118 * __md5_Decodes input (unsigned char) into output (uint32_t). Assumes len is
122 __md5_Decode(uint32_t *output, const unsigned char *input, unsigned int len)
126 for (i = 0, j = 0; j < len; i++, j += 4)
127 output[i] = ((uint32_t)input[j]) | (((uint32_t)input[j+1]) << 8) |
128 (((uint32_t)input[j+2]) << 16) | (((uint32_t)input[j+3]) << 24);
132 /* F, G, H and I are basic MD5 functions. */
133 #define F(x, y, z) (((x) & (y)) | (~(x) & (z)))
134 #define G(x, y, z) (((x) & (z)) | ((y) & ~(z)))
135 #define H(x, y, z) ((x) ^ (y) ^ (z))
136 #define I(x, y, z) ((y) ^ ((x) | ~(z)))
138 /* ROTATE_LEFT rotates x left n bits. */
139 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
142 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
143 * Rotation is separate from addition to prevent recomputation.
145 #define FF(a, b, c, d, x, s, ac) { \
146 (a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
147 (a) = ROTATE_LEFT((a), (s)); \
150 #define GG(a, b, c, d, x, s, ac) { \
151 (a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
152 (a) = ROTATE_LEFT((a), (s)); \
155 #define HH(a, b, c, d, x, s, ac) { \
156 (a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
157 (a) = ROTATE_LEFT((a), (s)); \
160 #define II(a, b, c, d, x, s, ac) { \
161 (a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
162 (a) = ROTATE_LEFT((a), (s)); \
166 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
167 static void __md5_Init(struct MD5Context *context)
169 context->count[0] = context->count[1] = 0;
171 /* Load magic initialization constants. */
172 context->state[0] = 0x67452301;
173 context->state[1] = 0xefcdab89;
174 context->state[2] = 0x98badcfe;
175 context->state[3] = 0x10325476;
179 * MD5 block update operation. Continues an MD5 message-digest
180 * operation, processing another message block, and updating the
183 static void __md5_Update(struct MD5Context *context, const unsigned char *input, unsigned int inputLen)
185 unsigned int i, idx, partLen;
187 /* Compute number of bytes mod 64 */
188 idx = (context->count[0] >> 3) & 0x3F;
190 /* Update number of bits */
191 context->count[0] += (inputLen << 3);
192 if (context->count[0] < (inputLen << 3))
194 context->count[1] += (inputLen >> 29);
198 /* Transform as many times as possible. */
199 if (inputLen >= partLen) {
200 memcpy(&context->buffer[idx], input, partLen);
201 __md5_Transform(context->state, context->buffer);
203 for (i = partLen; i + 63 < inputLen; i += 64)
204 __md5_Transform(context->state, &input[i]);
210 /* Buffer remaining input */
211 memcpy(&context->buffer[idx], &input[i], inputLen - i);
215 * MD5 padding. Adds padding followed by original length.
217 static void __md5_Pad(struct MD5Context *context)
219 unsigned char bits[8];
220 unsigned int idx, padLen;
221 unsigned char PADDING[64];
223 memset(PADDING, 0, sizeof(PADDING));
226 /* Save number of bits */
227 __md5_Encode(bits, context->count, 8);
229 /* Pad out to 56 mod 64. */
230 idx = (context->count[0] >> 3) & 0x3f;
231 padLen = (idx < 56) ? (56 - idx) : (120 - idx);
232 __md5_Update(context, PADDING, padLen);
234 /* Append length (before padding) */
235 __md5_Update(context, bits, 8);
239 * MD5 finalization. Ends an MD5 message-digest operation, writing the
240 * the message digest and zeroizing the context.
242 static void __md5_Final(unsigned char digest[16], struct MD5Context *context)
247 /* Store state in digest */
248 __md5_Encode(digest, context->state, 16);
250 /* Zeroize sensitive information. */
251 memset(context, 0, sizeof(*context));
254 /* MD5 basic transformation. Transforms state based on block. */
255 static void __md5_Transform(uint32_t state[4], const unsigned char block[64])
257 uint32_t a, b, c, d, x[16];
258 #if MD5_SIZE_OVER_SPEED > 1
260 const unsigned char *ps;
262 static const unsigned char S[] = {
268 #endif /* MD5_SIZE_OVER_SPEED > 1 */
270 #if MD5_SIZE_OVER_SPEED > 0
272 const unsigned char *pp;
275 static const uint32_t C[] = {
277 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
278 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
279 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
280 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
282 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
283 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
284 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
285 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
287 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
288 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
289 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
290 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
292 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
293 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
294 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
295 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
298 static const unsigned char P[] = {
299 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
300 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
301 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
302 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
305 #endif /* MD5_SIZE_OVER_SPEED > 0 */
307 __md5_Decode(x, block, 64);
309 a = state[0]; b = state[1]; c = state[2]; d = state[3];
311 #if MD5_SIZE_OVER_SPEED > 2
312 pc = C; pp = P; ps = S - 4;
314 for (i = 0; i < 64; i++) {
315 if ((i & 0x0f) == 0) ps += 4;
331 temp += x[*pp++] + *pc++;
332 temp = ROTATE_LEFT(temp, ps[i & 3]);
334 a = d; d = c; c = b; b = temp;
336 #elif MD5_SIZE_OVER_SPEED > 1
337 pc = C; pp = P; ps = S;
340 for (i = 0; i < 16; i++) {
341 FF(a, b, c, d, x[*pp], ps[i & 0x3], *pc); pp++; pc++;
342 temp = d; d = c; c = b; b = a; a = temp;
347 for (; i < 32; i++) {
348 GG(a, b, c, d, x[*pp], ps[i & 0x3], *pc); pp++; pc++;
349 temp = d; d = c; c = b; b = a; a = temp;
353 for (; i < 48; i++) {
354 HH(a, b, c, d, x[*pp], ps[i & 0x3], *pc); pp++; pc++;
355 temp = d; d = c; c = b; b = a; a = temp;
360 for (; i < 64; i++) {
361 II(a, b, c, d, x[*pp], ps[i & 0x3], *pc); pp++; pc++;
362 temp = d; d = c; c = b; b = a; a = temp;
364 #elif MD5_SIZE_OVER_SPEED > 0
368 for (i = 0; i < 4; i++) {
369 FF(a, b, c, d, x[*pp], 7, *pc); pp++; pc++;
370 FF(d, a, b, c, x[*pp], 12, *pc); pp++; pc++;
371 FF(c, d, a, b, x[*pp], 17, *pc); pp++; pc++;
372 FF(b, c, d, a, x[*pp], 22, *pc); pp++; pc++;
376 for (i = 0; i < 4; i++) {
377 GG(a, b, c, d, x[*pp], 5, *pc); pp++; pc++;
378 GG(d, a, b, c, x[*pp], 9, *pc); pp++; pc++;
379 GG(c, d, a, b, x[*pp], 14, *pc); pp++; pc++;
380 GG(b, c, d, a, x[*pp], 20, *pc); pp++; pc++;
383 for (i = 0; i < 4; i++) {
384 HH(a, b, c, d, x[*pp], 4, *pc); pp++; pc++;
385 HH(d, a, b, c, x[*pp], 11, *pc); pp++; pc++;
386 HH(c, d, a, b, x[*pp], 16, *pc); pp++; pc++;
387 HH(b, c, d, a, x[*pp], 23, *pc); pp++; pc++;
391 for (i = 0; i < 4; i++) {
392 II(a, b, c, d, x[*pp], 6, *pc); pp++; pc++;
393 II(d, a, b, c, x[*pp], 10, *pc); pp++; pc++;
394 II(c, d, a, b, x[*pp], 15, *pc); pp++; pc++;
395 II(b, c, d, a, x[*pp], 21, *pc); pp++; pc++;
403 FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
404 FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
405 FF(c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
406 FF(b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
407 FF(a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
408 FF(d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
409 FF(c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
410 FF(b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
411 FF(a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
412 FF(d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
413 FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
414 FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
415 FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
416 FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
417 FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
418 FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
425 GG(a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
426 GG(d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
427 GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
428 GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
429 GG(a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
430 GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */
431 GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
432 GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
433 GG(a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
434 GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
435 GG(c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
436 GG(b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
437 GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
438 GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
439 GG(c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
440 GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
447 HH(a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
448 HH(d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
449 HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
450 HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
451 HH(a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
452 HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
453 HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
454 HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
455 HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
456 HH(d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
457 HH(c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
458 HH(b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
459 HH(a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
460 HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
461 HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
462 HH(b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
469 II(a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
470 II(d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
471 II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
472 II(b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
473 II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
474 II(d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
475 II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
476 II(b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
477 II(a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
478 II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
479 II(c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
480 II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
481 II(a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
482 II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
483 II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
484 II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
492 /* Zeroize sensitive information. */
493 memset(x, 0, sizeof(x));
498 __md5_to64(char *s, unsigned v, int n)
501 *s++ = ascii64[v & 0x3f];
510 * Use MD5 for what it is best at...
512 #define MD5_OUT_BUFSIZE 36
515 md5_crypt(char passwd[MD5_OUT_BUFSIZE], const unsigned char *pw, const unsigned char *salt)
517 const unsigned char *sp, *ep;
519 unsigned char final[17]; /* final[16] exists only to aid in looping */
520 int sl, pl, i, pw_len;
521 struct MD5Context ctx, ctx1;
523 /* Refine the Salt first */
526 // always true for bbox
527 // /* If it starts with the magic string, then skip that */
528 // if (!strncmp(sp, __md5__magic, MD5_MAGIC_LEN))
531 /* It stops at the first '$', max 8 chars */
532 for (ep = sp; *ep && *ep != '$' && ep < (sp+8); ep++)
535 /* get the length of the true salt */
540 /* The password first, since that is what is most unknown */
541 pw_len = strlen((char*)pw);
542 __md5_Update(&ctx, pw, pw_len);
544 /* Then our magic string */
545 __md5_Update(&ctx, __md5__magic, MD5_MAGIC_LEN);
547 /* Then the raw salt */
548 __md5_Update(&ctx, sp, sl);
550 /* Then just as many characters of the MD5(pw, salt, pw) */
552 __md5_Update(&ctx1, pw, pw_len);
553 __md5_Update(&ctx1, sp, sl);
554 __md5_Update(&ctx1, pw, pw_len);
555 __md5_Final(final, &ctx1);
556 for (pl = pw_len; pl > 0; pl -= 16)
557 __md5_Update(&ctx, final, pl > 16 ? 16 : pl);
559 /* Don't leave anything around in vm they could use. */
560 //TODO: the above comment seems to be wrong. final is used later.
561 memset(final, 0, sizeof(final));
563 /* Then something really weird... */
564 for (i = pw_len; i; i >>= 1) {
565 __md5_Update(&ctx, ((i & 1) ? final : (const unsigned char *) pw), 1);
568 /* Now make the output string */
572 strncpy(passwd + 3, (char*)sp, sl);
573 passwd[sl + 3] = '$';
575 __md5_Final(final, &ctx);
578 * and now, just to make sure things don't run too fast
579 * On a 60 Mhz Pentium this takes 34 msec, so you would
580 * need 30 seconds to build a 1000 entry dictionary...
582 for (i = 0; i < 1000; i++) {
585 __md5_Update(&ctx1, pw, pw_len);
587 __md5_Update(&ctx1, final, 16);
590 __md5_Update(&ctx1, sp, sl);
593 __md5_Update(&ctx1, pw, pw_len);
596 __md5_Update(&ctx1, final, 16);
598 __md5_Update(&ctx1, pw, pw_len);
599 __md5_Final(final, &ctx1);
602 p = passwd + sl + 4; /* 12 bytes max (sl is up to 8 bytes) */
604 /* Add 5*4+2 = 22 bytes of hash, + NUL byte. */
605 final[16] = final[5];
606 for (i = 0; i < 5; i++) {
607 unsigned l = (final[i] << 16) | (final[i+6] << 8) | final[i+12];
608 p = __md5_to64(p, l, 4);
610 p = __md5_to64(p, final[11], 2);
613 /* Don't leave anything around in vm they could use. */
614 memset(final, 0, sizeof(final));
619 #undef MD5_SIZE_OVER_SPEED