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 /**********************************************************************/
76 #include <sys/types.h>
81 #include <sys/cdefs.h>
86 u_int32_t state[4]; /* state (ABCD) */
87 u_int32_t count[2]; /* number of bits, modulo 2^64 (lsb first) */
88 unsigned char buffer[64]; /* input buffer */
91 static void __md5_Init (struct MD5Context *);
92 static void __md5_Update (struct MD5Context *, const unsigned char *, unsigned int);
93 static void __md5_Pad (struct MD5Context *);
94 static void __md5_Final (unsigned char [16], struct MD5Context *);
95 static void __md5_Transform __P((u_int32_t [4], const unsigned char [64]));
98 static const unsigned char __md5__magic[] = "$1$"; /* This string is magic for this algorithm. Having
99 it this way, we can get better later on */
100 static const unsigned char __md5_itoa64[] = /* 0 ... 63 => ascii - 64 */
101 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
105 #define __md5_Encode memcpy
106 #define __md5_Decode memcpy
110 * __md5_Encodes input (u_int32_t) into output (unsigned char). Assumes len is
115 __md5_Encode (unsigned char *output, u_int32_t *input, unsigned int len)
119 for (i = 0, j = 0; j < len; i++, j += 4) {
120 output[j] = (unsigned char)(input[i] & 0xff);
121 output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
122 output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
123 output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
128 * __md5_Decodes input (unsigned char) into output (u_int32_t). Assumes len is
133 __md5_Decode (u_int32_t *output, const unsigned char *input, unsigned int len)
137 for (i = 0, j = 0; j < len; i++, j += 4)
138 output[i] = ((u_int32_t)input[j]) | (((u_int32_t)input[j+1]) << 8) |
139 (((u_int32_t)input[j+2]) << 16) | (((u_int32_t)input[j+3]) << 24);
143 /* F, G, H and I are basic MD5 functions. */
144 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
145 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
146 #define H(x, y, z) ((x) ^ (y) ^ (z))
147 #define I(x, y, z) ((y) ^ ((x) | (~z)))
149 /* ROTATE_LEFT rotates x left n bits. */
150 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
153 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
154 * Rotation is separate from addition to prevent recomputation.
156 #define FF(a, b, c, d, x, s, ac) { \
157 (a) += F ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
158 (a) = ROTATE_LEFT ((a), (s)); \
161 #define GG(a, b, c, d, x, s, ac) { \
162 (a) += G ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
163 (a) = ROTATE_LEFT ((a), (s)); \
166 #define HH(a, b, c, d, x, s, ac) { \
167 (a) += H ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
168 (a) = ROTATE_LEFT ((a), (s)); \
171 #define II(a, b, c, d, x, s, ac) { \
172 (a) += I ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
173 (a) = ROTATE_LEFT ((a), (s)); \
177 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
179 static void __md5_Init (struct MD5Context *context)
181 context->count[0] = context->count[1] = 0;
183 /* Load magic initialization constants. */
184 context->state[0] = 0x67452301;
185 context->state[1] = 0xefcdab89;
186 context->state[2] = 0x98badcfe;
187 context->state[3] = 0x10325476;
191 * MD5 block update operation. Continues an MD5 message-digest
192 * operation, processing another message block, and updating the
196 static void __md5_Update ( struct MD5Context *context, const unsigned char *input, unsigned int inputLen)
198 unsigned int i, idx, partLen;
200 /* Compute number of bytes mod 64 */
201 idx = (unsigned int)((context->count[0] >> 3) & 0x3F);
203 /* Update number of bits */
204 if ((context->count[0] += ((u_int32_t)inputLen << 3))
205 < ((u_int32_t)inputLen << 3))
207 context->count[1] += ((u_int32_t)inputLen >> 29);
211 /* Transform as many times as possible. */
212 if (inputLen >= partLen) {
213 memcpy((void *)&context->buffer[idx], (const void *)input,
215 __md5_Transform (context->state, context->buffer);
217 for (i = partLen; i + 63 < inputLen; i += 64)
218 __md5_Transform (context->state, &input[i]);
225 /* Buffer remaining input */
226 memcpy ((void *)&context->buffer[idx], (const void *)&input[i],
231 * MD5 padding. Adds padding followed by original length.
234 static void __md5_Pad ( struct MD5Context *context)
236 unsigned char bits[8];
237 unsigned int idx, padLen;
238 unsigned char PADDING[64];
240 memset(PADDING, 0, sizeof(PADDING));
243 /* Save number of bits */
244 __md5_Encode (bits, context->count, 8);
246 /* Pad out to 56 mod 64. */
247 idx = (unsigned int)((context->count[0] >> 3) & 0x3f);
248 padLen = (idx < 56) ? (56 - idx) : (120 - idx);
249 __md5_Update (context, PADDING, padLen);
251 /* Append length (before padding) */
252 __md5_Update (context, bits, 8);
256 * MD5 finalization. Ends an MD5 message-digest operation, writing the
257 * the message digest and zeroizing the context.
260 static void __md5_Final ( unsigned char digest[16], struct MD5Context *context)
265 /* Store state in digest */
266 __md5_Encode (digest, context->state, 16);
268 /* Zeroize sensitive information. */
269 memset ((void *)context, 0, sizeof (*context));
272 /* MD5 basic transformation. Transforms state based on block. */
274 static void __md5_Transform (u_int32_t state[4], const unsigned char block[64])
276 u_int32_t a, b, c, d, x[16];
277 #if MD5_SIZE_OVER_SPEED > 1
281 static const char S[] = {
287 #endif /* MD5_SIZE_OVER_SPEED > 1 */
289 #if MD5_SIZE_OVER_SPEED > 0
294 static const u_int32_t C[] = {
296 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
297 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
298 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
299 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
301 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
302 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
303 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
304 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
306 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
307 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
308 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
309 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
311 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
312 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
313 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
314 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
317 static const char P[] = {
318 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
319 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
320 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
321 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
324 #endif /* MD5_SIZE_OVER_SPEED > 0 */
326 __md5_Decode (x, block, 64);
328 a = state[0]; b = state[1]; c = state[2]; d = state[3];
330 #if MD5_SIZE_OVER_SPEED > 2
331 pc = C; pp = P; ps = S - 4;
333 for ( i = 0 ; i < 64 ; i++ ) {
334 if ((i&0x0f) == 0) ps += 4;
350 temp += x[(int)(*pp++)] + *pc++;
351 temp = ROTATE_LEFT(temp, ps[i&3]);
353 a = d; d = c; c = b; b = temp;
355 #elif MD5_SIZE_OVER_SPEED > 1
356 pc = C; pp = P; ps = S;
359 for ( i = 0 ; i < 16 ; i++ ) {
360 FF (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
361 temp = d; d = c; c = b; b = a; a = temp;
366 for ( ; i < 32 ; i++ ) {
367 GG (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
368 temp = d; d = c; c = b; b = a; a = temp;
372 for ( ; i < 48 ; i++ ) {
373 HH (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
374 temp = d; d = c; c = b; b = a; a = temp;
379 for ( ; i < 64 ; i++ ) {
380 II (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
381 temp = d; d = c; c = b; b = a; a = temp;
383 #elif MD5_SIZE_OVER_SPEED > 0
387 for ( i = 0 ; i < 4 ; i++ ) {
388 FF (a, b, c, d, x[(int)(*pp++)], 7, *pc++);
389 FF (d, a, b, c, x[(int)(*pp++)], 12, *pc++);
390 FF (c, d, a, b, x[(int)(*pp++)], 17, *pc++);
391 FF (b, c, d, a, x[(int)(*pp++)], 22, *pc++);
395 for ( i = 0 ; i < 4 ; i++ ) {
396 GG (a, b, c, d, x[(int)(*pp++)], 5, *pc++);
397 GG (d, a, b, c, x[(int)(*pp++)], 9, *pc++);
398 GG (c, d, a, b, x[(int)(*pp++)], 14, *pc++);
399 GG (b, c, d, a, x[(int)(*pp++)], 20, *pc++);
402 for ( i = 0 ; i < 4 ; i++ ) {
403 HH (a, b, c, d, x[(int)(*pp++)], 4, *pc++);
404 HH (d, a, b, c, x[(int)(*pp++)], 11, *pc++);
405 HH (c, d, a, b, x[(int)(*pp++)], 16, *pc++);
406 HH (b, c, d, a, x[(int)(*pp++)], 23, *pc++);
410 for ( i = 0 ; i < 4 ; i++ ) {
411 II (a, b, c, d, x[(int)(*pp++)], 6, *pc++);
412 II (d, a, b, c, x[(int)(*pp++)], 10, *pc++);
413 II (c, d, a, b, x[(int)(*pp++)], 15, *pc++);
414 II (b, c, d, a, x[(int)(*pp++)], 21, *pc++);
422 FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
423 FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
424 FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
425 FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
426 FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
427 FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
428 FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
429 FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
430 FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
431 FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
432 FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
433 FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
434 FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
435 FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
436 FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
437 FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
444 GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
445 GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
446 GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
447 GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
448 GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
449 GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
450 GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
451 GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
452 GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
453 GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
454 GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
455 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
456 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
457 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
458 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
459 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
466 HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
467 HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
468 HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
469 HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
470 HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
471 HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
472 HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
473 HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
474 HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
475 HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
476 HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
477 HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
478 HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
479 HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
480 HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
481 HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
488 II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
489 II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
490 II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
491 II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
492 II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
493 II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
494 II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
495 II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
496 II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
497 II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
498 II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
499 II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
500 II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
501 II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
502 II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
503 II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
511 /* Zeroize sensitive information. */
512 memset ((void *)x, 0, sizeof (x));
516 static void __md5_to64( char *s, unsigned long v, int n)
519 *s++ = __md5_itoa64[v&0x3f];
527 * Use MD5 for what it is best at...
530 char *__md5_crypt(const unsigned char *pw, const unsigned char *salt)
533 static const unsigned char *sp, *ep;
534 static char passwd[120], *p;
536 unsigned char final[17]; /* final[16] exists only to aid in looping */
537 int sl,pl,i,__md5__magic_len,pw_len;
538 struct MD5Context ctx,ctx1;
541 /* Refine the Salt first */
544 /* If it starts with the magic string, then skip that */
545 __md5__magic_len = strlen(__md5__magic);
546 if(!strncmp(sp,__md5__magic,__md5__magic_len))
547 sp += __md5__magic_len;
549 /* It stops at the first '$', max 8 chars */
550 for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
553 /* get the length of the true salt */
558 /* The password first, since that is what is most unknown */
560 __md5_Update(&ctx,pw,pw_len);
562 /* Then our magic string */
563 __md5_Update(&ctx,__md5__magic,__md5__magic_len);
565 /* Then the raw salt */
566 __md5_Update(&ctx,sp,sl);
568 /* Then just as many characters of the MD5(pw,salt,pw) */
570 __md5_Update(&ctx1,pw,pw_len);
571 __md5_Update(&ctx1,sp,sl);
572 __md5_Update(&ctx1,pw,pw_len);
573 __md5_Final(final,&ctx1);
574 for(pl = pw_len; pl > 0; pl -= 16)
575 __md5_Update(&ctx,final,pl>16 ? 16 : pl);
577 /* Don't leave anything around in vm they could use. */
578 memset(final,0,sizeof final);
580 /* Then something really weird... */
581 for (i = pw_len; i ; i >>= 1) {
582 __md5_Update(&ctx, ((i&1) ? final : (const unsigned char *) pw), 1);
585 /* Now make the output string */
586 strcpy(passwd,__md5__magic);
587 strncat(passwd,sp,sl);
590 __md5_Final(final,&ctx);
593 * and now, just to make sure things don't run too fast
594 * On a 60 Mhz Pentium this takes 34 msec, so you would
595 * need 30 seconds to build a 1000 entry dictionary...
597 for(i=0;i<1000;i++) {
600 __md5_Update(&ctx1,pw,pw_len);
602 __md5_Update(&ctx1,final,16);
605 __md5_Update(&ctx1,sp,sl);
608 __md5_Update(&ctx1,pw,pw_len);
611 __md5_Update(&ctx1,final,16);
613 __md5_Update(&ctx1,pw,pw_len);
614 __md5_Final(final,&ctx1);
617 p = passwd + strlen(passwd);
619 final[16] = final[5];
620 for ( i=0 ; i < 5 ; i++ ) {
621 l = (final[i]<<16) | (final[i+6]<<8) | final[i+12];
622 __md5_to64(p,l,4); p += 4;
625 __md5_to64(p,l,2); p += 2;
628 /* Don't leave anything around in vm they could use. */
629 memset(final,0,sizeof final);