xref: /illumos-gate/usr/src/grub/grub-0.97/stage2/md5.c (revision 1b8adde7ba7d5e04395c141c5400dc2cffd7d809)
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)
43 typedef 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 
56 static UINT4 initstate[4] =
57 {
58   0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476
59 };
60 
61 static char s1[4] = {  7, 12, 17, 22 };
62 static char s2[4] = {  5,  9, 14, 20 };
63 static char s3[4] = {  4, 11, 16, 23 };
64 static char s4[4] = {  6, 10, 15, 21 };
65 
66 static 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 
86 static const char *b64t =
87 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
88 
89 static UINT4 state[4];
90 static unsigned int length;
91 static unsigned char buffer[64];
92 
93 static void
md5_transform(const unsigned char block[64])94 md5_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 
144 static void
md5_init(void)145 md5_init(void)
146 {
147   memcpy ((char *) state, (char *) initstate, sizeof (initstate));
148   length = 0;
149 }
150 
151 static void
md5_update(const char * input,int inputlen)152 md5_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 
177 static unsigned char *
md5_final()178 md5_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.  */
206 int
md5_password(const char * key,char * crypted,int check)207 md5_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
326 static char *
md5(const char * input)327 md5 (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 
335 static void
test(char * buffer,char * expected)336 test (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 
351 int
main(void)352 main (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