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