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