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>
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 static void __md5_Init (struct MD5Context *);
86 static void __md5_Update (struct MD5Context *, const unsigned char *, unsigned int);
87 static void __md5_Pad (struct MD5Context *);
88 static void __md5_Final (unsigned char [16], struct MD5Context *);
89 static char * __md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data);
90 static void __md5_Transform __P((u_int32_t [4], const unsigned char [64]));
93 static const char __md5__magic[] = "$1$"; /* This string is magic for this algorithm. Having
94 it this way, we can get better later on */
95 static const unsigned char __md5_itoa64[] = /* 0 ... 63 => ascii - 64 */
96 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
101 #define __md5_Encode memcpy
102 #define __md5_Decode memcpy
106 * __md5_Encodes input (u_int32_t) into output (unsigned char). Assumes len is
111 __md5_Encode (output, input, len)
112 unsigned char *output;
118 for (i = 0, j = 0; j < len; i++, j += 4) {
119 output[j] = (unsigned char)(input[i] & 0xff);
120 output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
121 output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
122 output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
127 * __md5_Decodes input (unsigned char) into output (u_int32_t). Assumes len is
132 __md5_Decode (output, input, len)
134 const unsigned char *input;
139 for (i = 0, j = 0; j < len; i++, j += 4)
140 output[i] = ((u_int32_t)input[j]) | (((u_int32_t)input[j+1]) << 8) |
141 (((u_int32_t)input[j+2]) << 16) | (((u_int32_t)input[j+3]) << 24);
145 /* F, G, H and I are basic MD5 functions. */
146 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
147 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
148 #define H(x, y, z) ((x) ^ (y) ^ (z))
149 #define I(x, y, z) ((y) ^ ((x) | (~z)))
151 /* ROTATE_LEFT rotates x left n bits. */
152 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
155 * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
156 * Rotation is separate from addition to prevent recomputation.
158 #define FF(a, b, c, d, x, s, ac) { \
159 (a) += F ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
160 (a) = ROTATE_LEFT ((a), (s)); \
163 #define GG(a, b, c, d, x, s, ac) { \
164 (a) += G ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
165 (a) = ROTATE_LEFT ((a), (s)); \
168 #define HH(a, b, c, d, x, s, ac) { \
169 (a) += H ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
170 (a) = ROTATE_LEFT ((a), (s)); \
173 #define II(a, b, c, d, x, s, ac) { \
174 (a) += I ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
175 (a) = ROTATE_LEFT ((a), (s)); \
179 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
181 static void __md5_Init (struct MD5Context *context)
183 context->count[0] = context->count[1] = 0;
185 /* Load magic initialization constants. */
186 context->state[0] = 0x67452301;
187 context->state[1] = 0xefcdab89;
188 context->state[2] = 0x98badcfe;
189 context->state[3] = 0x10325476;
193 * MD5 block update operation. Continues an MD5 message-digest
194 * operation, processing another message block, and updating the
198 static void __md5_Update ( struct MD5Context *context, const unsigned char *input, unsigned int inputLen)
200 unsigned int i, index, partLen;
202 /* Compute number of bytes mod 64 */
203 index = (unsigned int)((context->count[0] >> 3) & 0x3F);
205 /* Update number of bits */
206 if ((context->count[0] += ((u_int32_t)inputLen << 3))
207 < ((u_int32_t)inputLen << 3))
209 context->count[1] += ((u_int32_t)inputLen >> 29);
211 partLen = 64 - index;
213 /* Transform as many times as possible. */
214 if (inputLen >= partLen) {
215 memcpy((void *)&context->buffer[index], (const void *)input,
217 __md5_Transform (context->state, context->buffer);
219 for (i = partLen; i + 63 < inputLen; i += 64)
220 __md5_Transform (context->state, &input[i]);
227 /* Buffer remaining input */
228 memcpy ((void *)&context->buffer[index], (const void *)&input[i],
233 * MD5 padding. Adds padding followed by original length.
236 static void __md5_Pad ( struct MD5Context *context)
238 unsigned char bits[8];
239 unsigned int index, padLen;
240 unsigned char PADDING[64];
242 memset(PADDING, 0, sizeof(PADDING));
245 /* Save number of bits */
246 __md5_Encode (bits, context->count, 8);
248 /* Pad out to 56 mod 64. */
249 index = (unsigned int)((context->count[0] >> 3) & 0x3f);
250 padLen = (index < 56) ? (56 - index) : (120 - index);
251 __md5_Update (context, PADDING, padLen);
253 /* Append length (before padding) */
254 __md5_Update (context, bits, 8);
258 * MD5 finalization. Ends an MD5 message-digest operation, writing the
259 * the message digest and zeroizing the context.
262 static void __md5_Final ( unsigned char digest[16], struct MD5Context *context)
267 /* Store state in digest */
268 __md5_Encode (digest, context->state, 16);
270 /* Zeroize sensitive information. */
271 memset ((void *)context, 0, sizeof (*context));
274 /* MD5 basic transformation. Transforms state based on block. */
277 __md5_Transform (state, block)
279 const unsigned char block[64];
281 u_int32_t a, b, c, d, x[16];
283 #if MD5_SIZE_OVER_SPEED > 1
287 static const char S[] = {
293 #endif /* MD5_SIZE_OVER_SPEED > 1 */
295 #if MD5_SIZE_OVER_SPEED > 0
300 static const u_int32_t C[] = {
302 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
303 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
304 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
305 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
307 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
308 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
309 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
310 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
312 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
313 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
314 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
315 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
317 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
318 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
319 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
320 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
323 static const char P[] = {
324 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, /* 1 */
325 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, /* 2 */
326 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, /* 3 */
327 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 /* 4 */
330 #endif /* MD5_SIZE_OVER_SPEED > 0 */
332 __md5_Decode (x, block, 64);
334 a = state[0]; b = state[1]; c = state[2]; d = state[3];
336 #if MD5_SIZE_OVER_SPEED > 2
337 pc = C; pp = P; ps = S - 4;
339 for ( i = 0 ; i < 64 ; i++ ) {
340 if ((i&0x0f) == 0) ps += 4;
356 temp += x[(int)(*pp++)] + *pc++;
357 temp = ROTATE_LEFT(temp, ps[i&3]);
359 a = d; d = c; c = b; b = temp;
361 #elif MD5_SIZE_OVER_SPEED > 1
362 pc = C; pp = P; ps = S;
365 for ( i = 0 ; i < 16 ; i++ ) {
366 FF (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
367 temp = d; d = c; c = b; b = a; a = temp;
372 for ( ; i < 32 ; i++ ) {
373 GG (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
374 temp = d; d = c; c = b; b = a; a = temp;
378 for ( ; i < 48 ; i++ ) {
379 HH (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
380 temp = d; d = c; c = b; b = a; a = temp;
385 for ( ; i < 64 ; i++ ) {
386 II (a, b, c, d, x[(int)(*pp++)], ps[i&0x3], *pc++);
387 temp = d; d = c; c = b; b = a; a = temp;
389 #elif MD5_SIZE_OVER_SPEED > 0
393 for ( i = 0 ; i < 4 ; i++ ) {
394 FF (a, b, c, d, x[(int)(*pp++)], 7, *pc++);
395 FF (d, a, b, c, x[(int)(*pp++)], 12, *pc++);
396 FF (c, d, a, b, x[(int)(*pp++)], 17, *pc++);
397 FF (b, c, d, a, x[(int)(*pp++)], 22, *pc++);
401 for ( i = 0 ; i < 4 ; i++ ) {
402 GG (a, b, c, d, x[(int)(*pp++)], 5, *pc++);
403 GG (d, a, b, c, x[(int)(*pp++)], 9, *pc++);
404 GG (c, d, a, b, x[(int)(*pp++)], 14, *pc++);
405 GG (b, c, d, a, x[(int)(*pp++)], 20, *pc++);
408 for ( i = 0 ; i < 4 ; i++ ) {
409 HH (a, b, c, d, x[(int)(*pp++)], 4, *pc++);
410 HH (d, a, b, c, x[(int)(*pp++)], 11, *pc++);
411 HH (c, d, a, b, x[(int)(*pp++)], 16, *pc++);
412 HH (b, c, d, a, x[(int)(*pp++)], 23, *pc++);
416 for ( i = 0 ; i < 4 ; i++ ) {
417 II (a, b, c, d, x[(int)(*pp++)], 6, *pc++);
418 II (d, a, b, c, x[(int)(*pp++)], 10, *pc++);
419 II (c, d, a, b, x[(int)(*pp++)], 15, *pc++);
420 II (b, c, d, a, x[(int)(*pp++)], 21, *pc++);
428 FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
429 FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
430 FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
431 FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
432 FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
433 FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
434 FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
435 FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
436 FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
437 FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
438 FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
439 FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
440 FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
441 FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
442 FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
443 FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
450 GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
451 GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
452 GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
453 GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
454 GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
455 GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
456 GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
457 GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
458 GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
459 GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
460 GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
461 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
462 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
463 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
464 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
465 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
472 HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
473 HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
474 HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
475 HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
476 HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
477 HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
478 HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
479 HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
480 HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
481 HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
482 HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
483 HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
484 HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
485 HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
486 HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
487 HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
494 II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
495 II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
496 II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
497 II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
498 II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
499 II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
500 II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
501 II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
502 II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
503 II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
504 II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
505 II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
506 II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
507 II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
508 II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
509 II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
517 /* Zeroize sensitive information. */
518 memset ((void *)x, 0, sizeof (x));
522 static void __md5_to64( char *s, unsigned long v, int n)
525 *s++ = __md5_itoa64[v&0x3f];
533 * Use MD5 for what it is best at...
536 static char * __md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data)
539 const char *sp = data->sp;
540 const char *ep = data->ep;
541 char *passwd = data->key.b_data; /* This is a nice place where we can grab
542 a bit of reentrant space... I'd create
543 a separate field in struct crypt_data,
544 but this spot should do nicely... */
545 unsigned char final[17]; /* final[16] exists only to aid in looping */
546 int sl,pl,i,__md5__magic_len,pw_len;
547 struct MD5Context ctx,ctx1;
550 /* Refine the Salt first */
553 /* If it starts with the magic string, then skip that */
554 __md5__magic_len = strlen(__md5__magic);
555 if(!strncmp(sp,__md5__magic,__md5__magic_len))
556 sp += __md5__magic_len;
558 /* It stops at the first '$', max 8 chars */
559 for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
562 /* get the length of the true salt */
567 /* The password first, since that is what is most unknown */
569 __md5_Update(&ctx,pw,pw_len);
571 /* Then our magic string */
572 __md5_Update(&ctx,__md5__magic,__md5__magic_len);
574 /* Then the raw salt */
575 __md5_Update(&ctx,sp,sl);
577 /* Then just as many characters of the MD5(pw,salt,pw) */
579 __md5_Update(&ctx1,pw,pw_len);
580 __md5_Update(&ctx1,sp,sl);
581 __md5_Update(&ctx1,pw,pw_len);
582 __md5_Final(final,&ctx1);
583 for(pl = pw_len; pl > 0; pl -= 16)
584 __md5_Update(&ctx,final,pl>16 ? 16 : pl);
586 /* Don't leave anything around in vm they could use. */
587 memset(final,0,sizeof final);
589 /* Then something really weird... */
590 for (i = pw_len; i ; i >>= 1) {
591 __md5_Update(&ctx, ((i&1) ? final : (const unsigned char *) pw), 1);
594 /* Now make the output string */
595 strcpy(passwd,__md5__magic);
596 strncat(passwd,sp,sl);
599 __md5_Final(final,&ctx);
602 * and now, just to make sure things don't run too fast
603 * On a 60 Mhz Pentium this takes 34 msec, so you would
604 * need 30 seconds to build a 1000 entry dictionary...
606 for(i=0;i<1000;i++) {
609 __md5_Update(&ctx1,pw,pw_len);
611 __md5_Update(&ctx1,final,16);
614 __md5_Update(&ctx1,sp,sl);
617 __md5_Update(&ctx1,pw,pw_len);
620 __md5_Update(&ctx1,final,16);
622 __md5_Update(&ctx1,pw,pw_len);
623 __md5_Final(final,&ctx1);
626 p = passwd + strlen(passwd);
628 final[16] = final[5];
629 for ( i=0 ; i < 5 ; i++ ) {
630 l = (final[i]<<16) | (final[i+6]<<8) | final[i+12];
631 __md5_to64(p,l,4); p += 4;
634 __md5_to64(p,l,2); p += 2;
637 /* Don't leave anything around in vm they could use. */
638 memset(final,0,sizeof final);