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