libcrypt/md5.c

   1 /*
   2  * MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
   3  *
   4  * Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
   5  * rights reserved.
   6  *
   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
  10  * or this function.
  11  *
  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.
  16  *
  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.
  21  *
  22  * These notices must be retained in any copies of any part of this
  23  * documentation and/or software.
  24  *
  25  * $FreeBSD: src/lib/libmd/md5c.c,v 1.9.2.1 1999/08/29 14:57:12 peter Exp $
  26  *
  27  * This code is the same as the code published by RSA Inc.  It has been
  28  * edited for clarity and style only.
  29  *
  30  * ----------------------------------------------------------------------------
  31  * The md5_crypt() function was taken from freeBSD's libcrypt and contains
  32  * this license:
  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
  37  *
  38  * $FreeBSD: src/lib/libcrypt/crypt.c,v 1.7.2.1 1999/08/29 14:56:33 peter Exp $
  39  *
  40  * ----------------------------------------------------------------------------
  41  * On April 19th, 2001 md5_crypt() was modified to make it reentrant
  42  * by Erik Andersen <andersen@lineo.com>, <andersee@debian.org>
  43  *
  44  * June 28, 2001             Manuel Novoa III
  45  *
  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).
  48  *
  49  * WARNING!!! Changed PADDING array from a staticly allocated object to
  50  *            a dynamicly generated one.  Although it was declared static
  51  *            and not static const, it doesn't appear that it ever changes.
  52  */
  53
  54 #include <sys/types.h>
  55 #include <string.h>
  56 #include <unistd.h>
  57 #include <stdio.h>
  58 #include <crypt.h>
  59 #include <sys/cdefs.h>
  60
  61 /* MD5 context. */
  62 typedef struct MD5Context {
  63   u_int32_t state[4];   /* state (ABCD) */
  64   u_int32_t count[2];   /* number of bits, modulo 2^64 (lsb first) */
  65   unsigned char buffer[64];     /* input buffer */
  66 } MD5_CTX;
  67
  68 void   MD5Init (MD5_CTX *);
  69 void   MD5Update (MD5_CTX *, const unsigned char *, unsigned int);
  70 void   MD5Pad (MD5_CTX *);
  71 void   MD5Final (unsigned char [16], MD5_CTX *);
  72 char * MD5End(MD5_CTX *, char *);
  73 char * MD5File(const char *, char *);
  74 char * MD5Data(const unsigned char *, unsigned int, char *);
  75 char * md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data);
  76
  77
  78 char    *md5_magic = "$1$";     /* * This string is magic for this algorithm.  Having
  79                                    it this way, we can get better later on */
  80 static const unsigned char itoa64[] =           /* 0 ... 63 => ascii - 64 */
  81         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  82
  83
  84 static void MD5Transform __P((u_int32_t [4], const unsigned char [64]));
  85
  86 #ifdef KERNEL
  87 #define memset(x,y,z)   bzero(x,z);
  88 #define memcpy(x,y,z)   bcopy(y, x, z)
  89 #endif
  90
  91 #ifdef i386
  92 #define Encode memcpy
  93 #define Decode memcpy
  94 #else /* i386 */
  95
  96 /*
  97  * Encodes input (u_int32_t) into output (unsigned char). Assumes len is
  98  * a multiple of 4.
  99  */
 100
 101 static void
 102 Encode (output, input, len)
 103         unsigned char *output;
 104         u_int32_t *input;
 105         unsigned int len;
 106 {
 107         unsigned int i, j;
 108
 109         for (i = 0, j = 0; j < len; i++, j += 4) {
 110                 output[j] = (unsigned char)(input[i] & 0xff);
 111                 output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
 112                 output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
 113                 output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
 114         }
 115 }
 116
 117 /*
 118  * Decodes input (unsigned char) into output (u_int32_t). Assumes len is
 119  * a multiple of 4.
 120  */
 121
 122 static void
 123 Decode (output, input, len)
 124         u_int32_t *output;
 125         const unsigned char *input;
 126         unsigned int len;
 127 {
 128         unsigned int i, j;
 129
 130         for (i = 0, j = 0; j < len; i++, j += 4)
 131                 output[i] = ((u_int32_t)input[j]) | (((u_int32_t)input[j+1]) << 8) |
 132                     (((u_int32_t)input[j+2]) << 16) | (((u_int32_t)input[j+3]) << 24);
 133 }
 134 #endif /* i386 */
 135
 136 /* F, G, H and I are basic MD5 functions. */
 137 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
 138 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
 139 #define H(x, y, z) ((x) ^ (y) ^ (z))
 140 #define I(x, y, z) ((y) ^ ((x) | (~z)))
 141
 142 /* ROTATE_LEFT rotates x left n bits. */
 143 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
 144
 145 /*
 146  * FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
 147  * Rotation is separate from addition to prevent recomputation.
 148  */
 149 #define FF(a, b, c, d, x, s, ac) { \
 150         (a) += F ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
 151         (a) = ROTATE_LEFT ((a), (s)); \
 152         (a) += (b); \
 153         }
 154 #define GG(a, b, c, d, x, s, ac) { \
 155         (a) += G ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
 156         (a) = ROTATE_LEFT ((a), (s)); \
 157         (a) += (b); \
 158         }
 159 #define HH(a, b, c, d, x, s, ac) { \
 160         (a) += H ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
 161         (a) = ROTATE_LEFT ((a), (s)); \
 162         (a) += (b); \
 163         }
 164 #define II(a, b, c, d, x, s, ac) { \
 165         (a) += I ((b), (c), (d)) + (x) + (u_int32_t)(ac); \
 166         (a) = ROTATE_LEFT ((a), (s)); \
 167         (a) += (b); \
 168         }
 169
 170 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
 171
 172 void MD5Init (MD5_CTX *context)
 173 {
 174         context->count[0] = context->count[1] = 0;
 175
 176         /* Load magic initialization constants.  */
 177         context->state[0] = 0x67452301;
 178         context->state[1] = 0xefcdab89;
 179         context->state[2] = 0x98badcfe;
 180         context->state[3] = 0x10325476;
 181 }
 182
 183 /*
 184  * MD5 block update operation. Continues an MD5 message-digest
 185  * operation, processing another message block, and updating the
 186  * context.
 187  */
 188
 189 void MD5Update ( MD5_CTX *context, const unsigned char *input, unsigned int inputLen)
 190 {
 191         unsigned int i, index, partLen;
 192
 193         /* Compute number of bytes mod 64 */
 194         index = (unsigned int)((context->count[0] >> 3) & 0x3F);
 195
 196         /* Update number of bits */
 197         if ((context->count[0] += ((u_int32_t)inputLen << 3))
 198             < ((u_int32_t)inputLen << 3))
 199                 context->count[1]++;
 200         context->count[1] += ((u_int32_t)inputLen >> 29);
 201
 202         partLen = 64 - index;
 203
 204         /* Transform as many times as possible. */
 205         if (inputLen >= partLen) {
 206                 memcpy((void *)&context->buffer[index], (const void *)input,
 207                     partLen);
 208                 MD5Transform (context->state, context->buffer);
 209
 210                 for (i = partLen; i + 63 < inputLen; i += 64)
 211                         MD5Transform (context->state, &input[i]);
 212
 213                 index = 0;
 214         }
 215         else
 216                 i = 0;
 217
 218         /* Buffer remaining input */
 219         memcpy ((void *)&context->buffer[index], (const void *)&input[i],
 220             inputLen-i);
 221 }
 222
 223 /*
 224  * MD5 padding. Adds padding followed by original length.
 225  */
 226
 227 #define STATIC_PADDING 0
 228 #if STATIC_PADDING
 229 static unsigned char PADDING[64] = {
 230   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 231   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 232   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 233 };
 234 #endif
 235
 236 void MD5Pad ( MD5_CTX *context)
 237 {
 238         unsigned char bits[8];
 239         unsigned int index, padLen;
 240
 241 #if !STATIC_PADDING
 242         unsigned char PADDING[64];
 243
 244         for (index = 0 ; index < sizeof(PADDING) ; index++) {
 245                 PADDING[index] = 0;
 246         }
 247         PADDING[0] = 0x80;
 248 #endif
 249
 250         /* Save number of bits */
 251         Encode (bits, context->count, 8);
 252
 253         /* Pad out to 56 mod 64. */
 254         index = (unsigned int)((context->count[0] >> 3) & 0x3f);
 255         padLen = (index < 56) ? (56 - index) : (120 - index);
 256         MD5Update (context, PADDING, padLen);
 257
 258         /* Append length (before padding) */
 259         MD5Update (context, bits, 8);
 260 }
 261
 262 /*
 263  * MD5 finalization. Ends an MD5 message-digest operation, writing the
 264  * the message digest and zeroizing the context.
 265  */
 266
 267 void MD5Final ( unsigned char digest[16], MD5_CTX *context)
 268 {
 269         /* Do padding. */
 270         MD5Pad (context);
 271
 272         /* Store state in digest */
 273         Encode (digest, context->state, 16);
 274
 275         /* Zeroize sensitive information. */
 276         memset ((void *)context, 0, sizeof (*context));
 277 }
 278
 279 /* MD5 basic transformation. Transforms state based on block. */
 280
 281 static void
 282 MD5Transform (state, block)
 283         u_int32_t state[4];
 284         const unsigned char block[64];
 285 {
 286         u_int32_t a, b, c, d, x[16], temp;
 287         int i;
 288
 289         static const int S1[] = { 7, 12, 17, 22 };
 290         static const u_int32_t C1[] = {
 291                 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
 292                 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
 293                 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
 294                 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821
 295         };
 296
 297         static const int p2[] = {
 298                 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12
 299         };
 300         static const int S2[] = { 5, 9, 14, 20 };
 301         static const u_int32_t C2[] = {
 302                 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
 303                 0xd62f105d, 0x2441453,  0xd8a1e681, 0xe7d3fbc8,
 304                 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
 305                 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a
 306         };
 307
 308         static const int p3[] = {
 309                 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2
 310         };
 311         static const int S3[] = { 4, 11, 16, 23 };
 312         static const u_int32_t C3[] = {
 313                 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
 314                 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
 315                 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
 316                 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665
 317         };
 318
 319         static const int p4[] = {
 320                 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9
 321         };
 322         static const int S4[] = { 6, 10, 15, 21 };
 323         static const u_int32_t C4[] = {
 324                 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
 325                 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
 326                 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
 327                 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
 328         };
 329
 330         Decode (x, block, 64);
 331
 332         a = state[0]; b = state[1]; c = state[2]; d = state[3];
 333
 334         /* Round 1 */
 335         for ( i = 0 ; i < 16 ; i++ ) {
 336                 FF (a, b, c, d, x[i], S1[i&3], C1[i]);
 337                 temp = d; d= c; c = b; b = a; a = temp;
 338         }
 339
 340         /* Round 2 */
 341         for ( i = 0 ; i < 16 ; i++ ) {
 342                 GG (a, b, c, d, x[p2[i]], S2[i&3], C2[i]);
 343                 temp = d; d= c; c = b; b = a; a = temp;
 344         }
 345         /* Round 3 */
 346         for ( i = 0 ; i < 16 ; i++ ) {
 347                 HH (a, b, c, d, x[p3[i]], S3[i&3], C3[i]);
 348                 temp = d; d= c; c = b; b = a; a = temp;
 349         }
 350
 351         /* Round 4 */
 352         for ( i = 0 ; i < 16 ; i++ ) {
 353                 II (a, b, c, d, x[p4[i]], S4[i&3], C4[i]);
 354                 temp = d; d= c; c = b; b = a; a = temp;
 355         }
 356
 357         state[0] += a;
 358         state[1] += b;
 359         state[2] += c;
 360         state[3] += d;
 361
 362         /* Zeroize sensitive information. */
 363         memset ((void *)x, 0, sizeof (x));
 364 }
 365
 366
 367 static void to64( char *s, unsigned long v, int n)
 368 {
 369         while (--n >= 0) {
 370                 *s++ = itoa64[v&0x3f];
 371                 v >>= 6;
 372         }
 373 }
 374
 375 /*
 376  * UNIX password
 377  *
 378  * Use MD5 for what it is best at...
 379  */
 380
 381 char * md5_crypt_r( const char *pw, const char *salt, struct crypt_data * data)
 382 {
 383         char *p = data->p;
 384         const char *sp = data->sp;
 385         const char *ep = data->ep;
 386         char *passwd = *data->KS;
 387         unsigned char   final[17];      /* final[16] exists only to aid in looping */
 388         int sl,pl,i,md5_magic_len,pw_len;
 389         MD5_CTX ctx,ctx1;
 390         unsigned long l;
 391
 392         /* Refine the Salt first */
 393         sp = salt;
 394
 395         /* If it starts with the magic string, then skip that */
 396         md5_magic_len = strlen(md5_magic);
 397         if(!strncmp(sp,md5_magic,md5_magic_len))
 398                 sp += md5_magic_len;
 399
 400         /* It stops at the first '$', max 8 chars */
 401         for(ep=sp;*ep && *ep != '$' && ep < (sp+8);ep++)
 402                 continue;
 403
 404         /* get the length of the true salt */
 405         sl = ep - sp;
 406
 407         MD5Init(&ctx);
 408
 409         /* The password first, since that is what is most unknown */
 410         pw_len = strlen(pw);
 411         MD5Update(&ctx,pw,pw_len);
 412
 413         /* Then our magic string */
 414         MD5Update(&ctx,md5_magic,md5_magic_len);
 415
 416         /* Then the raw salt */
 417         MD5Update(&ctx,sp,sl);
 418
 419         /* Then just as many characters of the MD5(pw,salt,pw) */
 420         MD5Init(&ctx1);
 421         MD5Update(&ctx1,pw,pw_len);
 422         MD5Update(&ctx1,sp,sl);
 423         MD5Update(&ctx1,pw,pw_len);
 424         MD5Final(final,&ctx1);
 425         for(pl = pw_len; pl > 0; pl -= 16)
 426                 MD5Update(&ctx,final,pl>16 ? 16 : pl);
 427
 428         /* Don't leave anything around in vm they could use. */
 429         memset(final,0,sizeof final);
 430
 431         /* Then something really weird... */
 432         for (i = pw_len; i ; i >>= 1) {
 433                 MD5Update(&ctx, ((i&1) ? final : (const unsigned char *) pw), 1);
 434         }
 435
 436         /* Now make the output string */
 437         strcpy(passwd,md5_magic);
 438         strncat(passwd,sp,sl);
 439         strcat(passwd,"$");
 440
 441         MD5Final(final,&ctx);
 442
 443         /*
 444          * and now, just to make sure things don't run too fast
 445          * On a 60 Mhz Pentium this takes 34 msec, so you would
 446          * need 30 seconds to build a 1000 entry dictionary...
 447          */
 448         for(i=0;i<1000;i++) {
 449                 MD5Init(&ctx1);
 450                 if(i & 1)
 451                         MD5Update(&ctx1,pw,pw_len);
 452                 else
 453                         MD5Update(&ctx1,final,16);
 454
 455                 if(i % 3)
 456                         MD5Update(&ctx1,sp,sl);
 457
 458                 if(i % 7)
 459                         MD5Update(&ctx1,pw,pw_len);
 460
 461                 if(i & 1)
 462                         MD5Update(&ctx1,final,16);
 463                 else
 464                         MD5Update(&ctx1,pw,pw_len);
 465                 MD5Final(final,&ctx1);
 466         }
 467
 468         p = passwd + strlen(passwd);
 469
 470         final[16] = final[5];
 471         for ( i=0 ; i < 5 ; i++ ) {
 472                 l = (final[i]<<16) | (final[i+6]<<8) | final[i+12];
 473                 to64(p,l,4); p += 4;
 474         }
 475         l = final[11];
 476         to64(p,l,2); p += 2;
 477         *p = '\0';
 478
 479         /* Don't leave anything around in vm they could use. */
 480         memset(final,0,sizeof final);
 481
 482         return passwd;
 483 }
 484