src/md5.c

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