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