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