md4.c

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