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 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 145 md5_init(void) 146 { 147 memcpy ((char *) state, (char *) initstate, sizeof (initstate)); 148 length = 0; 149 } 150 151 static void 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 * 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 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 * 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 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 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