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