d649f68e56ae8b81ea2307dc83580dc964640e60
[libgcrypt.git] / cipher / md4.c
1 /* md4.c - MD4 Message-Digest Algorithm
2  * Copyright (C) 2002 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser General Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt 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
14  * GNU 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 this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  *
20  * Based on md5.c in libgcrypt, but rewritten to compute md4 checksums
21  * using a public domain md4 implementation with the following comments:
22  *
23  * Modified by Wei Dai from Andrew M. Kuchling's md4.c
24  * The original code and all modifications are in the public domain.
25  *
26  * This is the original introductory comment:
27  *
28  *  md4.c : MD4 hash algorithm.
29  *
30  * Part of the Python Cryptography Toolkit, version 1.1
31  *
32  * Distribute and use freely; there are no restrictions on further
33  * dissemination and usage except those imposed by the laws of your
34  * country of residence.
35  *
36  */
37
38 /* MD4 test suite:
39  * MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
40  * MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
41  * MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
42  * MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
43  * MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
44  * MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
45  * 043f8582f241db351ce627e153e7f0e4
46  * MD4 ("123456789012345678901234567890123456789012345678901234567890123456
47  * 78901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536
48  */
49
50 #include <config.h>
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <assert.h>
55 #include "g10lib.h"
56 #include "memory.h"
57 #include "dynload.h"
58
59 #include "bithelp.h"
60
61
62 typedef struct {
63     u32 A,B,C,D;          /* chaining variables */
64     u32  nblocks;
65     byte buf[64];
66     int  count;
67 } MD4_CONTEXT;
68
69
70 static void
71 md4_init( MD4_CONTEXT *ctx )
72 {
73     ctx->A = 0x67452301;
74     ctx->B = 0xefcdab89;
75     ctx->C = 0x98badcfe;
76     ctx->D = 0x10325476;
77
78     ctx->nblocks = 0;
79     ctx->count = 0;
80 }
81
82 static void
83 burn_stack (int bytes)
84 {
85     char buf[128];
86     
87     memset (buf, 0, sizeof buf);
88     bytes -= sizeof buf;
89     if (bytes > 0)
90         burn_stack (bytes);
91 }
92
93 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
94 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
95 #define H(x, y, z) ((x) ^ (y) ^ (z))
96
97
98 /****************
99  * transform 64 bytes
100  */
101 static void
102 transform( MD4_CONTEXT *ctx, byte *data )
103 {
104     u32 in[16];
105     register u32 A = ctx->A;
106     register u32 B = ctx->B;
107     register u32 C = ctx->C;
108     register u32 D = ctx->D;
109
110 #ifdef BIG_ENDIAN_HOST
111     { int i;
112       byte *p2, *p1;
113       for(i=0, p1=data, p2=(byte*)in; i < 16; i++, p2 += 4 ) {
114         p2[3] = *p1++;
115         p2[2] = *p1++;
116         p2[1] = *p1++;
117         p2[0] = *p1++;
118       }
119     }
120 #else
121     memcpy (in, data, 64);
122 #endif
123
124     /* Round 1.  */
125 #define function(a,b,c,d,k,s) a=rol(a+F(b,c,d)+in[k],s);
126           function(A,B,C,D, 0, 3);
127           function(D,A,B,C, 1, 7);
128           function(C,D,A,B, 2,11);
129           function(B,C,D,A, 3,19);
130           function(A,B,C,D, 4, 3);
131           function(D,A,B,C, 5, 7);
132           function(C,D,A,B, 6,11);
133           function(B,C,D,A, 7,19);
134           function(A,B,C,D, 8, 3);
135           function(D,A,B,C, 9, 7);
136           function(C,D,A,B,10,11);
137           function(B,C,D,A,11,19);
138           function(A,B,C,D,12, 3);
139           function(D,A,B,C,13, 7);
140           function(C,D,A,B,14,11);
141           function(B,C,D,A,15,19);
142
143 #undef function
144
145     /* Round 2.  */
146 #define function(a,b,c,d,k,s) a=rol(a+G(b,c,d)+in[k]+0x5a827999,s);
147
148           function(A,B,C,D, 0, 3);
149           function(D,A,B,C, 4, 5);
150           function(C,D,A,B, 8, 9);
151           function(B,C,D,A,12,13);
152           function(A,B,C,D, 1, 3);
153           function(D,A,B,C, 5, 5);
154           function(C,D,A,B, 9, 9);
155           function(B,C,D,A,13,13);
156           function(A,B,C,D, 2, 3);
157           function(D,A,B,C, 6, 5);
158           function(C,D,A,B,10, 9);
159           function(B,C,D,A,14,13);
160           function(A,B,C,D, 3, 3);
161           function(D,A,B,C, 7, 5);
162           function(C,D,A,B,11, 9);
163           function(B,C,D,A,15,13);
164
165 #undef function
166
167     /* Round 3.  */
168 #define function(a,b,c,d,k,s) a=rol(a+H(b,c,d)+in[k]+0x6ed9eba1,s);
169
170           function(A,B,C,D, 0, 3);
171           function(D,A,B,C, 8, 9);
172           function(C,D,A,B, 4,11);
173           function(B,C,D,A,12,15);
174           function(A,B,C,D, 2, 3);
175           function(D,A,B,C,10, 9);
176           function(C,D,A,B, 6,11);
177           function(B,C,D,A,14,15);
178           function(A,B,C,D, 1, 3);
179           function(D,A,B,C, 9, 9);
180           function(C,D,A,B, 5,11);
181           function(B,C,D,A,13,15);
182           function(A,B,C,D, 3, 3);
183           function(D,A,B,C,11, 9);
184           function(C,D,A,B, 7,11);
185           function(B,C,D,A,15,15);
186
187
188     /* Put checksum in context given as argument.  */
189     ctx->A += A;
190     ctx->B += B;
191     ctx->C += C;
192     ctx->D += D;
193 }
194
195
196
197 /* The routine updates the message-digest context to
198  * account for the presence of each of the characters inBuf[0..inLen-1]
199  * in the message whose digest is being computed.
200  */
201 static void
202 md4_write( MD4_CONTEXT *hd, byte *inbuf, size_t inlen)
203 {
204     if( hd->count == 64 ) { /* flush the buffer */
205         transform( hd, hd->buf );
206         burn_stack (80+6*sizeof(void*));
207         hd->count = 0;
208         hd->nblocks++;
209     }
210     if( !inbuf )
211         return;
212     if( hd->count ) {
213         for( ; inlen && hd->count < 64; inlen-- )
214             hd->buf[hd->count++] = *inbuf++;
215         md4_write( hd, NULL, 0 );
216         if( !inlen )
217             return;
218     }
219     burn_stack (80+6*sizeof(void*));
220
221     while( inlen >= 64 ) {
222         transform( hd, inbuf );
223         hd->count = 0;
224         hd->nblocks++;
225         inlen -= 64;
226         inbuf += 64;
227     }
228     for( ; inlen && hd->count < 64; inlen-- )
229         hd->buf[hd->count++] = *inbuf++;
230
231 }
232
233
234
235 /* The routine final terminates the message-digest computation and
236  * ends with the desired message digest in mdContext->digest[0...15].
237  * The handle is prepared for a new MD4 cycle.
238  * Returns 16 bytes representing the digest.
239  */
240
241 static void
242 md4_final( MD4_CONTEXT *hd )
243 {
244     u32 t, msb, lsb;
245     byte *p;
246
247     md4_write(hd, NULL, 0); /* flush */;
248
249     t = hd->nblocks;
250     /* multiply by 64 to make a byte count */
251     lsb = t << 6;
252     msb = t >> 26;
253     /* add the count */
254     t = lsb;
255     if( (lsb += hd->count) < t )
256         msb++;
257     /* multiply by 8 to make a bit count */
258     t = lsb;
259     lsb <<= 3;
260     msb <<= 3;
261     msb |= t >> 29;
262
263     if( hd->count < 56 ) { /* enough room */
264         hd->buf[hd->count++] = 0x80; /* pad */
265         while( hd->count < 56 )
266             hd->buf[hd->count++] = 0;  /* pad */
267     }
268     else { /* need one extra block */
269         hd->buf[hd->count++] = 0x80; /* pad character */
270         while( hd->count < 64 )
271             hd->buf[hd->count++] = 0;
272         md4_write(hd, NULL, 0);  /* flush */;
273         memset(hd->buf, 0, 56 ); /* fill next block with zeroes */
274     }
275     /* append the 64 bit count */
276     hd->buf[56] = lsb      ;
277     hd->buf[57] = lsb >>  8;
278     hd->buf[58] = lsb >> 16;
279     hd->buf[59] = lsb >> 24;
280     hd->buf[60] = msb      ;
281     hd->buf[61] = msb >>  8;
282     hd->buf[62] = msb >> 16;
283     hd->buf[63] = msb >> 24;
284     transform( hd, hd->buf );
285     burn_stack (80+6*sizeof(void*));
286
287     p = hd->buf;
288   #ifdef BIG_ENDIAN_HOST
289     #define X(a) do { *p++ = hd->a      ; *p++ = hd->a >> 8;      \
290                       *p++ = hd->a >> 16; *p++ = hd->a >> 24; } while(0)
291   #else /* little endian */
292     #define X(a) do { *(u32*)p = (*hd).a ; p += 4; } while(0)
293   #endif
294     X(A);
295     X(B);
296     X(C);
297     X(D);
298   #undef X
299
300 }
301
302 static byte *
303 md4_read( MD4_CONTEXT *hd )
304 {
305     return hd->buf;
306 }
307
308 /****************
309  * Return some information about the algorithm.  We need algo here to
310  * distinguish different flavors of the algorithm.
311  * Returns: A pointer to string describing the algorithm or NULL if
312  *          the ALGO is invalid.
313  */
314 static const char *
315 md4_get_info( int algo, size_t *contextsize,
316                byte **r_asnoid, int *r_asnlen, int *r_mdlen,
317                void (**r_init)( void *c ),
318                void (**r_write)( void *c, byte *buf, size_t nbytes ),
319                void (**r_final)( void *c ),
320                byte *(**r_read)( void *c )
321              )
322 {
323     static byte asn[18] = /* Object ID is 1.2.840.113549.2.4 */
324                     { 0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86,0x48,
325                       0x86, 0xf7, 0x0d, 0x02, 0x04, 0x05, 0x00, 0x04, 0x10 };
326
327     if( algo != 301 )
328         return NULL;
329
330     *contextsize = sizeof(MD4_CONTEXT);
331     *r_asnoid = asn;
332     *r_asnlen = DIM(asn);
333     *r_mdlen = 16;
334     *(void  (**)(MD4_CONTEXT *))r_init                 = md4_init;
335     *(void  (**)(MD4_CONTEXT *, byte*, size_t))r_write = md4_write;
336     *(void  (**)(MD4_CONTEXT *))r_final                = md4_final;
337     *(byte *(**)(MD4_CONTEXT *))r_read                 = md4_read;
338
339     return "MD4";
340 }
341
342
343 #ifndef IS_MODULE
344 static
345 #endif
346 const char * const gnupgext_version = "MD4 ($Revision$)";
347
348 static struct {
349     int class;
350     int version;
351     int  value;
352     void (*func)(void);
353 } func_table[] = {
354     { 10, 1, 0, (void(*)(void))md4_get_info },
355     { 11, 1, 301 },
356 };
357
358
359 #ifndef IS_MODULE
360 static
361 #endif
362 void *
363 gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
364 {
365     void *ret;
366     int i = *sequence;
367
368     do {
369         if( i >= DIM(func_table) || i < 0 )
370             return NULL;
371         *class = func_table[i].class;
372         *vers  = func_table[i].version;
373         switch( *class ) {
374           case 11: case 21: case 31: ret = &func_table[i].value; break;
375           default:                   ret = func_table[i].func; break;
376         }
377         i++;
378     } while( what && what != *class );
379
380     *sequence = i;
381     return ret;
382 }
383
384
385
386
387 #ifndef IS_MODULE
388 void
389 _gcry_md4_constructor(void)
390 {
391     _gcry_register_internal_cipher_extension( gnupgext_version, gnupgext_enum_func );
392 }
393 #endif
394
395 /* end of file */