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,1996,1997,1999,2000,2001 Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, write to the Free
  18    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  19    02111-1307 USA.  */
  20
  21 /* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
  22
  23 #include "build-config.h"
  24
  25 #include <sys/types.h>
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include "md5.h"
  31
  32 #ifdef WORDS_BIGENDIAN
  33 # define SWAP(n)                                                        \
  34     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
  35 #else
  36 # define SWAP(n) (n)
  37 #endif
  38
  39
  40 /* This array contains the bytes used to pad the buffer to the next
  41    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
  42 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
  43
  44 /* These are the four functions used in the four steps of the MD5 algorithm
  45    and defined in the RFC 1321.  The first function is a little bit optimized
  46    (as found in Colin Plumbs public domain implementation).  */
  47 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
  48 #define FF(b, c, d) (d ^ (b & (c ^ d)))
  49 #define FG(b, c, d) FF (d, b, c)
  50 #define FH(b, c, d) (b ^ c ^ d)
  51 #define FI(b, c, d) (c ^ (b | ~d))
  52
  53 /* Process LEN bytes of BUFFER, accumulating context into CTX.
  54    It is assumed that LEN % 64 == 0.  */
  55
  56 void
  57 md5_process_block(const void *buffer, size_t len, struct md5_ctx *ctx)
  58 {
  59   uint32_t correct_words[16];
  60   const uint32_t *words = buffer;
  61   size_t nwords = len / sizeof (uint32_t);
  62   const uint32_t *endp = words + nwords;
  63   uint32_t A = ctx->A;
  64   uint32_t B = ctx->B;
  65   uint32_t C = ctx->C;
  66   uint32_t D = ctx->D;
  67
  68   /* First increment the byte count.  RFC 1321 specifies the possible
  69      length of the file up to 2^64 bits.  Here we only compute the
  70      number of bytes.  Do a double word increment.  */
  71   ctx->total[0] += len;
  72   if (ctx->total[0] < len)
  73     ++ctx->total[1];
  74
  75   /* Process all bytes in the buffer with 64 bytes in each round of
  76      the loop.  */
  77   while (words < endp)
  78     {
  79       uint32_t *cwp = correct_words;
  80       uint32_t A_save = A;
  81       uint32_t B_save = B;
  82       uint32_t C_save = C;
  83       uint32_t D_save = D;
  84
  85       /* First round: using the given function, the context and a constant
  86          the next context is computed.  Because the algorithms processing
  87          unit is a 32-bit word and it is determined to work on words in
  88          little endian byte order we perhaps have to change the byte order
  89          before the computation.  To reduce the work for the next steps
  90          we store the swapped words in the array CORRECT_WORDS.  */
  91
  92 #define OP(a, b, c, d, s, T)                                            \
  93       do                                                                \
  94         {                                                               \
  95           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;             \
  96           ++words;                                                      \
  97           CYCLIC (a, s);                                                \
  98           a += b;                                                       \
  99         }                                                               \
 100       while (0)
 101
 102       /* It is unfortunate that C does not provide an operator for
 103          cyclic rotation.  Hope the C compiler is smart enough.  */
 104 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
 105
 106       /* Before we start, one word to the strange constants.
 107          They are defined in RFC 1321 as
 108
 109          T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
 110        */
 111
 112       /* Round 1.  */
 113       OP (A, B, C, D,  7, 0xd76aa478);
 114       OP (D, A, B, C, 12, 0xe8c7b756);
 115       OP (C, D, A, B, 17, 0x242070db);
 116       OP (B, C, D, A, 22, 0xc1bdceee);
 117       OP (A, B, C, D,  7, 0xf57c0faf);
 118       OP (D, A, B, C, 12, 0x4787c62a);
 119       OP (C, D, A, B, 17, 0xa8304613);
 120       OP (B, C, D, A, 22, 0xfd469501);
 121       OP (A, B, C, D,  7, 0x698098d8);
 122       OP (D, A, B, C, 12, 0x8b44f7af);
 123       OP (C, D, A, B, 17, 0xffff5bb1);
 124       OP (B, C, D, A, 22, 0x895cd7be);
 125       OP (A, B, C, D,  7, 0x6b901122);
 126       OP (D, A, B, C, 12, 0xfd987193);
 127       OP (C, D, A, B, 17, 0xa679438e);
 128       OP (B, C, D, A, 22, 0x49b40821);
 129
 130       /* For the second to fourth round we have the possibly swapped words
 131          in CORRECT_WORDS.  Redefine the macro to take an additional first
 132          argument specifying the function to use.  */
 133 #undef OP
 134 #define OP(f, a, b, c, d, k, s, T)                                      \
 135       do                                                                \
 136         {                                                               \
 137           a += f (b, c, d) + correct_words[k] + T;                      \
 138           CYCLIC (a, s);                                                \
 139           a += b;                                                       \
 140         }                                                               \
 141       while (0)
 142
 143       /* Round 2.  */
 144       OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
 145       OP (FG, D, A, B, C,  6,  9, 0xc040b340);
 146       OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
 147       OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
 148       OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
 149       OP (FG, D, A, B, C, 10,  9, 0x02441453);
 150       OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
 151       OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
 152       OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
 153       OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
 154       OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
 155       OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
 156       OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
 157       OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
 158       OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
 159       OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
 160
 161       /* Round 3.  */
 162       OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
 163       OP (FH, D, A, B, C,  8, 11, 0x8771f681);
 164       OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
 165       OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
 166       OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
 167       OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
 168       OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
 169       OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
 170       OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
 171       OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
 172       OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
 173       OP (FH, B, C, D, A,  6, 23, 0x04881d05);
 174       OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
 175       OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
 176       OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
 177       OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
 178
 179       /* Round 4.  */
 180       OP (FI, A, B, C, D,  0,  6, 0xf4292244);
 181       OP (FI, D, A, B, C,  7, 10, 0x432aff97);
 182       OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
 183       OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
 184       OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
 185       OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
 186       OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
 187       OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
 188       OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
 189       OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
 190       OP (FI, C, D, A, B,  6, 15, 0xa3014314);
 191       OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
 192       OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
 193       OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
 194       OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
 195       OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
 196
 197       /* Add the starting values of the context.  */
 198       A += A_save;
 199       B += B_save;
 200       C += C_save;
 201       D += D_save;
 202     }
 203
 204   /* Put checksum in context given as argument.  */
 205   ctx->A = A;
 206   ctx->B = B;
 207   ctx->C = C;
 208   ctx->D = D;
 209 }
 210
 211 /* Initialize structure containing state of computation.
 212    (RFC 1321, 3.3: Step 3)  */
 213 void
 214 md5_init(struct md5_ctx *ctx)
 215 {
 216   ctx->A = 0x67452301;
 217   ctx->B = 0xefcdab89;
 218   ctx->C = 0x98badcfe;
 219   ctx->D = 0x10325476;
 220
 221   ctx->total[0] = ctx->total[1] = 0;
 222   ctx->buflen = 0;
 223 }
 224
 225 /* Put result from CTX in first 16 bytes following RESBUF.  The result
 226    must be in little endian byte order.
 227
 228    IMPORTANT: On some systems it is required that RESBUF is correctly
 229    aligned for a 32 bits value.  */
 230 void
 231 md5_read_ctx(const struct md5_ctx *ctx, void *resbuf)
 232 {
 233   ((uint32_t *) resbuf)[0] = SWAP (ctx->A);
 234   ((uint32_t *) resbuf)[1] = SWAP (ctx->B);
 235   ((uint32_t *) resbuf)[2] = SWAP (ctx->C);
 236   ((uint32_t *) resbuf)[3] = SWAP (ctx->D);
 237 }
 238
 239 /* Process the remaining bytes in the internal buffer and the usual
 240    prolog according to the standard and write the result to RESBUF.
 241
 242    IMPORTANT: On some systems it is required that RESBUF is correctly
 243    aligned for a 32 bits value.  */
 244 void
 245 md5_digest(struct md5_ctx *ctx, unsigned length, uint8_t *resbuf)
 246 {
 247   /* Take yet unprocessed bytes into account.  */
 248   uint32_t bytes = ctx->buflen;
 249   size_t pad;
 250
 251   /* Now count remaining bytes.  */
 252   ctx->total[0] += bytes;
 253   if (ctx->total[0] < bytes)
 254     ++ctx->total[1];
 255
 256   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
 257   memcpy (&ctx->buffer[bytes], fillbuf, pad);
 258
 259   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 260   *(uint32_t *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
 261   *(uint32_t *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
 262                                                         (ctx->total[0] >> 29));
 263
 264   /* Process last bytes.  */
 265   md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
 266
 267   md5_read_ctx(ctx, resbuf);
 268
 269   return;
 270 }
 271
 272 void
 273 md5_update(struct md5_ctx *ctx, unsigned length,
 274                         const uint8_t *buffer)
 275 {
 276   /* When we already have some bits in our internal buffer concatenate
 277      both inputs first.  */
 278   if (ctx->buflen != 0)
 279     {
 280       size_t left_over = ctx->buflen;
 281       size_t add = 128 - left_over > length ? length : 128 - left_over;
 282
 283       memcpy (&ctx->buffer[left_over], buffer, add);
 284       ctx->buflen += add;
 285
 286       if (ctx->buflen > 64)
 287         {
 288           md5_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
 289
 290           ctx->buflen &= 63;
 291           /* The regions in the following copy operation cannot overlap.  */
 292           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
 293                   ctx->buflen);
 294         }
 295
 296       buffer = (const uint8_t *) buffer + add;
 297       length -= add;
 298     }
 299
 300   /* Process available complete blocks.  */
 301   if (length >= 64)
 302     {
 303 #if !_STRING_ARCH_unaligned
 304 /* To check alignment gcc has an appropriate operator.  Other
 305    compilers don't.  */
 306 # if __GNUC__ >= 2
 307 #  define UNALIGNED_P(p) (((md5_uintptr) p) % __alignof__ (uint32_t) != 0)
 308 # else
 309 #  define UNALIGNED_P(p) (((md5_uintptr) p) % sizeof (uint32_t) != 0)
 310 # endif
 311       if (UNALIGNED_P (buffer))
 312         while (length > 64)
 313           {
 314             md5_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
 315             buffer = (const uint8_t *) buffer + 64;
 316             length -= 64;
 317           }
 318       else
 319 #endif
 320         {
 321           md5_process_block (buffer, length & ~63, ctx);
 322           buffer = (const uint8_t *) buffer + (length & ~63);
 323           length &= 63;
 324         }
 325     }
 326
 327   /* Move remaining bytes in internal buffer.  */
 328   if (length > 0)
 329     {
 330       size_t left_over = ctx->buflen;
 331
 332       memcpy (&ctx->buffer[left_over], buffer, length);
 333       left_over += length;
 334       if (left_over >= 64)
 335         {
 336           md5_process_block (ctx->buffer, 64, ctx);
 337           left_over -= 64;
 338           memcpy (ctx->buffer, &ctx->buffer[64], left_over);
 339         }
 340       ctx->buflen = left_over;
 341     }
 342 }