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>
85 u_int32_t state[4]; /* state (ABCD) */
86 u_int32_t count[2]; /* number of bits, modulo 2^64 (lsb first) */
87 unsigned char buffer[64]; /* input buffer */
90 static void __md5_Init (struct MD5Context *);
91 static void __md5_Update (struct MD5Context *, const unsigned char *, unsigned int);
92 static void __md5_Pad (struct MD5Context *);
93 static void __md5_Final (unsigned char [16], struct MD5Context *);
94 static void __md5_Transform __P((u_int32_t [4], const unsigned char [64]));
97 static const unsigned char __md5__magic[] = "$1$"; /* This string is magic for this algorithm. Having
98 it this way, we can get better later on */
99 static const unsigned char __md5_itoa64[] = /* 0 ... 63 => ascii - 64 */
100 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
103 /* shut up gcc-4.x signed warnings */
104 #define strcpy(dst,src) strcpy((char*)dst,(char*)src)
105 #define strlen(s) strlen((char*)s)
106 #define strncat(dst,src,n) strncat((char*)dst,(char*)src,n)
107 #define strncmp(s1,s2,n) strncmp((char*)s1,(char*)s2,n)
112 #define __md5_Encode memcpy
113 #define __md5_Decode memcpy
117 * __md5_Encodes input (u_int32_t) into output (unsigned char). Assumes len is
122 __md5_Encode (unsigned char *output, u_int32_t *input, unsigned int len)
126 for (i = 0, j = 0; j < len; i++, j += 4) {
127 output[j] = (unsigned char)(input[i] & 0xff);
128 output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
129 output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
130 output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
135 * __md5_Decodes input (unsigned char) into output (u_int32_t). Assumes len is
140 __md5_Decode (u_int32_t *output, const unsigned char *input, unsigned int len)
144 for (i = 0, j = 0; j < len; i++, j += 4)
145 output[i] = ((u_int32_t)input[j]) | (((u_int32_t)input[j+1]) << 8) |
146 (((u_int32_t)input[j+2]) << 16) | (((u_int32_t)input[j+3]) << 24);
150 /* F, G, H and I are basic MD5 functions. */
151 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
152 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
153 #define H(x, y, z) ((x) ^ (y) ^ (z))
154 #define I(x, y, z) ((y) ^ ((x) | (~z)))
156 /* ROTATE_LEFT rotates x left n bits. */
157 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
160 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
161 * Rotation is separate from addition to prevent recomputation.
163 #define FF(a, b, c, d, x, s, ac) { \
164 (a) += F ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
165 (a) = ROTATE_LEFT ((a), (s)); \
168 #define GG(a, b, c, d, x, s, ac) { \
169 (a) += G ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
170 (a) = ROTATE_LEFT ((a), (s)); \
173 #define HH(a, b, c, d, x, s, ac) { \
174 (a) += H ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
175 (a) = ROTATE_LEFT ((a), (s)); \
178 #define II(a, b, c, d, x, s, ac) { \
179 (a) += I ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
180 (a) = ROTATE_LEFT ((a), (s)); \
184 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
186 static void __md5_Init (struct MD5Context *context)
188 context->count[0] = context->count[1] = 0;
190 /* Load magic initialization constants. */
191 context->state[0] = 0x67452301;
192 context->state[1] = 0xefcdab89;
193 context->state[2] = 0x98badcfe;
194 context->state[3] = 0x10325476;
198 * MD5 block update operation. Continues an MD5 message-digest
199 * operation, processing another message block, and updating the
203 static void __md5_Update ( struct MD5Context *context, const unsigned char *input, unsigned int inputLen)
205 unsigned int i, idx, partLen;
207 /* Compute number of bytes mod 64 */
208 idx = (unsigned int)((context->count[0] >> 3) & 0x3F);
210 /* Update number of bits */
211 if ((context->count[0] += ((u_int32_t)inputLen << 3))
212 < ((u_int32_t)inputLen << 3))
214 context->count[1] += ((u_int32_t)inputLen >> 29);
218 /* Transform as many times as possible. */
219 if (inputLen >= partLen) {
220 memcpy((void *)&context->buffer[idx], (const void *)input,
222 __md5_Transform (context->state, context->buffer);
224 for (i = partLen; i + 63 < inputLen; i += 64)
225 __md5_Transform (context->state, &input[i]);
232 /* Buffer remaining input */
233 memcpy ((void *)&context->buffer[idx], (const void *)&input[i],
238 * MD5 padding. Adds padding followed by original length.
241 static void __md5_Pad ( struct MD5Context *context)
243 unsigned char bits[8];
244 unsigned int idx, padLen;
245 unsigned char PADDING[64];
247 memset(PADDING, 0, sizeof(PADDING));
250 /* Save number of bits */
251 __md5_Encode (bits, context->count, 8);
253 /* Pad out to 56 mod 64. */
254 idx = (unsigned int)((context->count[0] >> 3) & 0x3f);
255 padLen = (idx < 56) ? (56 - idx) : (120 - idx);
256 __md5_Update (context, PADDING, padLen);
258 /* Append length (before padding) */
259 __md5_Update (context, bits, 8);
263 * MD5 finalization. Ends an MD5 message-digest operation, writing the
264 * the message digest and zeroizing the context.
267 static void __md5_Final ( unsigned char digest[16], struct MD5Context *context)
272 /* Store state in digest */
273 __md5_Encode (digest, context->state, 16);
275 /* Zeroize sensitive information. */
276 memset ((void *)context, 0, sizeof (*context));
279 /* MD5 basic transformation. Transforms state based on block. */
282 __md5_Transform (state, block)
284 const unsigned char block[64];
286 u_int32_t a, b, c, d, x[16];
288 #if MD5_SIZE_OVER_SPEED > 1
292 static const char S[] = {
298 #endif /* MD5_SIZE_OVER_SPEED > 1 */
300 #if MD5_SIZE_OVER_SPEED > 0
305 static const u_int32_t C[] = {
307 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
308 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
309 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
310 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
312 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
313 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
314 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
315 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
317 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
318 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
319 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
320 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
322 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
323 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
324 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
325 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
328 static const char P[] = {
329 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
330 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
331 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
332 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
335 #endif /* MD5_SIZE_OVER_SPEED > 0 */
337 __md5_Decode (x, block, 64);
339 a = state[0]; b = state[1]; c = state[2]; d = state[3];
341 #if MD5_SIZE_OVER_SPEED > 2
342 pc = C; pp = P; ps = S - 4;
344 for ( i = 0 ; i < 64 ; i++ ) {
345 if ((i&0x0f) == 0) ps += 4;
361 temp += x[(int)(*pp++)] + *pc++;
362 temp = ROTATE_LEFT(temp, ps[i&3]);
364 a = d; d = c; c = b; b = temp;
366 #elif MD5_SIZE_OVER_SPEED > 1
367 pc = C; pp = P; ps = S;
370 for ( i = 0 ; i < 16 ; i++ ) {
371 FF (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
372 temp = d; d = c; c = b; b = a; a = temp;
377 for ( ; i < 32 ; i++ ) {
378 GG (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
379 temp = d; d = c; c = b; b = a; a = temp;
383 for ( ; i < 48 ; i++ ) {
384 HH (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
385 temp = d; d = c; c = b; b = a; a = temp;
390 for ( ; i < 64 ; i++ ) {
391 II (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
392 temp = d; d = c; c = b; b = a; a = temp;
394 #elif MD5_SIZE_OVER_SPEED > 0
398 for ( i = 0 ; i < 4 ; i++ ) {
399 FF (a, b, c, d, x[(int)(*pp++)], 7, *pc++);
400 FF (d, a, b, c, x[(int)(*pp++)], 12, *pc++);
401 FF (c, d, a, b, x[(int)(*pp++)], 17, *pc++);
402 FF (b, c, d, a, x[(int)(*pp++)], 22, *pc++);
406 for ( i = 0 ; i < 4 ; i++ ) {
407 GG (a, b, c, d, x[(int)(*pp++)], 5, *pc++);
408 GG (d, a, b, c, x[(int)(*pp++)], 9, *pc++);
409 GG (c, d, a, b, x[(int)(*pp++)], 14, *pc++);
410 GG (b, c, d, a, x[(int)(*pp++)], 20, *pc++);
413 for ( i = 0 ; i < 4 ; i++ ) {
414 HH (a, b, c, d, x[(int)(*pp++)], 4, *pc++);
415 HH (d, a, b, c, x[(int)(*pp++)], 11, *pc++);
416 HH (c, d, a, b, x[(int)(*pp++)], 16, *pc++);
417 HH (b, c, d, a, x[(int)(*pp++)], 23, *pc++);
421 for ( i = 0 ; i < 4 ; i++ ) {
422 II (a, b, c, d, x[(int)(*pp++)], 6, *pc++);
423 II (d, a, b, c, x[(int)(*pp++)], 10, *pc++);
424 II (c, d, a, b, x[(int)(*pp++)], 15, *pc++);
425 II (b, c, d, a, x[(int)(*pp++)], 21, *pc++);
433 FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
434 FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
435 FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
436 FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
437 FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
438 FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
439 FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
440 FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
441 FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
442 FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
443 FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
444 FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
445 FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
446 FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
447 FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
448 FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
455 GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
456 GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
457 GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
458 GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
459 GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
460 GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
461 GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
462 GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
463 GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
464 GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
465 GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
466 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
467 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
468 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
469 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
470 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
477 HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
478 HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
479 HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
480 HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
481 HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
482 HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
483 HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
484 HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
485 HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
486 HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
487 HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
488 HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
489 HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
490 HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
491 HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
492 HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
499 II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
500 II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
501 II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
502 II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
503 II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
504 II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
505 II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
506 II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
507 II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
508 II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
509 II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
510 II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
511 II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
512 II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
513 II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
514 II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
522 /* Zeroize sensitive information. */
523 memset ((void *)x, 0, sizeof (x));
527 static void __md5_to64( char *s, unsigned long v, int n)
530 *s++ = __md5_itoa64[v&0x3f];
538 * Use MD5 for what it is best at...
541 char * __md5_crypt( const unsigned char *pw, const unsigned char *salt) attribute_hidden;
542 char * __md5_crypt( const unsigned char *pw, const unsigned char *salt)
545 static const unsigned char *sp, *ep;
546 static char passwd[120], *p;
548 unsigned char final[17]; /* final[16] exists only to aid in looping */
549 int sl,pl,i,__md5__magic_len,pw_len;
550 struct MD5Context ctx,ctx1;
553 /* Refine the Salt first */
556 /* If it starts with the magic string, then skip that */
557 __md5__magic_len = strlen(__md5__magic);
558 if(!strncmp(sp,__md5__magic,__md5__magic_len))
559 sp += __md5__magic_len;
561 /* It stops at the first '$', max 8 chars */
562 for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
565 /* get the length of the true salt */
570 /* The password first, since that is what is most unknown */
572 __md5_Update(&ctx,pw,pw_len);
574 /* Then our magic string */
575 __md5_Update(&ctx,__md5__magic,__md5__magic_len);
577 /* Then the raw salt */
578 __md5_Update(&ctx,sp,sl);
580 /* Then just as many characters of the MD5(pw,salt,pw) */
582 __md5_Update(&ctx1,pw,pw_len);
583 __md5_Update(&ctx1,sp,sl);
584 __md5_Update(&ctx1,pw,pw_len);
585 __md5_Final(final,&ctx1);
586 for(pl = pw_len; pl > 0; pl -= 16)
587 __md5_Update(&ctx,final,pl>16 ? 16 : pl);
589 /* Don't leave anything around in vm they could use. */
590 memset(final,0,sizeof final);
592 /* Then something really weird... */
593 for (i = pw_len; i ; i >>= 1) {
594 __md5_Update(&ctx, ((i&1) ? final : (const unsigned char *) pw), 1);
597 /* Now make the output string */
598 strcpy(passwd,__md5__magic);
599 strncat(passwd,sp,sl);
602 __md5_Final(final,&ctx);
605 * and now, just to make sure things don't run too fast
606 * On a 60 Mhz Pentium this takes 34 msec, so you would
607 * need 30 seconds to build a 1000 entry dictionary...
609 for(i=0;i<1000;i++) {
612 __md5_Update(&ctx1,pw,pw_len);
614 __md5_Update(&ctx1,final,16);
617 __md5_Update(&ctx1,sp,sl);
620 __md5_Update(&ctx1,pw,pw_len);
623 __md5_Update(&ctx1,final,16);
625 __md5_Update(&ctx1,pw,pw_len);
626 __md5_Final(final,&ctx1);
629 p = passwd + strlen(passwd);
631 final[16] = final[5];
632 for ( i=0 ; i < 5 ; i++ ) {
633 l = (final[i]<<16) | (final[i+6]<<8) | final[i+12];
634 __md5_to64(p,l,4); p += 4;
637 __md5_to64(p,l,2); p += 2;
640 /* Don't leave anything around in vm they could use. */
641 memset(final,0,sizeof final);