1/* md5.c -- MD5 message-digest algorithm */
2/* $OpenLDAP$ */
3/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 1998-2011 The OpenLDAP Foundation.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
10 * Public License.
11 *
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
15 */
16/* This work was adapted for inclusion in OpenLDAP Software by
17 * Kurt D. Zeilenga based upon code developed by Colin Plumb
18 * and subsequently modified by Jim Kingdon.
19 */
20
21/*
22 * This code implements the MD5 message-digest algorithm.
23 * The algorithm is due to Ron Rivest.  This code was
24 * written by Colin Plumb in 1993, no copyright is claimed.
25 * This code is in the public domain; do with it what you wish.
26 *
27 * Equivalent code is available from RSA Data Security, Inc.
28 * This code has been tested against that, and is equivalent,
29 * except that you don't need to include two pages of legalese
30 * with every copy.
31 *
32 * To compute the message digest of a chunk of bytes, declare an
33 * MD5Context structure, pass it to MD5Init, call MD5Update as
34 * needed on buffers full of bytes, and then call MD5Final, which
35 * will fill a supplied 16-byte array with the digest.
36 */
37
38/* This code was modified in 1997 by Jim Kingdon of Cyclic Software to
39   not require an integer type which is exactly 32 bits.  This work
40   draws on the changes for the same purpose by Tatu Ylonen
41   <ylo@cs.hut.fi> as part of SSH, but since I didn't actually use
42   that code, there is no copyright issue.  I hereby disclaim
43   copyright in any changes I have made; this code remains in the
44   public domain.  */
45
46#include "portable.h"
47
48#include <ac/string.h>
49
50/* include socket.h to get sys/types.h and/or winsock2.h */
51#include <ac/socket.h>
52
53#include <lutil_md5.h>
54
55/* Little-endian byte-swapping routines.  Note that these do not
56   depend on the size of datatypes such as ber_uint_t, nor do they require
57   us to detect the endianness of the machine we are running on.  It
58   is possible they should be macros for speed, but I would be
59   surprised if they were a performance bottleneck for MD5.  */
60
61static ber_uint_t
62getu32( const unsigned char *addr )
63{
64	return (((((unsigned long)addr[3] << 8) | addr[2]) << 8)
65		| addr[1]) << 8 | addr[0];
66}
67
68static void
69putu32( ber_uint_t data, unsigned char *addr )
70{
71	addr[0] = (unsigned char)data;
72	addr[1] = (unsigned char)(data >> 8);
73	addr[2] = (unsigned char)(data >> 16);
74	addr[3] = (unsigned char)(data >> 24);
75}
76
77/*
78 * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
79 * initialization constants.
80 */
81void
82lutil_MD5Init( struct lutil_MD5Context *ctx )
83{
84	ctx->buf[0] = 0x67452301;
85	ctx->buf[1] = 0xefcdab89;
86	ctx->buf[2] = 0x98badcfe;
87	ctx->buf[3] = 0x10325476;
88
89	ctx->bits[0] = 0;
90	ctx->bits[1] = 0;
91}
92
93/*
94 * Update context to reflect the concatenation of another buffer full
95 * of bytes.
96 */
97void
98lutil_MD5Update(
99    struct lutil_MD5Context	*ctx,
100    const unsigned char		*buf,
101    ber_len_t		len
102)
103{
104	ber_uint_t t;
105
106	/* Update bitcount */
107
108	t = ctx->bits[0];
109	if ((ctx->bits[0] = (t + ((ber_uint_t)len << 3)) & 0xffffffff) < t)
110		ctx->bits[1]++;	/* Carry from low to high */
111	ctx->bits[1] += len >> 29;
112
113	t = (t >> 3) & 0x3f;	/* Bytes already in shsInfo->data */
114
115	/* Handle any leading odd-sized chunks */
116
117	if ( t ) {
118		unsigned char *p = ctx->in + t;
119
120		t = 64-t;
121		if (len < t) {
122			AC_MEMCPY(p, buf, len);
123			return;
124		}
125		AC_MEMCPY(p, buf, t);
126		lutil_MD5Transform(ctx->buf, ctx->in);
127		buf += t;
128		len -= t;
129	}
130
131	/* Process data in 64-byte chunks */
132
133	while (len >= 64) {
134		AC_MEMCPY(ctx->in, buf, 64);
135		lutil_MD5Transform(ctx->buf, ctx->in);
136		buf += 64;
137		len -= 64;
138	}
139
140	/* Handle any remaining bytes of data. */
141
142	AC_MEMCPY(ctx->in, buf, len);
143}
144
145/*
146 * Final wrapup - pad to 64-byte boundary with the bit pattern
147 * 1 0* (64-bit count of bits processed, MSB-first)
148 */
149void
150lutil_MD5Final( unsigned char *digest, struct lutil_MD5Context *ctx )
151{
152	unsigned count;
153	unsigned char *p;
154
155	/* Compute number of bytes mod 64 */
156	count = (ctx->bits[0] >> 3) & 0x3F;
157
158	/* Set the first char of padding to 0x80.  This is safe since there is
159	   always at least one byte free */
160	p = ctx->in + count;
161	*p++ = 0x80;
162
163	/* Bytes of padding needed to make 64 bytes */
164	count = 64 - 1 - count;
165
166	/* Pad out to 56 mod 64 */
167	if (count < 8) {
168		/* Two lots of padding:  Pad the first block to 64 bytes */
169		memset(p, '\0', count);
170		lutil_MD5Transform(ctx->buf, ctx->in);
171
172		/* Now fill the next block with 56 bytes */
173		memset(ctx->in, '\0', 56);
174	} else {
175		/* Pad block to 56 bytes */
176		memset(p, '\0', count-8);
177	}
178
179	/* Append length in bits and transform */
180	putu32(ctx->bits[0], ctx->in + 56);
181	putu32(ctx->bits[1], ctx->in + 60);
182
183	lutil_MD5Transform(ctx->buf, ctx->in);
184	putu32(ctx->buf[0], digest);
185	putu32(ctx->buf[1], digest + 4);
186	putu32(ctx->buf[2], digest + 8);
187	putu32(ctx->buf[3], digest + 12);
188	memset(ctx, '\0', sizeof(*ctx));	/* In case it's sensitive */
189}
190
191#ifndef ASM_MD5
192
193/* The four core functions - F1 is optimized somewhat */
194
195/* #define F1(x, y, z) (x & y | ~x & z) */
196#define F1(x, y, z) (z ^ (x & (y ^ z)))
197#define F2(x, y, z) F1(z, x, y)
198#define F3(x, y, z) (x ^ y ^ z)
199#define F4(x, y, z) (y ^ (x | ~z))
200
201/* This is the central step in the MD5 algorithm. */
202#define MD5STEP(f, w, x, y, z, data, s) \
203	( w += f(x, y, z) + data, w &= 0xffffffff, w = w<<s | w>>(32-s), w += x )
204
205/*
206 * The core of the MD5 algorithm, this alters an existing MD5 hash to
207 * reflect the addition of 16 longwords of new data.  MD5Update blocks
208 * the data and converts bytes into longwords for this routine.
209 */
210void
211lutil_MD5Transform( ber_uint_t *buf, const unsigned char *inraw )
212{
213	register ber_uint_t a, b, c, d;
214	ber_uint_t in[16];
215	int i;
216
217	for (i = 0; i < 16; ++i)
218		in[i] = getu32 (inraw + 4 * i);
219
220	a = buf[0];
221	b = buf[1];
222	c = buf[2];
223	d = buf[3];
224
225	MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478,  7);
226	MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12);
227	MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17);
228	MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22);
229	MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf,  7);
230	MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12);
231	MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17);
232	MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22);
233	MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8,  7);
234	MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12);
235	MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17);
236	MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22);
237	MD5STEP(F1, a, b, c, d, in[12]+0x6b901122,  7);
238	MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12);
239	MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17);
240	MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22);
241
242	MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562,  5);
243	MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340,  9);
244	MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14);
245	MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20);
246	MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d,  5);
247	MD5STEP(F2, d, a, b, c, in[10]+0x02441453,  9);
248	MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14);
249	MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20);
250	MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6,  5);
251	MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6,  9);
252	MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14);
253	MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20);
254	MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905,  5);
255	MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8,  9);
256	MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14);
257	MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20);
258
259	MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942,  4);
260	MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11);
261	MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16);
262	MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23);
263	MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44,  4);
264	MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11);
265	MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16);
266	MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23);
267	MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6,  4);
268	MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11);
269	MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16);
270	MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23);
271	MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039,  4);
272	MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11);
273	MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16);
274	MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23);
275
276	MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244,  6);
277	MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10);
278	MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15);
279	MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21);
280	MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3,  6);
281	MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10);
282	MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15);
283	MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21);
284	MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f,  6);
285	MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10);
286	MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15);
287	MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21);
288	MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82,  6);
289	MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10);
290	MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15);
291	MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21);
292
293	buf[0] += a;
294	buf[1] += b;
295	buf[2] += c;
296	buf[3] += d;
297}
298#endif
299
300#ifdef TEST
301/* Simple test program.  Can use it to manually run the tests from
302   RFC1321 for example.  */
303#include <stdio.h>
304
305int
306main (int  argc, char **argv )
307{
308	struct lutil_MD5Context context;
309	unsigned char checksum[LUTIL_MD5_BYTES];
310	int i;
311	int j;
312
313	if (argc < 2)
314	{
315		fprintf (stderr, "usage: %s string-to-hash\n", argv[0]);
316		return EXIT_FAILURE;
317	}
318	for (j = 1; j < argc; ++j)
319	{
320		printf ("MD5 (\"%s\") = ", argv[j]);
321		lutil_MD5Init (&context);
322		lutil_MD5Update (&context, argv[j], strlen (argv[j]));
323		lutil_MD5Final (checksum, &context);
324		for (i = 0; i < LUTIL_MD5_BYTES; i++)
325		{
326			printf ("%02x", (unsigned int) checksum[i]);
327		}
328		printf ("\n");
329	}
330	return EXIT_SUCCESS;
331}
332#endif /* TEST */
333