lib/md5.c

   1 /* Functions to compute MD5 message digest of files or memory blocks.
   2    according to the definition of MD5 in RFC 1321 from April 1992.
   3    Copyright (C) 1995-2011 Red Hat, Inc.
   4    This file is part of elfutils.
   5    Written by Ulrich Drepper <drepper@redhat.com>, 1995.
   6
   7    This file is free software; you can redistribute it and/or modify
   8    it under the terms of either
   9
  10      * the GNU Lesser General Public License as published by the Free
  11        Software Foundation; either version 3 of the License, or (at
  12        your option) any later version
  13
  14    or
  15
  16      * the GNU General Public License as published by the Free
  17        Software Foundation; either version 2 of the License, or (at
  18        your option) any later version
  19
  20    or both in parallel, as here.
  21
  22    elfutils is distributed in the hope that it will be useful, but
  23    WITHOUT ANY WARRANTY; without even the implied warranty of
  24    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  25    General Public License for more details.
  26
  27    You should have received copies of the GNU General Public License and
  28    the GNU Lesser General Public License along with this program.  If
  29    not, see <http://www.gnu.org/licenses/>.  */
  30
  31 #ifdef HAVE_CONFIG_H
  32 # include <config.h>
  33 #endif
  34
  35 #include <stdlib.h>
  36 #include <string.h>
  37 #include <sys/types.h>
  38
  39 #include "md5.h"
  40 #include "system.h"
  41
  42 #define SWAP(n) LE32 (n)
  43
  44 /* This array contains the bytes used to pad the buffer to the next
  45    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
  46 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  47
  48
  49 /* Initialize structure containing state of computation.
  50    (RFC 1321, 3.3: Step 3)  */
  51 void
  52 md5_init_ctx (ctx)
  53      struct md5_ctx *ctx;
  54 {
  55   ctx->A = 0x67452301;
  56   ctx->B = 0xefcdab89;
  57   ctx->C = 0x98badcfe;
  58   ctx->D = 0x10325476;
  59
  60   ctx->total[0] = ctx->total[1] = 0;
  61   ctx->buflen = 0;
  62 }
  63
  64 /* Put result from CTX in first 16 bytes following RESBUF.  The result
  65    must be in little endian byte order.
  66
  67    IMPORTANT: On some systems it is required that RESBUF is correctly
  68    aligned for a 32 bits value.  */
  69 void *
  70 md5_read_ctx (ctx, resbuf)
  71      const struct md5_ctx *ctx;
  72      void *resbuf;
  73 {
  74   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
  75   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
  76   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
  77   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
  78
  79   return resbuf;
  80 }
  81
  82 static void
  83 le64_copy (char *dest, uint64_t x)
  84 {
  85   for (size_t i = 0; i < 8; ++i)
  86     {
  87       dest[i] = (uint8_t) x;
  88       x >>= 8;
  89     }
  90 }
  91
  92 /* Process the remaining bytes in the internal buffer and the usual
  93    prolog according to the standard and write the result to RESBUF.
  94
  95    IMPORTANT: On some systems it is required that RESBUF is correctly
  96    aligned for a 32 bits value.  */
  97 void *
  98 md5_finish_ctx (ctx, resbuf)
  99      struct md5_ctx *ctx;
 100      void *resbuf;
 101 {
 102   /* Take yet unprocessed bytes into account.  */
 103   md5_uint32 bytes = ctx->buflen;
 104   size_t pad;
 105
 106   /* Now count remaining bytes.  */
 107   ctx->total[0] += bytes;
 108   if (ctx->total[0] < bytes)
 109     ++ctx->total[1];
 110
 111   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 112   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 113
 114   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 115   const uint64_t bit_length = ((ctx->total[0] << 3)
 116                                + ((uint64_t) ((ctx->total[1] << 3) |
 117                                               (ctx->total[0] >> 29)) << 32));
 118   le64_copy (&ctx->buffer[bytes + pad], bit_length);
 119
 120   /* Process last bytes.  */
 121   md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
 122
 123   return md5_read_ctx (ctx, resbuf);
 124 }
 125
 126
 127 #ifdef NEED_MD5_STREAM
 128 /* Compute MD5 message digest for bytes read from STREAM.  The
 129    resulting message digest number will be written into the 16 bytes
 130    beginning at RESBLOCK.  */
 131 int
 132 md5_stream (stream, resblock)
 133      FILE *stream;
 134      void *resblock;
 135 {
 136   /* Important: BLOCKSIZE must be a multiple of 64.  */
 137 #define BLOCKSIZE 4096
 138   struct md5_ctx ctx;
 139   char buffer[BLOCKSIZE + 72];
 140   size_t sum;
 141
 142   /* Initialize the computation context.  */
 143   md5_init_ctx (&ctx);
 144
 145   /* Iterate over full file contents.  */
 146   while (1)
 147     {
 148       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
 149          computation function processes the whole buffer so that with the
 150          next round of the loop another block can be read.  */
 151       size_t n;
 152       sum = 0;
 153
 154       /* Read block.  Take care for partial reads.  */
 155       do
 156         {
 157           n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
 158
 159           sum += n;
 160         }
 161       while (sum < BLOCKSIZE && n != 0);
 162       if (n == 0 && ferror (stream))
 163         return 1;
 164
 165       /* If end of file is reached, end the loop.  */
 166       if (n == 0)
 167         break;
 168
 169       /* Process buffer with BLOCKSIZE bytes.  Note that
 170                         BLOCKSIZE % 64 == 0
 171        */
 172       md5_process_block (buffer, BLOCKSIZE, &ctx);
 173     }
 174
 175   /* Add the last bytes if necessary.  */
 176   if (sum > 0)
 177     md5_process_bytes (buffer, sum, &ctx);
 178
 179   /* Construct result in desired memory.  */
 180   md5_finish_ctx (&ctx, resblock);
 181   return 0;
 182 }
 183 #endif
 184
 185
 186 #ifdef NEED_MD5_BUFFER
 187 /* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
 188    result is always in little endian byte order, so that a byte-wise
 189    output yields to the wanted ASCII representation of the message
 190    digest.  */
 191 void *
 192 md5_buffer (buffer, len, resblock)
 193      const char *buffer;
 194      size_t len;
 195      void *resblock;
 196 {
 197   struct md5_ctx ctx;
 198
 199   /* Initialize the computation context.  */
 200   md5_init_ctx (&ctx);
 201
 202   /* Process whole buffer but last len % 64 bytes.  */
 203   md5_process_bytes (buffer, len, &ctx);
 204
 205   /* Put result in desired memory area.  */
 206   return md5_finish_ctx (&ctx, resblock);
 207 }
 208 #endif
 209
 210
 211 void
 212 md5_process_bytes (buffer, len, ctx)
 213      const void *buffer;
 214      size_t len;
 215      struct md5_ctx *ctx;
 216 {
 217   /* When we already have some bits in our internal buffer concatenate
 218      both inputs first.  */
 219   if (ctx->buflen != 0)
 220     {
 221       size_t left_over = ctx->buflen;
 222       size_t add = 128 - left_over > len ? len : 128 - left_over;
 223
 224       memcpy (&ctx->buffer[left_over], buffer, add);
 225       ctx->buflen += add;
 226
 227       if (ctx->buflen > 64)
 228         {
 229           md5_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 230
 231           ctx->buflen &= 63;
 232           /* The regions in the following copy operation cannot overlap.  */
 233           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 234                   ctx->buflen);
 235         }
 236
 237       buffer = (const char *) buffer + add;
 238       len -= add;
 239     }
 240
 241   /* Process available complete blocks.  */
 242   if (len >= 64)
 243     {
 244 #if !_STRING_ARCH_unaligned
 245 /* To check alignment gcc has an appropriate operator.  Other
 246    compilers don't.  */
 247 # if __GNUC__ >= 2
 248 #  define UNALIGNED_P(p) (((md5_uintptr) p) % __alignof__ (md5_uint32) != 0)
 249 # else
 250 #  define UNALIGNED_P(p) (((md5_uintptr) p) % sizeof (md5_uint32) != 0)
 251 # endif
 252       if (UNALIGNED_P (buffer))
 253         while (len > 64)
 254           {
 255             md5_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 256             buffer = (const char *) buffer + 64;
 257             len -= 64;
 258           }
 259       else
 260 #endif
 261         {
 262           md5_process_block (buffer, len & ~63, ctx);
 263           buffer = (const char *) buffer + (len & ~63);
 264           len &= 63;
 265         }
 266     }
 267
 268   /* Move remaining bytes in internal buffer.  */
 269   if (len > 0)
 270     {
 271       size_t left_over = ctx->buflen;
 272
 273       memcpy (&ctx->buffer[left_over], buffer, len);
 274       left_over += len;
 275       if (left_over >= 64)
 276         {
 277           md5_process_block (ctx->buffer, 64, ctx);
 278           left_over -= 64;
 279           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 280         }
 281       ctx->buflen = left_over;
 282     }
 283 }
 284
 285
 286 /* These are the four functions used in the four steps of the MD5 algorithm
 287    and defined in the RFC 1321.  The first function is a little bit optimized
 288    (as found in Colin Plumbs public domain implementation).  */
 289 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
 290 #define FF(b, c, d) (d ^ (b & (c ^ d)))
 291 #define FG(b, c, d) FF (d, b, c)
 292 #define FH(b, c, d) (b ^ c ^ d)
 293 #define FI(b, c, d) (c ^ (b | ~d))
 294
 295 /* Process LEN bytes of BUFFER, accumulating context into CTX.
 296    It is assumed that LEN % 64 == 0.  */
 297
 298 void
 299 md5_process_block (buffer, len, ctx)
 300      const void *buffer;
 301      size_t len;
 302      struct md5_ctx *ctx;
 303 {
 304   md5_uint32 correct_words[16];
 305   const md5_uint32 *words = buffer;
 306   size_t nwords = len / sizeof (md5_uint32);
 307   const md5_uint32 *endp = words + nwords;
 308   md5_uint32 A = ctx->A;
 309   md5_uint32 B = ctx->B;
 310   md5_uint32 C = ctx->C;
 311   md5_uint32 D = ctx->D;
 312
 313   /* First increment the byte count.  RFC 1321 specifies the possible
 314      length of the file up to 2^64 bits.  Here we only compute the
 315      number of bytes.  Do a double word increment.  */
 316   ctx->total[0] += len;
 317   if (ctx->total[0] < len)
 318     ++ctx->total[1];
 319
 320   /* Process all bytes in the buffer with 64 bytes in each round of
 321      the loop.  */
 322   while (words < endp)
 323     {
 324       md5_uint32 *cwp = correct_words;
 325       md5_uint32 A_save = A;
 326       md5_uint32 B_save = B;
 327       md5_uint32 C_save = C;
 328       md5_uint32 D_save = D;
 329
 330       /* First round: using the given function, the context and a constant
 331          the next context is computed.  Because the algorithms processing
 332          unit is a 32-bit word and it is determined to work on words in
 333          little endian byte order we perhaps have to change the byte order
 334          before the computation.  To reduce the work for the next steps
 335          we store the swapped words in the array CORRECT_WORDS.  */
 336
 337 #define OP(a, b, c, d, s, T)                                            \
 338       do                                                                \
 339         {                                                               \
 340           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;             \
 341           ++words;                                                      \
 342           CYCLIC (a, s);                                                \
 343           a += b;                                                       \
 344         }                                                               \
 345       while (0)
 346
 347       /* It is unfortunate that C does not provide an operator for
 348          cyclic rotation.  Hope the C compiler is smart enough.  */
 349 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
 350
 351       /* Before we start, one word to the strange constants.
 352          They are defined in RFC 1321 as
 353
 354          T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
 355        */
 356
 357       /* Round 1.  */
 358       OP (A, B, C, D,  7, 0xd76aa478);
 359       OP (D, A, B, C, 12, 0xe8c7b756);
 360       OP (C, D, A, B, 17, 0x242070db);
 361       OP (B, C, D, A, 22, 0xc1bdceee);
 362       OP (A, B, C, D,  7, 0xf57c0faf);
 363       OP (D, A, B, C, 12, 0x4787c62a);
 364       OP (C, D, A, B, 17, 0xa8304613);
 365       OP (B, C, D, A, 22, 0xfd469501);
 366       OP (A, B, C, D,  7, 0x698098d8);
 367       OP (D, A, B, C, 12, 0x8b44f7af);
 368       OP (C, D, A, B, 17, 0xffff5bb1);
 369       OP (B, C, D, A, 22, 0x895cd7be);
 370       OP (A, B, C, D,  7, 0x6b901122);
 371       OP (D, A, B, C, 12, 0xfd987193);
 372       OP (C, D, A, B, 17, 0xa679438e);
 373       OP (B, C, D, A, 22, 0x49b40821);
 374
 375       /* For the second to fourth round we have the possibly swapped words
 376          in CORRECT_WORDS.  Redefine the macro to take an additional first
 377          argument specifying the function to use.  */
 378 #undef OP
 379 #define OP(f, a, b, c, d, k, s, T)                                      \
 380       do                                                                \
 381         {                                                               \
 382           a += f (b, c, d) + correct_words[k] + T;                      \
 383           CYCLIC (a, s);                                                \
 384           a += b;                                                       \
 385         }                                                               \
 386       while (0)
 387
 388       /* Round 2.  */
 389       OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
 390       OP (FG, D, A, B, C,  6,  9, 0xc040b340);
 391       OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
 392       OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
 393       OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
 394       OP (FG, D, A, B, C, 10,  9, 0x02441453);
 395       OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
 396       OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
 397       OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
 398       OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
 399       OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
 400       OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
 401       OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
 402       OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
 403       OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
 404       OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
 405
 406       /* Round 3.  */
 407       OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
 408       OP (FH, D, A, B, C,  8, 11, 0x8771f681);
 409       OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
 410       OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
 411       OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
 412       OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
 413       OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
 414       OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
 415       OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
 416       OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
 417       OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
 418       OP (FH, B, C, D, A,  6, 23, 0x04881d05);
 419       OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
 420       OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
 421       OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
 422       OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
 423
 424       /* Round 4.  */
 425       OP (FI, A, B, C, D,  0,  6, 0xf4292244);
 426       OP (FI, D, A, B, C,  7, 10, 0x432aff97);
 427       OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
 428       OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
 429       OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
 430       OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
 431       OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
 432       OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
 433       OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
 434       OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
 435       OP (FI, C, D, A, B,  6, 15, 0xa3014314);
 436       OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
 437       OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
 438       OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
 439       OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
 440       OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
 441
 442       /* Add the starting values of the context.  */
 443       A += A_save;
 444       B += B_save;
 445       C += C_save;
 446       D += D_save;
 447     }
 448
 449   /* Put checksum in context given as argument.  */
 450   ctx->A = A;
 451   ctx->B = B;
 452   ctx->C = C;
 453   ctx->D = D;
 454 }