Reduced size from 2087 bytes to 1056 bytes
[people/xl0/gpxe.git] / src / crypto / md5.c
1 /* 
2  * Cryptographic API.
3  *
4  * MD5 Message Digest Algorithm (RFC1321).
5  *
6  * Derived from cryptoapi implementation, originally based on the
7  * public domain implementation written by Colin Plumb in 1993.
8  *
9  * Copyright (c) Cryptoapi developers.
10  * Copyright (c) 2002 James Morris <jmorris@intercode.com.au>
11  * 
12  * This program is free software; you can redistribute it and/or modify it
13  * under the terms of the GNU General Public License as published by the Free
14  * Software Foundation; either version 2 of the License, or (at your option) 
15  * any later version.
16  *
17  */
18
19 #include <stdint.h>
20 #include <string.h>
21 #include <byteswap.h>
22 #include <gpxe/crypto.h>
23
24 #define MD5_DIGEST_SIZE         16
25 #define MD5_HMAC_BLOCK_SIZE     64
26 #define MD5_BLOCK_WORDS         16
27 #define MD5_HASH_WORDS          4
28
29 #define __md5step __attribute__ (( regparm ( 3 ) ))
30
31 struct md5_step {
32         uint32_t __md5step ( * f ) ( uint32_t b, uint32_t c, uint32_t d );
33         uint8_t coefficient;
34         uint8_t constant;
35 };
36
37 static uint32_t __md5step f1 ( uint32_t b, uint32_t c, uint32_t d ) {
38         return ( d ^ ( b & ( c ^ d ) ) );
39 }
40
41 static uint32_t __md5step f2 ( uint32_t b, uint32_t c, uint32_t d ) {
42         return ( c ^ ( d & ( b ^ c ) ) );
43 }
44
45 static uint32_t __md5step f3 ( uint32_t b, uint32_t c, uint32_t d ) {
46         return ( b ^ c ^ d );
47 }
48
49 static uint32_t __md5step f4 ( uint32_t b, uint32_t c, uint32_t d ) {
50         return ( c ^ ( b | ~d ) );
51 }
52
53 struct md5_step md5_steps[4] = {
54         {
55                 .f = f1,
56                 .coefficient = 1,
57                 .constant = 0,
58         },
59         {
60                 .f = f2,
61                 .coefficient = 5,
62                 .constant = 1,
63         },
64         {
65                 .f = f3,
66                 .coefficient = 3,
67                 .constant = 5,
68         },
69         {
70                 .f = f4,
71                 .coefficient = 7,
72                 .constant = 0,
73         }
74 };
75
76 static const uint8_t r[64] = {
77         7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22,
78         5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
79         4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,
80         6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21
81 };
82
83 static const uint32_t k[] = {
84         0xd76aa478UL, 0xe8c7b756UL, 0x242070dbUL, 0xc1bdceeeUL,
85         0xf57c0fafUL, 0x4787c62aUL, 0xa8304613UL, 0xfd469501UL,
86         0x698098d8UL, 0x8b44f7afUL, 0xffff5bb1UL, 0x895cd7beUL,
87         0x6b901122UL, 0xfd987193UL, 0xa679438eUL, 0x49b40821UL,
88         0xf61e2562UL, 0xc040b340UL, 0x265e5a51UL, 0xe9b6c7aaUL,
89         0xd62f105dUL, 0x02441453UL, 0xd8a1e681UL, 0xe7d3fbc8UL,
90         0x21e1cde6UL, 0xc33707d6UL, 0xf4d50d87UL, 0x455a14edUL,
91         0xa9e3e905UL, 0xfcefa3f8UL, 0x676f02d9UL, 0x8d2a4c8aUL,
92         0xfffa3942UL, 0x8771f681UL, 0x6d9d6122UL, 0xfde5380cUL,
93         0xa4beea44UL, 0x4bdecfa9UL, 0xf6bb4b60UL, 0xbebfbc70UL,
94         0x289b7ec6UL, 0xeaa127faUL, 0xd4ef3085UL, 0x04881d05UL,
95         0xd9d4d039UL, 0xe6db99e5UL, 0x1fa27cf8UL, 0xc4ac5665UL,
96         0xf4292244UL, 0x432aff97UL, 0xab9423a7UL, 0xfc93a039UL,
97         0x655b59c3UL, 0x8f0ccc92UL, 0xffeff47dUL, 0x85845dd1UL,
98         0x6fa87e4fUL, 0xfe2ce6e0UL, 0xa3014314UL, 0x4e0811a1UL,
99         0xf7537e82UL, 0xbd3af235UL, 0x2ad7d2bbUL, 0xeb86d391UL,
100         0xe1f27f3aUL, 0xf5710fb0UL, 0xada0e5c4UL, 0x98e4c919UL
101 };
102
103
104 #define F1(x, y, z)     (z ^ (x & (y ^ z)))
105 #define F2(x, y, z)     F1(z, x, y)
106 #define F3(x, y, z)     (x ^ y ^ z)
107 #define F4(x, y, z)     (y ^ (x | ~z))
108
109 #define MD5STEP(f, w, x, y, z, in, s) do {                      \
110                 (w += f(x, y, z) + in, w = (w<<s | w>>(32-s)) + x) ; \
111                 printf ( "a=%#08x, b=%#08x, c=%#08x, d=%#08x\n", a, b, c, d );\
112 } while ( 0 )
113
114 struct md5_ctx {
115         u32 hash[MD5_HASH_WORDS];
116         u32 block[MD5_BLOCK_WORDS];
117         u64 byte_count;
118 };
119
120 static void md5_transform(u32 *hash, const u32 *in)
121 {
122         u32 a, b, c, d, f, g, t, q;
123         int i;
124         struct md5_step *step;
125
126         a = hash[0];
127         b = hash[1];
128         c = hash[2];
129         d = hash[3];
130
131 #if 1
132
133         for ( i = 0 ; i < 64 ; i++ ) {
134                 step = &md5_steps[i >> 4];
135                 f = step->f ( b, c, d );
136                 g = ( ( i * step->coefficient + step->constant ) & 0xf );
137                 t = d;
138                 d = c;
139                 c = b;
140                 q = ( a + f + k[i] + in[g] );
141                 b += ( ( q << r[i] ) | ( q >> ( 32-r[i] ) ) );
142                 a = t;
143                 printf ( "a=%#08x, b=%#08x, c=%#08x, d=%#08x\n", a, b, c, d );
144         }
145
146 #else
147         MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
148         MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
149         MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
150         MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
151         MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
152         MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
153         MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
154         MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
155         MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
156         MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
157         MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
158         MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
159         MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
160         MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
161         MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
162         MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
163
164         MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
165         MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
166         MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
167         MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
168         MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
169         MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
170         MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
171         MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
172         MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
173         MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
174         MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
175         MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
176         MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
177         MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
178         MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
179         MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
180
181         MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
182         MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
183         MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
184         MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
185         MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
186         MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
187         MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
188         MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
189         MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
190         MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
191         MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
192         MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
193         MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
194         MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
195         MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
196         MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
197
198         MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
199         MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
200         MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
201         MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
202         MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
203         MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
204         MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
205         MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
206         MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
207         MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
208         MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
209         MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
210         MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
211         MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
212         MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
213         MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
214 #endif
215
216         hash[0] += a;
217         hash[1] += b;
218         hash[2] += c;
219         hash[3] += d;
220 }
221
222 /* XXX: this stuff can be optimized */
223 static inline void le32_to_cpu_array(u32 *buf, unsigned int words)
224 {
225         while (words--) {
226                 //              __le32_to_cpus(buf);
227                 buf++;
228         }
229 }
230
231 static inline void cpu_to_le32_array(u32 *buf, unsigned int words)
232 {
233         while (words--) {
234                 //              __cpu_to_le32s(buf);
235                 buf++;
236         }
237 }
238
239 static inline void md5_transform_helper(struct md5_ctx *ctx)
240 {
241         le32_to_cpu_array(ctx->block, sizeof(ctx->block) / sizeof(u32));
242         md5_transform(ctx->hash, ctx->block);
243 }
244
245 static void md5_init(void *context)
246 {
247         struct md5_ctx *mctx = context;
248
249         mctx->hash[0] = 0x67452301;
250         mctx->hash[1] = 0xefcdab89;
251         mctx->hash[2] = 0x98badcfe;
252         mctx->hash[3] = 0x10325476;
253         mctx->byte_count = 0;
254 }
255
256 static void md5_update(void *context, const void *data, size_t len)
257 {
258         struct md5_ctx *mctx = context;
259         const u32 avail = sizeof(mctx->block) - (mctx->byte_count & 0x3f);
260
261         mctx->byte_count += len;
262
263         if (avail > len) {
264                 memcpy((char *)mctx->block + (sizeof(mctx->block) - avail),
265                        data, len);
266                 return;
267         }
268
269         memcpy((char *)mctx->block + (sizeof(mctx->block) - avail),
270                data, avail);
271
272         md5_transform_helper(mctx);
273         data += avail;
274         len -= avail;
275
276         while (len >= sizeof(mctx->block)) {
277                 memcpy(mctx->block, data, sizeof(mctx->block));
278                 md5_transform_helper(mctx);
279                 data += sizeof(mctx->block);
280                 len -= sizeof(mctx->block);
281         }
282
283         memcpy(mctx->block, data, len);
284 }
285
286 static void md5_finish(void *context, void *out)
287 {
288         struct md5_ctx *mctx = context;
289         const unsigned int offset = mctx->byte_count & 0x3f;
290         char *p = (char *)mctx->block + offset;
291         int padding = 56 - (offset + 1);
292
293         *p++ = 0x80;
294         if (padding < 0) {
295                 memset(p, 0x00, padding + sizeof (u64));
296                 md5_transform_helper(mctx);
297                 p = (char *)mctx->block;
298                 padding = 56;
299         }
300
301         memset(p, 0, padding);
302         mctx->block[14] = mctx->byte_count << 3;
303         mctx->block[15] = mctx->byte_count >> 29;
304         le32_to_cpu_array(mctx->block, (sizeof(mctx->block) -
305                           sizeof(u64)) / sizeof(u32));
306         md5_transform(mctx->hash, mctx->block);
307         cpu_to_le32_array(mctx->hash, sizeof(mctx->hash) / sizeof(u32));
308         memcpy(out, mctx->hash, sizeof(mctx->hash));
309         memset(mctx, 0, sizeof(*mctx));
310 }
311
312 struct digest_algorithm md5_algorithm = {
313         .context_len    = sizeof ( struct md5_ctx ),
314         .digest_len     = MD5_DIGEST_SIZE,
315         .init           = md5_init,
316         .update         = md5_update,
317         .finish         = md5_finish,
318 };