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>
44 * June 28, 2001 Manuel Novoa III
46 * "Un-inlined" code using loops and static const tables in order to
47 * reduce generated code size (on i386 from approx 4k to approx 2.5k).
49 * June 29, 2001 Manuel Novoa III
51 * Completely removed static PADDING array.
53 * Reintroduced the loop unrolling in MD5_Transform and added the
54 * MD5_SIZE_OVER_SPEED option for configurability. Define below as:
55 * 0 fully unrolled loops
56 * 1 partially unrolled (4 ops per loop)
57 * 2 no unrolling -- introduces the need to swap 4 variables (slow)
58 * 3 no unrolling and all 4 loops merged into one with switch
59 * in each loop (glacial)
60 * On i386, sizes are roughly (-Os -fno-builtin):
61 * 0: 3k 1: 2.5k 2: 2.2k 3: 2k
65 * Valid values are 1 (fastest/largest) to 3 (smallest/slowest).
67 #define MD5_SIZE_OVER_SPEED 3
69 /**********************************************************************/
71 #include <sys/types.h>
76 #include <sys/cdefs.h>
79 typedef struct MD5Context {
80 u_int32_t state[4]; /* state (ABCD) */
81 u_int32_t count[2]; /* number of bits, modulo 2^64 (lsb first) */
82 unsigned char buffer[64]; /* input buffer */
85 void MD5Init (MD5_CTX *);
86 void MD5Update (MD5_CTX *, const unsigned char *, unsigned int);
87 void MD5Pad (MD5_CTX *);
88 void MD5Final (unsigned char [16], MD5_CTX *);
89 char * MD5End(MD5_CTX *, char *);
90 char * MD5File(const char *, char *);
91 char * MD5Data(const unsigned char *, unsigned int, char *);
92 char * md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data);
95 char *md5_magic = "$1$"; /* * This string is magic for this algorithm. Having
96 it this way, we can get better later on */
97 static const unsigned char itoa64[] = /* 0 ... 63 => ascii - 64 */
98 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
101 static void MD5Transform __P((u_int32_t [4], const unsigned char [64]));
104 #define memset(x,y,z) bzero(x,z);
105 #define memcpy(x,y,z) bcopy(y, x, z)
109 #define Encode memcpy
110 #define Decode memcpy
114 * Encodes input (u_int32_t) into output (unsigned char). Assumes len is
119 Encode (output, input, len)
120 unsigned char *output;
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 * Decodes input (unsigned char) into output (u_int32_t). Assumes len is
140 Decode (output, input, len)
142 const unsigned char *input;
147 for (i = 0, j = 0; j < len; i++, j += 4)
148 output[i] = ((u_int32_t)input[j]) | (((u_int32_t)input[j+1]) << 8) |
149 (((u_int32_t)input[j+2]) << 16) | (((u_int32_t)input[j+3]) << 24);
153 /* F, G, H and I are basic MD5 functions. */
154 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
155 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
156 #define H(x, y, z) ((x) ^ (y) ^ (z))
157 #define I(x, y, z) ((y) ^ ((x) | (~z)))
159 /* ROTATE_LEFT rotates x left n bits. */
160 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
163 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
164 * Rotation is separate from addition to prevent recomputation.
166 #define FF(a, b, c, d, x, s, ac) { \
167 (a) += F ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
168 (a) = ROTATE_LEFT ((a), (s)); \
171 #define GG(a, b, c, d, x, s, ac) { \
172 (a) += G ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
173 (a) = ROTATE_LEFT ((a), (s)); \
176 #define HH(a, b, c, d, x, s, ac) { \
177 (a) += H ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
178 (a) = ROTATE_LEFT ((a), (s)); \
181 #define II(a, b, c, d, x, s, ac) { \
182 (a) += I ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
183 (a) = ROTATE_LEFT ((a), (s)); \
187 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
189 void MD5Init (MD5_CTX *context)
191 context->count[0] = context->count[1] = 0;
193 /* Load magic initialization constants. */
194 context->state[0] = 0x67452301;
195 context->state[1] = 0xefcdab89;
196 context->state[2] = 0x98badcfe;
197 context->state[3] = 0x10325476;
201 * MD5 block update operation. Continues an MD5 message-digest
202 * operation, processing another message block, and updating the
206 void MD5Update ( MD5_CTX *context, const unsigned char *input, unsigned int inputLen)
208 unsigned int i, index, partLen;
210 /* Compute number of bytes mod 64 */
211 index = (unsigned int)((context->count[0] >> 3) & 0x3F);
213 /* Update number of bits */
214 if ((context->count[0] += ((u_int32_t)inputLen << 3))
215 < ((u_int32_t)inputLen << 3))
217 context->count[1] += ((u_int32_t)inputLen >> 29);
219 partLen = 64 - index;
221 /* Transform as many times as possible. */
222 if (inputLen >= partLen) {
223 memcpy((void *)&context->buffer[index], (const void *)input,
225 MD5Transform (context->state, context->buffer);
227 for (i = partLen; i + 63 < inputLen; i += 64)
228 MD5Transform (context->state, &input[i]);
235 /* Buffer remaining input */
236 memcpy ((void *)&context->buffer[index], (const void *)&input[i],
241 * MD5 padding. Adds padding followed by original length.
244 void MD5Pad ( MD5_CTX *context)
246 unsigned char bits[8];
247 unsigned int index, padLen;
248 unsigned char PADDING[64];
250 memset(PADDING, 0, sizeof(PADDING));
253 /* Save number of bits */
254 Encode (bits, context->count, 8);
256 /* Pad out to 56 mod 64. */
257 index = (unsigned int)((context->count[0] >> 3) & 0x3f);
258 padLen = (index < 56) ? (56 - index) : (120 - index);
259 MD5Update (context, PADDING, padLen);
261 /* Append length (before padding) */
262 MD5Update (context, bits, 8);
266 * MD5 finalization. Ends an MD5 message-digest operation, writing the
267 * the message digest and zeroizing the context.
270 void MD5Final ( unsigned char digest[16], MD5_CTX *context)
275 /* Store state in digest */
276 Encode (digest, context->state, 16);
278 /* Zeroize sensitive information. */
279 memset ((void *)context, 0, sizeof (*context));
282 /* MD5 basic transformation. Transforms state based on block. */
285 MD5Transform (state, block)
287 const unsigned char block[64];
289 u_int32_t a, b, c, d, x[16];
291 #if MD5_SIZE_OVER_SPEED > 1
295 static const char S[] = {
301 #endif /* MD5_SIZE_OVER_SPEED > 1 */
303 #if MD5_SIZE_OVER_SPEED > 0
308 static const u_int32_t C[] = {
310 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
311 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
312 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
313 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
315 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
316 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
317 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
318 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
320 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
321 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
322 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
323 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
325 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
326 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
327 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
328 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
331 static const char P[] = {
332 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
333 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
334 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
335 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
338 #endif /* MD5_SIZE_OVER_SPEED > 0 */
340 Decode (x, block, 64);
342 a = state[0]; b = state[1]; c = state[2]; d = state[3];
344 #if MD5_SIZE_OVER_SPEED > 2
345 pc = C; pp = P; ps = S - 4;
347 for ( i = 0 ; i < 64 ; i++ ) {
348 if ((i&0x0f) == 0) ps += 4;
364 temp += x[(int)(*pp++)] + *pc++;
365 temp = ROTATE_LEFT(temp, ps[i&3]);
367 a = d; d = c; c = b; b = temp;
369 #elif MD5_SIZE_OVER_SPEED > 1
370 pc = C; pp = P; ps = S;
373 for ( i = 0 ; i < 16 ; i++ ) {
374 FF (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
375 temp = d; d = c; c = b; b = a; a = temp;
380 for ( ; i < 32 ; i++ ) {
381 GG (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
382 temp = d; d = c; c = b; b = a; a = temp;
386 for ( ; i < 48 ; i++ ) {
387 HH (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
388 temp = d; d = c; c = b; b = a; a = temp;
393 for ( ; i < 64 ; i++ ) {
394 II (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
395 temp = d; d = c; c = b; b = a; a = temp;
397 #elif MD5_SIZE_OVER_SPEED > 0
401 for ( i = 0 ; i < 4 ; i++ ) {
402 FF (a, b, c, d, x[(int)(*pp++)], 7, *pc++);
403 FF (d, a, b, c, x[(int)(*pp++)], 12, *pc++);
404 FF (c, d, a, b, x[(int)(*pp++)], 17, *pc++);
405 FF (b, c, d, a, x[(int)(*pp++)], 22, *pc++);
409 for ( i = 0 ; i < 4 ; i++ ) {
410 GG (a, b, c, d, x[(int)(*pp++)], 5, *pc++);
411 GG (d, a, b, c, x[(int)(*pp++)], 9, *pc++);
412 GG (c, d, a, b, x[(int)(*pp++)], 14, *pc++);
413 GG (b, c, d, a, x[(int)(*pp++)], 20, *pc++);
416 for ( i = 0 ; i < 4 ; i++ ) {
417 HH (a, b, c, d, x[(int)(*pp++)], 4, *pc++);
418 HH (d, a, b, c, x[(int)(*pp++)], 11, *pc++);
419 HH (c, d, a, b, x[(int)(*pp++)], 16, *pc++);
420 HH (b, c, d, a, x[(int)(*pp++)], 23, *pc++);
424 for ( i = 0 ; i < 4 ; i++ ) {
425 II (a, b, c, d, x[(int)(*pp++)], 6, *pc++);
426 II (d, a, b, c, x[(int)(*pp++)], 10, *pc++);
427 II (c, d, a, b, x[(int)(*pp++)], 15, *pc++);
428 II (b, c, d, a, x[(int)(*pp++)], 21, *pc++);
436 FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
437 FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
438 FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
439 FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
440 FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
441 FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
442 FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
443 FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
444 FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
445 FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
446 FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
447 FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
448 FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
449 FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
450 FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
451 FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
458 GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
459 GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
460 GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
461 GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
462 GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
463 GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
464 GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
465 GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
466 GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
467 GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
468 GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
469 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
470 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
471 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
472 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
473 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
480 HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
481 HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
482 HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
483 HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
484 HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
485 HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
486 HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
487 HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
488 HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
489 HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
490 HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
491 HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
492 HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
493 HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
494 HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
495 HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
502 II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
503 II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
504 II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
505 II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
506 II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
507 II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
508 II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
509 II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
510 II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
511 II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
512 II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
513 II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
514 II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
515 II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
516 II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
517 II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
525 /* Zeroize sensitive information. */
526 memset ((void *)x, 0, sizeof (x));
530 static void to64( char *s, unsigned long v, int n)
533 *s++ = itoa64[v&0x3f];
541 * Use MD5 for what it is best at...
544 char * md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data)
547 const char *sp = data->sp;
548 const char *ep = data->ep;
549 char *passwd = data->key.b_data; /* This is a nice place where we can grab
550 a bit of reentrant space... I'd create
551 a separate field in struct crypt_data,
552 but this spot should do nicely... */
553 unsigned char final[17]; /* final[16] exists only to aid in looping */
554 int sl,pl,i,md5_magic_len,pw_len;
558 /* Refine the Salt first */
561 /* If it starts with the magic string, then skip that */
562 md5_magic_len = strlen(md5_magic);
563 if(!strncmp(sp,md5_magic,md5_magic_len))
566 /* It stops at the first '$', max 8 chars */
567 for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
570 /* get the length of the true salt */
575 /* The password first, since that is what is most unknown */
577 MD5Update(&ctx,pw,pw_len);
579 /* Then our magic string */
580 MD5Update(&ctx,md5_magic,md5_magic_len);
582 /* Then the raw salt */
583 MD5Update(&ctx,sp,sl);
585 /* Then just as many characters of the MD5(pw,salt,pw) */
587 MD5Update(&ctx1,pw,pw_len);
588 MD5Update(&ctx1,sp,sl);
589 MD5Update(&ctx1,pw,pw_len);
590 MD5Final(final,&ctx1);
591 for(pl = pw_len; pl > 0; pl -= 16)
592 MD5Update(&ctx,final,pl>16 ? 16 : pl);
594 /* Don't leave anything around in vm they could use. */
595 memset(final,0,sizeof final);
597 /* Then something really weird... */
598 for (i = pw_len; i ; i >>= 1) {
599 MD5Update(&ctx, ((i&1) ? final : (const unsigned char *) pw), 1);
602 /* Now make the output string */
603 strcpy(passwd,md5_magic);
604 strncat(passwd,sp,sl);
607 MD5Final(final,&ctx);
610 * and now, just to make sure things don't run too fast
611 * On a 60 Mhz Pentium this takes 34 msec, so you would
612 * need 30 seconds to build a 1000 entry dictionary...
614 for(i=0;i<1000;i++) {
617 MD5Update(&ctx1,pw,pw_len);
619 MD5Update(&ctx1,final,16);
622 MD5Update(&ctx1,sp,sl);
625 MD5Update(&ctx1,pw,pw_len);
628 MD5Update(&ctx1,final,16);
630 MD5Update(&ctx1,pw,pw_len);
631 MD5Final(final,&ctx1);
634 p = passwd + strlen(passwd);
636 final[16] = final[5];
637 for ( i=0 ; i < 5 ; i++ ) {
638 l = (final[i]<<16) | (final[i+6]<<8) | final[i+12];
645 /* Don't leave anything around in vm they could use. */
646 memset(final,0,sizeof final);