Home | History | Annotate | Download | only in crypto
      1 /*
      2  * MD4 hash implementation
      3  * Copyright (c) 2006, Jouni Malinen <j (at) w1.fi>
      4  *
      5  * This program is free software; you can redistribute it and/or modify
      6  * it under the terms of the GNU General Public License version 2 as
      7  * published by the Free Software Foundation.
      8  *
      9  * Alternatively, this software may be distributed under the terms of BSD
     10  * license.
     11  *
     12  * See README and COPYING for more details.
     13  */
     14 
     15 #include "includes.h"
     16 
     17 #include "common.h"
     18 #include "crypto.h"
     19 
     20 
     21 #ifdef INTERNAL_MD4
     22 
     23 #define	MD4_BLOCK_LENGTH		64
     24 #define	MD4_DIGEST_LENGTH		16
     25 
     26 typedef struct MD4Context {
     27 	u32 state[4];			/* state */
     28 	u64 count;			/* number of bits, mod 2^64 */
     29 	u8 buffer[MD4_BLOCK_LENGTH];	/* input buffer */
     30 } MD4_CTX;
     31 
     32 
     33 static void MD4Init(MD4_CTX *ctx);
     34 static void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len);
     35 static void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx);
     36 
     37 
     38 void md4_vector(size_t num_elem, const u8 *addr[], const size_t *len, u8 *mac)
     39 {
     40 	MD4_CTX ctx;
     41 	size_t i;
     42 
     43 	MD4Init(&ctx);
     44 	for (i = 0; i < num_elem; i++)
     45 		MD4Update(&ctx, addr[i], len[i]);
     46 	MD4Final(mac, &ctx);
     47 }
     48 
     49 
     50 /* ===== start - public domain MD4 implementation ===== */
     51 /*	$OpenBSD: md4.c,v 1.7 2005/08/08 08:05:35 espie Exp $	*/
     52 
     53 /*
     54  * This code implements the MD4 message-digest algorithm.
     55  * The algorithm is due to Ron Rivest.	This code was
     56  * written by Colin Plumb in 1993, no copyright is claimed.
     57  * This code is in the public domain; do with it what you wish.
     58  * Todd C. Miller modified the MD5 code to do MD4 based on RFC 1186.
     59  *
     60  * Equivalent code is available from RSA Data Security, Inc.
     61  * This code has been tested against that, and is equivalent,
     62  * except that you don't need to include two pages of legalese
     63  * with every copy.
     64  *
     65  * To compute the message digest of a chunk of bytes, declare an
     66  * MD4Context structure, pass it to MD4Init, call MD4Update as
     67  * needed on buffers full of bytes, and then call MD4Final, which
     68  * will fill a supplied 16-byte array with the digest.
     69  */
     70 
     71 #define	MD4_DIGEST_STRING_LENGTH	(MD4_DIGEST_LENGTH * 2 + 1)
     72 
     73 
     74 static void
     75 MD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH]);
     76 
     77 #define PUT_64BIT_LE(cp, value) do {					\
     78 	(cp)[7] = (value) >> 56;					\
     79 	(cp)[6] = (value) >> 48;					\
     80 	(cp)[5] = (value) >> 40;					\
     81 	(cp)[4] = (value) >> 32;					\
     82 	(cp)[3] = (value) >> 24;					\
     83 	(cp)[2] = (value) >> 16;					\
     84 	(cp)[1] = (value) >> 8;						\
     85 	(cp)[0] = (value); } while (0)
     86 
     87 #define PUT_32BIT_LE(cp, value) do {					\
     88 	(cp)[3] = (value) >> 24;					\
     89 	(cp)[2] = (value) >> 16;					\
     90 	(cp)[1] = (value) >> 8;						\
     91 	(cp)[0] = (value); } while (0)
     92 
     93 static u8 PADDING[MD4_BLOCK_LENGTH] = {
     94 	0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     95 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
     96 	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
     97 };
     98 
     99 /*
    100  * Start MD4 accumulation.
    101  * Set bit count to 0 and buffer to mysterious initialization constants.
    102  */
    103 static void MD4Init(MD4_CTX *ctx)
    104 {
    105 	ctx->count = 0;
    106 	ctx->state[0] = 0x67452301;
    107 	ctx->state[1] = 0xefcdab89;
    108 	ctx->state[2] = 0x98badcfe;
    109 	ctx->state[3] = 0x10325476;
    110 }
    111 
    112 /*
    113  * Update context to reflect the concatenation of another buffer full
    114  * of bytes.
    115  */
    116 static void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len)
    117 {
    118 	size_t have, need;
    119 
    120 	/* Check how many bytes we already have and how many more we need. */
    121 	have = (size_t)((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1));
    122 	need = MD4_BLOCK_LENGTH - have;
    123 
    124 	/* Update bitcount */
    125 	ctx->count += (u64)len << 3;
    126 
    127 	if (len >= need) {
    128 		if (have != 0) {
    129 			os_memcpy(ctx->buffer + have, input, need);
    130 			MD4Transform(ctx->state, ctx->buffer);
    131 			input += need;
    132 			len -= need;
    133 			have = 0;
    134 		}
    135 
    136 		/* Process data in MD4_BLOCK_LENGTH-byte chunks. */
    137 		while (len >= MD4_BLOCK_LENGTH) {
    138 			MD4Transform(ctx->state, input);
    139 			input += MD4_BLOCK_LENGTH;
    140 			len -= MD4_BLOCK_LENGTH;
    141 		}
    142 	}
    143 
    144 	/* Handle any remaining bytes of data. */
    145 	if (len != 0)
    146 		os_memcpy(ctx->buffer + have, input, len);
    147 }
    148 
    149 /*
    150  * Pad pad to 64-byte boundary with the bit pattern
    151  * 1 0* (64-bit count of bits processed, MSB-first)
    152  */
    153 static void MD4Pad(MD4_CTX *ctx)
    154 {
    155 	u8 count[8];
    156 	size_t padlen;
    157 
    158 	/* Convert count to 8 bytes in little endian order. */
    159 	PUT_64BIT_LE(count, ctx->count);
    160 
    161 	/* Pad out to 56 mod 64. */
    162 	padlen = MD4_BLOCK_LENGTH -
    163 	    ((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1));
    164 	if (padlen < 1 + 8)
    165 		padlen += MD4_BLOCK_LENGTH;
    166 	MD4Update(ctx, PADDING, padlen - 8);		/* padlen - 8 <= 64 */
    167 	MD4Update(ctx, count, 8);
    168 }
    169 
    170 /*
    171  * Final wrapup--call MD4Pad, fill in digest and zero out ctx.
    172  */
    173 static void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx)
    174 {
    175 	int i;
    176 
    177 	MD4Pad(ctx);
    178 	if (digest != NULL) {
    179 		for (i = 0; i < 4; i++)
    180 			PUT_32BIT_LE(digest + i * 4, ctx->state[i]);
    181 		os_memset(ctx, 0, sizeof(*ctx));
    182 	}
    183 }
    184 
    185 
    186 /* The three core functions - F1 is optimized somewhat */
    187 
    188 /* #define F1(x, y, z) (x & y | ~x & z) */
    189 #define F1(x, y, z) (z ^ (x & (y ^ z)))
    190 #define F2(x, y, z) ((x & y) | (x & z) | (y & z))
    191 #define F3(x, y, z) (x ^ y ^ z)
    192 
    193 /* This is the central step in the MD4 algorithm. */
    194 #define MD4STEP(f, w, x, y, z, data, s) \
    195 	( w += f(x, y, z) + data,  w = w<<s | w>>(32-s) )
    196 
    197 /*
    198  * The core of the MD4 algorithm, this alters an existing MD4 hash to
    199  * reflect the addition of 16 longwords of new data.  MD4Update blocks
    200  * the data and converts bytes into longwords for this routine.
    201  */
    202 static void
    203 MD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH])
    204 {
    205 	u32 a, b, c, d, in[MD4_BLOCK_LENGTH / 4];
    206 
    207 #if BYTE_ORDER == LITTLE_ENDIAN
    208 	os_memcpy(in, block, sizeof(in));
    209 #else
    210 	for (a = 0; a < MD4_BLOCK_LENGTH / 4; a++) {
    211 		in[a] = (u32)(
    212 		    (u32)(block[a * 4 + 0]) |
    213 		    (u32)(block[a * 4 + 1]) <<  8 |
    214 		    (u32)(block[a * 4 + 2]) << 16 |
    215 		    (u32)(block[a * 4 + 3]) << 24);
    216 	}
    217 #endif
    218 
    219 	a = state[0];
    220 	b = state[1];
    221 	c = state[2];
    222 	d = state[3];
    223 
    224 	MD4STEP(F1, a, b, c, d, in[ 0],  3);
    225 	MD4STEP(F1, d, a, b, c, in[ 1],  7);
    226 	MD4STEP(F1, c, d, a, b, in[ 2], 11);
    227 	MD4STEP(F1, b, c, d, a, in[ 3], 19);
    228 	MD4STEP(F1, a, b, c, d, in[ 4],  3);
    229 	MD4STEP(F1, d, a, b, c, in[ 5],  7);
    230 	MD4STEP(F1, c, d, a, b, in[ 6], 11);
    231 	MD4STEP(F1, b, c, d, a, in[ 7], 19);
    232 	MD4STEP(F1, a, b, c, d, in[ 8],  3);
    233 	MD4STEP(F1, d, a, b, c, in[ 9],  7);
    234 	MD4STEP(F1, c, d, a, b, in[10], 11);
    235 	MD4STEP(F1, b, c, d, a, in[11], 19);
    236 	MD4STEP(F1, a, b, c, d, in[12],  3);
    237 	MD4STEP(F1, d, a, b, c, in[13],  7);
    238 	MD4STEP(F1, c, d, a, b, in[14], 11);
    239 	MD4STEP(F1, b, c, d, a, in[15], 19);
    240 
    241 	MD4STEP(F2, a, b, c, d, in[ 0] + 0x5a827999,  3);
    242 	MD4STEP(F2, d, a, b, c, in[ 4] + 0x5a827999,  5);
    243 	MD4STEP(F2, c, d, a, b, in[ 8] + 0x5a827999,  9);
    244 	MD4STEP(F2, b, c, d, a, in[12] + 0x5a827999, 13);
    245 	MD4STEP(F2, a, b, c, d, in[ 1] + 0x5a827999,  3);
    246 	MD4STEP(F2, d, a, b, c, in[ 5] + 0x5a827999,  5);
    247 	MD4STEP(F2, c, d, a, b, in[ 9] + 0x5a827999,  9);
    248 	MD4STEP(F2, b, c, d, a, in[13] + 0x5a827999, 13);
    249 	MD4STEP(F2, a, b, c, d, in[ 2] + 0x5a827999,  3);
    250 	MD4STEP(F2, d, a, b, c, in[ 6] + 0x5a827999,  5);
    251 	MD4STEP(F2, c, d, a, b, in[10] + 0x5a827999,  9);
    252 	MD4STEP(F2, b, c, d, a, in[14] + 0x5a827999, 13);
    253 	MD4STEP(F2, a, b, c, d, in[ 3] + 0x5a827999,  3);
    254 	MD4STEP(F2, d, a, b, c, in[ 7] + 0x5a827999,  5);
    255 	MD4STEP(F2, c, d, a, b, in[11] + 0x5a827999,  9);
    256 	MD4STEP(F2, b, c, d, a, in[15] + 0x5a827999, 13);
    257 
    258 	MD4STEP(F3, a, b, c, d, in[ 0] + 0x6ed9eba1,  3);
    259 	MD4STEP(F3, d, a, b, c, in[ 8] + 0x6ed9eba1,  9);
    260 	MD4STEP(F3, c, d, a, b, in[ 4] + 0x6ed9eba1, 11);
    261 	MD4STEP(F3, b, c, d, a, in[12] + 0x6ed9eba1, 15);
    262 	MD4STEP(F3, a, b, c, d, in[ 2] + 0x6ed9eba1,  3);
    263 	MD4STEP(F3, d, a, b, c, in[10] + 0x6ed9eba1,  9);
    264 	MD4STEP(F3, c, d, a, b, in[ 6] + 0x6ed9eba1, 11);
    265 	MD4STEP(F3, b, c, d, a, in[14] + 0x6ed9eba1, 15);
    266 	MD4STEP(F3, a, b, c, d, in[ 1] + 0x6ed9eba1,  3);
    267 	MD4STEP(F3, d, a, b, c, in[ 9] + 0x6ed9eba1,  9);
    268 	MD4STEP(F3, c, d, a, b, in[ 5] + 0x6ed9eba1, 11);
    269 	MD4STEP(F3, b, c, d, a, in[13] + 0x6ed9eba1, 15);
    270 	MD4STEP(F3, a, b, c, d, in[ 3] + 0x6ed9eba1,  3);
    271 	MD4STEP(F3, d, a, b, c, in[11] + 0x6ed9eba1,  9);
    272 	MD4STEP(F3, c, d, a, b, in[ 7] + 0x6ed9eba1, 11);
    273 	MD4STEP(F3, b, c, d, a, in[15] + 0x6ed9eba1, 15);
    274 
    275 	state[0] += a;
    276 	state[1] += b;
    277 	state[2] += c;
    278 	state[3] += d;
    279 }
    280 /* ===== end - public domain MD4 implementation ===== */
    281 
    282 #endif /* INTERNAL_MD4 */
    283