base/md5.cc

   1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // The original file was copied from sqlite, and was in the public domain.
   6
   7 /*
   8  * This code implements the MD5 message-digest algorithm.
   9  * The algorithm is due to Ron Rivest.  This code was
  10  * written by Colin Plumb in 1993, no copyright is claimed.
  11  * This code is in the public domain; do with it what you wish.
  12  *
  13  * Equivalent code is available from RSA Data Security, Inc.
  14  * This code has been tested against that, and is equivalent,
  15  * except that you don't need to include two pages of legalese
  16  * with every copy.
  17  *
  18  * To compute the message digest of a chunk of bytes, declare an
  19  * MD5Context structure, pass it to MD5Init, call MD5Update as
  20  * needed on buffers full of bytes, and then call MD5Final, which
  21  * will fill a supplied 16-byte array with the digest.
  22  */
  23
  24 #include "base/md5.h"
  25
  26 #include <stddef.h>
  27
  28 namespace {
  29
  30 struct Context {
  31   uint32_t buf[4];
  32   uint32_t bits[2];
  33   uint8_t in[64];
  34 };
  35
  36 /*
  37  * Note: this code is harmless on little-endian machines.
  38  */
  39 void byteReverse(uint8_t* buf, unsigned longs) {
  40   do {
  41     uint32_t temp = static_cast<uint32_t>(
  42         static_cast<unsigned>(buf[3]) << 8 |
  43         buf[2]) << 16 |
  44         (static_cast<unsigned>(buf[1]) << 8 | buf[0]);
  45     *reinterpret_cast<uint32_t*>(buf) = temp;
  46     buf += 4;
  47   } while (--longs);
  48 }
  49
  50 /* The four core functions - F1 is optimized somewhat */
  51
  52 /* #define F1(x, y, z) (x & y | ~x & z) */
  53 #define F1(x, y, z) (z ^ (x & (y ^ z)))
  54 #define F2(x, y, z) F1(z, x, y)
  55 #define F3(x, y, z) (x ^ y ^ z)
  56 #define F4(x, y, z) (y ^ (x | ~z))
  57
  58 /* This is the central step in the MD5 algorithm. */
  59 #define MD5STEP(f, w, x, y, z, data, s) \
  60   (w += f(x, y, z) + data, w = w << s | w >> (32 - s), w += x)
  61
  62 /*
  63  * The core of the MD5 algorithm, this alters an existing MD5 hash to
  64  * reflect the addition of 16 longwords of new data.  MD5Update blocks
  65  * the data and converts bytes into longwords for this routine.
  66  */
  67 void MD5Transform(uint32_t buf[4], const uint32_t in[16]) {
  68   uint32_t a, b, c, d;
  69
  70   a = buf[0];
  71   b = buf[1];
  72   c = buf[2];
  73   d = buf[3];
  74
  75   MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
  76   MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
  77   MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
  78   MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
  79   MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
  80   MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
  81   MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
  82   MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
  83   MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
  84   MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
  85   MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
  86   MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
  87   MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
  88   MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
  89   MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
  90   MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
  91
  92   MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
  93   MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
  94   MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
  95   MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
  96   MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
  97   MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
  98   MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
  99   MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
 100   MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
 101   MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
 102   MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
 103   MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
 104   MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
 105   MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
 106   MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
 107   MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
 108
 109   MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
 110   MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
 111   MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
 112   MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
 113   MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
 114   MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
 115   MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
 116   MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
 117   MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
 118   MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
 119   MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
 120   MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
 121   MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
 122   MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
 123   MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
 124   MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
 125
 126   MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
 127   MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
 128   MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
 129   MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
 130   MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
 131   MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
 132   MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
 133   MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
 134   MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
 135   MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
 136   MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
 137   MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
 138   MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
 139   MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
 140   MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
 141   MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
 142
 143   buf[0] += a;
 144   buf[1] += b;
 145   buf[2] += c;
 146   buf[3] += d;
 147 }
 148
 149 }  // namespace
 150
 151 namespace base {
 152
 153 /*
 154  * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
 155  * initialization constants.
 156  */
 157 void MD5Init(MD5Context* context) {
 158   struct Context* ctx = reinterpret_cast<struct Context*>(context);
 159   ctx->buf[0] = 0x67452301;
 160   ctx->buf[1] = 0xefcdab89;
 161   ctx->buf[2] = 0x98badcfe;
 162   ctx->buf[3] = 0x10325476;
 163   ctx->bits[0] = 0;
 164   ctx->bits[1] = 0;
 165 }
 166
 167 /*
 168  * Update context to reflect the concatenation of another buffer full
 169  * of bytes.
 170  */
 171 void MD5Update(MD5Context* context, const StringPiece& data) {
 172   struct Context* ctx = reinterpret_cast<struct Context*>(context);
 173   const uint8_t* buf = reinterpret_cast<const uint8_t*>(data.data());
 174   size_t len = data.size();
 175
 176   /* Update bitcount */
 177
 178   uint32_t t = ctx->bits[0];
 179   if ((ctx->bits[0] = t + (static_cast<uint32_t>(len) << 3)) < t)
 180     ctx->bits[1]++; /* Carry from low to high */
 181   ctx->bits[1] += static_cast<uint32_t>(len >> 29);
 182
 183   t = (t >> 3) & 0x3f; /* Bytes already in shsInfo->data */
 184
 185   /* Handle any leading odd-sized chunks */
 186
 187   if (t) {
 188     uint8_t* p = static_cast<uint8_t*>(ctx->in + t);
 189
 190     t = 64 - t;
 191     if (len < t) {
 192       memcpy(p, buf, len);
 193       return;
 194     }
 195     memcpy(p, buf, t);
 196     byteReverse(ctx->in, 16);
 197     MD5Transform(ctx->buf, reinterpret_cast<uint32_t*>(ctx->in));
 198     buf += t;
 199     len -= t;
 200   }
 201
 202   /* Process data in 64-byte chunks */
 203
 204   while (len >= 64) {
 205     memcpy(ctx->in, buf, 64);
 206     byteReverse(ctx->in, 16);
 207     MD5Transform(ctx->buf, reinterpret_cast<uint32_t*>(ctx->in));
 208     buf += 64;
 209     len -= 64;
 210   }
 211
 212   /* Handle any remaining bytes of data. */
 213
 214   memcpy(ctx->in, buf, len);
 215 }
 216
 217 /*
 218  * Final wrapup - pad to 64-byte boundary with the bit pattern
 219  * 1 0* (64-bit count of bits processed, MSB-first)
 220  */
 221 void MD5Final(MD5Digest* digest, MD5Context* context) {
 222   struct Context* ctx = reinterpret_cast<struct Context*>(context);
 223   unsigned count;
 224   uint8_t* p;
 225
 226   /* Compute number of bytes mod 64 */
 227   count = (ctx->bits[0] >> 3) & 0x3F;
 228
 229   /* Set the first char of padding to 0x80.  This is safe since there is
 230      always at least one byte free */
 231   p = ctx->in + count;
 232   *p++ = 0x80;
 233
 234   /* Bytes of padding needed to make 64 bytes */
 235   count = 64 - 1 - count;
 236
 237   /* Pad out to 56 mod 64 */
 238   if (count < 8) {
 239     /* Two lots of padding:  Pad the first block to 64 bytes */
 240     memset(p, 0, count);
 241     byteReverse(ctx->in, 16);
 242     MD5Transform(ctx->buf, reinterpret_cast<uint32_t*>(ctx->in));
 243
 244     /* Now fill the next block with 56 bytes */
 245     memset(ctx->in, 0, 56);
 246   } else {
 247     /* Pad block to 56 bytes */
 248     memset(p, 0, count - 8);
 249   }
 250   byteReverse(ctx->in, 14);
 251
 252   /* Append length in bits and transform */
 253   memcpy(&ctx->in[14 * sizeof(ctx->bits[0])], &ctx->bits[0],
 254          sizeof(ctx->bits[0]));
 255   memcpy(&ctx->in[15 * sizeof(ctx->bits[1])], &ctx->bits[1],
 256          sizeof(ctx->bits[1]));
 257
 258   MD5Transform(ctx->buf, reinterpret_cast<uint32_t*>(ctx->in));
 259   byteReverse(reinterpret_cast<uint8_t*>(ctx->buf), 4);
 260   memcpy(digest->a, ctx->buf, 16);
 261   memset(ctx, 0, sizeof(*ctx)); /* In case it's sensitive */
 262 }
 263
 264 void MD5IntermediateFinal(MD5Digest* digest, const MD5Context* context) {
 265   /* MD5Final mutates the MD5Context*. Make a copy for generating the
 266      intermediate value. */
 267   MD5Context context_copy;
 268   memcpy(&context_copy, context, sizeof(context_copy));
 269   MD5Final(digest, &context_copy);
 270 }
 271
 272 std::string MD5DigestToBase16(const MD5Digest& digest) {
 273   static char const zEncode[] = "0123456789abcdef";
 274
 275   std::string ret;
 276   ret.resize(32);
 277
 278   for (int i = 0, j = 0; i < 16; i++, j += 2) {
 279     uint8_t a = digest.a[i];
 280     ret[j] = zEncode[(a >> 4) & 0xf];
 281     ret[j + 1] = zEncode[a & 0xf];
 282   }
 283   return ret;
 284 }
 285
 286 void MD5Sum(const void* data, size_t length, MD5Digest* digest) {
 287   MD5Context ctx;
 288   MD5Init(&ctx);
 289   MD5Update(&ctx, StringPiece(reinterpret_cast<const char*>(data), length));
 290   MD5Final(digest, &ctx);
 291 }
 292
 293 std::string MD5String(const StringPiece& str) {
 294   MD5Digest digest;
 295   MD5Sum(str.data(), str.length(), &digest);
 296   return MD5DigestToBase16(digest);
 297 }
 298
 299 }  // namespace base