lib/md5.c

   1 /*  $Id: md5.c 4154 2000-10-31 16:28:53Z kondou $
   2 **
   3 **  RSA Data Security, Inc. MD5 Message-Digest Algorithm
   4 **
   5 **  The standard MD5 message digest routines, from RSA Data Security, Inc.
   6 **  by way of Landon Curt Noll, modified and integrated into INN by Clayton
   7 **  O'Neill and then simplified somewhat, converted to INN coding style,
   8 **  and commented by Russ Allbery.
   9 **
  10 **  To form the message digest for a message M:
  11 **    (1) Initialize a context buffer md5_context using md5_init
  12 **    (2) Call md5_update on md5_context and M
  13 **    (3) Call md5_final on md5_context
  14 **  The message digest is now in md5_context->digest[0...15].
  15 **
  16 **  Alternately, just call md5_hash on M, passing it a buffer of at least
  17 **  16 bytes into which to put the digest.  md5_hash does the above
  18 **  internally for you and is the most convenient interface; the interface
  19 **  described above, however, is better when all of the data to hash isn't
  20 **  available neatly in a single buffer (such as hashing data aquired a
  21 **  block at a time).
  22 **
  23 **  For information about MD5, see RFC 1321.
  24 **
  25 **  LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  26 **  INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO
  27 **  EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  28 **  CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  29 **  USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  30 **  OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  31 **  PERFORMANCE OF THIS SOFTWARE.
  32 **
  33 **  Copyright (C) 1990, RSA Data Security, Inc.  All rights reserved.
  34 **
  35 **  License to copy and use this software is granted provided that it is
  36 **  identified as the "RSA Data Security, Inc. MD5 Message-Digest Algorithm"
  37 **  in all material mentioning or referencing this software or this
  38 **  function.
  39 **
  40 **  License is also granted to make and use derivative works provided that
  41 **  such works are identified as "derived from the RSA Data Security,
  42 **  Inc. MD5 Message-Digest Algorithm" in all material mentioning or
  43 **  referencing the derived work.
  44 **
  45 **  RSA Data Security, Inc. makes no representations concerning either the
  46 **  merchantability of this software or the suitability of this software for
  47 **  any particular purpose.  It is provided "as is" without express or
  48 **  implied warranty of any kind.
  49 **
  50 **  These notices must be retained in any copies of any part of this
  51 **  documentation and/or software.
  52 */
  53
  54 /*
  55 **  The actual mathematics and cryptography are at the bottom of this file,
  56 **  as those parts should be fully debugged and very infrequently changed.
  57 **  The core of actual work is done by md5_transform.  The beginning of this
  58 **  file contains the infrastructure around the mathematics.
  59 */
  60
  61 #include "config.h"
  62 #include "clibrary.h"
  63 #include "inn/md5.h"
  64
  65 /* Rotate a 32-bit value left, used by both the MD5 mathematics and by the
  66    routine below to byteswap data on big-endian machines. */
  67 #define ROT(X, n)       (((X) << (n)) | ((X) >> (32 - (n))))
  68
  69 /* Almost zero fill padding, used by md5_final.  The 0x80 is part of the MD5
  70    hash algorithm, from RFC 1321 section 3.1:
  71
  72      Padding is performed as follows: a single "1" bit is appended to the
  73      message, and then "0" bits are appended so that the length in bits of
  74      the padded message becomes congruent to 448, modulo 512.  In all, at
  75      least one bit and at most 512 bits are appended.
  76
  77    Let the compiler zero the remainder of the array for us, guaranteed by
  78    ISO C99 6.7.8 paragraph 21.  */
  79 static const unsigned char padding[MD5_CHUNKSIZE] = { 0x80, 0 /* 0, ... */ };
  80
  81 /* Internal prototypes. */
  82 static void md5_transform(uint32_t *, const uint32_t *);
  83 static void md5_update_block(struct md5_context *, const unsigned char *,
  84                              size_t);
  85
  86 /* MD5 requires that input data be treated as words in little-endian byte
  87    order.  From RFC 1321 section 2:
  88
  89      Similarly, a sequence of bytes can be interpreted as a sequence of
  90      32-bit words, where each consecutive group of four bytes is interpreted
  91      as a word with the low-order (least significant) byte given first.
  92
  93    Input data must therefore be byteswapped on big-endian machines, as must
  94    the 16-byte result digest.  Since we have to make a copy of the incoming
  95    data anyway to ensure alignment for 4-byte access, we can byteswap it in
  96    place. */
  97 #if !WORDS_BIGENDIAN
  98 # define decode(data)           /* empty */
  99 # define encode(data, out)      memcpy((out), (data), MD5_DIGESTSIZE)
 100 #else
 101
 102 /* The obvious way to do this is to pull single bytes at a time out of the
 103    input array and build words from them; this requires three shifts and
 104    three Boolean or operations, but it requires four memory reads per word
 105    unless the compiler is really smart.  Since we can assume four-byte
 106    alignment for the input data, use this optimized routine from J. Touch,
 107    USC/ISI.  This requires four shifts, two ands, and two ors, but only one
 108    memory read per word. */
 109 #define swap(word)              \
 110     do {                        \
 111         htmp = ROT((word), 16); \
 112         ltmp = htmp >> 8;       \
 113         htmp &= 0x00ff00ff;     \
 114         ltmp &= 0x00ff00ff;     \
 115         htmp <<= 8;             \
 116         (word) = htmp | ltmp;   \
 117     } while (0)
 118
 119 /* We process 16 words of data (one MD5 block) of data at a time, completely
 120    unrolling the loop manually since it should allow the compiler to take
 121    advantage of pipelining and parallel arithmetic units. */
 122 static void
 123 decode(uint32_t *data)
 124 {
 125     uint32_t ltmp, htmp;
 126
 127     swap(data[ 0]); swap(data[ 1]); swap(data[ 2]); swap(data[ 3]);
 128     swap(data[ 4]); swap(data[ 5]); swap(data[ 6]); swap(data[ 7]);
 129     swap(data[ 8]); swap(data[ 9]); swap(data[10]); swap(data[11]);
 130     swap(data[12]); swap(data[13]); swap(data[14]); swap(data[15]);
 131 }
 132
 133 /* Used by md5_final to generate the final digest.  The digest is not
 134    guaranteed to be aligned for 4-byte access but we are allowed to be
 135    destructive, so byteswap first and then copy the result over. */
 136 static void
 137 encode(uint32_t *data, unsigned char *out)
 138 {
 139     uint32_t ltmp, htmp;
 140
 141     swap(data[0]);
 142     swap(data[1]);
 143     swap(data[2]);
 144     swap(data[3]);
 145     memcpy(out, data, MD5_DIGESTSIZE);
 146 }
 147
 148 #endif /* WORDS_BIGENDIAN */
 149
 150
 151 /*
 152 **  That takes care of the preliminaries; now the real fun begins.  The
 153 **  initialization function for a struct md5_context; set lengths to zero
 154 **  and initialize our working buffer with the magic constants (c.f. RFC
 155 **  1321 section 3.3).
 156 */
 157 void
 158 md5_init(struct md5_context *context)
 159 {
 160     context->buf[0] = 0x67452301U;
 161     context->buf[1] = 0xefcdab89U;
 162     context->buf[2] = 0x98badcfeU;
 163     context->buf[3] = 0x10325476U;
 164
 165     context->count[0] = 0;
 166     context->count[1] = 0;
 167     context->datalen  = 0;
 168 }
 169
 170
 171 /*
 172 **  The workhorse function, called for each chunk of data.  Update the
 173 **  message-digest context to account for the presence of each of the
 174 **  characters data[0 .. count - 1] in the message whose digest is being
 175 **  computed.  Accepts any length of data; all whole blocks are processed
 176 **  and the remaining data is buffered for later processing by either
 177 **  another call to md5_update or by md5_final.
 178 */
 179 void
 180 md5_update(struct md5_context *context, const unsigned char *data,
 181            size_t count)
 182 {
 183     unsigned int datalen = context->datalen;
 184     unsigned int left;
 185     size_t high_count, low_count, used;
 186
 187     /* Update the count of hashed bytes.  The machinations here are to do
 188        the right thing on a platform where size_t > 32 bits without causing
 189        compiler warnings on platforms where it's 32 bits.  RFC 1321 section
 190        3.2 says:
 191
 192          A 64-bit representation of b (the length of the message before the
 193          padding bits were added) is appended to the result of the previous
 194          step.  In the unlikely event that b is greater than 2^64, then only
 195          the low-order 64 bits of b are used.
 196
 197        so we can just ignore the higher bits of count if size_t is larger
 198        than 64 bits.  (Think ahead!)  If size_t is only 32 bits, the
 199        compiler should kill the whole if statement as dead code. */
 200     if (sizeof(count) > 4) {
 201         high_count = count >> 31;
 202         context->count[1] += (high_count >> 1) & 0xffffffffU;
 203     }
 204
 205     /* Now deal with count[0].  Add in the low 32 bits of count and
 206        increment count[1] if count[0] wraps.  Isn't unsigned arithmetic
 207        cool? */
 208     low_count = count & 0xffffffffU;
 209     context->count[0] += low_count;
 210     if (context->count[0] < low_count)
 211         context->count[1]++;
 212
 213     /* See if we already have some data queued.  If so, try to complete a
 214        block and then deal with it first.  If the new data still doesn't
 215        fill the buffer, add it to the buffer and return.  Otherwise,
 216        transform that block and update data and count to account for the
 217        data we've already used. */
 218     if (datalen > 0) {
 219         left = MD5_CHUNKSIZE - datalen;
 220         if (left > count) {
 221             memcpy(context->in.byte + datalen, data, count);
 222             context->datalen += count;
 223             return;
 224         } else {
 225             memcpy(context->in.byte + datalen, data, left);
 226             decode(context->in.word);
 227             md5_transform(context->buf, context->in.word);
 228             data += left;
 229             count -= left;
 230             context->datalen = 0;
 231         }
 232     }
 233
 234     /* If we have a block of data or more left, pass the rest off to
 235        md5_update_block to deal with all of the full blocks available. */
 236     if (count >= MD5_CHUNKSIZE) {
 237         md5_update_block(context, data, count);
 238         used = (count / MD5_CHUNKSIZE) * MD5_CHUNKSIZE;
 239         data += used;
 240         count -= used;
 241     }
 242
 243     /* If there's anything left, buffer it until we can complete a block or
 244        for md5_final to deal with. */
 245     if (count > 0) {
 246         memcpy(context->in.byte, data, count);
 247         context->datalen = count;
 248     }
 249 }
 250
 251
 252 /*
 253 **  Update the message-digest context to account for the presence of each of
 254 **  the characters data[0 .. count - 1] in the message whose digest is being
 255 **  computed, except that we only deal with full blocks of data.  The data
 256 **  is processed one block at a time, and partial blocks at the end are
 257 **  ignored (they're dealt with by md5_update, which calls this routine.
 258 **
 259 **  Note that we always make a copy of the input data into an array of
 260 **  4-byte values.  If our input data were guaranteed to be aligned for
 261 **  4-byte access, we could just use the input buffer directly on
 262 **  little-endian machines, and in fact this implementation used to do that.
 263 **  However, a requirement to align isn't always easily detectable, even by
 264 **  configure (an Alpha running Tru64 will appear to allow unaligned
 265 **  accesses, but will spew errors to the terminal if you do it).  On top of
 266 **  that, even when it's allowed, unaligned access is quite frequently
 267 **  slower; we're about to do four reads of each word of the input data for
 268 **  the calculations, so doing one additional copy of the data up-front is
 269 **  probably worth it.
 270 */
 271 static void
 272 md5_update_block(struct md5_context *context, const unsigned char *data,
 273                  size_t count)
 274 {
 275     uint32_t in[MD5_CHUNKWORDS];
 276
 277     /* Process data in MD5_CHUNKSIZE blocks. */
 278     while (count >= MD5_CHUNKSIZE) {
 279         memcpy(in, data, MD5_CHUNKSIZE);
 280         decode(in);
 281         md5_transform(context->buf, in);
 282         data += MD5_CHUNKSIZE;
 283         count -= MD5_CHUNKSIZE;
 284     }
 285 }
 286
 287
 288 /*
 289 **  Terminates the message-digest computation, accounting for any final
 290 **  trailing data and adding the message length to the hashed data, and ends
 291 **  with the desired message digest in context->digest[0...15].
 292 */
 293 void
 294 md5_final(struct md5_context *context)
 295 {
 296     unsigned int pad_needed, left;
 297     uint32_t count[2];
 298     uint32_t *countloc;
 299
 300     /* Save the count before appending the padding. */
 301     count[0] = context->count[0];
 302     count[1] = context->count[1];
 303
 304     /* Pad the final block of data.  RFC 1321 section 3.1:
 305
 306          The message is "padded" (extended) so that its length (in bits) is
 307          congruent to 448, modulo 512.  That is, the message is extended so
 308          that it is just 64 bits shy of being a multiple of 512 bits long.
 309          Padding is always performed, even if the length of the message is
 310          already congruent to 448, modulo 512.
 311
 312        The 64 bits (two words) left are for the 64-bit count of bits
 313        hashed.  We'll need at most 64 bytes of padding; lucky that the
 314        padding array is exactly that size! */
 315     left = context->datalen;
 316     pad_needed = (left < 64 - 8) ? (64 - 8 - left) : (128 - 8 - left);
 317     md5_update(context, padding, pad_needed);
 318
 319     /* Append length in bits and transform.  Note that we cheat slightly
 320        here to save a few operations on big-endian machines; the algorithm
 321        says that we should add the length, in little-endian byte order, to
 322        the last block of data.  We'd then transform it into big-endian order
 323        on a big-endian machine.  But the count is *already* in big-endian
 324        order on a big-endian machine, so effectively we'd be byteswapping it
 325        twice.  Instead, add it to the block after doing byte swapping on the
 326        rest.
 327
 328        Note that we've been counting *bytes*, but the algorithm demands the
 329        length in *bits*, so shift things around a bit. */
 330     decode(context->in.word);
 331     countloc = &context->in.word[MD5_CHUNKWORDS - 2];
 332     countloc[0] = count[0] << 3;
 333     countloc[1] = (count[1] << 3) | (count[0] >> 29);
 334     md5_transform(context->buf, context->in.word);
 335
 336     /* Recover the final digest.  Whoo-hoo, we're done! */
 337     encode(context->buf, context->digest);
 338 }
 339
 340
 341 /*
 342 **  A convenience wrapper around md5_init, md5_update, and md5_final.  Takes
 343 **  a pointer to a buffer of data, the length of the data, and a pointer to
 344 **  a buffer of at least 16 bytes into which to write the message digest.
 345 */
 346 void
 347 md5_hash(const unsigned char *data, size_t length, unsigned char *digest)
 348 {
 349     struct md5_context context;
 350
 351     md5_init(&context);
 352     md5_update(&context, data, length);
 353     md5_final(&context);
 354     memcpy(digest, context.digest, MD5_DIGESTSIZE);
 355 }
 356
 357
 358 /*
 359 **  Look out, here comes the math.
 360 **
 361 **  There are no user-serviceable parts below this point unless you know
 362 **  quite a bit about MD5 or optimization of integer math.  The only
 363 **  function remaining, down below, is md5_transform; the rest of this is
 364 **  setting up macros to make that function more readable.
 365 **
 366 **  The F, G, H and I are basic MD5 functions.  The following identity saves
 367 **  one boolean operation.
 368 **
 369 **  F: (((x) & (y)) | (~(x) & (z))) == ((z) ^ ((x) & ((y) ^ (z))))
 370 **  G: (((x) & (z)) | ((y) & ~(z))) == ((y) ^ ((z) & ((x) ^ (y))))
 371 */
 372 #define F(x, y, z)      ((z) ^ ((x) & ((y) ^ (z))))
 373 #define G(x, y, z)      ((y) ^ ((z) & ((x) ^ (y))))
 374 #define H(x, y, z)      ((x) ^ (y) ^ (z))
 375 #define I(x, y, z)      ((y) ^ ((x) | (~z)))
 376
 377 /*
 378 **  FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.  Rotation
 379 **  is separate from addition to prevent recomputation.  S?? are the shift
 380 **  values for each round.
 381 */
 382 #define S11 7
 383 #define S12 12
 384 #define S13 17
 385 #define S14 22
 386 #define FF(a, b, c, d, x, s, ac)                                \
 387     {                                                           \
 388         (a) += F((b), (c), (d)) + (x) + (uint32_t) (ac);        \
 389         (a) = ROT((a), (s));                                    \
 390         (a) += (b);                                             \
 391     }
 392
 393 #define S21 5
 394 #define S22 9
 395 #define S23 14
 396 #define S24 20
 397 #define GG(a, b, c, d, x, s, ac)                                \
 398     {                                                           \
 399         (a) += G((b), (c), (d)) + (x) + (uint32_t) (ac);        \
 400         (a) = ROT((a), (s));                                    \
 401         (a) += (b);                                             \
 402     }
 403
 404 #define S31 4
 405 #define S32 11
 406 #define S33 16
 407 #define S34 23
 408 #define HH(a, b, c, d, x, s, ac)                                \
 409     {                                                           \
 410         (a) += H((b), (c), (d)) + (x) + (uint32_t) (ac);        \
 411         (a) = ROT((a), (s));                                    \
 412         (a) += (b);                                             \
 413     }
 414
 415 #define S41 6
 416 #define S42 10
 417 #define S43 15
 418 #define S44 21
 419 #define II(a, b, c, d, x, s, ac)                                \
 420     {                                                           \
 421         (a) += I((b), (c), (d)) + (x) + (uint32_t) (ac);        \
 422         (a) = ROT((a), (s));                                    \
 423         (a) += (b);                                             \
 424     }
 425
 426 /*
 427 **  Basic MD5 step.  Transforms buf based on in.
 428 */
 429 static void
 430 md5_transform(uint32_t *buf, const uint32_t *in)
 431 {
 432     uint32_t a = buf[0];
 433     uint32_t b = buf[1];
 434     uint32_t c = buf[2];
 435     uint32_t d = buf[3];
 436
 437     /* Round 1 */
 438     FF(a, b, c, d, in[ 0], S11, 3614090360UL); /*  1 */
 439     FF(d, a, b, c, in[ 1], S12, 3905402710UL); /*  2 */
 440     FF(c, d, a, b, in[ 2], S13,  606105819UL); /*  3 */
 441     FF(b, c, d, a, in[ 3], S14, 3250441966UL); /*  4 */
 442     FF(a, b, c, d, in[ 4], S11, 4118548399UL); /*  5 */
 443     FF(d, a, b, c, in[ 5], S12, 1200080426UL); /*  6 */
 444     FF(c, d, a, b, in[ 6], S13, 2821735955UL); /*  7 */
 445     FF(b, c, d, a, in[ 7], S14, 4249261313UL); /*  8 */
 446     FF(a, b, c, d, in[ 8], S11, 1770035416UL); /*  9 */
 447     FF(d, a, b, c, in[ 9], S12, 2336552879UL); /* 10 */
 448     FF(c, d, a, b, in[10], S13, 4294925233UL); /* 11 */
 449     FF(b, c, d, a, in[11], S14, 2304563134UL); /* 12 */
 450     FF(a, b, c, d, in[12], S11, 1804603682UL); /* 13 */
 451     FF(d, a, b, c, in[13], S12, 4254626195UL); /* 14 */
 452     FF(c, d, a, b, in[14], S13, 2792965006UL); /* 15 */
 453     FF(b, c, d, a, in[15], S14, 1236535329UL); /* 16 */
 454
 455     /* Round 2 */
 456     GG(a, b, c, d, in[ 1], S21, 4129170786UL); /* 17 */
 457     GG(d, a, b, c, in[ 6], S22, 3225465664UL); /* 18 */
 458     GG(c, d, a, b, in[11], S23,  643717713UL); /* 19 */
 459     GG(b, c, d, a, in[ 0], S24, 3921069994UL); /* 20 */
 460     GG(a, b, c, d, in[ 5], S21, 3593408605UL); /* 21 */
 461     GG(d, a, b, c, in[10], S22,   38016083UL); /* 22 */
 462     GG(c, d, a, b, in[15], S23, 3634488961UL); /* 23 */
 463     GG(b, c, d, a, in[ 4], S24, 3889429448UL); /* 24 */
 464     GG(a, b, c, d, in[ 9], S21,  568446438UL); /* 25 */
 465     GG(d, a, b, c, in[14], S22, 3275163606UL); /* 26 */
 466     GG(c, d, a, b, in[ 3], S23, 4107603335UL); /* 27 */
 467     GG(b, c, d, a, in[ 8], S24, 1163531501UL); /* 28 */
 468     GG(a, b, c, d, in[13], S21, 2850285829UL); /* 29 */
 469     GG(d, a, b, c, in[ 2], S22, 4243563512UL); /* 30 */
 470     GG(c, d, a, b, in[ 7], S23, 1735328473UL); /* 31 */
 471     GG(b, c, d, a, in[12], S24, 2368359562UL); /* 32 */
 472
 473     /* Round 3 */
 474     HH(a, b, c, d, in[ 5], S31, 4294588738UL); /* 33 */
 475     HH(d, a, b, c, in[ 8], S32, 2272392833UL); /* 34 */
 476     HH(c, d, a, b, in[11], S33, 1839030562UL); /* 35 */
 477     HH(b, c, d, a, in[14], S34, 4259657740UL); /* 36 */
 478     HH(a, b, c, d, in[ 1], S31, 2763975236UL); /* 37 */
 479     HH(d, a, b, c, in[ 4], S32, 1272893353UL); /* 38 */
 480     HH(c, d, a, b, in[ 7], S33, 4139469664UL); /* 39 */
 481     HH(b, c, d, a, in[10], S34, 3200236656UL); /* 40 */
 482     HH(a, b, c, d, in[13], S31,  681279174UL); /* 41 */
 483     HH(d, a, b, c, in[ 0], S32, 3936430074UL); /* 42 */
 484     HH(c, d, a, b, in[ 3], S33, 3572445317UL); /* 43 */
 485     HH(b, c, d, a, in[ 6], S34,   76029189UL); /* 44 */
 486     HH(a, b, c, d, in[ 9], S31, 3654602809UL); /* 45 */
 487     HH(d, a, b, c, in[12], S32, 3873151461UL); /* 46 */
 488     HH(c, d, a, b, in[15], S33,  530742520UL); /* 47 */
 489     HH(b, c, d, a, in[ 2], S34, 3299628645UL); /* 48 */
 490
 491     /* Round 4 */
 492     II(a, b, c, d, in[ 0], S41, 4096336452UL); /* 49 */
 493     II(d, a, b, c, in[ 7], S42, 1126891415UL); /* 50 */
 494     II(c, d, a, b, in[14], S43, 2878612391UL); /* 51 */
 495     II(b, c, d, a, in[ 5], S44, 4237533241UL); /* 52 */
 496     II(a, b, c, d, in[12], S41, 1700485571UL); /* 53 */
 497     II(d, a, b, c, in[ 3], S42, 2399980690UL); /* 54 */
 498     II(c, d, a, b, in[10], S43, 4293915773UL); /* 55 */
 499     II(b, c, d, a, in[ 1], S44, 2240044497UL); /* 56 */
 500     II(a, b, c, d, in[ 8], S41, 1873313359UL); /* 57 */
 501     II(d, a, b, c, in[15], S42, 4264355552UL); /* 58 */
 502     II(c, d, a, b, in[ 6], S43, 2734768916UL); /* 59 */
 503     II(b, c, d, a, in[13], S44, 1309151649UL); /* 60 */
 504     II(a, b, c, d, in[ 4], S41, 4149444226UL); /* 61 */
 505     II(d, a, b, c, in[11], S42, 3174756917UL); /* 62 */
 506     II(c, d, a, b, in[ 2], S43,  718787259UL); /* 63 */
 507     II(b, c, d, a, in[ 9], S44, 3951481745UL); /* 64 */
 508
 509     buf[0] += a;
 510     buf[1] += b;
 511     buf[2] += c;
 512     buf[3] += d;
 513 }