md5.c revision 5b1eb061628a97aae48a9c0bcaa96eb0bfa07aa4 
1/* md5.c - an implementation of the MD5 algorithm and MD5 crypt */
2/*
3 *  GRUB  --  GRand Unified Bootloader
4 *  Copyright (C) 2000, 2001  Free Software Foundation, Inc.
5 *
6 *  This program is free software; you can redistribute it and/or modify
7 *  it under the terms of the GNU General Public License as published by
8 *  the Free Software Foundation; either version 2 of the License, or
9 *  (at your option) any later version.
10 *
11 *  This program is distributed in the hope that it will be useful,
12 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 *  GNU General Public License for more details.
15 *
16 *  You should have received a copy of the GNU General Public License
17 *  along with this program; if not, write to the Free Software
18 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21/* See RFC 1321 for a description of the MD5 algorithm.
22 */
23
24#include <md5.h>
25#ifndef TEST
26# include <shared.h>
27#endif
28
29#ifdef TEST
30# include <string.h>
31# define USE_MD5_PASSWORDS
32# define USE_MD5
33#endif
34
35#ifdef USE_MD5_PASSWORDS
36# define USE_MD5
37#endif
38
39#ifdef USE_MD5
40
41#define cpu_to_le32(x) (x)
42#define le32_to_cpu(x) cpu_to_le32(x)
43typedef unsigned int UINT4;
44
45/* F, G, H and I are basic MD5 functions.
46 */
47#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
48#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
49#define H(x, y, z) ((x) ^ (y) ^ (z))
50#define I(x, y, z) ((y) ^ ((x) | (~z)))
51
52/* ROTATE_LEFT rotates x left n bits.
53 */
54#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x >> (32 - (n)))))
55
56static UINT4 initstate[4] =
57{
58  0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476
59};
60
61static char s1[4] = {  7, 12, 17, 22 };
62static char s2[4] = {  5,  9, 14, 20 };
63static char s3[4] = {  4, 11, 16, 23 };
64static char s4[4] = {  6, 10, 15, 21 };
65
66static UINT4 T[64] =
67{
68  0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
69  0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
70  0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
71  0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
72  0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
73  0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
74  0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
75  0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
76  0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
77  0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
78  0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
79  0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
80  0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
81  0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
82  0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
83  0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
84};
85
86static const char *b64t =
87"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
88
89static UINT4 state[4];
90static unsigned int length;
91static unsigned char buffer[64];
92
93static void
94md5_transform (const unsigned char block[64])
95{
96  int i, j;
97  UINT4 a,b,c,d,tmp;
98  const UINT4 *x = (UINT4 *) block;
99
100  a = state[0];
101  b = state[1];
102  c = state[2];
103  d = state[3];
104
105  /* Round 1 */
106  for (i = 0; i < 16; i++)
107    {
108      tmp = a + F (b, c, d) + le32_to_cpu (x[i]) + T[i];
109      tmp = ROTATE_LEFT (tmp, s1[i & 3]);
110      tmp += b;
111      a = d; d = c; c = b; b = tmp;
112    }
113  /* Round 2 */
114  for (i = 0, j = 1; i < 16; i++, j += 5)
115    {
116      tmp = a + G (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+16];
117      tmp = ROTATE_LEFT (tmp, s2[i & 3]);
118      tmp += b;
119      a = d; d = c; c = b; b = tmp;
120    }
121  /* Round 3 */
122  for (i = 0, j = 5; i < 16; i++, j += 3)
123    {
124      tmp = a + H (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+32];
125      tmp = ROTATE_LEFT (tmp, s3[i & 3]);
126      tmp += b;
127      a = d; d = c; c = b; b = tmp;
128    }
129  /* Round 4 */
130  for (i = 0, j = 0; i < 16; i++, j += 7)
131    {
132      tmp = a + I (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+48];
133      tmp = ROTATE_LEFT (tmp, s4[i & 3]);
134      tmp += b;
135      a = d; d = c; c = b; b = tmp;
136    }
137
138  state[0] += a;
139  state[1] += b;
140  state[2] += c;
141  state[3] += d;
142}
143
144static void
145md5_init(void)
146{
147  memcpy ((char *) state, (char *) initstate, sizeof (initstate));
148  length = 0;
149}
150
151static void
152md5_update (const char *input, int inputlen)
153{
154  int buflen = length & 63;
155  length += inputlen;
156  if (buflen + inputlen < 64)
157    {
158      memcpy (buffer + buflen, input, inputlen);
159      buflen += inputlen;
160      return;
161    }
162
163  memcpy (buffer + buflen, input, 64 - buflen);
164  md5_transform (buffer);
165  input += 64 - buflen;
166  inputlen -= 64 - buflen;
167  while (inputlen >= 64)
168    {
169      md5_transform (input);
170      input += 64;
171      inputlen -= 64;
172    }
173  memcpy (buffer, input, inputlen);
174  buflen = inputlen;
175}
176
177static unsigned char *
178md5_final()
179{
180  int i, buflen = length & 63;
181
182  buffer[buflen++] = 0x80;
183  memset (buffer+buflen, 0, 64 - buflen);
184  if (buflen > 56)
185    {
186      md5_transform (buffer);
187      memset (buffer, 0, 64);
188      buflen = 0;
189    }
190
191  *(UINT4 *) (buffer + 56) = cpu_to_le32 (8 * length);
192  *(UINT4 *) (buffer + 60) = 0;
193  md5_transform (buffer);
194
195  for (i = 0; i < 4; i++)
196    state[i] = cpu_to_le32 (state[i]);
197  return (unsigned char *) state;
198}
199
200#ifdef USE_MD5_PASSWORDS
201/* If CHECK is true, check a password for correctness. Returns 0
202   if password was correct, and a value != 0 for error, similarly
203   to strcmp.
204   If CHECK is false, crypt KEY and save the result in CRYPTED.
205   CRYPTED must have a salt.  */
206int
207md5_password (const char *key, char *crypted, int check)
208{
209  int keylen = strlen (key);
210  char *salt = crypted + 3; /* skip $1$ header */
211  char *p;
212  int saltlen;
213  int i, n;
214  unsigned char alt_result[16];
215  unsigned char *digest;
216
217  if (check)
218    {
219      /* If our crypted password isn't 3 chars, then it can't be md5
220	 crypted. So, they don't match.  */
221      if (strlen(crypted) <= 3)
222	return 1;
223
224      saltlen = strstr (salt, "$") - salt;
225    }
226  else
227    {
228      char *end = strstr (salt, "$");
229      if (end && end - salt < 8)
230	saltlen = end - salt;
231      else
232	saltlen = 8;
233
234      salt[saltlen] = '$';
235    }
236
237  md5_init ();
238  md5_update (key, keylen);
239  md5_update (salt, saltlen);
240  md5_update (key, keylen);
241  digest = md5_final ();
242  memcpy (alt_result, digest, 16);
243
244  memcpy ((char *) state, (char *) initstate, sizeof (initstate));
245  length = 0;
246  md5_update (key, keylen);
247  md5_update (crypted, 3 + saltlen); /* include the $1$ header */
248  for (i = keylen; i > 16; i -= 16)
249    md5_update (alt_result, 16);
250  md5_update (alt_result, i);
251
252  for (i = keylen; i > 0; i >>= 1)
253    md5_update (key + ((i & 1) ? keylen : 0), 1);
254  digest = md5_final ();
255
256  for (i = 0; i < 1000; i++)
257    {
258      memcpy (alt_result, digest, 16);
259
260      memcpy ((char *) state, (char *) initstate, sizeof (initstate));
261      length = 0;
262      if ((i & 1) != 0)
263	md5_update (key, keylen);
264      else
265	md5_update (alt_result, 16);
266
267      if (i % 3 != 0)
268	md5_update (salt, saltlen);
269
270      if (i % 7 != 0)
271	md5_update (key, keylen);
272
273      if ((i & 1) != 0)
274	md5_update (alt_result, 16);
275      else
276	md5_update (key, keylen);
277      digest = md5_final ();
278    }
279
280  p = salt + saltlen + 1;
281  for (i = 0; i < 5; i++)
282    {
283      unsigned int w =
284	digest[i == 4 ? 5 : 12+i] | (digest[6+i] << 8) | (digest[i] << 16);
285      for (n = 4; n-- > 0;)
286	{
287	  if (check)
288	    {
289	      if (*p++ != b64t[w & 0x3f])
290		return 1;
291	    }
292	  else
293	    {
294	      *p++ = b64t[w & 0x3f];
295	    }
296
297	  w >>= 6;
298	}
299    }
300  {
301    unsigned int w = digest[11];
302    for (n = 2; n-- > 0;)
303      {
304	if (check)
305	  {
306	    if (*p++ != b64t[w & 0x3f])
307	      return 1;
308	  }
309	else
310	  {
311	    *p++ = b64t[w & 0x3f];
312	  }
313
314	w >>= 6;
315      }
316  }
317
318  if (! check)
319    *p = '\0';
320
321  return *p;
322}
323#endif
324
325#ifdef TEST
326static char *
327md5 (const char *input)
328{
329  memcpy ((char *) state, (char *) initstate, sizeof (initstate));
330  length = 0;
331  md5_update (input, strlen (input));
332  return md5_final ();
333}
334
335static void
336test (char *buffer, char *expected)
337{
338  char result[16 * 3 +1];
339  unsigned char* digest = md5 (buffer);
340  int i;
341
342  for (i=0; i < 16; i++)
343    sprintf (result+2*i, "%02x", digest[i]);
344
345  if (strcmp (result, expected))
346    printf ("MD5(%s) failed: %s\n", buffer, result);
347  else
348    printf ("MD5(%s) OK\n", buffer);
349}
350
351int
352main (void)
353{
354  test ("", "d41d8cd98f00b204e9800998ecf8427e");
355  test ("a", "0cc175b9c0f1b6a831c399e269772661");
356  test ("abc", "900150983cd24fb0d6963f7d28e17f72");
357  test ("message digest", "f96b697d7cb7938d525a2f31aaf161d0");
358  test ("abcdefghijklmnopqrstuvwxyz", "c3fcd3d76192e4007dfb496cca67e13b");
359  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
360	"d174ab98d277d9f5a5611c2c9f419d9f");
361  test ("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
362	"57edf4a22be3c955ac49da2e2107b67a");
363  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz3456",
364	"6831fa90115bb9a54fbcd4f9fee0b5c4");
365  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz345",
366	"bc40505cc94a43b7ff3e2ac027325233");
367  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz34567",
368	"fa94b73a6f072a0239b52acacfbcf9fa");
369  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz345678901234",
370	"bd201eae17f29568927414fa326f1267");
371  test ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz34567890123",
372	"80063db1e6b70a2e91eac903f0e46b85");
373
374  if (check_md5_password ("Hello world!",
375			  "$1$saltstri$YMyguxXMBpd2TEZ.vS/3q1"))
376    printf ("Password differs\n");
377  else
378    printf ("Password OK\n");
379  return 0;
380}
381#endif
382
383#endif
384