See ChangeLog: Wed Feb 10 17:15:39 CET 1999 Werner Koch
[libgcrypt.git] / cipher / md5.c
1 /* md5.c - MD5 Message-Digest Algorithm
2  *      Copyright (C) 1995, 1996, 1998 Free Software Foundation, Inc.
3  *
4  * according to the definition of MD5 in RFC 1321 from April 1992.
5  * NOTE: This is *not* the same file as the one from glibc.
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 /* modified for GnuPG by <werner.koch@guug.de> */
23
24 /* Test values:
25  * ""                  D4 1D 8C D9 8F 00 B2 04  E9 80 09 98 EC F8 42 7E
26  * "a"                 0C C1 75 B9 C0 F1 B6 A8  31 C3 99 E2 69 77 26 61
27  * "abc                90 01 50 98 3C D2 4F B0  D6 96 3F 7D 28 E1 7F 72
28  * "message digest"    F9 6B 69 7D 7C B7 93 8D  52 5A 2F 31 AA F1 61 D0
29  */
30
31 #include <config.h>
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <assert.h>
36 #include "util.h"
37 #include "memory.h"
38 #include "dynload.h"
39
40
41 typedef struct {
42     u32 A,B,C,D;          /* chaining variables */
43     u32 total[2];
44     u32  buflen;
45     char buffer[128];
46 } MD5_CONTEXT;
47
48
49
50 #ifdef BIG_ENDIAN_HOST
51   #define SWAP(n) \
52     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
53 #else
54   #define SWAP(n) (n)
55 #endif
56
57 /* This array contains the bytes used to pad the buffer to the next
58    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
59 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
60
61 static void
62 md5_init( MD5_CONTEXT *ctx )
63 {
64     ctx->A = 0x67452301;
65     ctx->B = 0xefcdab89;
66     ctx->C = 0x98badcfe;
67     ctx->D = 0x10325476;
68
69     ctx->total[0] = ctx->total[1] = 0;
70     ctx->buflen = 0;
71 }
72
73
74
75
76 /* These are the four functions used in the four steps of the MD5 algorithm
77    and defined in the RFC 1321.  The first function is a little bit optimized
78    (as found in Colin Plumbs public domain implementation).  */
79 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
80 #define FF(b, c, d) (d ^ (b & (c ^ d)))
81 #define FG(b, c, d) FF (d, b, c)
82 #define FH(b, c, d) (b ^ c ^ d)
83 #define FI(b, c, d) (c ^ (b | ~d))
84
85
86 /****************
87  * transform n*64 bytes
88  */
89 static void
90 transform( MD5_CONTEXT *ctx, const void *buffer, size_t len )
91 {
92     u32 correct_words[16];
93     const u32 *words = buffer;
94     size_t nwords = len / sizeof(u32);
95     const u32 *endp = words + nwords;
96     u32 A = ctx->A;
97     u32 B = ctx->B;
98     u32 C = ctx->C;
99     u32 D = ctx->D;
100
101     /* First increment the byte count.  RFC 1321 specifies the possible
102        length of the file up to 2^64 bits.  Here we only compute the
103        number of bytes.  Do a double word increment.  */
104     ctx->total[0] += len;
105     if( ctx->total[0] < len )
106         ++ctx->total[1];
107
108
109     /* Process all bytes in the buffer with 64 bytes in each round of
110        the loop.  */
111     while(words < endp) {
112         u32 *cwp = correct_words;
113         u32 A_save = A;
114         u32 B_save = B;
115         u32 C_save = C;
116         u32 D_save = D;
117
118       /* First round: using the given function, the context and a constant
119          the next context is computed.  Because the algorithm's processing
120          unit is a 32-bit word, and it is determined to work on words in
121          little endian byte order, we perhaps have to change the byte order
122          before the computation.  To reduce the work for the next steps
123          we store the swapped words in the array CORRECT_WORDS.  */
124
125 #define OP(a, b, c, d, s, T)                                            \
126       do                                                                \
127         {                                                               \
128           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;             \
129           ++words;                                                      \
130           CYCLIC (a, s);                                                \
131           a += b;                                                       \
132         }                                                               \
133       while (0)
134
135       /* It is unfortunate that C does not provide an operator for
136          cyclic rotation.  Hope the C compiler is smart enough.  */
137 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
138
139         /* Before we start, one word about the strange constants.
140            They are defined in RFC 1321 as
141
142            T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
143          */
144
145         /* Round 1.  */
146         OP (A, B, C, D,  7, 0xd76aa478);
147         OP (D, A, B, C, 12, 0xe8c7b756);
148         OP (C, D, A, B, 17, 0x242070db);
149         OP (B, C, D, A, 22, 0xc1bdceee);
150         OP (A, B, C, D,  7, 0xf57c0faf);
151         OP (D, A, B, C, 12, 0x4787c62a);
152         OP (C, D, A, B, 17, 0xa8304613);
153         OP (B, C, D, A, 22, 0xfd469501);
154         OP (A, B, C, D,  7, 0x698098d8);
155         OP (D, A, B, C, 12, 0x8b44f7af);
156         OP (C, D, A, B, 17, 0xffff5bb1);
157         OP (B, C, D, A, 22, 0x895cd7be);
158         OP (A, B, C, D,  7, 0x6b901122);
159         OP (D, A, B, C, 12, 0xfd987193);
160         OP (C, D, A, B, 17, 0xa679438e);
161         OP (B, C, D, A, 22, 0x49b40821);
162
163         /* For the second to fourth round we have the possibly swapped words
164            in CORRECT_WORDS.  Redefine the macro to take an additional first
165            argument specifying the function to use.  */
166 #undef OP
167 #define OP(f, a, b, c, d, k, s, T)  \
168         do                                                                \
169           {                                                               \
170             a += f (b, c, d) + correct_words[k] + T;                      \
171             CYCLIC (a, s);                                                \
172             a += b;                                                       \
173           }                                                               \
174         while (0)
175
176         /* Round 2.  */
177         OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
178         OP (FG, D, A, B, C,  6,  9, 0xc040b340);
179         OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
180         OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
181         OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
182         OP (FG, D, A, B, C, 10,  9, 0x02441453);
183         OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
184         OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
185         OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
186         OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
187         OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
188         OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
189         OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
190         OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
191         OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
192         OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
193
194         /* Round 3.  */
195         OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
196         OP (FH, D, A, B, C,  8, 11, 0x8771f681);
197         OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
198         OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
199         OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
200         OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
201         OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
202         OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
203         OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
204         OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
205         OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
206         OP (FH, B, C, D, A,  6, 23, 0x04881d05);
207         OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
208         OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
209         OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
210         OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
211
212         /* Round 4.  */
213         OP (FI, A, B, C, D,  0,  6, 0xf4292244);
214         OP (FI, D, A, B, C,  7, 10, 0x432aff97);
215         OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
216         OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
217         OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
218         OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
219         OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
220         OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
221         OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
222         OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
223         OP (FI, C, D, A, B,  6, 15, 0xa3014314);
224         OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
225         OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
226         OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
227         OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
228         OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
229         /* Add the starting values of the context.  */
230         A += A_save;
231         B += B_save;
232         C += C_save;
233         D += D_save;
234     }
235
236     /* Put checksum in context given as argument.  */
237     ctx->A = A;
238     ctx->B = B;
239     ctx->C = C;
240     ctx->D = D;
241 }
242
243
244
245 /* The routine updates the message-digest context to
246  * account for the presence of each of the characters inBuf[0..inLen-1]
247  * in the message whose digest is being computed.
248  */
249 static void
250 md5_write( MD5_CONTEXT *ctx, const void *buffer, size_t len)
251 {
252     /* When we already have some bits in our internal buffer concatenate
253        both inputs first.  */
254     if (ctx->buflen != 0)
255       {
256         size_t left_over = ctx->buflen;
257         size_t add = 128 - left_over > len ? len : 128 - left_over;
258
259         memcpy (&ctx->buffer[left_over], buffer, add);
260         ctx->buflen += add;
261
262         if (left_over + add > 64)
263           {
264             transform(ctx, ctx->buffer, (left_over + add) & ~63);
265             /* The regions in the following copy operation cannot overlap.  */
266             memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
267                     (left_over + add) & 63);
268             ctx->buflen = (left_over + add) & 63;
269           }
270
271         buffer = (const char *) buffer + add;
272         len -= add;
273       }
274
275     /* Process available complete blocks.  */
276     if (len > 64)
277       {
278         transform( ctx, buffer, len & ~63);
279         buffer = (const char *) buffer + (len & ~63);
280         len &= 63;
281       }
282
283     /* Move remaining bytes in internal buffer.  */
284     if (len > 0)
285       {
286         memcpy (ctx->buffer, buffer, len);
287         ctx->buflen = len;
288       }
289 }
290
291
292
293 /* The routine final terminates the message-digest computation and
294  * ends with the desired message digest in mdContext->digest[0...15].
295  * The handle is prepared for a new MD5 cycle.
296  * Returns 16 bytes representing the digest.
297  */
298
299 static void
300 md5_final( MD5_CONTEXT *ctx )
301 {
302     /* Take yet unprocessed bytes into account.  */
303     u32 bytes = ctx->buflen;
304     size_t pad;
305
306     /* Now count remaining bytes.  */
307     ctx->total[0] += bytes;
308     if( ctx->total[0] < bytes )
309         ++ctx->total[1];
310
311     pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
312     memcpy (&ctx->buffer[bytes], fillbuf, pad);
313
314     /* Put the 64-bit file length in *bits* at the end of the buffer.  */
315     *(u32 *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
316     *(u32 *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
317                                                     (ctx->total[0] >> 29));
318
319     /* Process last bytes.  */
320     transform( ctx, ctx->buffer, bytes + pad + 8);
321
322     /* Store the result in buffer */
323     ((u32 *)ctx->buffer)[0] = SWAP (ctx->A);
324     ((u32 *)ctx->buffer)[1] = SWAP (ctx->B);
325     ((u32 *)ctx->buffer)[2] = SWAP (ctx->C);
326     ((u32 *)ctx->buffer)[3] = SWAP (ctx->D);
327 }
328
329 static byte *
330 md5_read( MD5_CONTEXT *hd )
331 {
332     return hd->buffer;
333 }
334
335 /****************
336  * Return some information about the algorithm.  We need algo here to
337  * distinguish different flavors of the algorithm.
338  * Returns: A pointer to string describing the algorithm or NULL if
339  *          the ALGO is invalid.
340  */
341 static const char *
342 md5_get_info( int algo, size_t *contextsize,
343                byte **r_asnoid, int *r_asnlen, int *r_mdlen,
344                void (**r_init)( void *c ),
345                void (**r_write)( void *c, byte *buf, size_t nbytes ),
346                void (**r_final)( void *c ),
347                byte *(**r_read)( void *c )
348              )
349 {
350     static byte asn[18] = /* Object ID is 1.2.840.113549.2.5 */
351                     { 0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86,0x48,
352                       0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10 };
353
354     if( algo != 1 )
355         return NULL;
356
357     *contextsize = sizeof(MD5_CONTEXT);
358     *r_asnoid = asn;
359     *r_asnlen = DIM(asn);
360     *r_mdlen = 16;
361     *r_init  = (void (*)(void *))md5_init;
362     *r_write = (void (*)(void *, byte*, size_t))md5_write;
363     *r_final = (void (*)(void *))md5_final;
364     *r_read  = (byte *(*)(void *))md5_read;
365
366     return "MD5";
367 }
368
369
370 #ifndef IS_MODULE
371 static
372 #endif
373 const char * const gnupgext_version = "MD5 ($Revision$)";
374
375 static struct {
376     int class;
377     int version;
378     int  value;
379     void (*func)(void);
380 } func_table[] = {
381     { 10, 1, 0, (void(*)(void))md5_get_info },
382     { 11, 1, 1 },
383 };
384
385
386 #ifndef IS_MODULE
387 static
388 #endif
389 void *
390 gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
391 {
392     void *ret;
393     int i = *sequence;
394
395     do {
396         if( i >= DIM(func_table) || i < 0 )
397             return NULL;
398         *class = func_table[i].class;
399         *vers  = func_table[i].version;
400         switch( *class ) {
401           case 11: case 21: case 31: ret = &func_table[i].value; break;
402           default:                   ret = func_table[i].func; break;
403         }
404         i++;
405     } while( what && what != *class );
406
407     *sequence = i;
408     return ret;
409 }
410
411
412
413
414 #ifndef IS_MODULE
415 void
416 md5_constructor(void)
417 {
418     register_internal_cipher_extension( gnupgext_version, gnupgext_enum_func );
419 }
420 #endif
421
422
423
424 /* end of file */