lib/md5.c

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