git.m6w6.name Git - awesomized/libmemcached/blob - libhashkit/md5.cc

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