1/*
2 * MD4 hash implementation
3 * Copyright (c) 2006, Jouni Malinen <j@w1.fi>
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
17typedef 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
24static void MD4Init(MD4_CTX *ctx);
25static void MD4Update(MD4_CTX *ctx, const unsigned char *input, size_t len);
26static void MD4Final(unsigned char digest[MD4_DIGEST_LENGTH], MD4_CTX *ctx);
27
28
29int 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
69static void
70MD4Transform(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
88static 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 */
98static 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 */
111static 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 */
148static 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 */
168static 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 */
197static void
198MD4Transform(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 ===== */
276