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