1214501Srpaulo/* 2214501Srpaulo * MD4 hash implementation 3214501Srpaulo * Copyright (c) 2006, Jouni Malinen <j@w1.fi> 4214501Srpaulo * 5252726Srpaulo * This software may be distributed under the terms of the BSD license. 6252726Srpaulo * See README for more details. 7214501Srpaulo */ 8214501Srpaulo 9214501Srpaulo#include "includes.h" 10214501Srpaulo 11214501Srpaulo#include "common.h" 12214501Srpaulo#include "crypto.h" 13214501Srpaulo 14214501Srpaulo#define MD4_BLOCK_LENGTH 64 15214501Srpaulo#define MD4_DIGEST_LENGTH 16 16214501Srpaulo 17214501Srpaulotypedef struct MD4Context { 18214501Srpaulo u32 state[4]; /* state */ 19214501Srpaulo u64 count; /* number of bits, mod 2^64 */ 20214501Srpaulo u8 buffer[MD4_BLOCK_LENGTH]; /* input buffer */ 21214501Srpaulo} MD4_CTX; 22214501Srpaulo 23214501Srpaulo 24214501Srpaulostatic void MD4Init(MD4_CTX *ctx); 25214501Srpaulostatic void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len); 26214501Srpaulostatic void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx); 27214501Srpaulo 28214501Srpaulo 29214501Srpauloint md4_vector(size_t num_elem, const u8 *addr[], const size_t *len, u8 *mac) 30214501Srpaulo{ 31214501Srpaulo MD4_CTX ctx; 32214501Srpaulo size_t i; 33214501Srpaulo 34214501Srpaulo MD4Init(&ctx); 35214501Srpaulo for (i = 0; i < num_elem; i++) 36214501Srpaulo MD4Update(&ctx, addr[i], len[i]); 37214501Srpaulo MD4Final(mac, &ctx); 38214501Srpaulo return 0; 39214501Srpaulo} 40214501Srpaulo 41214501Srpaulo 42214501Srpaulo/* ===== start - public domain MD4 implementation ===== */ 43214501Srpaulo/* $OpenBSD: md4.c,v 1.7 2005/08/08 08:05:35 espie Exp $ */ 44214501Srpaulo 45214501Srpaulo/* 46214501Srpaulo * This code implements the MD4 message-digest algorithm. 47214501Srpaulo * The algorithm is due to Ron Rivest. This code was 48214501Srpaulo * written by Colin Plumb in 1993, no copyright is claimed. 49214501Srpaulo * This code is in the public domain; do with it what you wish. 50214501Srpaulo * Todd C. Miller modified the MD5 code to do MD4 based on RFC 1186. 51214501Srpaulo * 52214501Srpaulo * Equivalent code is available from RSA Data Security, Inc. 53214501Srpaulo * This code has been tested against that, and is equivalent, 54214501Srpaulo * except that you don't need to include two pages of legalese 55214501Srpaulo * with every copy. 56214501Srpaulo * 57214501Srpaulo * To compute the message digest of a chunk of bytes, declare an 58214501Srpaulo * MD4Context structure, pass it to MD4Init, call MD4Update as 59214501Srpaulo * needed on buffers full of bytes, and then call MD4Final, which 60214501Srpaulo * will fill a supplied 16-byte array with the digest. 61214501Srpaulo */ 62214501Srpaulo 63214501Srpaulo#define MD4_DIGEST_STRING_LENGTH (MD4_DIGEST_LENGTH * 2 + 1) 64214501Srpaulo 65214501Srpaulo 66214501Srpaulostatic void 67214501SrpauloMD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH]); 68214501Srpaulo 69214501Srpaulo#define PUT_64BIT_LE(cp, value) do { \ 70214501Srpaulo (cp)[7] = (value) >> 56; \ 71214501Srpaulo (cp)[6] = (value) >> 48; \ 72214501Srpaulo (cp)[5] = (value) >> 40; \ 73214501Srpaulo (cp)[4] = (value) >> 32; \ 74214501Srpaulo (cp)[3] = (value) >> 24; \ 75214501Srpaulo (cp)[2] = (value) >> 16; \ 76214501Srpaulo (cp)[1] = (value) >> 8; \ 77214501Srpaulo (cp)[0] = (value); } while (0) 78214501Srpaulo 79214501Srpaulo#define PUT_32BIT_LE(cp, value) do { \ 80214501Srpaulo (cp)[3] = (value) >> 24; \ 81214501Srpaulo (cp)[2] = (value) >> 16; \ 82214501Srpaulo (cp)[1] = (value) >> 8; \ 83214501Srpaulo (cp)[0] = (value); } while (0) 84214501Srpaulo 85214501Srpaulostatic u8 PADDING[MD4_BLOCK_LENGTH] = { 86214501Srpaulo 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 87214501Srpaulo 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 88214501Srpaulo 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 89214501Srpaulo}; 90214501Srpaulo 91214501Srpaulo/* 92214501Srpaulo * Start MD4 accumulation. 93214501Srpaulo * Set bit count to 0 and buffer to mysterious initialization constants. 94214501Srpaulo */ 95214501Srpaulostatic void MD4Init(MD4_CTX *ctx) 96214501Srpaulo{ 97214501Srpaulo ctx->count = 0; 98214501Srpaulo ctx->state[0] = 0x67452301; 99214501Srpaulo ctx->state[1] = 0xefcdab89; 100214501Srpaulo ctx->state[2] = 0x98badcfe; 101214501Srpaulo ctx->state[3] = 0x10325476; 102214501Srpaulo} 103214501Srpaulo 104214501Srpaulo/* 105214501Srpaulo * Update context to reflect the concatenation of another buffer full 106214501Srpaulo * of bytes. 107214501Srpaulo */ 108214501Srpaulostatic void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len) 109214501Srpaulo{ 110214501Srpaulo size_t have, need; 111214501Srpaulo 112214501Srpaulo /* Check how many bytes we already have and how many more we need. */ 113214501Srpaulo have = (size_t)((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1)); 114214501Srpaulo need = MD4_BLOCK_LENGTH - have; 115214501Srpaulo 116214501Srpaulo /* Update bitcount */ 117214501Srpaulo ctx->count += (u64)len << 3; 118214501Srpaulo 119214501Srpaulo if (len >= need) { 120214501Srpaulo if (have != 0) { 121214501Srpaulo os_memcpy(ctx->buffer + have, input, need); 122214501Srpaulo MD4Transform(ctx->state, ctx->buffer); 123214501Srpaulo input += need; 124214501Srpaulo len -= need; 125214501Srpaulo have = 0; 126214501Srpaulo } 127214501Srpaulo 128214501Srpaulo /* Process data in MD4_BLOCK_LENGTH-byte chunks. */ 129214501Srpaulo while (len >= MD4_BLOCK_LENGTH) { 130214501Srpaulo MD4Transform(ctx->state, input); 131214501Srpaulo input += MD4_BLOCK_LENGTH; 132214501Srpaulo len -= MD4_BLOCK_LENGTH; 133214501Srpaulo } 134214501Srpaulo } 135214501Srpaulo 136214501Srpaulo /* Handle any remaining bytes of data. */ 137214501Srpaulo if (len != 0) 138214501Srpaulo os_memcpy(ctx->buffer + have, input, len); 139214501Srpaulo} 140214501Srpaulo 141214501Srpaulo/* 142214501Srpaulo * Pad pad to 64-byte boundary with the bit pattern 143214501Srpaulo * 1 0* (64-bit count of bits processed, MSB-first) 144214501Srpaulo */ 145214501Srpaulostatic void MD4Pad(MD4_CTX *ctx) 146214501Srpaulo{ 147214501Srpaulo u8 count[8]; 148214501Srpaulo size_t padlen; 149214501Srpaulo 150214501Srpaulo /* Convert count to 8 bytes in little endian order. */ 151214501Srpaulo PUT_64BIT_LE(count, ctx->count); 152214501Srpaulo 153214501Srpaulo /* Pad out to 56 mod 64. */ 154214501Srpaulo padlen = MD4_BLOCK_LENGTH - 155214501Srpaulo ((ctx->count >> 3) & (MD4_BLOCK_LENGTH - 1)); 156214501Srpaulo if (padlen < 1 + 8) 157214501Srpaulo padlen += MD4_BLOCK_LENGTH; 158214501Srpaulo MD4Update(ctx, PADDING, padlen - 8); /* padlen - 8 <= 64 */ 159214501Srpaulo MD4Update(ctx, count, 8); 160214501Srpaulo} 161214501Srpaulo 162214501Srpaulo/* 163214501Srpaulo * Final wrapup--call MD4Pad, fill in digest and zero out ctx. 164214501Srpaulo */ 165214501Srpaulostatic void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx) 166214501Srpaulo{ 167214501Srpaulo int i; 168214501Srpaulo 169214501Srpaulo MD4Pad(ctx); 170214501Srpaulo if (digest != NULL) { 171214501Srpaulo for (i = 0; i < 4; i++) 172214501Srpaulo PUT_32BIT_LE(digest + i * 4, ctx->state[i]); 173214501Srpaulo os_memset(ctx, 0, sizeof(*ctx)); 174214501Srpaulo } 175214501Srpaulo} 176214501Srpaulo 177214501Srpaulo 178214501Srpaulo/* The three core functions - F1 is optimized somewhat */ 179214501Srpaulo 180214501Srpaulo/* #define F1(x, y, z) (x & y | ~x & z) */ 181214501Srpaulo#define F1(x, y, z) (z ^ (x & (y ^ z))) 182214501Srpaulo#define F2(x, y, z) ((x & y) | (x & z) | (y & z)) 183214501Srpaulo#define F3(x, y, z) (x ^ y ^ z) 184214501Srpaulo 185214501Srpaulo/* This is the central step in the MD4 algorithm. */ 186214501Srpaulo#define MD4STEP(f, w, x, y, z, data, s) \ 187214501Srpaulo ( w += f(x, y, z) + data, w = w<<s | w>>(32-s) ) 188214501Srpaulo 189214501Srpaulo/* 190214501Srpaulo * The core of the MD4 algorithm, this alters an existing MD4 hash to 191214501Srpaulo * reflect the addition of 16 longwords of new data. MD4Update blocks 192214501Srpaulo * the data and converts bytes into longwords for this routine. 193214501Srpaulo */ 194214501Srpaulostatic void 195214501SrpauloMD4Transform(u32 state[4], const u8 block[MD4_BLOCK_LENGTH]) 196214501Srpaulo{ 197214501Srpaulo u32 a, b, c, d, in[MD4_BLOCK_LENGTH / 4]; 198214501Srpaulo 199214501Srpaulo#if BYTE_ORDER == LITTLE_ENDIAN 200214501Srpaulo os_memcpy(in, block, sizeof(in)); 201214501Srpaulo#else 202214501Srpaulo for (a = 0; a < MD4_BLOCK_LENGTH / 4; a++) { 203214501Srpaulo in[a] = (u32)( 204214501Srpaulo (u32)(block[a * 4 + 0]) | 205214501Srpaulo (u32)(block[a * 4 + 1]) << 8 | 206214501Srpaulo (u32)(block[a * 4 + 2]) << 16 | 207214501Srpaulo (u32)(block[a * 4 + 3]) << 24); 208214501Srpaulo } 209214501Srpaulo#endif 210214501Srpaulo 211214501Srpaulo a = state[0]; 212214501Srpaulo b = state[1]; 213214501Srpaulo c = state[2]; 214214501Srpaulo d = state[3]; 215214501Srpaulo 216214501Srpaulo MD4STEP(F1, a, b, c, d, in[ 0], 3); 217214501Srpaulo MD4STEP(F1, d, a, b, c, in[ 1], 7); 218214501Srpaulo MD4STEP(F1, c, d, a, b, in[ 2], 11); 219214501Srpaulo MD4STEP(F1, b, c, d, a, in[ 3], 19); 220214501Srpaulo MD4STEP(F1, a, b, c, d, in[ 4], 3); 221214501Srpaulo MD4STEP(F1, d, a, b, c, in[ 5], 7); 222214501Srpaulo MD4STEP(F1, c, d, a, b, in[ 6], 11); 223214501Srpaulo MD4STEP(F1, b, c, d, a, in[ 7], 19); 224214501Srpaulo MD4STEP(F1, a, b, c, d, in[ 8], 3); 225214501Srpaulo MD4STEP(F1, d, a, b, c, in[ 9], 7); 226214501Srpaulo MD4STEP(F1, c, d, a, b, in[10], 11); 227214501Srpaulo MD4STEP(F1, b, c, d, a, in[11], 19); 228214501Srpaulo MD4STEP(F1, a, b, c, d, in[12], 3); 229214501Srpaulo MD4STEP(F1, d, a, b, c, in[13], 7); 230214501Srpaulo MD4STEP(F1, c, d, a, b, in[14], 11); 231214501Srpaulo MD4STEP(F1, b, c, d, a, in[15], 19); 232214501Srpaulo 233214501Srpaulo MD4STEP(F2, a, b, c, d, in[ 0] + 0x5a827999, 3); 234214501Srpaulo MD4STEP(F2, d, a, b, c, in[ 4] + 0x5a827999, 5); 235214501Srpaulo MD4STEP(F2, c, d, a, b, in[ 8] + 0x5a827999, 9); 236214501Srpaulo MD4STEP(F2, b, c, d, a, in[12] + 0x5a827999, 13); 237214501Srpaulo MD4STEP(F2, a, b, c, d, in[ 1] + 0x5a827999, 3); 238214501Srpaulo MD4STEP(F2, d, a, b, c, in[ 5] + 0x5a827999, 5); 239214501Srpaulo MD4STEP(F2, c, d, a, b, in[ 9] + 0x5a827999, 9); 240214501Srpaulo MD4STEP(F2, b, c, d, a, in[13] + 0x5a827999, 13); 241214501Srpaulo MD4STEP(F2, a, b, c, d, in[ 2] + 0x5a827999, 3); 242214501Srpaulo MD4STEP(F2, d, a, b, c, in[ 6] + 0x5a827999, 5); 243214501Srpaulo MD4STEP(F2, c, d, a, b, in[10] + 0x5a827999, 9); 244214501Srpaulo MD4STEP(F2, b, c, d, a, in[14] + 0x5a827999, 13); 245214501Srpaulo MD4STEP(F2, a, b, c, d, in[ 3] + 0x5a827999, 3); 246214501Srpaulo MD4STEP(F2, d, a, b, c, in[ 7] + 0x5a827999, 5); 247214501Srpaulo MD4STEP(F2, c, d, a, b, in[11] + 0x5a827999, 9); 248214501Srpaulo MD4STEP(F2, b, c, d, a, in[15] + 0x5a827999, 13); 249214501Srpaulo 250214501Srpaulo MD4STEP(F3, a, b, c, d, in[ 0] + 0x6ed9eba1, 3); 251214501Srpaulo MD4STEP(F3, d, a, b, c, in[ 8] + 0x6ed9eba1, 9); 252214501Srpaulo MD4STEP(F3, c, d, a, b, in[ 4] + 0x6ed9eba1, 11); 253214501Srpaulo MD4STEP(F3, b, c, d, a, in[12] + 0x6ed9eba1, 15); 254214501Srpaulo MD4STEP(F3, a, b, c, d, in[ 2] + 0x6ed9eba1, 3); 255214501Srpaulo MD4STEP(F3, d, a, b, c, in[10] + 0x6ed9eba1, 9); 256214501Srpaulo MD4STEP(F3, c, d, a, b, in[ 6] + 0x6ed9eba1, 11); 257214501Srpaulo MD4STEP(F3, b, c, d, a, in[14] + 0x6ed9eba1, 15); 258214501Srpaulo MD4STEP(F3, a, b, c, d, in[ 1] + 0x6ed9eba1, 3); 259214501Srpaulo MD4STEP(F3, d, a, b, c, in[ 9] + 0x6ed9eba1, 9); 260214501Srpaulo MD4STEP(F3, c, d, a, b, in[ 5] + 0x6ed9eba1, 11); 261214501Srpaulo MD4STEP(F3, b, c, d, a, in[13] + 0x6ed9eba1, 15); 262214501Srpaulo MD4STEP(F3, a, b, c, d, in[ 3] + 0x6ed9eba1, 3); 263214501Srpaulo MD4STEP(F3, d, a, b, c, in[11] + 0x6ed9eba1, 9); 264214501Srpaulo MD4STEP(F3, c, d, a, b, in[ 7] + 0x6ed9eba1, 11); 265214501Srpaulo MD4STEP(F3, b, c, d, a, in[15] + 0x6ed9eba1, 15); 266214501Srpaulo 267214501Srpaulo state[0] += a; 268214501Srpaulo state[1] += b; 269214501Srpaulo state[2] += c; 270214501Srpaulo state[3] += d; 271214501Srpaulo} 272214501Srpaulo/* ===== end - public domain MD4 implementation ===== */ 273