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