1/*
2 * Copyright (c) 2007, Cameron Rich
3 *
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 * * Neither the name of the axTLS project nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31/**
32 * This file implements the MD5 algorithm as defined in RFC1321
33 */
34
35#include <string.h>
36#include "os_port.h"
37#include "crypto.h"
38
39/* Constants for MD5Transform routine.
40 */
41#define S11 7
42#define S12 12
43#define S13 17
44#define S14 22
45#define S21 5
46#define S22 9
47#define S23 14
48#define S24 20
49#define S31 4
50#define S32 11
51#define S33 16
52#define S34 23
53#define S41 6
54#define S42 10
55#define S43 15
56#define S44 21
57
58/* ----- static functions ----- */
59static void MD5Transform(uint32_t state[4], const uint8_t block[64]);
60static void Encode(uint8_t *output, uint32_t *input, uint32_t len);
61static void Decode(uint32_t *output, const uint8_t *input, uint32_t len);
62
63static const uint8_t PADDING[64] =
64{
65 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
68};
69
70/* F, G, H and I are basic MD5 functions.
71 */
72#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
73#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
74#define H(x, y, z) ((x) ^ (y) ^ (z))
75#define I(x, y, z) ((y) ^ ((x) | (~z)))
76
77/* Versions for size-optimized code. */
78#define IDX(v) ((v) & 3)
79#define F_(a, i) ((a[IDX(i + 1)] & a[IDX(i + 2)]) | (~a[IDX(i + 1)] & a[IDX(i + 3)]))
80#define G_(a, i) ((a[IDX(i + 1)] & a[IDX(i + 3)]) | (a[IDX(i + 2)] & ~a[IDX(i + 3)]))
81#define H_(a, i) (a[IDX(i + 1)] ^ a[IDX(i + 2)] ^ a[IDX(i + 3)])
82#define I_(a, i) (a[IDX(i + 2)] ^ (a[IDX(i + 1)] | ~a[IDX(i + 3)]))
83
84/* ROTATE_LEFT rotates x left n bits. */
85#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
86
87/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
88 Rotation is separate from addition to prevent recomputation. */
89#define FF(a, b, c, d, x, s, ac) { \
90 (a) += F ((b), (c), (d)) + (x) + (uint32_t)(ac); \
91 (a) = ROTATE_LEFT ((a), (s)); \
92 (a) += (b); \
93 }
94#define GG(a, b, c, d, x, s, ac) { \
95 (a) += G ((b), (c), (d)) + (x) + (uint32_t)(ac); \
96 (a) = ROTATE_LEFT ((a), (s)); \
97 (a) += (b); \
98 }
99#define HH(a, b, c, d, x, s, ac) { \
100 (a) += H ((b), (c), (d)) + (x) + (uint32_t)(ac); \
101 (a) = ROTATE_LEFT ((a), (s)); \
102 (a) += (b); \
103 }
104#define II(a, b, c, d, x, s, ac) { \
105 (a) += I ((b), (c), (d)) + (x) + (uint32_t)(ac); \
106 (a) = ROTATE_LEFT ((a), (s)); \
107 (a) += (b); \
108 }
109
110/**
111 * MD5 initialization - begins an MD5 operation, writing a new ctx.
112 */
113EXP_FUNC void STDCALL MD5_Init(MD5_CTX *ctx)
114{
115 ctx->count[0] = ctx->count[1] = 0;
116
117 /* Load magic initialization constants.
118 */
119 ctx->state[0] = 0x67452301;
120 ctx->state[1] = 0xefcdab89;
121 ctx->state[2] = 0x98badcfe;
122 ctx->state[3] = 0x10325476;
123}
124
125/**
126 * Accepts an array of octets as the next portion of the message.
127 */
128EXP_FUNC void STDCALL MD5_Update(MD5_CTX *ctx, const uint8_t * msg, int len)
129{
130 uint32_t x;
131 int i, partLen;
132
133 /* Compute number of bytes mod 64 */
134 x = (uint32_t)((ctx->count[0] >> 3) & 0x3F);
135
136 /* Update number of bits */
137 if ((ctx->count[0] += ((uint32_t)len << 3)) < ((uint32_t)len << 3))
138 ctx->count[1]++;
139 ctx->count[1] += ((uint32_t)len >> 29);
140
141 partLen = 64 - x;
142
143 /* Transform as many times as possible. */
144 if (len >= partLen)
145 {
146 memcpy(&ctx->buffer[x], msg, partLen);
147 MD5Transform(ctx->state, ctx->buffer);
148
149 for (i = partLen; i + 63 < len; i += 64)
150 MD5Transform(ctx->state, &msg[i]);
151
152 x = 0;
153 }
154 else
155 i = 0;
156
157 /* Buffer remaining input */
158 memcpy(&ctx->buffer[x], &msg[i], len-i);
159}
160
161/**
162 * Return the 128-bit message digest into the user's array
163 */
164EXP_FUNC void STDCALL MD5_Final(uint8_t *digest, MD5_CTX *ctx)
165{
166 uint8_t bits[8];
167 uint32_t x, padLen;
168
169 /* Save number of bits */
170 Encode(bits, ctx->count, 8);
171
172 /* Pad out to 56 mod 64.
173 */
174 x = (uint32_t)((ctx->count[0] >> 3) & 0x3f);
175 padLen = (x < 56) ? (56 - x) : (120 - x);
176 MD5_Update(ctx, PADDING, padLen);
177
178 /* Append length (before padding) */
179 MD5_Update(ctx, bits, 8);
180
181 /* Store state in digest */
182 Encode(digest, ctx->state, MD5_SIZE);
183}
184
185/**
186 * MD5 basic transformation. Transforms state based on block.
187 */
188#if OPTIMIZE_FOR_SPEED
189
190static void MD5Transform(uint32_t state[4], const uint8_t block[64])
191{
192 uint32_t a = state[0], b = state[1], c = state[2],
193 d = state[3], x[MD5_SIZE];
194
195 Decode(x, block, 64);
196
197 /* Round 1 */
198 FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
199 FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
200 FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
201 FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
202 FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
203 FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
204 FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
205 FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
206 FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
207 FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
208 FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
209 FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
210 FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
211 FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
212 FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
213 FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
214
215 /* Round 2 */
216 GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
217 GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
218 GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
219 GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
220 GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
221 GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
222 GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
223 GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
224 GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
225 GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
226 GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
227 GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
228 GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
229 GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
230 GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
231 GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
232
233 /* Round 3 */
234 HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
235 HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
236 HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
237 HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
238 HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
239 HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
240 HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
241 HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
242 HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
243 HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
244 HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
245 HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
246 HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
247 HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
248 HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
249 HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
250
251 /* Round 4 */
252 II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
253 II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
254 II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
255 II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
256 II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
257 II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
258 II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
259 II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
260 II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
261 II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
262 II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
263 II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
264 II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
265 II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
266 II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
267 II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
268
269 state[0] += a;
270 state[1] += b;
271 state[2] += c;
272 state[3] += d;
273}
274
275#else
276
277static void MD5Transform(uint32_t state[4], const uint8_t block[64])
278{
279 uint32_t arr[4], x[MD5_SIZE];
280 memcpy(arr, state, sizeof(arr));
281
282 Decode(x, block, 64);
283
284 static const uint32_t round_ac[] = {
285 0xd76aa478, /* 1 */
286 0xe8c7b756, /* 2 */
287 0x242070db, /* 3 */
288 0xc1bdceee, /* 4 */
289 0xf57c0faf, /* 5 */
290 0x4787c62a, /* 6 */
291 0xa8304613, /* 7 */
292 0xfd469501, /* 8 */
293 0x698098d8, /* 9 */
294 0x8b44f7af, /* 10 */
295 0xffff5bb1, /* 11 */
296 0x895cd7be, /* 12 */
297 0x6b901122, /* 13 */
298 0xfd987193, /* 14 */
299 0xa679438e, /* 15 */
300 0x49b40821, /* 16 */
301 0xf61e2562, /* 17 */
302 0xc040b340, /* 18 */
303 0x265e5a51, /* 19 */
304 0xe9b6c7aa, /* 20 */
305 0xd62f105d, /* 21 */
306 0x2441453, /* 22 */
307 0xd8a1e681, /* 23 */
308 0xe7d3fbc8, /* 24 */
309 0x21e1cde6, /* 25 */
310 0xc33707d6, /* 26 */
311 0xf4d50d87, /* 27 */
312 0x455a14ed, /* 28 */
313 0xa9e3e905, /* 29 */
314 0xfcefa3f8, /* 30 */
315 0x676f02d9, /* 31 */
316 0x8d2a4c8a, /* 32 */
317 0xfffa3942, /* 33 */
318 0x8771f681, /* 34 */
319 0x6d9d6122, /* 35 */
320 0xfde5380c, /* 36 */
321 0xa4beea44, /* 37 */
322 0x4bdecfa9, /* 38 */
323 0xf6bb4b60, /* 39 */
324 0xbebfbc70, /* 40 */
325 0x289b7ec6, /* 41 */
326 0xeaa127fa, /* 42 */
327 0xd4ef3085, /* 43 */
328 0x4881d05, /* 44 */
329 0xd9d4d039, /* 45 */
330 0xe6db99e5, /* 46 */
331 0x1fa27cf8, /* 47 */
332 0xc4ac5665, /* 48 */
333 0xf4292244, /* 49 */
334 0x432aff97, /* 50 */
335 0xab9423a7, /* 51 */
336 0xfc93a039, /* 52 */
337 0x655b59c3, /* 53 */
338 0x8f0ccc92, /* 54 */
339 0xffeff47d, /* 55 */
340 0x85845dd1, /* 56 */
341 0x6fa87e4f, /* 57 */
342 0xfe2ce6e0, /* 58 */
343 0xa3014314, /* 59 */
344 0x4e0811a1, /* 60 */
345 0xf7537e82, /* 61 */
346 0xbd3af235, /* 62 */
347 0x2ad7d2bb, /* 63 */
348 0xeb86d391, /* 64 */
349 };
350
351 static const uint8_t round1_s[] = {
352 7, 12, 17, 22,
353 5, 9, 14, 20,
354 4, 11, 16, 23,
355 6, 10, 15, 21,
356 };
357
358 static const uint8_t round_order[] = {
359 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
360 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
361 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
362 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9,
363 };
364
365 unsigned i;
366
367 const uint8_t *round_s = round1_s - 4;
368 for (i = 0; i < 64; i++) {
369 int off = IDX(4 - i);
370 uint32_t v;
371
372 // Code size is bigger
373 //round_s = round1_s + (i >> 4) * 4;
374 if ((i & 15) == 0) {
375 round_s += 4;
376 }
377
378 if (i < 32) {
379 if (i < 16) {
380 v = F_(arr, off);
381 } else {
382 v = G_(arr, off);
383 }
384 } else {
385 if (i < 48) {
386 v = H_(arr, off);
387 } else {
388 v = I_(arr, off);
389 }
390 }
391 v += arr[off];
392 v += x[round_order[i]] + round_ac[i];
393 v = ROTATE_LEFT(v, round_s[i & 3]);
394 v += arr[IDX(off + 1)];
395 arr[off] = v;
396 }
397
398 state[0] += arr[0];
399 state[1] += arr[1];
400 state[2] += arr[2];
401 state[3] += arr[3];
402}
403#endif // OPTIMIZE_FOR_SPEED
404
405/**
406 * Encodes input (uint32_t) into output (uint8_t). Assumes len is
407 * a multiple of 4.
408 */
409static void Encode(uint8_t *output, uint32_t *input, uint32_t len)
410{
411 uint32_t i, j;
412
413 for (i = 0, j = 0; j < len; i++, j += 4)
414 {
415 output[j] = (uint8_t)(input[i] & 0xff);
416 output[j+1] = (uint8_t)((input[i] >> 8) & 0xff);
417 output[j+2] = (uint8_t)((input[i] >> 16) & 0xff);
418 output[j+3] = (uint8_t)((input[i] >> 24) & 0xff);
419 }
420}
421
422/**
423 * Decodes input (uint8_t) into output (uint32_t). Assumes len is
424 * a multiple of 4.
425 */
426static void Decode(uint32_t *output, const uint8_t *input, uint32_t len)
427{
428 uint32_t i, j;
429
430 for (i = 0, j = 0; j < len; i++, j += 4)
431 output[i] = ((uint32_t)input[j]) | (((uint32_t)input[j+1]) << 8) |
432 (((uint32_t)input[j+2]) << 16) | (((uint32_t)input[j+3]) << 24);
433}
434