lib/md4.c

   1 /*
   2  * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc.
   3  * MD4 Message-Digest Algorithm (RFC 1320).
   4  *
   5  * Homepage:
   6  http://openwall.info/wiki/people/solar/software/public-domain-source-code/md4
   7  *
   8  * Author:
   9  * Alexander Peslyak, better known as Solar Designer <solar at openwall.com>
  10  *
  11  * This software was written by Alexander Peslyak in 2001.  No copyright is
  12  * claimed, and the software is hereby placed in the public domain.  In case
  13  * this attempt to disclaim copyright and place the software in the public
  14  * domain is deemed null and void, then the software is Copyright (c) 2001
  15  * Alexander Peslyak and it is hereby released to the general public under the
  16  * following terms:
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted.
  20  *
  21  * There's ABSOLUTELY NO WARRANTY, express or implied.
  22  *
  23  * (This is a heavily cut-down "BSD license".)
  24  *
  25  * This differs from Colin Plumb's older public domain implementation in that
  26  * no exactly 32-bit integer data type is required (any 32-bit or wider
  27  * unsigned integer data type will do), there's no compile-time endianness
  28  * configuration, and the function prototypes match OpenSSL's.  No code from
  29  * Colin Plumb's implementation has been reused; this comment merely compares
  30  * the properties of the two independent implementations.
  31  *
  32  * The primary goals of this implementation are portability and ease of use.
  33  * It is meant to be fast, but not as fast as possible.  Some known
  34  * optimizations are not included to reduce source code size and avoid
  35  * compile-time configuration.
  36  */
  37
  38 #include "curl_setup.h"
  39
  40 /* The NSS, OS/400 and sometimes mbed TLS crypto libraries do not provide the
  41  * MD4 hash algorithm, so we have a local implementation of it */
  42 #if defined(USE_NSS) || defined(USE_OS400CRYPTO) || \
  43     (defined(USE_MBEDTLS) && !defined(MBEDTLS_MD4_C))
  44
  45 #include "curl_md4.h"
  46 #include "warnless.h"
  47
  48 #ifndef HAVE_OPENSSL
  49
  50 #include <string.h>
  51
  52 /* Any 32-bit or wider unsigned integer data type will do */
  53 typedef unsigned int MD4_u32plus;
  54
  55 typedef struct {
  56   MD4_u32plus lo, hi;
  57   MD4_u32plus a, b, c, d;
  58   unsigned char buffer[64];
  59   MD4_u32plus block[16];
  60 } MD4_CTX;
  61
  62 static void MD4_Init(MD4_CTX *ctx);
  63 static void MD4_Update(MD4_CTX *ctx, const void *data, unsigned long size);
  64 static void MD4_Final(unsigned char *result, MD4_CTX *ctx);
  65
  66 /*
  67  * The basic MD4 functions.
  68  *
  69  * F and G are optimized compared to their RFC 1320 definitions, with the
  70  * optimization for F borrowed from Colin Plumb's MD5 implementation.
  71  */
  72 #define F(x, y, z)                      ((z) ^ ((x) & ((y) ^ (z))))
  73 #define G(x, y, z)                      (((x) & ((y) | (z))) | ((y) & (z)))
  74 #define H(x, y, z)                      ((x) ^ (y) ^ (z))
  75
  76 /*
  77  * The MD4 transformation for all three rounds.
  78  */
  79 #define STEP(f, a, b, c, d, x, s) \
  80         (a) += f((b), (c), (d)) + (x); \
  81         (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s))));
  82
  83 /*
  84  * SET reads 4 input bytes in little-endian byte order and stores them
  85  * in a properly aligned word in host byte order.
  86  *
  87  * The check for little-endian architectures that tolerate unaligned
  88  * memory accesses is just an optimization.  Nothing will break if it
  89  * doesn't work.
  90  */
  91 #if defined(__i386__) || defined(__x86_64__) || defined(__vax__)
  92 #define SET(n) \
  93         (*(MD4_u32plus *)(void *)&ptr[(n) * 4])
  94 #define GET(n) \
  95         SET(n)
  96 #else
  97 #define SET(n) \
  98         (ctx->block[(n)] = \
  99         (MD4_u32plus)ptr[(n) * 4] | \
 100         ((MD4_u32plus)ptr[(n) * 4 + 1] << 8) | \
 101         ((MD4_u32plus)ptr[(n) * 4 + 2] << 16) | \
 102         ((MD4_u32plus)ptr[(n) * 4 + 3] << 24))
 103 #define GET(n) \
 104         (ctx->block[(n)])
 105 #endif
 106
 107 /*
 108  * This processes one or more 64-byte data blocks, but does NOT update
 109  * the bit counters.  There are no alignment requirements.
 110  */
 111 static const void *body(MD4_CTX *ctx, const void *data, unsigned long size)
 112 {
 113   const unsigned char *ptr;
 114   MD4_u32plus a, b, c, d;
 115   MD4_u32plus saved_a, saved_b, saved_c, saved_d;
 116
 117   ptr = (const unsigned char *)data;
 118
 119   a = ctx->a;
 120   b = ctx->b;
 121   c = ctx->c;
 122   d = ctx->d;
 123
 124   do {
 125     saved_a = a;
 126     saved_b = b;
 127     saved_c = c;
 128     saved_d = d;
 129
 130 /* Round 1 */
 131     STEP(F, a, b, c, d, SET(0), 3)
 132       STEP(F, d, a, b, c, SET(1), 7)
 133       STEP(F, c, d, a, b, SET(2), 11)
 134       STEP(F, b, c, d, a, SET(3), 19)
 135       STEP(F, a, b, c, d, SET(4), 3)
 136       STEP(F, d, a, b, c, SET(5), 7)
 137       STEP(F, c, d, a, b, SET(6), 11)
 138       STEP(F, b, c, d, a, SET(7), 19)
 139       STEP(F, a, b, c, d, SET(8), 3)
 140       STEP(F, d, a, b, c, SET(9), 7)
 141       STEP(F, c, d, a, b, SET(10), 11)
 142       STEP(F, b, c, d, a, SET(11), 19)
 143       STEP(F, a, b, c, d, SET(12), 3)
 144       STEP(F, d, a, b, c, SET(13), 7)
 145       STEP(F, c, d, a, b, SET(14), 11)
 146       STEP(F, b, c, d, a, SET(15), 19)
 147
 148 /* Round 2 */
 149       STEP(G, a, b, c, d, GET(0) + 0x5a827999, 3)
 150       STEP(G, d, a, b, c, GET(4) + 0x5a827999, 5)
 151       STEP(G, c, d, a, b, GET(8) + 0x5a827999, 9)
 152       STEP(G, b, c, d, a, GET(12) + 0x5a827999, 13)
 153       STEP(G, a, b, c, d, GET(1) + 0x5a827999, 3)
 154       STEP(G, d, a, b, c, GET(5) + 0x5a827999, 5)
 155       STEP(G, c, d, a, b, GET(9) + 0x5a827999, 9)
 156       STEP(G, b, c, d, a, GET(13) + 0x5a827999, 13)
 157       STEP(G, a, b, c, d, GET(2) + 0x5a827999, 3)
 158       STEP(G, d, a, b, c, GET(6) + 0x5a827999, 5)
 159       STEP(G, c, d, a, b, GET(10) + 0x5a827999, 9)
 160       STEP(G, b, c, d, a, GET(14) + 0x5a827999, 13)
 161       STEP(G, a, b, c, d, GET(3) + 0x5a827999, 3)
 162       STEP(G, d, a, b, c, GET(7) + 0x5a827999, 5)
 163       STEP(G, c, d, a, b, GET(11) + 0x5a827999, 9)
 164       STEP(G, b, c, d, a, GET(15) + 0x5a827999, 13)
 165
 166 /* Round 3 */
 167       STEP(H, a, b, c, d, GET(0) + 0x6ed9eba1, 3)
 168       STEP(H, d, a, b, c, GET(8) + 0x6ed9eba1, 9)
 169       STEP(H, c, d, a, b, GET(4) + 0x6ed9eba1, 11)
 170       STEP(H, b, c, d, a, GET(12) + 0x6ed9eba1, 15)
 171       STEP(H, a, b, c, d, GET(2) + 0x6ed9eba1, 3)
 172       STEP(H, d, a, b, c, GET(10) + 0x6ed9eba1, 9)
 173       STEP(H, c, d, a, b, GET(6) + 0x6ed9eba1, 11)
 174       STEP(H, b, c, d, a, GET(14) + 0x6ed9eba1, 15)
 175       STEP(H, a, b, c, d, GET(1) + 0x6ed9eba1, 3)
 176       STEP(H, d, a, b, c, GET(9) + 0x6ed9eba1, 9)
 177       STEP(H, c, d, a, b, GET(5) + 0x6ed9eba1, 11)
 178       STEP(H, b, c, d, a, GET(13) + 0x6ed9eba1, 15)
 179       STEP(H, a, b, c, d, GET(3) + 0x6ed9eba1, 3)
 180       STEP(H, d, a, b, c, GET(11) + 0x6ed9eba1, 9)
 181       STEP(H, c, d, a, b, GET(7) + 0x6ed9eba1, 11)
 182       STEP(H, b, c, d, a, GET(15) + 0x6ed9eba1, 15)
 183
 184       a += saved_a;
 185     b += saved_b;
 186     c += saved_c;
 187     d += saved_d;
 188
 189     ptr += 64;
 190   } while(size -= 64);
 191
 192   ctx->a = a;
 193   ctx->b = b;
 194   ctx->c = c;
 195   ctx->d = d;
 196
 197   return ptr;
 198 }
 199
 200 static void MD4_Init(MD4_CTX *ctx)
 201 {
 202   ctx->a = 0x67452301;
 203   ctx->b = 0xefcdab89;
 204   ctx->c = 0x98badcfe;
 205   ctx->d = 0x10325476;
 206
 207   ctx->lo = 0;
 208   ctx->hi = 0;
 209 }
 210
 211 static void MD4_Update(MD4_CTX *ctx, const void *data, unsigned long size)
 212 {
 213   MD4_u32plus saved_lo;
 214   unsigned long used, available;
 215
 216   saved_lo = ctx->lo;
 217   ctx->lo = (saved_lo + size) & 0x1fffffff;
 218   if(ctx->lo < saved_lo)
 219     ctx->hi++;
 220   ctx->hi += (MD4_u32plus)size >> 29;
 221
 222   used = saved_lo & 0x3f;
 223
 224   if(used) {
 225     available = 64 - used;
 226
 227     if(size < available) {
 228       memcpy(&ctx->buffer[used], data, size);
 229       return;
 230     }
 231
 232     memcpy(&ctx->buffer[used], data, available);
 233     data = (const unsigned char *)data + available;
 234     size -= available;
 235     body(ctx, ctx->buffer, 64);
 236   }
 237
 238   if(size >= 64) {
 239     data = body(ctx, data, size & ~(unsigned long)0x3f);
 240     size &= 0x3f;
 241   }
 242
 243   memcpy(ctx->buffer, data, size);
 244 }
 245
 246 static void MD4_Final(unsigned char *result, MD4_CTX *ctx)
 247 {
 248   unsigned long used, available;
 249
 250   used = ctx->lo & 0x3f;
 251
 252   ctx->buffer[used++] = 0x80;
 253
 254   available = 64 - used;
 255
 256   if(available < 8) {
 257     memset(&ctx->buffer[used], 0, available);
 258     body(ctx, ctx->buffer, 64);
 259     used = 0;
 260     available = 64;
 261   }
 262
 263   memset(&ctx->buffer[used], 0, available - 8);
 264
 265   ctx->lo <<= 3;
 266   ctx->buffer[56] = curlx_ultouc((ctx->lo)&0xff);
 267   ctx->buffer[57] = curlx_ultouc((ctx->lo >> 8)&0xff);
 268   ctx->buffer[58] = curlx_ultouc((ctx->lo >> 16)&0xff);
 269   ctx->buffer[59] = curlx_ultouc((ctx->lo >> 24)&0xff);
 270   ctx->buffer[60] = curlx_ultouc((ctx->hi)&0xff);
 271   ctx->buffer[61] = curlx_ultouc((ctx->hi >> 8)&0xff);
 272   ctx->buffer[62] = curlx_ultouc((ctx->hi >> 16)&0xff);
 273   ctx->buffer[63] = curlx_ultouc(ctx->hi >> 24);
 274
 275   body(ctx, ctx->buffer, 64);
 276
 277   result[0] = curlx_ultouc((ctx->a)&0xff);
 278   result[1] = curlx_ultouc((ctx->a >> 8)&0xff);
 279   result[2] = curlx_ultouc((ctx->a >> 16)&0xff);
 280   result[3] = curlx_ultouc(ctx->a >> 24);
 281   result[4] = curlx_ultouc((ctx->b)&0xff);
 282   result[5] = curlx_ultouc((ctx->b >> 8)&0xff);
 283   result[6] = curlx_ultouc((ctx->b >> 16)&0xff);
 284   result[7] = curlx_ultouc(ctx->b >> 24);
 285   result[8] = curlx_ultouc((ctx->c)&0xff);
 286   result[9] = curlx_ultouc((ctx->c >> 8)&0xff);
 287   result[10] = curlx_ultouc((ctx->c >> 16)&0xff);
 288   result[11] = curlx_ultouc(ctx->c >> 24);
 289   result[12] = curlx_ultouc((ctx->d)&0xff);
 290   result[13] = curlx_ultouc((ctx->d >> 8)&0xff);
 291   result[14] = curlx_ultouc((ctx->d >> 16)&0xff);
 292   result[15] = curlx_ultouc(ctx->d >> 24);
 293
 294   memset(ctx, 0, sizeof(*ctx));
 295 }
 296
 297 #endif
 298
 299 void Curl_md4it(unsigned char *output, const unsigned char *input, size_t len)
 300 {
 301   MD4_CTX ctx;
 302   MD4_Init(&ctx);
 303   MD4_Update(&ctx, input, curlx_uztoui(len));
 304   MD4_Final(output, &ctx);
 305 }
 306 #endif /* defined(USE_NSS) || defined(USE_OS400CRYPTO) ||
 307     (defined(USE_MBEDTLS) && !defined(MBEDTLS_MD4_C)) */