library/md4.c

   1 /*
   2  *      RFC 1186/1320 compliant MD4 implementation
   3  *
   4  *      Based on XySSL: Copyright (C) 2006-2008  Christophe Devine
   5  *
   6  *      Copyright (C) 2009      Paul Bakker <polarssl_maintainer at polarssl dot org>
   7  *
   8  *      All rights reserved.
   9  *
  10  *      Redistribution and use in source and binary forms, with or without
  11  *      modification, are permitted provided that the following conditions
  12  *      are met:
  13  *
  14  *        * Redistributions of source code must retain the above copyright
  15  *              notice, this list of conditions and the following disclaimer.
  16  *        * Redistributions in binary form must reproduce the above copyright
  17  *              notice, this list of conditions and the following disclaimer in the
  18  *              documentation and/or other materials provided with the distribution.
  19  *        * Neither the names of PolarSSL or XySSL nor the names of its contributors
  20  *              may be used to endorse or promote products derived from this software
  21  *              without specific prior written permission.
  22  *
  23  *      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  *      "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  *      LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  *      FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  *      OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  *      SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  *      TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  *      PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  *      LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  *      NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  *      SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 /*
  36  *      The MD4 algorithm was designed by Ron Rivest in 1990.
  37  *
  38  *      http://www.ietf.org/rfc/rfc1186.txt
  39  *      http://www.ietf.org/rfc/rfc1320.txt
  40  */
  41
  42 #include "tropicssl/config.h"
  43
  44 #if defined(TROPICSSL_MD4_C)
  45
  46 #include "tropicssl/md4.h"
  47
  48 #include <string.h>
  49 #include <stdio.h>
  50
  51 /*
  52  * 32-bit integer manipulation macros (little endian)
  53  */
  54 #ifndef GET_ULONG_LE
  55 #define GET_ULONG_LE(n,b,i)                                                             \
  56         {                                                                                                       \
  57                 (n) = ( (unsigned long) (b)[(i)    ]       )    \
  58                         | ( (unsigned long) (b)[(i) + 1] <<      8 )    \
  59                         | ( (unsigned long) (b)[(i) + 2] << 16 )        \
  60                         | ( (unsigned long) (b)[(i) + 3] << 24 );       \
  61         }
  62 #endif
  63
  64 #ifndef PUT_ULONG_LE
  65 #define PUT_ULONG_LE(n,b,i)                                                             \
  66         {                                                                                                       \
  67                 (b)[(i)    ] = (unsigned char) ( (n)       );   \
  68                 (b)[(i) + 1] = (unsigned char) ( (n) >>  8 );   \
  69                 (b)[(i) + 2] = (unsigned char) ( (n) >> 16 );   \
  70                 (b)[(i) + 3] = (unsigned char) ( (n) >> 24 );   \
  71         }
  72 #endif
  73
  74 /*
  75  * MD4 context setup
  76  */
  77 void md4_starts(md4_context * ctx)
  78 {
  79         ctx->total[0] = 0;
  80         ctx->total[1] = 0;
  81
  82         ctx->state[0] = 0x67452301;
  83         ctx->state[1] = 0xEFCDAB89;
  84         ctx->state[2] = 0x98BADCFE;
  85         ctx->state[3] = 0x10325476;
  86 }
  87
  88 static void md4_process(md4_context * ctx, const unsigned char data[64])
  89 {
  90         unsigned long X[16], A, B, C, D;
  91
  92         GET_ULONG_LE(X[0], data, 0);
  93         GET_ULONG_LE(X[1], data, 4);
  94         GET_ULONG_LE(X[2], data, 8);
  95         GET_ULONG_LE(X[3], data, 12);
  96         GET_ULONG_LE(X[4], data, 16);
  97         GET_ULONG_LE(X[5], data, 20);
  98         GET_ULONG_LE(X[6], data, 24);
  99         GET_ULONG_LE(X[7], data, 28);
 100         GET_ULONG_LE(X[8], data, 32);
 101         GET_ULONG_LE(X[9], data, 36);
 102         GET_ULONG_LE(X[10], data, 40);
 103         GET_ULONG_LE(X[11], data, 44);
 104         GET_ULONG_LE(X[12], data, 48);
 105         GET_ULONG_LE(X[13], data, 52);
 106         GET_ULONG_LE(X[14], data, 56);
 107         GET_ULONG_LE(X[15], data, 60);
 108
 109 #define S(x,n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
 110
 111         A = ctx->state[0];
 112         B = ctx->state[1];
 113         C = ctx->state[2];
 114         D = ctx->state[3];
 115
 116 #define F(x, y, z) ((x & y) | ((~x) & z))
 117 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x; a = S(a,s); }
 118
 119         P(A, B, C, D, X[0], 3);
 120         P(D, A, B, C, X[1], 7);
 121         P(C, D, A, B, X[2], 11);
 122         P(B, C, D, A, X[3], 19);
 123         P(A, B, C, D, X[4], 3);
 124         P(D, A, B, C, X[5], 7);
 125         P(C, D, A, B, X[6], 11);
 126         P(B, C, D, A, X[7], 19);
 127         P(A, B, C, D, X[8], 3);
 128         P(D, A, B, C, X[9], 7);
 129         P(C, D, A, B, X[10], 11);
 130         P(B, C, D, A, X[11], 19);
 131         P(A, B, C, D, X[12], 3);
 132         P(D, A, B, C, X[13], 7);
 133         P(C, D, A, B, X[14], 11);
 134         P(B, C, D, A, X[15], 19);
 135
 136 #undef P
 137 #undef F
 138
 139 #define F(x,y,z) ((x & y) | (x & z) | (y & z))
 140 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x5A827999; a = S(a,s); }
 141
 142         P(A, B, C, D, X[0], 3);
 143         P(D, A, B, C, X[4], 5);
 144         P(C, D, A, B, X[8], 9);
 145         P(B, C, D, A, X[12], 13);
 146         P(A, B, C, D, X[1], 3);
 147         P(D, A, B, C, X[5], 5);
 148         P(C, D, A, B, X[9], 9);
 149         P(B, C, D, A, X[13], 13);
 150         P(A, B, C, D, X[2], 3);
 151         P(D, A, B, C, X[6], 5);
 152         P(C, D, A, B, X[10], 9);
 153         P(B, C, D, A, X[14], 13);
 154         P(A, B, C, D, X[3], 3);
 155         P(D, A, B, C, X[7], 5);
 156         P(C, D, A, B, X[11], 9);
 157         P(B, C, D, A, X[15], 13);
 158
 159 #undef P
 160 #undef F
 161
 162 #define F(x,y,z) (x ^ y ^ z)
 163 #define P(a,b,c,d,x,s) { a += F(b,c,d) + x + 0x6ED9EBA1; a = S(a,s); }
 164
 165         P(A, B, C, D, X[0], 3);
 166         P(D, A, B, C, X[8], 9);
 167         P(C, D, A, B, X[4], 11);
 168         P(B, C, D, A, X[12], 15);
 169         P(A, B, C, D, X[2], 3);
 170         P(D, A, B, C, X[10], 9);
 171         P(C, D, A, B, X[6], 11);
 172         P(B, C, D, A, X[14], 15);
 173         P(A, B, C, D, X[1], 3);
 174         P(D, A, B, C, X[9], 9);
 175         P(C, D, A, B, X[5], 11);
 176         P(B, C, D, A, X[13], 15);
 177         P(A, B, C, D, X[3], 3);
 178         P(D, A, B, C, X[11], 9);
 179         P(C, D, A, B, X[7], 11);
 180         P(B, C, D, A, X[15], 15);
 181
 182 #undef F
 183 #undef P
 184
 185         ctx->state[0] += A;
 186         ctx->state[1] += B;
 187         ctx->state[2] += C;
 188         ctx->state[3] += D;
 189 }
 190
 191 /*
 192  * MD4 process buffer
 193  */
 194 void md4_update(md4_context * ctx, const unsigned char *input, int ilen)
 195 {
 196         int fill;
 197         unsigned long left;
 198
 199         if (ilen <= 0)
 200                 return;
 201
 202         left = ctx->total[0] & 0x3F;
 203         fill = 64 - left;
 204
 205         ctx->total[0] += ilen;
 206         ctx->total[0] &= 0xFFFFFFFF;
 207
 208         if (ctx->total[0] < (unsigned long)ilen)
 209                 ctx->total[1]++;
 210
 211         if (left && ilen >= fill) {
 212                 memcpy((void *)(ctx->buffer + left), (const void *)input, fill);
 213                 md4_process(ctx, ctx->buffer);
 214                 input += fill;
 215                 ilen -= fill;
 216                 left = 0;
 217         }
 218
 219         while (ilen >= 64) {
 220                 md4_process(ctx, input);
 221                 input += 64;
 222                 ilen -= 64;
 223         }
 224
 225         if (ilen > 0) {
 226                 memcpy((void *)(ctx->buffer + left), (const void *)input, ilen);
 227         }
 228 }
 229
 230 static const unsigned char md4_padding[64] = {
 231         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 232         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 233         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 234         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 235 };
 236
 237 /*
 238  * MD4 final digest
 239  */
 240 void md4_finish(md4_context * ctx, unsigned char output[16])
 241 {
 242         unsigned long last, padn;
 243         unsigned long high, low;
 244         unsigned char msglen[8];
 245
 246         high = (ctx->total[0] >> 29)
 247             | (ctx->total[1] << 3);
 248         low = (ctx->total[0] << 3);
 249
 250         PUT_ULONG_LE(low, msglen, 0);
 251         PUT_ULONG_LE(high, msglen, 4);
 252
 253         last = ctx->total[0] & 0x3F;
 254         padn = (last < 56) ? (56 - last) : (120 - last);
 255
 256         md4_update(ctx, md4_padding, padn);
 257         md4_update(ctx, msglen, 8);
 258
 259         PUT_ULONG_LE(ctx->state[0], output, 0);
 260         PUT_ULONG_LE(ctx->state[1], output, 4);
 261         PUT_ULONG_LE(ctx->state[2], output, 8);
 262         PUT_ULONG_LE(ctx->state[3], output, 12);
 263 }
 264
 265 /*
 266  * output = MD4( input buffer )
 267  */
 268 void md4(const unsigned char *input, int ilen, unsigned char output[16])
 269 {
 270         md4_context ctx;
 271
 272         md4_starts(&ctx);
 273         md4_update(&ctx, input, ilen);
 274         md4_finish(&ctx, output);
 275
 276         memset(&ctx, 0, sizeof(md4_context));
 277 }
 278
 279 /*
 280  * output = MD4( file contents )
 281  */
 282 int md4_file(const char *path, unsigned char output[16])
 283 {
 284         FILE *f;
 285         size_t n;
 286         md4_context ctx;
 287         unsigned char buf[1024];
 288
 289         if ((f = fopen(path, "rb")) == NULL)
 290                 return (1);
 291
 292         md4_starts(&ctx);
 293
 294         while ((n = fread(buf, 1, sizeof(buf), f)) > 0)
 295                 md4_update(&ctx, buf, (int)n);
 296
 297         md4_finish(&ctx, output);
 298
 299         memset(&ctx, 0, sizeof(md4_context));
 300
 301         if (ferror(f) != 0) {
 302                 fclose(f);
 303                 return (2);
 304         }
 305
 306         fclose(f);
 307         return (0);
 308 }
 309
 310 /*
 311  * MD4 HMAC context setup
 312  */
 313 void md4_hmac_starts(md4_context * ctx, const unsigned char *key, int keylen)
 314 {
 315         int i;
 316         unsigned char sum[16];
 317
 318         if (keylen > 64) {
 319                 md4(key, keylen, sum);
 320                 keylen = 16;
 321                 key = sum;
 322         }
 323
 324         memset(ctx->ipad, 0x36, 64);
 325         memset(ctx->opad, 0x5C, 64);
 326
 327         for (i = 0; i < keylen; i++) {
 328                 ctx->ipad[i] = (unsigned char)(ctx->ipad[i] ^ key[i]);
 329                 ctx->opad[i] = (unsigned char)(ctx->opad[i] ^ key[i]);
 330         }
 331
 332         md4_starts(ctx);
 333         md4_update(ctx, ctx->ipad, 64);
 334
 335         memset(sum, 0, sizeof(sum));
 336 }
 337
 338 /*
 339  * MD4 HMAC process buffer
 340  */
 341 void md4_hmac_update(md4_context * ctx, const unsigned char *input, int ilen)
 342 {
 343         md4_update(ctx, input, ilen);
 344 }
 345
 346 /*
 347  * MD4 HMAC final digest
 348  */
 349 void md4_hmac_finish(md4_context * ctx, unsigned char output[16])
 350 {
 351         unsigned char tmpbuf[16];
 352
 353         md4_finish(ctx, tmpbuf);
 354         md4_starts(ctx);
 355         md4_update(ctx, ctx->opad, 64);
 356         md4_update(ctx, tmpbuf, 16);
 357         md4_finish(ctx, output);
 358
 359         memset(tmpbuf, 0, sizeof(tmpbuf));
 360 }
 361
 362 /*
 363  * output = HMAC-MD4( hmac key, input buffer )
 364  */
 365 void md4_hmac(const unsigned char *key, int keylen,
 366               const unsigned char *input, int ilen,
 367               unsigned char output[16])
 368 {
 369         md4_context ctx;
 370
 371         md4_hmac_starts(&ctx, key, keylen);
 372         md4_hmac_update(&ctx, input, ilen);
 373         md4_hmac_finish(&ctx, output);
 374
 375         memset(&ctx, 0, sizeof(md4_context));
 376 }
 377
 378 #if defined(TROPICSSL_SELF_TEST)
 379
 380 /*
 381  * RFC 1320 test vectors
 382  */
 383 static const char md4_test_str[7][81] = {
 384         {""},
 385         {"a"},
 386         {"abc"},
 387         {"message digest"},
 388         {"abcdefghijklmnopqrstuvwxyz"},
 389         {"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"},
 390         {
 391          "12345678901234567890123456789012345678901234567890123456789012"
 392          "345678901234567890"}
 393 };
 394
 395 static const unsigned char md4_test_sum[7][16] = {
 396         {
 397          0x31, 0xD6, 0xCF, 0xE0, 0xD1, 0x6A, 0xE9, 0x31,
 398          0xB7, 0x3C, 0x59, 0xD7, 0xE0, 0xC0, 0x89, 0xC0},
 399         {
 400          0xBD, 0xE5, 0x2C, 0xB3, 0x1D, 0xE3, 0x3E, 0x46,
 401          0x24, 0x5E, 0x05, 0xFB, 0xDB, 0xD6, 0xFB, 0x24},
 402         {
 403          0xA4, 0x48, 0x01, 0x7A, 0xAF, 0x21, 0xD8, 0x52,
 404          0x5F, 0xC1, 0x0A, 0xE8, 0x7A, 0xA6, 0x72, 0x9D},
 405         {
 406          0xD9, 0x13, 0x0A, 0x81, 0x64, 0x54, 0x9F, 0xE8,
 407          0x18, 0x87, 0x48, 0x06, 0xE1, 0xC7, 0x01, 0x4B},
 408         {
 409          0xD7, 0x9E, 0x1C, 0x30, 0x8A, 0xA5, 0xBB, 0xCD,
 410          0xEE, 0xA8, 0xED, 0x63, 0xDF, 0x41, 0x2D, 0xA9},
 411         {
 412          0x04, 0x3F, 0x85, 0x82, 0xF2, 0x41, 0xDB, 0x35,
 413          0x1C, 0xE6, 0x27, 0xE1, 0x53, 0xE7, 0xF0, 0xE4},
 414         {
 415          0xE3, 0x3B, 0x4D, 0xDC, 0x9C, 0x38, 0xF2, 0x19,
 416          0x9C, 0x3E, 0x7B, 0x16, 0x4F, 0xCC, 0x05, 0x36}
 417 };
 418
 419 /*
 420  * Checkup routine
 421  */
 422 int md4_self_test(int verbose)
 423 {
 424         int i;
 425         unsigned char md4sum[16];
 426
 427         for (i = 0; i < 7; i++) {
 428                 if (verbose != 0)
 429                         printf("  MD4 test #%d: ", i + 1);
 430
 431                 md4((const unsigned char *)md4_test_str[i],
 432                     strlen(md4_test_str[i]), md4sum);
 433
 434                 if (memcmp(md4sum, md4_test_sum[i], 16) != 0) {
 435                         if (verbose != 0)
 436                                 printf("failed\n");
 437
 438                         return (1);
 439                 }
 440
 441                 if (verbose != 0)
 442                         printf("passed\n");
 443         }
 444
 445         if (verbose != 0)
 446                 printf("\n");
 447
 448         return (0);
 449 }
 450
 451 #endif
 452
 453 #endif