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