All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
md4.c
Go to the documentation of this file.
1 /**
2  * $Id: 2ff492e5b5a6635b6b44b6d38437b7cba0164d3d $
3  *
4  * @note license is LGPL, but largely derived from a public domain source.
5  *
6  * @file md4.c
7  * @brief md4 digest functions.
8  */
9 
10 RCSID("$Id: 2ff492e5b5a6635b6b44b6d38437b7cba0164d3d $")
11 
12 /*
13  * FORCE MD4 TO USE OUR MD4 HEADER FILE!
14  * If we don't do this, it might pick up the systems broken MD4.
15  */
16 #include <freeradius-devel/md4.h>
17 
18 /** Calculate the MD4 hash of the contents of a buffer
19  *
20  * @param[out] out Where to write the MD4 digest. Must be a minimum of MD4_DIGEST_LENGTH.
21  * @param[in] in Data to hash.
22  * @param[in] inlen Length of the data.
23  */
24 void fr_md4_calc(uint8_t out[MD4_DIGEST_LENGTH], uint8_t const *in, size_t inlen)
25 {
26  FR_MD4_CTX ctx;
27 
28  fr_md4_init(&ctx);
29  fr_md4_update(&ctx, in, inlen);
30  fr_md4_final(out, &ctx);
31 }
32 
33 #ifndef HAVE_OPENSSL_EVP_H
34 /*
35  * This code implements the MD4 message-digest algorithm.
36  * The algorithm is due to Ron Rivest. This code was
37  * written by Colin Plumb in 1993, no copyright is claimed.
38  * This code is in the public domain; do with it what you wish.
39  * Todd C. Miller modified the MD5 code to do MD4 based on RFC 1186.
40  *
41  * Equivalent code is available from RSA Data Security, Inc.
42  * This code has been tested against that, and is equivalent,
43  * except that you don't need to include two pages of legalese
44  * with every copy.
45  *
46  * To compute the message digest of a chunk of bytes, declare an
47  * MD4Context structure, pass it to fr_md4_init, call fr_md4_update as
48  * needed on buffers full of bytes, and then call fr_md4_final, which
49  * will fill a supplied 16-byte array with the digest.
50  */
51 
52 #ifndef WORDS_BIGENDIAN
53 # define htole32_4(buf) /* Nothing */
54 # define htole32_14(buf) /* Nothing */
55 # define htole32_16(buf) /* Nothing */
56 #else
57 /* Sometimes defined by endian.h */
58 # ifndef htole32
59 # define htole32(x)\
60  (((((uint32_t)x) & 0xff000000) >> 24) |\
61  ((((uint32_t)x) & 0x00ff0000) >> 8) |\
62  ((((uint32_t)x) & 0x0000ff00) << 8) |\
63  ((((uint32_t)x) & 0x000000ff) << 24))
64 # endif
65 # define htole32_4(buf) do {\
66  (buf)[0] = htole32((buf)[0]);\
67  (buf)[1] = htole32((buf)[1]);\
68  (buf)[2] = htole32((buf)[2]);\
69  (buf)[3] = htole32((buf)[3]);\
70 } while (0)
71 
72 # define htole32_14(buf) do {\
73  (buf)[0] = htole32((buf)[0]);\
74  (buf)[1] = htole32((buf)[1]);\
75  (buf)[2] = htole32((buf)[2]);\
76  (buf)[3] = htole32((buf)[3]);\
77  (buf)[4] = htole32((buf)[4]);\
78  (buf)[5] = htole32((buf)[5]);\
79  (buf)[6] = htole32((buf)[6]);\
80  (buf)[7] = htole32((buf)[7]);\
81  (buf)[8] = htole32((buf)[8]);\
82  (buf)[9] = htole32((buf)[9]);\
83  (buf)[10] = htole32((buf)[10]);\
84  (buf)[11] = htole32((buf)[11]);\
85  (buf)[12] = htole32((buf)[12]);\
86  (buf)[13] = htole32((buf)[13]);\
87 } while (0)
88 
89 # define htole32_16(buf) do {\
90  (buf)[0] = htole32((buf)[0]);\
91  (buf)[1] = htole32((buf)[1]);\
92  (buf)[2] = htole32((buf)[2]);\
93  (buf)[3] = htole32((buf)[3]);\
94  (buf)[4] = htole32((buf)[4]);\
95  (buf)[5] = htole32((buf)[5]);\
96  (buf)[6] = htole32((buf)[6]);\
97  (buf)[7] = htole32((buf)[7]);\
98  (buf)[8] = htole32((buf)[8]);\
99  (buf)[9] = htole32((buf)[9]);\
100  (buf)[10] = htole32((buf)[10]);\
101  (buf)[11] = htole32((buf)[11]);\
102  (buf)[12] = htole32((buf)[12]);\
103  (buf)[13] = htole32((buf)[13]);\
104  (buf)[14] = htole32((buf)[14]);\
105  (buf)[15] = htole32((buf)[15]);\
106 } while (0)
107 #endif
108 
109 /** Initialise a new MD4 context
110  *
111  * Set bit count to 0 and buffer to mysterious initialization constants.
112  *
113  * @param[out] ctx to initialise.
114  */
116 {
117  ctx->count[0] = 0;
118  ctx->count[1] = 0;
119  ctx->state[0] = 0x67452301;
120  ctx->state[1] = 0xefcdab89;
121  ctx->state[2] = 0x98badcfe;
122  ctx->state[3] = 0x10325476;
123 }
124 
125 /** Feed additional data into the MD4 hashing function
126  *
127  * @param[in,out] ctx to update.
128  * @param[in] in Data to hash.
129  * @param[in] inlen Length of the data.
130  */
131 void fr_md4_update(FR_MD4_CTX *ctx, uint8_t const *in, size_t inlen)
132 {
133  uint32_t count;
134 
135  /* Bytes already stored in ctx->buffer */
136  count = (uint32_t)((ctx->count[0] >> 3) & 0x3f);
137 
138  /* Update bitcount */
139 /* ctx->count += (uint64_t)inlen << 3;*/
140  if ((ctx->count[0] += ((uint32_t)inlen << 3)) < (uint32_t)inlen) {
141  /* Overflowed ctx->count[0] */
142  ctx->count[1]++;
143  }
144  ctx->count[1] += ((uint32_t)inlen >> 29);
145 
146  /* Handle any leading odd-sized chunks */
147  if (count) {
148  unsigned char *p = (unsigned char *)ctx->buffer + count;
149 
150  count = MD4_BLOCK_LENGTH - count;
151  if (inlen < count) {
152  memcpy(p, in, inlen);
153  return;
154  }
155  memcpy(p, in, count);
156  htole32_16((uint32_t *)ctx->buffer);
157  fr_md4_transform(ctx->state, ctx->buffer);
158  in += count;
159  inlen -= count;
160  }
161 
162  /* Process data in MD4_BLOCK_LENGTH-byte chunks */
163  while (inlen >= MD4_BLOCK_LENGTH) {
164  memcpy(ctx->buffer, in, MD4_BLOCK_LENGTH);
165  htole32_16((uint32_t *)ctx->buffer);
166  fr_md4_transform(ctx->state, ctx->buffer);
167  in += MD4_BLOCK_LENGTH;
168  inlen -= MD4_BLOCK_LENGTH;
169  }
170 
171  /* Handle any remaining bytes of data. */
172  memcpy(ctx->buffer, in, inlen);
173 }
174 
175 /** Finalise the MD4 context and write out the hash
176  *
177  * Final wrapup - pad to 64-byte boundary with the bit pattern 1 0*
178  * (64-bit count of bits processed, MSB-first).
179  *
180  * @param[out] out Where to write the MD4 digest. Minimum length of MD4_DIGEST_LENGTH.
181  * @param[in,out] ctx to finalise.
182  */
183 void fr_md4_final(uint8_t out[MD4_DIGEST_LENGTH], FR_MD4_CTX *ctx)
184 {
185  uint32_t count;
186  unsigned char *p;
187 
188  /* number of bytes mod 64 */
189  count = (uint32_t)(ctx->count[0] >> 3) & 0x3f;
190 
191  /*
192  * Set the first char of padding to 0x80.
193  * This is safe since there is always at least one byte free.
194  */
195  p = ctx->buffer + count;
196  *p++ = 0x80;
197 
198  /* Bytes of padding needed to make 64 bytes */
199  count = 64 - 1 - count;
200 
201  /* Pad out to 56 mod 64 */
202  if (count < 8) {
203  /* Two lots of padding: Pad the first block to 64 bytes */
204  memset(p, 0, count);
205  htole32_16((uint32_t *)ctx->buffer);
206  fr_md4_transform(ctx->state, ctx->buffer);
207 
208  /* Now fill the next block with 56 bytes */
209  memset(ctx->buffer, 0, 56);
210  } else {
211  /* Pad block to 56 bytes */
212  memset(p, 0, count - 8);
213  }
214  htole32_14((uint32_t *)ctx->buffer);
215 
216  /* Append bit count and transform */
217  ((uint32_t *)ctx->buffer)[14] = ctx->count[0];
218  ((uint32_t *)ctx->buffer)[15] = ctx->count[1];
219 
220  fr_md4_transform(ctx->state, ctx->buffer);
221  htole32_4(ctx->state);
222  memcpy(out, ctx->state, MD4_DIGEST_LENGTH);
223  memset(ctx, 0, sizeof(*ctx)); /* in case it's sensitive */
224 }
225 
226 /* The three core functions - F1 is optimized somewhat */
227 #define F1(x, y, z) (z ^ (x & (y ^ z)))
228 #define F2(x, y, z) ((x & y) | (x & z) | (y & z))
229 #define F3(x, y, z) (x ^ y ^ z)
230 
231 /* This is the central step in the MD4 algorithm. */
232 #define MD4STEP(f, w, x, y, z, data, s) (w += f(x, y, z) + data, w = w << s | w >> (32 - s))
233 
234 /** The core of the MD4 algorithm
235  *
236  * This alters an existing MD4 hash to reflect the addition of 16
237  * longwords of new data. fr_md4_update blocks the data and converts bytes
238  * into longwords for this routine.
239  *
240  * @param[in] state 16 bytes of data to feed into the hashing function.
241  * @param[in,out] block MD4 digest block to update.
242  */
243 void fr_md4_transform(uint32_t state[4], uint8_t const block[MD4_BLOCK_LENGTH])
244 {
245  uint32_t a, b, c, d;
246  uint32_t const *in = (uint32_t const *)block;
247 
248  a = state[0];
249  b = state[1];
250  c = state[2];
251  d = state[3];
252 
253  MD4STEP(F1, a, b, c, d, in[ 0], 3);
254  MD4STEP(F1, d, a, b, c, in[ 1], 7);
255  MD4STEP(F1, c, d, a, b, in[ 2], 11);
256  MD4STEP(F1, b, c, d, a, in[ 3], 19);
257  MD4STEP(F1, a, b, c, d, in[ 4], 3);
258  MD4STEP(F1, d, a, b, c, in[ 5], 7);
259  MD4STEP(F1, c, d, a, b, in[ 6], 11);
260  MD4STEP(F1, b, c, d, a, in[ 7], 19);
261  MD4STEP(F1, a, b, c, d, in[ 8], 3);
262  MD4STEP(F1, d, a, b, c, in[ 9], 7);
263  MD4STEP(F1, c, d, a, b, in[10], 11);
264  MD4STEP(F1, b, c, d, a, in[11], 19);
265  MD4STEP(F1, a, b, c, d, in[12], 3);
266  MD4STEP(F1, d, a, b, c, in[13], 7);
267  MD4STEP(F1, c, d, a, b, in[14], 11);
268  MD4STEP(F1, b, c, d, a, in[15], 19);
269 
270  MD4STEP(F2, a, b, c, d, in[ 0] + 0x5a827999, 3);
271  MD4STEP(F2, d, a, b, c, in[ 4] + 0x5a827999, 5);
272  MD4STEP(F2, c, d, a, b, in[ 8] + 0x5a827999, 9);
273  MD4STEP(F2, b, c, d, a, in[12] + 0x5a827999, 13);
274  MD4STEP(F2, a, b, c, d, in[ 1] + 0x5a827999, 3);
275  MD4STEP(F2, d, a, b, c, in[ 5] + 0x5a827999, 5);
276  MD4STEP(F2, c, d, a, b, in[ 9] + 0x5a827999, 9);
277  MD4STEP(F2, b, c, d, a, in[13] + 0x5a827999, 13);
278  MD4STEP(F2, a, b, c, d, in[ 2] + 0x5a827999, 3);
279  MD4STEP(F2, d, a, b, c, in[ 6] + 0x5a827999, 5);
280  MD4STEP(F2, c, d, a, b, in[10] + 0x5a827999, 9);
281  MD4STEP(F2, b, c, d, a, in[14] + 0x5a827999, 13);
282  MD4STEP(F2, a, b, c, d, in[ 3] + 0x5a827999, 3);
283  MD4STEP(F2, d, a, b, c, in[ 7] + 0x5a827999, 5);
284  MD4STEP(F2, c, d, a, b, in[11] + 0x5a827999, 9);
285  MD4STEP(F2, b, c, d, a, in[15] + 0x5a827999, 13);
286 
287  MD4STEP(F3, a, b, c, d, in[ 0] + 0x6ed9eba1, 3);
288  MD4STEP(F3, d, a, b, c, in[ 8] + 0x6ed9eba1, 9);
289  MD4STEP(F3, c, d, a, b, in[ 4] + 0x6ed9eba1, 11);
290  MD4STEP(F3, b, c, d, a, in[12] + 0x6ed9eba1, 15);
291  MD4STEP(F3, a, b, c, d, in[ 2] + 0x6ed9eba1, 3);
292  MD4STEP(F3, d, a, b, c, in[10] + 0x6ed9eba1, 9);
293  MD4STEP(F3, c, d, a, b, in[ 6] + 0x6ed9eba1, 11);
294  MD4STEP(F3, b, c, d, a, in[14] + 0x6ed9eba1, 15);
295  MD4STEP(F3, a, b, c, d, in[ 1] + 0x6ed9eba1, 3);
296  MD4STEP(F3, d, a, b, c, in[ 9] + 0x6ed9eba1, 9);
297  MD4STEP(F3, c, d, a, b, in[ 5] + 0x6ed9eba1, 11);
298  MD4STEP(F3, b, c, d, a, in[13] + 0x6ed9eba1, 15);
299  MD4STEP(F3, a, b, c, d, in[ 3] + 0x6ed9eba1, 3);
300  MD4STEP(F3, d, a, b, c, in[11] + 0x6ed9eba1, 9);
301  MD4STEP(F3, c, d, a, b, in[ 7] + 0x6ed9eba1, 11);
302  MD4STEP(F3, b, c, d, a, in[15] + 0x6ed9eba1, 15);
303 
304  state[0] += a;
305  state[1] += b;
306  state[2] += c;
307  state[3] += d;
308 }
309 #endif
void fr_md4_update(FR_MD4_CTX *ctx, uint8_t const *in, size_t inlen)
Feed additional data into the MD4 hashing function.
Definition: md4.c:131
#define MD4STEP(f, w, x, y, z, data, s)
Definition: md4.c:232
uint32_t count[2]
Number of bits, mod 2^64.
Definition: md4.h:60
#define htole32_14(buf)
Definition: md4.c:54
void fr_md4_calc(uint8_t out[MD4_DIGEST_LENGTH], uint8_t const *in, size_t inlen)
Calculate the MD4 hash of the contents of a buffer.
Definition: md4.c:24
void fr_md4_init(FR_MD4_CTX *ctx)
Initialise a new MD4 context.
Definition: md4.c:115
void MD4_BLOCK_LENGTH
Definition: md4.h:71
void fr_md4_final(uint8_t out[MD4_DIGEST_LENGTH], FR_MD4_CTX *ctx)
Finalise the MD4 context and write out the hash.
Definition: md4.c:183
void void MD4_DIGEST_LENGTH
Definition: md4.h:68
void fr_md4_transform(uint32_t state[4], uint8_t const block[MD4_BLOCK_LENGTH])
The core of the MD4 algorithm.
Definition: md4.c:243
unsigned int state
Definition: proto_bfd.c:200
#define F1(x, y, z)
Definition: md4.c:227
uint32_t state[4]
State.
Definition: md4.h:59
#define F2(x, y, z)
Definition: md4.c:228
#define htole32_4(buf)
Definition: md4.c:53
#define htole32_16(buf)
Definition: md4.c:55
#define F3(x, y, z)
Definition: md4.c:229
#define RCSID(id)
Definition: build.h:135
uint8_t buffer[MD4_BLOCK_LENGTH]
Input buffer.
Definition: md4.h:61