00001 /* 00002 * RFC 1186/1320 compliant MD4 implementation 00003 * 00004 * Copyright (C) 2006-2007 Christophe Devine 00005 * 00006 * This program is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2 of the License, or 00009 * (at your option) any later version. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License along 00017 * with this program; if not, write to the Free Software Foundation, Inc., 00018 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00019 */ 00020 /* 00021 * The MD4 algorithm was designed by Ron Rivest in 1990. 00022 * 00023 * http://www.ietf.org/rfc/rfc1186.txt 00024 * http://www.ietf.org/rfc/rfc1320.txt 00025 */ 00026 00027 #include "xyssl/config.h" 00028 00029 #if defined(XYSSL_MD4_C) 00030 00031 #include "xyssl/md4.h" 00032 00033 #include <string.h> 00034 #include <stdio.h> 00035 00036 /* 00037 * 32-bit integer manipulation macros (little endian) 00038 */ 00039 #ifndef GET_ULONG_LE 00040 #define GET_ULONG_LE(n,b,i) \ 00041 { \ 00042 (n) = ( (unsigned long) (b)[(i) ] ) \ 00043 | ( (unsigned long) (b)[(i) + 1] << 8 ) \ 00044 | ( (unsigned long) (b)[(i) + 2] << 16 ) \ 00045 | ( (unsigned long) (b)[(i) + 3] << 24 ); \ 00046 } 00047 #endif 00048 00049 #ifndef PUT_ULONG_LE 00050 #define PUT_ULONG_LE(n,b,i) \ 00051 { \ 00052 (b)[(i) ] = (unsigned char) ( (n) ); \ 00053 (b)[(i) + 1] = (unsigned char) ( (n) >> 8 ); \ 00054 (b)[(i) + 2] = (unsigned char) ( (n) >> 16 ); \ 00055 (b)[(i) + 3] = (unsigned char) ( (n) >> 24 ); \ 00056 } 00057 #endif 00058 00059 /* 00060 * MD4 context setup 00061 */ 00062 void md4_starts( md4_context *ctx ) 00063 { 00064 ctx->total[0] = 0; 00065 ctx->total[1] = 0; 00066 00067 ctx->state[0] = 0x67452301; 00068 ctx->state[1] = 0xEFCDAB89; 00069 ctx->state[2] = 0x98BADCFE; 00070 ctx->state[3] = 0x10325476; 00071 } 00072 00073 static void md4_process( md4_context *ctx, unsigned char data[64] ) 00074 { 00075 unsigned long X[16], A, B, C, D; 00076 00077 GET_ULONG_LE( X[ 0], data, 0 ); 00078 GET_ULONG_LE( X[ 1], data, 4 ); 00079 GET_ULONG_LE( X[ 2], data, 8 ); 00080 GET_ULONG_LE( X[ 3], data, 12 ); 00081 GET_ULONG_LE( X[ 4], data, 16 ); 00082 GET_ULONG_LE( X[ 5], data, 20 ); 00083 GET_ULONG_LE( X[ 6], data, 24 ); 00084 GET_ULONG_LE( X[ 7], data, 28 ); 00085 GET_ULONG_LE( X[ 8], data, 32 ); 00086 GET_ULONG_LE( X[ 9], data, 36 ); 00087 GET_ULONG_LE( X[10], data, 40 ); 00088 GET_ULONG_LE( X[11], data, 44 ); 00089 GET_ULONG_LE( X[12], data, 48 ); 00090 GET_ULONG_LE( X[13], data, 52 ); 00091 GET_ULONG_LE( X[14], data, 56 ); 00092 GET_ULONG_LE( X[15], data, 60 ); 00093 00094 #define S(x,n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n))) 00095 00096 A = ctx->state[0]; 00097 B = ctx->state[1]; 00098 C = ctx->state[2]; 00099 D = ctx->state[3]; 00100 00101 #define F(x, y, z) ((x & y) | ((~x) & z)) 00102 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x; a = S(a,s); } 00103 00104 P( A, B, C, D, X[ 0], 3 ); 00105 P( D, A, B, C, X[ 1], 7 ); 00106 P( C, D, A, B, X[ 2], 11 ); 00107 P( B, C, D, A, X[ 3], 19 ); 00108 P( A, B, C, D, X[ 4], 3 ); 00109 P( D, A, B, C, X[ 5], 7 ); 00110 P( C, D, A, B, X[ 6], 11 ); 00111 P( B, C, D, A, X[ 7], 19 ); 00112 P( A, B, C, D, X[ 8], 3 ); 00113 P( D, A, B, C, X[ 9], 7 ); 00114 P( C, D, A, B, X[10], 11 ); 00115 P( B, C, D, A, X[11], 19 ); 00116 P( A, B, C, D, X[12], 3 ); 00117 P( D, A, B, C, X[13], 7 ); 00118 P( C, D, A, B, X[14], 11 ); 00119 P( B, C, D, A, X[15], 19 ); 00120 00121 #undef P 00122 #undef F 00123 00124 #define F(x,y,z) ((x & y) | (x & z) | (y & z)) 00125 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x5A827999; a = S(a,s); } 00126 00127 P( A, B, C, D, X[ 0], 3 ); 00128 P( D, A, B, C, X[ 4], 5 ); 00129 P( C, D, A, B, X[ 8], 9 ); 00130 P( B, C, D, A, X[12], 13 ); 00131 P( A, B, C, D, X[ 1], 3 ); 00132 P( D, A, B, C, X[ 5], 5 ); 00133 P( C, D, A, B, X[ 9], 9 ); 00134 P( B, C, D, A, X[13], 13 ); 00135 P( A, B, C, D, X[ 2], 3 ); 00136 P( D, A, B, C, X[ 6], 5 ); 00137 P( C, D, A, B, X[10], 9 ); 00138 P( B, C, D, A, X[14], 13 ); 00139 P( A, B, C, D, X[ 3], 3 ); 00140 P( D, A, B, C, X[ 7], 5 ); 00141 P( C, D, A, B, X[11], 9 ); 00142 P( B, C, D, A, X[15], 13 ); 00143 00144 #undef P 00145 #undef F 00146 00147 #define F(x,y,z) (x ^ y ^ z) 00148 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x6ED9EBA1; a = S(a,s); } 00149 00150 P( A, B, C, D, X[ 0], 3 ); 00151 P( D, A, B, C, X[ 8], 9 ); 00152 P( C, D, A, B, X[ 4], 11 ); 00153 P( B, C, D, A, X[12], 15 ); 00154 P( A, B, C, D, X[ 2], 3 ); 00155 P( D, A, B, C, X[10], 9 ); 00156 P( C, D, A, B, X[ 6], 11 ); 00157 P( B, C, D, A, X[14], 15 ); 00158 P( A, B, C, D, X[ 1], 3 ); 00159 P( D, A, B, C, X[ 9], 9 ); 00160 P( C, D, A, B, X[ 5], 11 ); 00161 P( B, C, D, A, X[13], 15 ); 00162 P( A, B, C, D, X[ 3], 3 ); 00163 P( D, A, B, C, X[11], 9 ); 00164 P( C, D, A, B, X[ 7], 11 ); 00165 P( B, C, D, A, X[15], 15 ); 00166 00167 #undef F 00168 #undef P 00169 00170 ctx->state[0] += A; 00171 ctx->state[1] += B; 00172 ctx->state[2] += C; 00173 ctx->state[3] += D; 00174 } 00175 00176 /* 00177 * MD4 process buffer 00178 */ 00179 void md4_update( md4_context *ctx, unsigned char *input, int ilen ) 00180 { 00181 int fill; 00182 unsigned long left; 00183 00184 if( ilen <= 0 ) 00185 return; 00186 00187 left = ctx->total[0] & 0x3F; 00188 fill = 64 - left; 00189 00190 ctx->total[0] += ilen; 00191 ctx->total[0] &= 0xFFFFFFFF; 00192 00193 if( ctx->total[0] < (unsigned long) ilen ) 00194 ctx->total[1]++; 00195 00196 if( left && ilen >= fill ) 00197 { 00198 memcpy( (void *) (ctx->buffer + left), 00199 (void *) input, fill ); 00200 md4_process( ctx, ctx->buffer ); 00201 input += fill; 00202 ilen -= fill; 00203 left = 0; 00204 } 00205 00206 while( ilen >= 64 ) 00207 { 00208 md4_process( ctx, input ); 00209 input += 64; 00210 ilen -= 64; 00211 } 00212 00213 if( ilen > 0 ) 00214 { 00215 memcpy( (void *) (ctx->buffer + left), 00216 (void *) input, ilen ); 00217 } 00218 } 00219 00220 static const unsigned char md4_padding[64] = 00221 { 00222 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00223 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00224 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00225 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 00226 }; 00227 00228 /* 00229 * MD4 final digest 00230 */ 00231 void md4_finish( md4_context *ctx, unsigned char output[16] ) 00232 { 00233 unsigned long last, padn; 00234 unsigned long high, low; 00235 unsigned char msglen[8]; 00236 00237 high = ( ctx->total[0] >> 29 ) 00238 | ( ctx->total[1] << 3 ); 00239 low = ( ctx->total[0] << 3 ); 00240 00241 PUT_ULONG_LE( low, msglen, 0 ); 00242 PUT_ULONG_LE( high, msglen, 4 ); 00243 00244 last = ctx->total[0] & 0x3F; 00245 padn = ( last < 56 ) ? ( 56 - last ) : ( 120 - last ); 00246 00247 md4_update( ctx, (unsigned char *) md4_padding, padn ); 00248 md4_update( ctx, msglen, 8 ); 00249 00250 PUT_ULONG_LE( ctx->state[0], output, 0 ); 00251 PUT_ULONG_LE( ctx->state[1], output, 4 ); 00252 PUT_ULONG_LE( ctx->state[2], output, 8 ); 00253 PUT_ULONG_LE( ctx->state[3], output, 12 ); 00254 } 00255 00256 /* 00257 * output = MD4( input buffer ) 00258 */ 00259 void md4( unsigned char *input, int ilen, unsigned char output[16] ) 00260 { 00261 md4_context ctx; 00262 00263 md4_starts( &ctx ); 00264 md4_update( &ctx, input, ilen ); 00265 md4_finish( &ctx, output ); 00266 00267 memset( &ctx, 0, sizeof( md4_context ) ); 00268 } 00269 00270 /* 00271 * output = MD4( file contents ) 00272 */ 00273 int md4_file( char *path, unsigned char output[16] ) 00274 { 00275 FILE *f; 00276 size_t n; 00277 md4_context ctx; 00278 unsigned char buf[1024]; 00279 00280 if( ( f = fopen( path, "rb" ) ) == NULL ) 00281 return( 1 ); 00282 00283 md4_starts( &ctx ); 00284 00285 while( ( n = fread( buf, 1, sizeof( buf ), f ) ) > 0 ) 00286 md4_update( &ctx, buf, (int) n ); 00287 00288 md4_finish( &ctx, output ); 00289 00290 memset( &ctx, 0, sizeof( md4_context ) ); 00291 00292 if( ferror( f ) != 0 ) 00293 { 00294 fclose( f ); 00295 return( 2 ); 00296 } 00297 00298 fclose( f ); 00299 return( 0 ); 00300 } 00301 00302 /* 00303 * MD4 HMAC context setup 00304 */ 00305 void md4_hmac_starts( md4_context *ctx, unsigned char *key, int keylen ) 00306 { 00307 int i; 00308 unsigned char sum[16]; 00309 00310 if( keylen > 64 ) 00311 { 00312 md4( key, keylen, sum ); 00313 keylen = 16; 00314 key = sum; 00315 } 00316 00317 memset( ctx->ipad, 0x36, 64 ); 00318 memset( ctx->opad, 0x5C, 64 ); 00319 00320 for( i = 0; i < keylen; i++ ) 00321 { 00322 ctx->ipad[i] = (unsigned char)( ctx->ipad[i] ^ key[i] ); 00323 ctx->opad[i] = (unsigned char)( ctx->opad[i] ^ key[i] ); 00324 } 00325 00326 md4_starts( ctx ); 00327 md4_update( ctx, ctx->ipad, 64 ); 00328 00329 memset( sum, 0, sizeof( sum ) ); 00330 } 00331 00332 /* 00333 * MD4 HMAC process buffer 00334 */ 00335 void md4_hmac_update( md4_context *ctx, unsigned char *input, int ilen ) 00336 { 00337 md4_update( ctx, input, ilen ); 00338 } 00339 00340 /* 00341 * MD4 HMAC final digest 00342 */ 00343 void md4_hmac_finish( md4_context *ctx, unsigned char output[16] ) 00344 { 00345 unsigned char tmpbuf[16]; 00346 00347 md4_finish( ctx, tmpbuf ); 00348 md4_starts( ctx ); 00349 md4_update( ctx, ctx->opad, 64 ); 00350 md4_update( ctx, tmpbuf, 16 ); 00351 md4_finish( ctx, output ); 00352 00353 memset( tmpbuf, 0, sizeof( tmpbuf ) ); 00354 } 00355 00356 /* 00357 * output = HMAC-MD4( hmac key, input buffer ) 00358 */ 00359 void md4_hmac( unsigned char *key, int keylen, unsigned char *input, int ilen, 00360 unsigned char output[16] ) 00361 { 00362 md4_context ctx; 00363 00364 md4_hmac_starts( &ctx, key, keylen ); 00365 md4_hmac_update( &ctx, input, ilen ); 00366 md4_hmac_finish( &ctx, output ); 00367 00368 memset( &ctx, 0, sizeof( md4_context ) ); 00369 } 00370 00371 #if defined(XYSSL_SELF_TEST) 00372 00373 /* 00374 * RFC 1320 test vectors 00375 */ 00376 static const char md4_test_str[7][81] = 00377 { 00378 { "" }, 00379 { "a" }, 00380 { "abc" }, 00381 { "message digest" }, 00382 { "abcdefghijklmnopqrstuvwxyz" }, 00383 { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" }, 00384 { "12345678901234567890123456789012345678901234567890123456789012" \ 00385 "345678901234567890" } 00386 }; 00387 00388 static const unsigned char md4_test_sum[7][16] = 00389 { 00390 { 0x31, 0xD6, 0xCF, 0xE0, 0xD1, 0x6A, 0xE9, 0x31, 00391 0xB7, 0x3C, 0x59, 0xD7, 0xE0, 0xC0, 0x89, 0xC0 }, 00392 { 0xBD, 0xE5, 0x2C, 0xB3, 0x1D, 0xE3, 0x3E, 0x46, 00393 0x24, 0x5E, 0x05, 0xFB, 0xDB, 0xD6, 0xFB, 0x24 }, 00394 { 0xA4, 0x48, 0x01, 0x7A, 0xAF, 0x21, 0xD8, 0x52, 00395 0x5F, 0xC1, 0x0A, 0xE8, 0x7A, 0xA6, 0x72, 0x9D }, 00396 { 0xD9, 0x13, 0x0A, 0x81, 0x64, 0x54, 0x9F, 0xE8, 00397 0x18, 0x87, 0x48, 0x06, 0xE1, 0xC7, 0x01, 0x4B }, 00398 { 0xD7, 0x9E, 0x1C, 0x30, 0x8A, 0xA5, 0xBB, 0xCD, 00399 0xEE, 0xA8, 0xED, 0x63, 0xDF, 0x41, 0x2D, 0xA9 }, 00400 { 0x04, 0x3F, 0x85, 0x82, 0xF2, 0x41, 0xDB, 0x35, 00401 0x1C, 0xE6, 0x27, 0xE1, 0x53, 0xE7, 0xF0, 0xE4 }, 00402 { 0xE3, 0x3B, 0x4D, 0xDC, 0x9C, 0x38, 0xF2, 0x19, 00403 0x9C, 0x3E, 0x7B, 0x16, 0x4F, 0xCC, 0x05, 0x36 } 00404 }; 00405 00406 /* 00407 * Checkup routine 00408 */ 00409 int md4_self_test( int verbose ) 00410 { 00411 int i; 00412 unsigned char md4sum[16]; 00413 00414 for( i = 0; i < 7; i++ ) 00415 { 00416 if( verbose != 0 ) 00417 printf( " MD4 test #%d: ", i + 1 ); 00418 00419 md4( (unsigned char *) md4_test_str[i], 00420 strlen( md4_test_str[i] ), md4sum ); 00421 00422 if( memcmp( md4sum, md4_test_sum[i], 16 ) != 0 ) 00423 { 00424 if( verbose != 0 ) 00425 printf( "failed\n" ); 00426 00427 return( 1 ); 00428 } 00429 00430 if( verbose != 0 ) 00431 printf( "passed\n" ); 00432 } 00433 00434 if( verbose != 0 ) 00435 printf( "\n" ); 00436 00437 return( 0 ); 00438 } 00439 00440 #endif 00441 00442 #endif