md4.c

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