PolarSSL v1.2.5
md4.c
Go to the documentation of this file.
1 /*
2  * RFC 1186/1320 compliant MD4 implementation
3  *
4  * Copyright (C) 2006-2010, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 /*
26  * The MD4 algorithm was designed by Ron Rivest in 1990.
27  *
28  * http://www.ietf.org/rfc/rfc1186.txt
29  * http://www.ietf.org/rfc/rfc1320.txt
30  */
31 
32 #include "polarssl/config.h"
33 
34 #if defined(POLARSSL_MD4_C)
35 
36 #include "polarssl/md4.h"
37 
38 #if defined(POLARSSL_FS_IO) || defined(POLARSSL_SELF_TEST)
39 #include <stdio.h>
40 #endif
41 
42 /*
43  * 32-bit integer manipulation macros (little endian)
44  */
45 #ifndef GET_UINT32_LE
46 #define GET_UINT32_LE(n,b,i) \
47 { \
48  (n) = ( (uint32_t) (b)[(i) ] ) \
49  | ( (uint32_t) (b)[(i) + 1] << 8 ) \
50  | ( (uint32_t) (b)[(i) + 2] << 16 ) \
51  | ( (uint32_t) (b)[(i) + 3] << 24 ); \
52 }
53 #endif
54 
55 #ifndef PUT_UINT32_LE
56 #define PUT_UINT32_LE(n,b,i) \
57 { \
58  (b)[(i) ] = (unsigned char) ( (n) ); \
59  (b)[(i) + 1] = (unsigned char) ( (n) >> 8 ); \
60  (b)[(i) + 2] = (unsigned char) ( (n) >> 16 ); \
61  (b)[(i) + 3] = (unsigned char) ( (n) >> 24 ); \
62 }
63 #endif
64 
65 /*
66  * MD4 context setup
67  */
68 void md4_starts( md4_context *ctx )
69 {
70  ctx->total[0] = 0;
71  ctx->total[1] = 0;
72 
73  ctx->state[0] = 0x67452301;
74  ctx->state[1] = 0xEFCDAB89;
75  ctx->state[2] = 0x98BADCFE;
76  ctx->state[3] = 0x10325476;
77 }
78 
79 static void md4_process( md4_context *ctx, const unsigned char data[64] )
80 {
81  uint32_t X[16], A, B, C, D;
82 
83  GET_UINT32_LE( X[ 0], data, 0 );
84  GET_UINT32_LE( X[ 1], data, 4 );
85  GET_UINT32_LE( X[ 2], data, 8 );
86  GET_UINT32_LE( X[ 3], data, 12 );
87  GET_UINT32_LE( X[ 4], data, 16 );
88  GET_UINT32_LE( X[ 5], data, 20 );
89  GET_UINT32_LE( X[ 6], data, 24 );
90  GET_UINT32_LE( X[ 7], data, 28 );
91  GET_UINT32_LE( X[ 8], data, 32 );
92  GET_UINT32_LE( X[ 9], data, 36 );
93  GET_UINT32_LE( X[10], data, 40 );
94  GET_UINT32_LE( X[11], data, 44 );
95  GET_UINT32_LE( X[12], data, 48 );
96  GET_UINT32_LE( X[13], data, 52 );
97  GET_UINT32_LE( X[14], data, 56 );
98  GET_UINT32_LE( X[15], data, 60 );
99 
100 #define S(x,n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
101 
102  A = ctx->state[0];
103  B = ctx->state[1];
104  C = ctx->state[2];
105  D = ctx->state[3];
106 
107 #define F(x, y, z) ((x & y) | ((~x) & z))
108 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x; a = S(a,s); }
109 
110  P( A, B, C, D, X[ 0], 3 );
111  P( D, A, B, C, X[ 1], 7 );
112  P( C, D, A, B, X[ 2], 11 );
113  P( B, C, D, A, X[ 3], 19 );
114  P( A, B, C, D, X[ 4], 3 );
115  P( D, A, B, C, X[ 5], 7 );
116  P( C, D, A, B, X[ 6], 11 );
117  P( B, C, D, A, X[ 7], 19 );
118  P( A, B, C, D, X[ 8], 3 );
119  P( D, A, B, C, X[ 9], 7 );
120  P( C, D, A, B, X[10], 11 );
121  P( B, C, D, A, X[11], 19 );
122  P( A, B, C, D, X[12], 3 );
123  P( D, A, B, C, X[13], 7 );
124  P( C, D, A, B, X[14], 11 );
125  P( B, C, D, A, X[15], 19 );
126 
127 #undef P
128 #undef F
129 
130 #define F(x,y,z) ((x & y) | (x & z) | (y & z))
131 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x5A827999; a = S(a,s); }
132 
133  P( A, B, C, D, X[ 0], 3 );
134  P( D, A, B, C, X[ 4], 5 );
135  P( C, D, A, B, X[ 8], 9 );
136  P( B, C, D, A, X[12], 13 );
137  P( A, B, C, D, X[ 1], 3 );
138  P( D, A, B, C, X[ 5], 5 );
139  P( C, D, A, B, X[ 9], 9 );
140  P( B, C, D, A, X[13], 13 );
141  P( A, B, C, D, X[ 2], 3 );
142  P( D, A, B, C, X[ 6], 5 );
143  P( C, D, A, B, X[10], 9 );
144  P( B, C, D, A, X[14], 13 );
145  P( A, B, C, D, X[ 3], 3 );
146  P( D, A, B, C, X[ 7], 5 );
147  P( C, D, A, B, X[11], 9 );
148  P( B, C, D, A, X[15], 13 );
149 
150 #undef P
151 #undef F
152 
153 #define F(x,y,z) (x ^ y ^ z)
154 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x6ED9EBA1; a = S(a,s); }
155 
156  P( A, B, C, D, X[ 0], 3 );
157  P( D, A, B, C, X[ 8], 9 );
158  P( C, D, A, B, X[ 4], 11 );
159  P( B, C, D, A, X[12], 15 );
160  P( A, B, C, D, X[ 2], 3 );
161  P( D, A, B, C, X[10], 9 );
162  P( C, D, A, B, X[ 6], 11 );
163  P( B, C, D, A, X[14], 15 );
164  P( A, B, C, D, X[ 1], 3 );
165  P( D, A, B, C, X[ 9], 9 );
166  P( C, D, A, B, X[ 5], 11 );
167  P( B, C, D, A, X[13], 15 );
168  P( A, B, C, D, X[ 3], 3 );
169  P( D, A, B, C, X[11], 9 );
170  P( C, D, A, B, X[ 7], 11 );
171  P( B, C, D, A, X[15], 15 );
172 
173 #undef F
174 #undef P
175 
176  ctx->state[0] += A;
177  ctx->state[1] += B;
178  ctx->state[2] += C;
179  ctx->state[3] += D;
180 }
181 
182 /*
183  * MD4 process buffer
184  */
185 void md4_update( md4_context *ctx, const unsigned char *input, size_t ilen )
186 {
187  size_t fill;
188  uint32_t left;
189 
190  if( ilen <= 0 )
191  return;
192 
193  left = ctx->total[0] & 0x3F;
194  fill = 64 - left;
195 
196  ctx->total[0] += (uint32_t) ilen;
197  ctx->total[0] &= 0xFFFFFFFF;
198 
199  if( ctx->total[0] < (uint32_t) ilen )
200  ctx->total[1]++;
201 
202  if( left && ilen >= fill )
203  {
204  memcpy( (void *) (ctx->buffer + left),
205  (void *) input, fill );
206  md4_process( ctx, ctx->buffer );
207  input += fill;
208  ilen -= fill;
209  left = 0;
210  }
211 
212  while( ilen >= 64 )
213  {
214  md4_process( ctx, input );
215  input += 64;
216  ilen -= 64;
217  }
218 
219  if( ilen > 0 )
220  {
221  memcpy( (void *) (ctx->buffer + left),
222  (void *) input, ilen );
223  }
224 }
225 
226 static const unsigned char md4_padding[64] =
227 {
228  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
229  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
230  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
231  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
232 };
233 
234 /*
235  * MD4 final digest
236  */
237 void md4_finish( md4_context *ctx, unsigned char output[16] )
238 {
239  uint32_t last, padn;
240  uint32_t high, low;
241  unsigned char msglen[8];
242 
243  high = ( ctx->total[0] >> 29 )
244  | ( ctx->total[1] << 3 );
245  low = ( ctx->total[0] << 3 );
246 
247  PUT_UINT32_LE( low, msglen, 0 );
248  PUT_UINT32_LE( high, msglen, 4 );
249 
250  last = ctx->total[0] & 0x3F;
251  padn = ( last < 56 ) ? ( 56 - last ) : ( 120 - last );
252 
253  md4_update( ctx, (unsigned char *) md4_padding, padn );
254  md4_update( ctx, msglen, 8 );
255 
256  PUT_UINT32_LE( ctx->state[0], output, 0 );
257  PUT_UINT32_LE( ctx->state[1], output, 4 );
258  PUT_UINT32_LE( ctx->state[2], output, 8 );
259  PUT_UINT32_LE( ctx->state[3], output, 12 );
260 }
261 
262 /*
263  * output = MD4( input buffer )
264  */
265 void md4( const unsigned char *input, size_t ilen, unsigned char output[16] )
266 {
267  md4_context ctx;
268 
269  md4_starts( &ctx );
270  md4_update( &ctx, input, ilen );
271  md4_finish( &ctx, output );
272 
273  memset( &ctx, 0, sizeof( md4_context ) );
274 }
275 
276 #if defined(POLARSSL_FS_IO)
277 /*
278  * output = MD4( file contents )
279  */
280 int md4_file( const char *path, unsigned char output[16] )
281 {
282  FILE *f;
283  size_t n;
284  md4_context ctx;
285  unsigned char buf[1024];
286 
287  if( ( f = fopen( path, "rb" ) ) == NULL )
289 
290  md4_starts( &ctx );
291 
292  while( ( n = fread( buf, 1, sizeof( buf ), f ) ) > 0 )
293  md4_update( &ctx, buf, n );
294 
295  md4_finish( &ctx, output );
296 
297  memset( &ctx, 0, sizeof( md4_context ) );
298 
299  if( ferror( f ) != 0 )
300  {
301  fclose( f );
303  }
304 
305  fclose( f );
306  return( 0 );
307 }
308 #endif /* POLARSSL_FS_IO */
309 
310 /*
311  * MD4 HMAC context setup
312  */
313 void md4_hmac_starts( md4_context *ctx, const unsigned char *key, size_t keylen )
314 {
315  size_t i;
316  unsigned char sum[16];
317 
318  if( keylen > 64 )
319  {
320  md4( key, keylen, sum );
321  keylen = 16;
322  key = sum;
323  }
324 
325  memset( ctx->ipad, 0x36, 64 );
326  memset( ctx->opad, 0x5C, 64 );
327 
328  for( i = 0; i < keylen; i++ )
329  {
330  ctx->ipad[i] = (unsigned char)( ctx->ipad[i] ^ key[i] );
331  ctx->opad[i] = (unsigned char)( ctx->opad[i] ^ key[i] );
332  }
333 
334  md4_starts( ctx );
335  md4_update( ctx, ctx->ipad, 64 );
336 
337  memset( sum, 0, sizeof( sum ) );
338 }
339 
340 /*
341  * MD4 HMAC process buffer
342  */
343 void md4_hmac_update( md4_context *ctx, const unsigned char *input, size_t ilen )
344 {
345  md4_update( ctx, input, ilen );
346 }
347 
348 /*
349  * MD4 HMAC final digest
350  */
351 void md4_hmac_finish( md4_context *ctx, unsigned char output[16] )
352 {
353  unsigned char tmpbuf[16];
354 
355  md4_finish( ctx, tmpbuf );
356  md4_starts( ctx );
357  md4_update( ctx, ctx->opad, 64 );
358  md4_update( ctx, tmpbuf, 16 );
359  md4_finish( ctx, output );
360 
361  memset( tmpbuf, 0, sizeof( tmpbuf ) );
362 }
363 
364 /*
365  * MD4 HMAC context reset
366  */
367 void md4_hmac_reset( md4_context *ctx )
368 {
369  md4_starts( ctx );
370  md4_update( ctx, ctx->ipad, 64 );
371 }
372 
373 /*
374  * output = HMAC-MD4( hmac key, input buffer )
375  */
376 void md4_hmac( const unsigned char *key, size_t keylen,
377  const unsigned char *input, size_t ilen,
378  unsigned char output[16] )
379 {
380  md4_context ctx;
381 
382  md4_hmac_starts( &ctx, key, keylen );
383  md4_hmac_update( &ctx, input, ilen );
384  md4_hmac_finish( &ctx, output );
385 
386  memset( &ctx, 0, sizeof( md4_context ) );
387 }
388 
389 #if defined(POLARSSL_SELF_TEST)
390 
391 /*
392  * RFC 1320 test vectors
393  */
394 static const char md4_test_str[7][81] =
395 {
396  { "" },
397  { "a" },
398  { "abc" },
399  { "message digest" },
400  { "abcdefghijklmnopqrstuvwxyz" },
401  { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" },
402  { "12345678901234567890123456789012345678901234567890123456789012" \
403  "345678901234567890" }
404 };
405 
406 static const unsigned char md4_test_sum[7][16] =
407 {
408  { 0x31, 0xD6, 0xCF, 0xE0, 0xD1, 0x6A, 0xE9, 0x31,
409  0xB7, 0x3C, 0x59, 0xD7, 0xE0, 0xC0, 0x89, 0xC0 },
410  { 0xBD, 0xE5, 0x2C, 0xB3, 0x1D, 0xE3, 0x3E, 0x46,
411  0x24, 0x5E, 0x05, 0xFB, 0xDB, 0xD6, 0xFB, 0x24 },
412  { 0xA4, 0x48, 0x01, 0x7A, 0xAF, 0x21, 0xD8, 0x52,
413  0x5F, 0xC1, 0x0A, 0xE8, 0x7A, 0xA6, 0x72, 0x9D },
414  { 0xD9, 0x13, 0x0A, 0x81, 0x64, 0x54, 0x9F, 0xE8,
415  0x18, 0x87, 0x48, 0x06, 0xE1, 0xC7, 0x01, 0x4B },
416  { 0xD7, 0x9E, 0x1C, 0x30, 0x8A, 0xA5, 0xBB, 0xCD,
417  0xEE, 0xA8, 0xED, 0x63, 0xDF, 0x41, 0x2D, 0xA9 },
418  { 0x04, 0x3F, 0x85, 0x82, 0xF2, 0x41, 0xDB, 0x35,
419  0x1C, 0xE6, 0x27, 0xE1, 0x53, 0xE7, 0xF0, 0xE4 },
420  { 0xE3, 0x3B, 0x4D, 0xDC, 0x9C, 0x38, 0xF2, 0x19,
421  0x9C, 0x3E, 0x7B, 0x16, 0x4F, 0xCC, 0x05, 0x36 }
422 };
423 
424 /*
425  * Checkup routine
426  */
427 int md4_self_test( int verbose )
428 {
429  int i;
430  unsigned char md4sum[16];
431 
432  for( i = 0; i < 7; i++ )
433  {
434  if( verbose != 0 )
435  printf( " MD4 test #%d: ", i + 1 );
436 
437  md4( (unsigned char *) md4_test_str[i],
438  strlen( md4_test_str[i] ), md4sum );
439 
440  if( memcmp( md4sum, md4_test_sum[i], 16 ) != 0 )
441  {
442  if( verbose != 0 )
443  printf( "failed\n" );
444 
445  return( 1 );
446  }
447 
448  if( verbose != 0 )
449  printf( "passed\n" );
450  }
451 
452  if( verbose != 0 )
453  printf( "\n" );
454 
455  return( 0 );
456 }
457 
458 #endif
459 
460 #endif