1/*	$KAME: md5.c,v 1.3 2000/05/27 07:14:22 itojun Exp $	*/
2
3/*
4 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the project nor the names of its contributors
16 *    may be used to endorse or promote products derived from this software
17 *    without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32#include <sys/param.h>
33#include <sys/types.h>
34#include <sys/cdefs.h>
35#include <sys/time.h>
36#include <string.h>
37#include "md5.h"
38
39#define SHIFT(X, s) (((X) << (s)) | ((X) >> (32 - (s))))
40
41#define F(X, Y, Z) (((X) & (Y)) | ((~X) & (Z)))
42#define G(X, Y, Z) (((X) & (Z)) | ((Y) & (~Z)))
43#define H(X, Y, Z) ((X) ^ (Y) ^ (Z))
44#define I(X, Y, Z) ((Y) ^ ((X) | (~Z)))
45
46#define ROUND1(a, b, c, d, k, s, i) { \
47	(a) = (a) + F((b), (c), (d)) + X[(k)] + T[(i)]; \
48	(a) = SHIFT((a), (s)); \
49	(a) = (b) + (a); \
50}
51
52#define ROUND2(a, b, c, d, k, s, i) { \
53	(a) = (a) + G((b), (c), (d)) + X[(k)] + T[(i)]; \
54	(a) = SHIFT((a), (s)); \
55	(a) = (b) + (a); \
56}
57
58#define ROUND3(a, b, c, d, k, s, i) { \
59	(a) = (a) + H((b), (c), (d)) + X[(k)] + T[(i)]; \
60	(a) = SHIFT((a), (s)); \
61	(a) = (b) + (a); \
62}
63
64#define ROUND4(a, b, c, d, k, s, i) { \
65	(a) = (a) + I((b), (c), (d)) + X[(k)] + T[(i)]; \
66	(a) = SHIFT((a), (s)); \
67	(a) = (b) + (a); \
68}
69
70#define Sa	 7
71#define Sb	12
72#define Sc	17
73#define Sd	22
74
75#define Se	 5
76#define Sf	 9
77#define Sg	14
78#define Sh	20
79
80#define Si	 4
81#define Sj	11
82#define Sk	16
83#define Sl	23
84
85#define Sm	 6
86#define Sn	10
87#define So	15
88#define Sp	21
89
90#define MD5_A0	0x67452301
91#define MD5_B0	0xefcdab89
92#define MD5_C0	0x98badcfe
93#define MD5_D0	0x10325476
94
95/* Integer part of 4294967296 times abs(sin(i)), where i is in radians. */
96static const u_int32_t T[65] = {
97	0,
98	0xd76aa478, 	0xe8c7b756,	0x242070db,	0xc1bdceee,
99	0xf57c0faf,	0x4787c62a, 	0xa8304613,	0xfd469501,
100	0x698098d8,	0x8b44f7af,	0xffff5bb1,	0x895cd7be,
101	0x6b901122, 	0xfd987193, 	0xa679438e,	0x49b40821,
102
103	0xf61e2562,	0xc040b340, 	0x265e5a51, 	0xe9b6c7aa,
104	0xd62f105d,	0x2441453,	0xd8a1e681,	0xe7d3fbc8,
105	0x21e1cde6,	0xc33707d6, 	0xf4d50d87, 	0x455a14ed,
106	0xa9e3e905,	0xfcefa3f8, 	0x676f02d9, 	0x8d2a4c8a,
107
108	0xfffa3942,	0x8771f681, 	0x6d9d6122, 	0xfde5380c,
109	0xa4beea44, 	0x4bdecfa9, 	0xf6bb4b60, 	0xbebfbc70,
110	0x289b7ec6, 	0xeaa127fa, 	0xd4ef3085,	0x4881d05,
111	0xd9d4d039, 	0xe6db99e5, 	0x1fa27cf8, 	0xc4ac5665,
112
113	0xf4292244, 	0x432aff97, 	0xab9423a7, 	0xfc93a039,
114	0x655b59c3, 	0x8f0ccc92, 	0xffeff47d, 	0x85845dd1,
115	0x6fa87e4f, 	0xfe2ce6e0, 	0xa3014314, 	0x4e0811a1,
116	0xf7537e82, 	0xbd3af235, 	0x2ad7d2bb, 	0xeb86d391,
117};
118
119static const u_int8_t md5_paddat[MD5_BUFLEN] = {
120	0x80,	0,	0,	0,	0,	0,	0,	0,
121	0,	0,	0,	0,	0,	0,	0,	0,
122	0,	0,	0,	0,	0,	0,	0,	0,
123	0,	0,	0,	0,	0,	0,	0,	0,
124	0,	0,	0,	0,	0,	0,	0,	0,
125	0,	0,	0,	0,	0,	0,	0,	0,
126	0,	0,	0,	0,	0,	0,	0,	0,
127	0,	0,	0,	0,	0,	0,	0,	0,
128};
129
130static void md5_calc __P((u_int8_t *, md5_ctxt *));
131
132void md5_init(ctxt)
133	md5_ctxt *ctxt;
134{
135	ctxt->md5_n = 0;
136	ctxt->md5_i = 0;
137	ctxt->md5_sta = MD5_A0;
138	ctxt->md5_stb = MD5_B0;
139	ctxt->md5_stc = MD5_C0;
140	ctxt->md5_std = MD5_D0;
141	bzero(ctxt->md5_buf, sizeof(ctxt->md5_buf));
142}
143
144void md5_loop(ctxt, input, len)
145	md5_ctxt *ctxt;
146	u_int8_t *input;
147	u_int len; /* number of bytes */
148{
149	u_int gap, i;
150
151	ctxt->md5_n += len * 8; /* byte to bit */
152	gap = MD5_BUFLEN - ctxt->md5_i;
153
154	if (len >= gap) {
155		bcopy((void *)input, (void *)(ctxt->md5_buf + ctxt->md5_i),
156			gap);
157		md5_calc(ctxt->md5_buf, ctxt);
158
159		for (i = gap; i + MD5_BUFLEN <= len; i += MD5_BUFLEN) {
160			md5_calc((u_int8_t *)(input + i), ctxt);
161		}
162
163		ctxt->md5_i = len - i;
164		bcopy((void *)(input + i), (void *)ctxt->md5_buf, ctxt->md5_i);
165	} else {
166		bcopy((void *)input, (void *)(ctxt->md5_buf + ctxt->md5_i),
167			len);
168		ctxt->md5_i += len;
169	}
170}
171
172void md5_pad(ctxt)
173	md5_ctxt *ctxt;
174{
175	u_int gap;
176
177	/* Don't count up padding. Keep md5_n. */
178	gap = MD5_BUFLEN - ctxt->md5_i;
179	if (gap > 8) {
180		bcopy((void *)md5_paddat,
181		      (void *)(ctxt->md5_buf + ctxt->md5_i),
182		      gap - sizeof(ctxt->md5_n));
183	} else {
184		/* including gap == 8 */
185		bcopy((void *)md5_paddat, (void *)(ctxt->md5_buf + ctxt->md5_i),
186			gap);
187		md5_calc(ctxt->md5_buf, ctxt);
188		bcopy((void *)(md5_paddat + gap),
189		      (void *)ctxt->md5_buf,
190		      MD5_BUFLEN - sizeof(ctxt->md5_n));
191	}
192
193	/* 8 byte word */
194#if BYTE_ORDER == LITTLE_ENDIAN
195	bcopy(&ctxt->md5_n8[0], &ctxt->md5_buf[56], 8);
196#endif
197#if BYTE_ORDER == BIG_ENDIAN
198	ctxt->md5_buf[56] = ctxt->md5_n8[7];
199	ctxt->md5_buf[57] = ctxt->md5_n8[6];
200	ctxt->md5_buf[58] = ctxt->md5_n8[5];
201	ctxt->md5_buf[59] = ctxt->md5_n8[4];
202	ctxt->md5_buf[60] = ctxt->md5_n8[3];
203	ctxt->md5_buf[61] = ctxt->md5_n8[2];
204	ctxt->md5_buf[62] = ctxt->md5_n8[1];
205	ctxt->md5_buf[63] = ctxt->md5_n8[0];
206#endif
207
208	md5_calc(ctxt->md5_buf, ctxt);
209}
210
211void md5_result(digest, ctxt)
212	u_int8_t *digest;
213	md5_ctxt *ctxt;
214{
215	/* 4 byte words */
216#if BYTE_ORDER == LITTLE_ENDIAN
217	bcopy(&ctxt->md5_st8[0], digest, 16);
218#endif
219#if BYTE_ORDER == BIG_ENDIAN
220	digest[ 0] = ctxt->md5_st8[ 3]; digest[ 1] = ctxt->md5_st8[ 2];
221	digest[ 2] = ctxt->md5_st8[ 1]; digest[ 3] = ctxt->md5_st8[ 0];
222	digest[ 4] = ctxt->md5_st8[ 7]; digest[ 5] = ctxt->md5_st8[ 6];
223	digest[ 6] = ctxt->md5_st8[ 5]; digest[ 7] = ctxt->md5_st8[ 4];
224	digest[ 8] = ctxt->md5_st8[11]; digest[ 9] = ctxt->md5_st8[10];
225	digest[10] = ctxt->md5_st8[ 9]; digest[11] = ctxt->md5_st8[ 8];
226	digest[12] = ctxt->md5_st8[15]; digest[13] = ctxt->md5_st8[14];
227	digest[14] = ctxt->md5_st8[13]; digest[15] = ctxt->md5_st8[12];
228#endif
229}
230
231#if BYTE_ORDER == BIG_ENDIAN
232u_int32_t X[16];
233#endif
234
235static void md5_calc(b64, ctxt)
236	u_int8_t *b64;
237	md5_ctxt *ctxt;
238{
239	u_int32_t A = ctxt->md5_sta;
240	u_int32_t B = ctxt->md5_stb;
241	u_int32_t C = ctxt->md5_stc;
242	u_int32_t D = ctxt->md5_std;
243#if BYTE_ORDER == LITTLE_ENDIAN
244	u_int32_t *X = (u_int32_t *)b64;
245#endif
246#if BYTE_ORDER == BIG_ENDIAN
247	/* 4 byte words */
248	/* what a brute force but fast! */
249	u_int8_t *y = (u_int8_t *)X;
250	y[ 0] = b64[ 3]; y[ 1] = b64[ 2]; y[ 2] = b64[ 1]; y[ 3] = b64[ 0];
251	y[ 4] = b64[ 7]; y[ 5] = b64[ 6]; y[ 6] = b64[ 5]; y[ 7] = b64[ 4];
252	y[ 8] = b64[11]; y[ 9] = b64[10]; y[10] = b64[ 9]; y[11] = b64[ 8];
253	y[12] = b64[15]; y[13] = b64[14]; y[14] = b64[13]; y[15] = b64[12];
254	y[16] = b64[19]; y[17] = b64[18]; y[18] = b64[17]; y[19] = b64[16];
255	y[20] = b64[23]; y[21] = b64[22]; y[22] = b64[21]; y[23] = b64[20];
256	y[24] = b64[27]; y[25] = b64[26]; y[26] = b64[25]; y[27] = b64[24];
257	y[28] = b64[31]; y[29] = b64[30]; y[30] = b64[29]; y[31] = b64[28];
258	y[32] = b64[35]; y[33] = b64[34]; y[34] = b64[33]; y[35] = b64[32];
259	y[36] = b64[39]; y[37] = b64[38]; y[38] = b64[37]; y[39] = b64[36];
260	y[40] = b64[43]; y[41] = b64[42]; y[42] = b64[41]; y[43] = b64[40];
261	y[44] = b64[47]; y[45] = b64[46]; y[46] = b64[45]; y[47] = b64[44];
262	y[48] = b64[51]; y[49] = b64[50]; y[50] = b64[49]; y[51] = b64[48];
263	y[52] = b64[55]; y[53] = b64[54]; y[54] = b64[53]; y[55] = b64[52];
264	y[56] = b64[59]; y[57] = b64[58]; y[58] = b64[57]; y[59] = b64[56];
265	y[60] = b64[63]; y[61] = b64[62]; y[62] = b64[61]; y[63] = b64[60];
266#endif
267
268	ROUND1(A, B, C, D,  0, Sa,  1); ROUND1(D, A, B, C,  1, Sb,  2);
269	ROUND1(C, D, A, B,  2, Sc,  3); ROUND1(B, C, D, A,  3, Sd,  4);
270	ROUND1(A, B, C, D,  4, Sa,  5); ROUND1(D, A, B, C,  5, Sb,  6);
271	ROUND1(C, D, A, B,  6, Sc,  7); ROUND1(B, C, D, A,  7, Sd,  8);
272	ROUND1(A, B, C, D,  8, Sa,  9); ROUND1(D, A, B, C,  9, Sb, 10);
273	ROUND1(C, D, A, B, 10, Sc, 11); ROUND1(B, C, D, A, 11, Sd, 12);
274	ROUND1(A, B, C, D, 12, Sa, 13); ROUND1(D, A, B, C, 13, Sb, 14);
275	ROUND1(C, D, A, B, 14, Sc, 15); ROUND1(B, C, D, A, 15, Sd, 16);
276
277	ROUND2(A, B, C, D,  1, Se, 17); ROUND2(D, A, B, C,  6, Sf, 18);
278	ROUND2(C, D, A, B, 11, Sg, 19); ROUND2(B, C, D, A,  0, Sh, 20);
279	ROUND2(A, B, C, D,  5, Se, 21); ROUND2(D, A, B, C, 10, Sf, 22);
280	ROUND2(C, D, A, B, 15, Sg, 23); ROUND2(B, C, D, A,  4, Sh, 24);
281	ROUND2(A, B, C, D,  9, Se, 25); ROUND2(D, A, B, C, 14, Sf, 26);
282	ROUND2(C, D, A, B,  3, Sg, 27); ROUND2(B, C, D, A,  8, Sh, 28);
283	ROUND2(A, B, C, D, 13, Se, 29); ROUND2(D, A, B, C,  2, Sf, 30);
284	ROUND2(C, D, A, B,  7, Sg, 31); ROUND2(B, C, D, A, 12, Sh, 32);
285
286	ROUND3(A, B, C, D,  5, Si, 33); ROUND3(D, A, B, C,  8, Sj, 34);
287	ROUND3(C, D, A, B, 11, Sk, 35); ROUND3(B, C, D, A, 14, Sl, 36);
288	ROUND3(A, B, C, D,  1, Si, 37); ROUND3(D, A, B, C,  4, Sj, 38);
289	ROUND3(C, D, A, B,  7, Sk, 39); ROUND3(B, C, D, A, 10, Sl, 40);
290	ROUND3(A, B, C, D, 13, Si, 41); ROUND3(D, A, B, C,  0, Sj, 42);
291	ROUND3(C, D, A, B,  3, Sk, 43); ROUND3(B, C, D, A,  6, Sl, 44);
292	ROUND3(A, B, C, D,  9, Si, 45); ROUND3(D, A, B, C, 12, Sj, 46);
293	ROUND3(C, D, A, B, 15, Sk, 47); ROUND3(B, C, D, A,  2, Sl, 48);
294
295	ROUND4(A, B, C, D,  0, Sm, 49); ROUND4(D, A, B, C,  7, Sn, 50);
296	ROUND4(C, D, A, B, 14, So, 51); ROUND4(B, C, D, A,  5, Sp, 52);
297	ROUND4(A, B, C, D, 12, Sm, 53); ROUND4(D, A, B, C,  3, Sn, 54);
298	ROUND4(C, D, A, B, 10, So, 55); ROUND4(B, C, D, A,  1, Sp, 56);
299	ROUND4(A, B, C, D,  8, Sm, 57); ROUND4(D, A, B, C, 15, Sn, 58);
300	ROUND4(C, D, A, B,  6, So, 59); ROUND4(B, C, D, A, 13, Sp, 60);
301	ROUND4(A, B, C, D,  4, Sm, 61); ROUND4(D, A, B, C, 11, Sn, 62);
302	ROUND4(C, D, A, B,  2, So, 63); ROUND4(B, C, D, A,  9, Sp, 64);
303
304	ctxt->md5_sta += A;
305	ctxt->md5_stb += B;
306	ctxt->md5_stc += C;
307	ctxt->md5_std += D;
308}
309