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