md5.c

Go to the documentation of this file.
00001 /* md5.c - Functions to compute MD5 message digest of files or memory blocks
00002    according to the definition of MD5 in RFC 1321 from April 1992.
00003    Copyright (C) 1995, 1996 Free Software Foundation, Inc.
00004    NOTE: The canonical source of this file is maintained with the GNU C
00005    Library.  Bugs can be reported to bug-glibc@prep.ai.mit.edu.
00006 
00007    This program is free software; you can redistribute it and/or modify it
00008    under the terms of the GNU General Public License as published by the
00009    Free Software Foundation; either version 2, or (at your option) any
00010    later version.
00011 
00012    This program is distributed in the hope that it will be useful,
00013    but WITHOUT ANY WARRANTY; without even the implied warranty of
00014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015    GNU General Public License for more details.
00016 
00017    You should have received a copy of the GNU General Public License
00018    along with this program; if not, write to the Free Software Foundation,
00019    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
00020 
00021 /* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
00022 
00023 #include <config.h>
00024 
00025 #include <stdlib.h>
00026 
00027 #ifdef HAVE_STRING_H
00028 #include <string.h>
00029 #endif
00030 
00031 #ifdef HAVE_SYS_TYPES_H
00032 #include <sys/types.h>
00033 #endif
00034 
00035 #include "md5.h"
00036 
00037 
00038 #ifdef WORDS_BIGENDIAN
00039 # define SWAP(n)                            \
00040     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
00041 #else
00042 # define SWAP(n) (n)
00043 #endif
00044 
00045 
00046 /* This array contains the bytes used to pad the buffer to the next
00047    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
00048 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
00049 
00050 
00051 /* Initialize structure containing state of computation.
00052    (RFC 1321, 3.3: Step 3)  */
00053 void
00054 md5_init_ctx (ctx)
00055      struct md5_ctx *ctx;
00056 {
00057   ctx->A = 0x67452301;
00058   ctx->B = 0xefcdab89;
00059   ctx->C = 0x98badcfe;
00060   ctx->D = 0x10325476;
00061 
00062   ctx->total[0] = ctx->total[1] = 0;
00063   ctx->buflen = 0;
00064 }
00065 
00066 /* Put result from CTX in first 16 bytes following RESBUF.  The result
00067    must be in little endian byte order.
00068 
00069    IMPORTANT: On some systems it is required that RESBUF is correctly
00070    aligned for a 32 bits value.  */
00071 void *
00072 md5_read_ctx (ctx, resbuf)
00073      const struct md5_ctx *ctx;
00074      void *resbuf;
00075 {
00076   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
00077   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
00078   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
00079   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
00080 
00081   return resbuf;
00082 }
00083 
00084 /* Process the remaining bytes in the internal buffer and the usual
00085    prolog according to the standard and write the result to RESBUF.
00086 
00087    IMPORTANT: On some systems it is required that RESBUF is correctly
00088    aligned for a 32 bits value.  */
00089 void *
00090 md5_finish_ctx (ctx, resbuf)
00091      struct md5_ctx *ctx;
00092      void *resbuf;
00093 {
00094   /* Take yet unprocessed bytes into account.  */
00095   md5_uint32 bytes = ctx->buflen;
00096   size_t pad;
00097 
00098   /* Now count remaining bytes.  */
00099   ctx->total[0] += bytes;
00100   if (ctx->total[0] < bytes)
00101     ++ctx->total[1];
00102 
00103   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
00104   memcpy (&ctx->buffer[bytes], fillbuf, pad);
00105 
00106   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
00107   *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
00108   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
00109                             (ctx->total[0] >> 29));
00110 
00111   /* Process last bytes.  */
00112   md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
00113 
00114   return md5_read_ctx (ctx, resbuf);
00115 }
00116 
00117 /* Compute MD5 message digest for bytes read from STREAM.  The
00118    resulting message digest number will be written into the 16 bytes
00119    beginning at RESBLOCK.  */
00120 int
00121 md5_stream (stream, resblock)
00122      FILE *stream;
00123      void *resblock;
00124 {
00125   /* Important: BLOCKSIZE must be a multiple of 64.  */
00126 #define BLOCKSIZE 4096
00127   struct md5_ctx ctx;
00128   char buffer[BLOCKSIZE + 72];
00129   size_t sum;
00130 
00131   /* Initialize the computation context.  */
00132   md5_init_ctx (&ctx);
00133 
00134   /* Iterate over full file contents.  */
00135   while (1)
00136     {
00137       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
00138      computation function processes the whole buffer so that with the
00139      next round of the loop another block can be read.  */
00140       size_t n;
00141       sum = 0;
00142 
00143       /* Read block.  Take care for partial reads.  */
00144       do
00145     {
00146       n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
00147 
00148       sum += n;
00149     }
00150       while (sum < BLOCKSIZE && n != 0);
00151       if (n == 0 && ferror (stream))
00152         return 1;
00153 
00154       /* If end of file is reached, end the loop.  */
00155       if (n == 0)
00156     break;
00157 
00158       /* Process buffer with BLOCKSIZE bytes.  Note that
00159             BLOCKSIZE % 64 == 0
00160        */
00161       md5_process_block (buffer, BLOCKSIZE, &ctx);
00162     }
00163 
00164   /* Add the last bytes if necessary.  */
00165   if (sum > 0)
00166     md5_process_bytes (buffer, sum, &ctx);
00167 
00168   /* Construct result in desired memory.  */
00169   md5_finish_ctx (&ctx, resblock);
00170   return 0;
00171 }
00172 
00173 /* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
00174    result is always in little endian byte order, so that a byte-wise
00175    output yields to the wanted ASCII representation of the message
00176    digest.  */
00177 void *
00178 md5_buffer (buffer, len, resblock)
00179      const char *buffer;
00180      size_t len;
00181      void *resblock;
00182 {
00183   struct md5_ctx ctx;
00184 
00185   /* Initialize the computation context.  */
00186   md5_init_ctx (&ctx);
00187 
00188   /* Process whole buffer but last len % 64 bytes.  */
00189   md5_process_bytes (buffer, len, &ctx);
00190 
00191   /* Put result in desired memory area.  */
00192   return md5_finish_ctx (&ctx, resblock);
00193 }
00194 
00195 
00196 void
00197 md5_process_bytes (buffer, len, ctx)
00198      const void *buffer;
00199      size_t len;
00200      struct md5_ctx *ctx;
00201 {
00202   /* When we already have some bits in our internal buffer concatenate
00203      both inputs first.  */
00204   if (ctx->buflen != 0)
00205     {
00206       size_t left_over = ctx->buflen;
00207       size_t add = 128 - left_over > len ? len : 128 - left_over;
00208 
00209       memcpy (&ctx->buffer[left_over], buffer, add);
00210       ctx->buflen += add;
00211 
00212       if (left_over + add > 64)
00213     {
00214       md5_process_block (ctx->buffer, (left_over + add) & ~63, ctx);
00215       /* The regions in the following copy operation cannot overlap.  */
00216       memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
00217           (left_over + add) & 63);
00218       ctx->buflen = (left_over + add) & 63;
00219     }
00220 
00221       buffer = (const char *) buffer + add;
00222       len -= add;
00223     }
00224 
00225   /* Process available complete blocks.  */
00226   if (len > 64)
00227     {
00228       md5_process_block (buffer, len & ~63, ctx);
00229       buffer = (const char *) buffer + (len & ~63);
00230       len &= 63;
00231     }
00232 
00233   /* Move remaining bytes in internal buffer.  */
00234   if (len > 0)
00235     {
00236       memcpy (ctx->buffer, buffer, len);
00237       ctx->buflen = len;
00238     }
00239 }
00240 
00241 
00242 /* These are the four functions used in the four steps of the MD5 algorithm
00243    and defined in the RFC 1321.  The first function is a little bit optimized
00244    (as found in Colin Plumbs public domain implementation).  */
00245 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
00246 #define FF(b, c, d) (d ^ (b & (c ^ d)))
00247 #define FG(b, c, d) FF (d, b, c)
00248 #define FH(b, c, d) (b ^ c ^ d)
00249 #define FI(b, c, d) (c ^ (b | ~d))
00250 
00251 /* Process LEN bytes of BUFFER, accumulating context into CTX.
00252    It is assumed that LEN % 64 == 0.  */
00253 
00254 void
00255 md5_process_block (buffer, len, ctx)
00256      const void *buffer;
00257      size_t len;
00258      struct md5_ctx *ctx;
00259 {
00260   md5_uint32 correct_words[16];
00261   const md5_uint32 *words = buffer;
00262   size_t nwords = len / sizeof (md5_uint32);
00263   const md5_uint32 *endp = words + nwords;
00264   md5_uint32 A = ctx->A;
00265   md5_uint32 B = ctx->B;
00266   md5_uint32 C = ctx->C;
00267   md5_uint32 D = ctx->D;
00268 
00269   /* First increment the byte count.  RFC 1321 specifies the possible
00270      length of the file up to 2^64 bits.  Here we only compute the
00271      number of bytes.  Do a double word increment.  */
00272   ctx->total[0] += len;
00273   if (ctx->total[0] < len)
00274     ++ctx->total[1];
00275 
00276   /* Process all bytes in the buffer with 64 bytes in each round of
00277      the loop.  */
00278   while (words < endp)
00279     {
00280       md5_uint32 *cwp = correct_words;
00281       md5_uint32 A_save = A;
00282       md5_uint32 B_save = B;
00283       md5_uint32 C_save = C;
00284       md5_uint32 D_save = D;
00285 
00286       /* First round: using the given function, the context and a constant
00287      the next context is computed.  Because the algorithms processing
00288      unit is a 32-bit word and it is determined to work on words in
00289      little endian byte order we perhaps have to change the byte order
00290      before the computation.  To reduce the work for the next steps
00291      we store the swapped words in the array CORRECT_WORDS.  */
00292 
00293 #define OP(a, b, c, d, s, T)                        \
00294       do                                \
00295         {                               \
00296       a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;     \
00297       ++words;                          \
00298       CYCLIC (a, s);                        \
00299       a += b;                           \
00300         }                               \
00301       while (0)
00302 
00303       /* It is unfortunate that C does not provide an operator for
00304      cyclic rotation.  Hope the C compiler is smart enough.  */
00305 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
00306 
00307       /* Before we start, one word to the strange constants.
00308      They are defined in RFC 1321 as
00309 
00310      T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
00311        */
00312 
00313       /* Round 1.  */
00314       OP (A, B, C, D,  7, 0xd76aa478);
00315       OP (D, A, B, C, 12, 0xe8c7b756);
00316       OP (C, D, A, B, 17, 0x242070db);
00317       OP (B, C, D, A, 22, 0xc1bdceee);
00318       OP (A, B, C, D,  7, 0xf57c0faf);
00319       OP (D, A, B, C, 12, 0x4787c62a);
00320       OP (C, D, A, B, 17, 0xa8304613);
00321       OP (B, C, D, A, 22, 0xfd469501);
00322       OP (A, B, C, D,  7, 0x698098d8);
00323       OP (D, A, B, C, 12, 0x8b44f7af);
00324       OP (C, D, A, B, 17, 0xffff5bb1);
00325       OP (B, C, D, A, 22, 0x895cd7be);
00326       OP (A, B, C, D,  7, 0x6b901122);
00327       OP (D, A, B, C, 12, 0xfd987193);
00328       OP (C, D, A, B, 17, 0xa679438e);
00329       OP (B, C, D, A, 22, 0x49b40821);
00330 
00331       /* For the second to fourth round we have the possibly swapped words
00332      in CORRECT_WORDS.  Redefine the macro to take an additional first
00333      argument specifying the function to use.  */
00334 #undef OP
00335 #define OP(f, a, b, c, d, k, s, T)                  \
00336       do                                \
00337     {                               \
00338       a += f (b, c, d) + correct_words[k] + T;          \
00339       CYCLIC (a, s);                        \
00340       a += b;                           \
00341     }                               \
00342       while (0)
00343 
00344       /* Round 2.  */
00345       OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
00346       OP (FG, D, A, B, C,  6,  9, 0xc040b340);
00347       OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
00348       OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
00349       OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
00350       OP (FG, D, A, B, C, 10,  9, 0x02441453);
00351       OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
00352       OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
00353       OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
00354       OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
00355       OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
00356       OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
00357       OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
00358       OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
00359       OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
00360       OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
00361 
00362       /* Round 3.  */
00363       OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
00364       OP (FH, D, A, B, C,  8, 11, 0x8771f681);
00365       OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
00366       OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
00367       OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
00368       OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
00369       OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
00370       OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
00371       OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
00372       OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
00373       OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
00374       OP (FH, B, C, D, A,  6, 23, 0x04881d05);
00375       OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
00376       OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
00377       OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
00378       OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
00379 
00380       /* Round 4.  */
00381       OP (FI, A, B, C, D,  0,  6, 0xf4292244);
00382       OP (FI, D, A, B, C,  7, 10, 0x432aff97);
00383       OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
00384       OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
00385       OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
00386       OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
00387       OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
00388       OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
00389       OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
00390       OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
00391       OP (FI, C, D, A, B,  6, 15, 0xa3014314);
00392       OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
00393       OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
00394       OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
00395       OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
00396       OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
00397 
00398       /* Add the starting values of the context.  */
00399       A += A_save;
00400       B += B_save;
00401       C += C_save;
00402       D += D_save;
00403     }
00404 
00405   /* Put checksum in context given as argument.  */
00406   ctx->A = A;
00407   ctx->B = B;
00408   ctx->C = C;
00409   ctx->D = D;
00410 }