libmultihash/md4.c

   1 /*
   2  *  RFC 1186/1320 compliant MD4 implementation
   3  *
   4  *  Copyright (C) 2006-2007  Christophe Devine
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License, version 2.1 as published by the Free Software Foundation.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  18  *  MA  02110-1301  USA
  19  */
  20 /*
  21  *  The MD4 algorithm was designed by Ron Rivest in 1990.
  22  *
  23  *  http://www.ietf.org/rfc/rfc1186.txt
  24  *  http://www.ietf.org/rfc/rfc1320.txt
  25  */
  26
  27 #ifndef _CRT_SECURE_NO_DEPRECATE
  28 #define _CRT_SECURE_NO_DEPRECATE 1
  29 #endif
  30
  31 #include <string.h>
  32 #include <stdio.h>
  33
  34 #include "md4.h"
  35
  36 /*
  37  * 32-bit integer manipulation macros (little endian)
  38  */
  39 #ifndef GET_UINT32_LE
  40 #define GET_UINT32_LE(n,b,i)                            \
  41 {                                                       \
  42     (n) = ( (unsigned long) (b)[(i)    ]       )        \
  43         | ( (unsigned long) (b)[(i) + 1] <<  8 )        \
  44         | ( (unsigned long) (b)[(i) + 2] << 16 )        \
  45         | ( (unsigned long) (b)[(i) + 3] << 24 );       \
  46 }
  47 #endif
  48
  49 #ifndef PUT_UINT32_LE
  50 #define PUT_UINT32_LE(n,b,i)                            \
  51 {                                                       \
  52     (b)[(i)    ] = (unsigned char) ( (n)       );       \
  53     (b)[(i) + 1] = (unsigned char) ( (n) >>  8 );       \
  54     (b)[(i) + 2] = (unsigned char) ( (n) >> 16 );       \
  55     (b)[(i) + 3] = (unsigned char) ( (n) >> 24 );       \
  56 }
  57 #endif
  58
  59 /*
  60  * MD4 context setup
  61  */
  62 void md4_starts( md4_context *ctx )
  63 {
  64     ctx->total[0] = 0;
  65     ctx->total[1] = 0;
  66
  67     ctx->state[0] = 0x67452301;
  68     ctx->state[1] = 0xEFCDAB89;
  69     ctx->state[2] = 0x98BADCFE;
  70     ctx->state[3] = 0x10325476;
  71 }
  72
  73 static void md4_process( md4_context *ctx, unsigned char data[64] )
  74 {
  75     unsigned long X[16], A, B, C, D;
  76
  77     GET_UINT32_LE( X[ 0], data,  0 );
  78     GET_UINT32_LE( X[ 1], data,  4 );
  79     GET_UINT32_LE( X[ 2], data,  8 );
  80     GET_UINT32_LE( X[ 3], data, 12 );
  81     GET_UINT32_LE( X[ 4], data, 16 );
  82     GET_UINT32_LE( X[ 5], data, 20 );
  83     GET_UINT32_LE( X[ 6], data, 24 );
  84     GET_UINT32_LE( X[ 7], data, 28 );
  85     GET_UINT32_LE( X[ 8], data, 32 );
  86     GET_UINT32_LE( X[ 9], data, 36 );
  87     GET_UINT32_LE( X[10], data, 40 );
  88     GET_UINT32_LE( X[11], data, 44 );
  89     GET_UINT32_LE( X[12], data, 48 );
  90     GET_UINT32_LE( X[13], data, 52 );
  91     GET_UINT32_LE( X[14], data, 56 );
  92     GET_UINT32_LE( X[15], data, 60 );
  93
  94 #define S(x,n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
  95
  96     A = ctx->state[0];
  97     B = ctx->state[1];
  98     C = ctx->state[2];
  99     D = ctx->state[3];
 100
 101 #define F(x, y, z) ((x & y) | ((~x) & z))
 102 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x; a = S(a,s); }
 103
 104     P( A, B, C, D, X[ 0],  3 );
 105     P( D, A, B, C, X[ 1],  7 );
 106     P( C, D, A, B, X[ 2], 11 );
 107     P( B, C, D, A, X[ 3], 19 );
 108     P( A, B, C, D, X[ 4],  3 );
 109     P( D, A, B, C, X[ 5],  7 );
 110     P( C, D, A, B, X[ 6], 11 );
 111     P( B, C, D, A, X[ 7], 19 );
 112     P( A, B, C, D, X[ 8],  3 );
 113     P( D, A, B, C, X[ 9],  7 );
 114     P( C, D, A, B, X[10], 11 );
 115     P( B, C, D, A, X[11], 19 );
 116     P( A, B, C, D, X[12],  3 );
 117     P( D, A, B, C, X[13],  7 );
 118     P( C, D, A, B, X[14], 11 );
 119     P( B, C, D, A, X[15], 19 );
 120
 121 #undef P
 122 #undef F
 123
 124 #define F(x,y,z) ((x & y) | (x & z) | (y & z))
 125 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x5A827999; a = S(a,s); }
 126
 127     P( A, B, C, D, X[ 0],  3 );
 128     P( D, A, B, C, X[ 4],  5 );
 129     P( C, D, A, B, X[ 8],  9 );
 130     P( B, C, D, A, X[12], 13 );
 131     P( A, B, C, D, X[ 1],  3 );
 132     P( D, A, B, C, X[ 5],  5 );
 133     P( C, D, A, B, X[ 9],  9 );
 134     P( B, C, D, A, X[13], 13 );
 135     P( A, B, C, D, X[ 2],  3 );
 136     P( D, A, B, C, X[ 6],  5 );
 137     P( C, D, A, B, X[10],  9 );
 138     P( B, C, D, A, X[14], 13 );
 139     P( A, B, C, D, X[ 3],  3 );
 140     P( D, A, B, C, X[ 7],  5 );
 141     P( C, D, A, B, X[11],  9 );
 142     P( B, C, D, A, X[15], 13 );
 143
 144 #undef P
 145 #undef F
 146
 147 #define F(x,y,z) (x ^ y ^ z)
 148 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x6ED9EBA1; a = S(a,s); }
 149
 150     P( A, B, C, D, X[ 0],  3 );
 151     P( D, A, B, C, X[ 8],  9 );
 152     P( C, D, A, B, X[ 4], 11 );
 153     P( B, C, D, A, X[12], 15 );
 154     P( A, B, C, D, X[ 2],  3 );
 155     P( D, A, B, C, X[10],  9 );
 156     P( C, D, A, B, X[ 6], 11 );
 157     P( B, C, D, A, X[14], 15 );
 158     P( A, B, C, D, X[ 1],  3 );
 159     P( D, A, B, C, X[ 9],  9 );
 160     P( C, D, A, B, X[ 5], 11 );
 161     P( B, C, D, A, X[13], 15 );
 162     P( A, B, C, D, X[ 3],  3 );
 163     P( D, A, B, C, X[11],  9 );
 164     P( C, D, A, B, X[ 7], 11 );
 165     P( B, C, D, A, X[15], 15 );
 166
 167 #undef F
 168 #undef P
 169
 170     ctx->state[0] += A;
 171     ctx->state[1] += B;
 172     ctx->state[2] += C;
 173     ctx->state[3] += D;
 174 }
 175
 176 /*
 177  * MD4 process buffer
 178  */
 179 void md4_update( md4_context *ctx, unsigned char *input, int ilen )
 180 {
 181     int fill;
 182     unsigned long left;
 183
 184     if( ilen <= 0 )
 185         return;
 186
 187     left = ctx->total[0] & 0x3F;
 188     fill = 64 - left;
 189
 190     ctx->total[0] += ilen;
 191     ctx->total[0] &= 0xFFFFFFFF;
 192
 193     if( ctx->total[0] < (unsigned long) ilen )
 194         ctx->total[1]++;
 195
 196     if( left && ilen >= fill )
 197     {
 198         memcpy( (void *) (ctx->buffer + left),
 199                 (void *) input, fill );
 200         md4_process( ctx, ctx->buffer );
 201         input += fill;
 202         ilen  -= fill;
 203         left = 0;
 204     }
 205
 206     while( ilen >= 64 )
 207     {
 208         md4_process( ctx, input );
 209         input += 64;
 210         ilen  -= 64;
 211     }
 212
 213     if( ilen > 0 )
 214     {
 215         memcpy( (void *) (ctx->buffer + left),
 216                 (void *) input, ilen );
 217     }
 218 }
 219
 220 static const unsigned char md4_padding[64] =
 221 {
 222  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 223     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 224     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 225     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 226 };
 227
 228 /*
 229  * MD4 final digest
 230  */
 231 void md4_finish( md4_context *ctx, unsigned char *output )
 232 {
 233     unsigned long last, padn;
 234     unsigned long high, low;
 235     unsigned char msglen[8];
 236
 237     high = ( ctx->total[0] >> 29 )
 238          | ( ctx->total[1] <<  3 );
 239     low  = ( ctx->total[0] <<  3 );
 240
 241     PUT_UINT32_LE( low,  msglen, 0 );
 242     PUT_UINT32_LE( high, msglen, 4 );
 243
 244     last = ctx->total[0] & 0x3F;
 245     padn = ( last < 56 ) ? ( 56 - last ) : ( 120 - last );
 246
 247     md4_update( ctx, (unsigned char *) md4_padding, padn );
 248     md4_update( ctx, msglen, 8 );
 249
 250     PUT_UINT32_LE( ctx->state[0], output,  0 );
 251     PUT_UINT32_LE( ctx->state[1], output,  4 );
 252     PUT_UINT32_LE( ctx->state[2], output,  8 );
 253     PUT_UINT32_LE( ctx->state[3], output, 12 );
 254 }
 255
 256 /*
 257  * Output = MD4( input buffer )
 258  */
 259 void md4( unsigned char *input, int ilen,
 260           unsigned char *output )
 261 {
 262     md4_context ctx;
 263
 264     md4_starts( &ctx );
 265     md4_update( &ctx, input, ilen );
 266     md4_finish( &ctx, output );
 267
 268     memset( &ctx, 0, sizeof( md4_context ) );
 269 }
 270
 271 /*
 272  * Output = MD4( file contents )
 273  */
 274 int md4_file( char *path, unsigned char *output )
 275 {
 276     FILE *f;
 277     size_t n;
 278     md4_context ctx;
 279     unsigned char buf[1024];
 280
 281     if( ( f = fopen( path, "rb" ) ) == NULL )
 282         return( 1 );
 283
 284     md4_starts( &ctx );
 285
 286     while( ( n = fread( buf, 1, sizeof( buf ), f ) ) > 0 )
 287         md4_update( &ctx, buf, (int) n );
 288
 289     md4_finish( &ctx, output );
 290
 291     memset( &ctx, 0, sizeof( md4_context ) );
 292
 293     if( ferror( f ) != 0 )
 294     {
 295         fclose( f );
 296         return( 2 );
 297     }
 298
 299     fclose( f );
 300     return( 0 );
 301 }
 302
 303 /*
 304  * MD4 HMAC context setup
 305  */
 306 void md4_hmac_starts( md4_context *ctx,
 307                       unsigned char *key, int keylen )
 308 {
 309     int i;
 310
 311     memset( ctx->ipad, 0x36, 64 );
 312     memset( ctx->opad, 0x5C, 64 );
 313
 314     for( i = 0; i < keylen; i++ )
 315     {
 316         if( i >= 64 ) break;
 317
 318         ctx->ipad[i] ^= key[i];
 319         ctx->opad[i] ^= key[i];
 320     }
 321
 322     md4_starts( ctx );
 323     md4_update( ctx, ctx->ipad, 64 );
 324 }
 325
 326 /*
 327  * MD4 HMAC process buffer
 328  */
 329 void md4_hmac_update( md4_context *ctx,
 330                       unsigned char *input, int ilen )
 331 {
 332     md4_update( ctx, input, ilen );
 333 }
 334
 335 /*
 336  * MD4 HMAC final digest
 337  */
 338 void md4_hmac_finish( md4_context *ctx, unsigned char *output )
 339 {
 340     unsigned char tmpbuf[16];
 341
 342     md4_finish( ctx, tmpbuf );
 343     md4_starts( ctx );
 344     md4_update( ctx, ctx->opad, 64 );
 345     md4_update( ctx, tmpbuf, 16 );
 346     md4_finish( ctx, output );
 347
 348     memset( tmpbuf, 0, sizeof( tmpbuf ) );
 349 }
 350
 351 /*
 352  * Output = HMAC-MD4( hmac key, input buffer )
 353  */
 354 void md4_hmac( unsigned char *key, int keylen,
 355                unsigned char *input, int ilen,
 356                unsigned char *output )
 357 {
 358     md4_context ctx;
 359
 360     md4_hmac_starts( &ctx, key, keylen );
 361     md4_hmac_update( &ctx, input, ilen );
 362     md4_hmac_finish( &ctx, output );
 363
 364     memset( &ctx, 0, sizeof( md4_context ) );
 365 }
 366
 367 static const char _md4_src[] = "_md4_src";
 368
 369 #if defined(SELF_TEST)
 370 /*
 371  * RFC 1320 test vectors
 372  */
 373 static const char md4_test_str[7][81] =
 374 {
 375     { "" },
 376     { "a" },
 377     { "abc" },
 378     { "message digest" },
 379     { "abcdefghijklmnopqrstuvwxyz" },
 380     { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" },
 381     { "12345678901234567890123456789012345678901234567890123456789012" \
 382       "345678901234567890" }
 383 };
 384
 385 static const unsigned char md4_test_sum[7][16] =
 386 {
 387     { 0x31, 0xD6, 0xCF, 0xE0, 0xD1, 0x6A, 0xE9, 0x31,
 388       0xB7, 0x3C, 0x59, 0xD7, 0xE0, 0xC0, 0x89, 0xC0 },
 389     { 0xBD, 0xE5, 0x2C, 0xB3, 0x1D, 0xE3, 0x3E, 0x46,
 390       0x24, 0x5E, 0x05, 0xFB, 0xDB, 0xD6, 0xFB, 0x24 },
 391     { 0xA4, 0x48, 0x01, 0x7A, 0xAF, 0x21, 0xD8, 0x52,
 392       0x5F, 0xC1, 0x0A, 0xE8, 0x7A, 0xA6, 0x72, 0x9D },
 393     { 0xD9, 0x13, 0x0A, 0x81, 0x64, 0x54, 0x9F, 0xE8,
 394       0x18, 0x87, 0x48, 0x06, 0xE1, 0xC7, 0x01, 0x4B },
 395     { 0xD7, 0x9E, 0x1C, 0x30, 0x8A, 0xA5, 0xBB, 0xCD,
 396       0xEE, 0xA8, 0xED, 0x63, 0xDF, 0x41, 0x2D, 0xA9 },
 397     { 0x04, 0x3F, 0x85, 0x82, 0xF2, 0x41, 0xDB, 0x35,
 398       0x1C, 0xE6, 0x27, 0xE1, 0x53, 0xE7, 0xF0, 0xE4 },
 399     { 0xE3, 0x3B, 0x4D, 0xDC, 0x9C, 0x38, 0xF2, 0x19,
 400       0x9C, 0x3E, 0x7B, 0x16, 0x4F, 0xCC, 0x05, 0x36 }
 401 };
 402
 403 /*
 404  * Checkup routine
 405  */
 406 int md4_self_test( int verbose )
 407 {
 408     int i;
 409     unsigned char md4sum[16];
 410
 411     for( i = 0; i < 7; i++ )
 412     {
 413         if( verbose != 0 )
 414             printf( "  MD4 test #%d: ", i + 1 );
 415
 416         md4( (unsigned char *) md4_test_str[i],
 417              strlen( md4_test_str[i] ), md4sum );
 418
 419         if( memcmp( md4sum, md4_test_sum[i], 16 ) != 0 )
 420         {
 421             if( verbose != 0 )
 422                 printf( "failed\n" );
 423
 424             return( 1 );
 425         }
 426
 427         if( verbose != 0 )
 428             printf( "passed\n" );
 429     }
 430
 431     if( verbose != 0 )
 432         printf( "\n" );
 433
 434     return( 0 );
 435 }
 436 #else
 437 int md4_self_test( int verbose )
 438 {
 439     return( 0 );
 440 }
 441 #endif