git.m6w6.name Git - awesomized/libmemcached/blob - lib/md5.c

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