src/md5.c

   1 /* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm */
   2
   3 /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
   4 rights reserved.
   5
   6 License to copy and use this software is granted provided that it
   7 is identified as the "RSA Data Security, Inc. MD5 Message-Digest
   8 Algorithm" in all material mentioning or referencing this software
   9 or this function.
  10
  11 License is also granted to make and use derivative works provided
  12 that such works are identified as "derived from the RSA Data
  13 Security, Inc. MD5 Message-Digest Algorithm" in all material
  14 mentioning or referencing the derived work.
  15
  16 RSA Data Security, Inc. makes no representations concerning either
  17 the merchantability of this software or the suitability of this
  18 software for any particular purpose. It is provided "as is"
  19 without express or implied warranty of any kind.
  20
  21 These notices must be retained in any copies of any part of this
  22 documentation and/or software.
  23  */
  24
  25 #include "common.h"
  26 #include "md5.h"
  27
  28 /* Constants for MD5Transform routine.
  29  */
  30 #define S11 7
  31 #define S12 12
  32 #define S13 17
  33 #define S14 22
  34 #define S21 5
  35 #define S22 9
  36 #define S23 14
  37 #define S24 20
  38 #define S31 4
  39 #define S32 11
  40 #define S33 16
  41 #define S34 23
  42 #define S41 6
  43 #define S42 10
  44 #define S43 15
  45 #define S44 21
  46
  47 static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));
  48 static void Encode PROTO_LIST
  49   ((unsigned char *, UINT4 *, unsigned int));
  50 static void Decode PROTO_LIST
  51   ((UINT4 *, unsigned char *, unsigned int));
  52
  53 static unsigned char PADDING[64] = {
  54   0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  55   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  56   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
  57 };
  58
  59 /* F, G, H and I are basic MD5 functions.
  60  */
  61 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  62 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
  63 #define H(x, y, z) ((x) ^ (y) ^ (z))
  64 #define I(x, y, z) ((y) ^ ((x) | (~z)))
  65
  66 /* ROTATE_LEFT rotates x left n bits. */
  67 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
  68
  69 /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
  70 Rotation is separate from addition to prevent recomputation.
  71  */
  72 #define FF(a, b, c, d, x, s, ac) { \
  73  (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
  74  (a) = ROTATE_LEFT ((a), (s)); \
  75  (a) += (b); \
  76   }
  77 #define GG(a, b, c, d, x, s, ac) { \
  78  (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
  79  (a) = ROTATE_LEFT ((a), (s)); \
  80  (a) += (b); \
  81   }
  82 #define HH(a, b, c, d, x, s, ac) { \
  83  (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
  84  (a) = ROTATE_LEFT ((a), (s)); \
  85  (a) += (b); \
  86   }
  87 #define II(a, b, c, d, x, s, ac) { \
  88  (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
  89  (a) = ROTATE_LEFT ((a), (s)); \
  90  (a) += (b); \
  91   }
  92
  93 /* MD5 initialization. Begins an MD5 operation, writing a new context. */
  94 void MD5Init (context)
  95 MD5_CTX *context;                                        /* context */
  96 {
  97   context->count[0] = context->count[1] = 0;
  98   /* Load magic initialization constants. */
  99   context->state[0] = 0x67452301;
 100   context->state[1] = 0xefcdab89;
 101   context->state[2] = 0x98badcfe;
 102   context->state[3] = 0x10325476;
 103 }
 104
 105 /* MD5 block update operation. Continues an MD5 message-digest
 106   operation, processing another message block, and updating the
 107   context.
 108  */
 109 void MD5Update (context, input, inputLen)
 110 MD5_CTX *context;                                        /* context */
 111 unsigned char *input;                                /* input block */
 112 unsigned int inputLen;                     /* length of input block */
 113 {
 114   unsigned int i, idx, partLen;
 115
 116   /* Compute number of bytes mod 64 */
 117   idx = (unsigned int)((context->count[0] >> 3) & 0x3F);
 118
 119   /* Update number of bits */
 120   if ((context->count[0] += ((UINT4)inputLen << 3))
 121       < ((UINT4)inputLen << 3))
 122       context->count[1]++;
 123   context->count[1] += ((UINT4)inputLen >> 29);
 124
 125   partLen = 64 - idx;
 126
 127   /* Transform as many times as possible. */
 128   if (inputLen >= partLen) {
 129       memcpy((POINTER)&context->buffer[idx], (POINTER)input, partLen);
 130       MD5Transform (context->state, context->buffer);
 131
 132       for (i = partLen; i + 63 < inputLen; i += 64)
 133           MD5Transform (context->state, &input[i]);
 134
 135       idx = 0;
 136   }
 137   else
 138     i = 0;
 139
 140   /* Buffer remaining input */
 141   memcpy((POINTER)&context->buffer[idx], (POINTER)&input[i],
 142   inputLen-i);
 143 }
 144
 145 /* MD5 finalization. Ends an MD5 message-digest operation, writing the
 146   the message digest and zeroizing the context.
 147  */
 148 void MD5Final (digest, context)
 149 unsigned char digest[16];                         /* message digest */
 150 MD5_CTX *context;                                       /* context */
 151 {
 152   unsigned char bits[8];
 153   unsigned int idx, padLen;
 154
 155   /* Save number of bits */
 156   Encode (bits, context->count, 8);
 157
 158   /* Pad out to 56 mod 64. */
 159   idx = (unsigned int)((context->count[0] >> 3) & 0x3f);
 160   padLen = (idx < 56) ? (56 - idx) : (120 - idx);
 161   MD5Update (context, PADDING, padLen);
 162
 163   /* Append length (before padding) */
 164   MD5Update (context, bits, 8);
 165
 166   /* Store state in digest */
 167   Encode (digest, context->state, 16);
 168
 169   /* Zeroize sensitive information. */
 170   memset ((POINTER)context, 0, sizeof (*context));
 171 }
 172
 173 /* MD5 basic transformation. Transforms state based on block. */
 174 static void MD5Transform (state, block)
 175 UINT4 state[4];
 176 unsigned char block[64];
 177 {
 178   UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
 179
 180   Decode (x, block, 64);
 181
 182   /* Round 1 */
 183   FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
 184   FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
 185   FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
 186   FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
 187   FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
 188   FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
 189   FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
 190   FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
 191   FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
 192   FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
 193   FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
 194   FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
 195   FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
 196   FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
 197   FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
 198   FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
 199
 200  /* Round 2 */
 201   GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
 202   GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
 203   GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
 204   GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
 205   GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
 206   GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
 207   GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
 208   GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
 209   GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
 210   GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
 211   GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
 212   GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
 213   GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
 214   GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
 215   GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
 216   GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
 217
 218   /* Round 3 */
 219   HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
 220   HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
 221   HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
 222   HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
 223   HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
 224   HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
 225   HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
 226   HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
 227   HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
 228   HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
 229   HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
 230   HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
 231   HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
 232   HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
 233   HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
 234   HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
 235
 236   /* Round 4 */
 237   II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
 238   II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
 239   II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
 240   II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
 241   II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
 242   II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
 243   II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
 244   II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
 245   II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
 246   II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
 247   II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
 248   II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
 249   II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
 250   II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
 251   II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
 252   II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
 253
 254   state[0] += a;
 255   state[1] += b;
 256   state[2] += c;
 257   state[3] += d;
 258
 259   /* Zeroize sensitive information. */
 260   memset ((POINTER)x, 0, sizeof (x));
 261 }
 262
 263 /* Encodes input (UINT4) into output (unsigned char). Assumes len is
 264   a multiple of 4.
 265  */
 266 static void Encode (output, input, len)
 267 unsigned char *output;
 268 UINT4 *input;
 269 unsigned int len;
 270 {
 271   unsigned int i, j;
 272
 273   for (i = 0, j = 0; j < len; i++, j += 4) {
 274     output[j] = (unsigned char)(input[i] & 0xff);
 275     output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
 276     output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
 277     output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
 278   }
 279 }
 280
 281 /* Decodes input (unsigned char) into output (UINT4). Assumes len is
 282   a multiple of 4.
 283  */
 284 static void Decode (output, input, len)
 285 UINT4 *output;
 286 unsigned char *input;
 287 unsigned int len;
 288 {
 289   unsigned int i, j;
 290
 291   for (i = 0, j = 0; j < len; i++, j += 4)
 292     output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
 293       (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
 294 }
 295
 296 static const char *
 297 cryptpass_real(const char *pass, char *buffer, int seed)
 298 {
 299     static const char hex_digits[] = "0123456789ABCDEF";
 300     MD5_CTX ctx;
 301     unsigned int len, i, j;
 302     unsigned char temp[64], buff[16];
 303
 304     /* first: generate seed */
 305     if (seed) {
 306         for (i=j=0; j<4; j++) {
 307             temp[i++] = hex_digits[(seed >> (28 - 8*j)) & 15];
 308             temp[i++] = hex_digits[(seed >> (24 - 8*j)) & 15];
 309         }
 310         /* fill temp buffer with password, 1 and then 0's */
 311         j = strlen(pass);
 312         if ((sizeof(temp) - i) < j) j = sizeof(temp) - i;
 313         memcpy(temp+i, pass, j);
 314         i += j;
 315         if (i < sizeof(temp)) temp[i++] = '1';
 316         while (i < sizeof(temp)) temp[i++] = '0';
 317     } else {
 318         i = 0;
 319         /* next: duplicate password to fill temp buffer */
 320         len = strlen(pass);
 321         for (j=0; i<sizeof(temp); i++) {
 322             temp[i] = pass[j];
 323             if (++j == len) j = 0;
 324         }
 325     }
 326     /* next: compute MD5 digest of repeated password */
 327     MD5Init(&ctx);
 328     MD5Update(&ctx, temp, sizeof(temp));
 329     MD5Final(buff, &ctx);
 330     /* finally: write digest to output buffer */
 331     if (seed) {
 332         buffer[0] = '$';
 333         for (i=0,j=1; i<4; i++) {
 334             buffer[j++] = hex_digits[(seed >> (28 - 8*i)) & 15];
 335             buffer[j++] = hex_digits[(seed >> (24 - 8*i)) & 15];
 336         }
 337     } else {
 338         j = 0;
 339     }
 340     for (i=0; i<sizeof(buff); i++) {
 341         buffer[j++] = hex_digits[buff[i] >> 4];
 342         buffer[j++] = hex_digits[buff[i] & 15];
 343     }
 344     buffer[j] = 0;
 345     return buffer;
 346 }
 347
 348 const char *
 349 cryptpass(const char *pass, char *buffer)
 350 {
 351     int seed;
 352     do { seed = rand(); } while (!seed);
 353     return cryptpass_real(pass, buffer, seed);
 354 }
 355
 356 int
 357 checkpass(const char *pass, const char *crypted)
 358 {
 359     char new_crypted[MD5_CRYPT_LENGTH], hseed[9];
 360     int seed;
 361
 362     if (crypted[0] == '$') {
 363         /* new-style crypt, use "seed" after '$' */
 364         strncpy(hseed, crypted+1, 8);
 365         hseed[8] = 0;
 366         seed = strtoul(hseed, NULL, 16);
 367     } else {
 368         /* old-style crypt, use "seed" of 0 */
 369         seed = 0;
 370     }
 371     cryptpass_real(pass, new_crypted, seed);
 372     return !strcmp(crypted, new_crypted);
 373 }