second/md5.c

   1 /*
   2  *  md5.c - an implementation of the MD5 algorithm and MD5 crypt
   3  *
   4  *  Copyright (C) 2001, 2002 Ethan Benson
   5  *
   6  *  Adapted from GRUB
   7  *
   8  *  Copyright (C) 2000  Free Software Foundation, Inc.
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23  */
  24
  25 /* See RFC 1321 for a description of the MD5 algorithm. */
  26
  27 #include "string.h"
  28 #include "md5.h"
  29
  30 #ifdef TEST
  31 # include <stdio.h>
  32 # define USE_MD5_PASSWORDS
  33 # define USE_MD5
  34 #endif
  35
  36 #ifdef USE_MD5_PASSWORDS
  37 # define USE_MD5
  38 #endif
  39
  40 #ifdef USE_MD5
  41 #define cpu_to_le32(x) le32_to_cpu((x))
  42 unsigned long le32_to_cpu(unsigned long x)
  43 {
  44         return (((x & 0x000000ffU) << 24) |
  45                 ((x & 0x0000ff00U) <<  8) |
  46                 ((x & 0x00ff0000U) >>  8) |
  47                 ((x & 0xff000000U) >> 24));
  48 }
  49
  50 typedef unsigned int UINT4;
  51
  52 /* F, G, H and I are basic MD5 functions.
  53  */
  54 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
  55 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
  56 #define H(x, y, z) ((x) ^ (y) ^ (z))
  57 #define I(x, y, z) ((y) ^ ((x) | (~z)))
  58
  59 /* ROTATE_LEFT rotates x left n bits.
  60  */
  61 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x >> (32 - (n)))))
  62
  63 static UINT4 initstate[4] =
  64 {
  65   0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476
  66 };
  67
  68 static char s1[4] = {  7, 12, 17, 22 };
  69 static char s2[4] = {  5,  9, 14, 20 };
  70 static char s3[4] = {  4, 11, 16, 23 };
  71 static char s4[4] = {  6, 10, 15, 21 };
  72
  73 static UINT4 T[64] =
  74 {
  75   0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
  76   0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
  77   0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
  78   0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
  79   0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
  80   0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
  81   0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
  82   0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
  83   0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
  84   0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
  85   0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
  86   0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
  87   0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
  88   0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
  89   0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
  90   0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
  91 };
  92
  93 static const char *b64t =
  94 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  95
  96 static UINT4 state[4];
  97 static unsigned int length;
  98 static unsigned char buffer[64];
  99
 100 static void
 101 md5_transform (const unsigned char block[64])
 102 {
 103   int i, j;
 104   UINT4 a,b,c,d,tmp;
 105   const UINT4 *x = (UINT4 *) block;
 106
 107   a = state[0];
 108   b = state[1];
 109   c = state[2];
 110   d = state[3];
 111
 112   /* Round 1 */
 113   for (i = 0; i < 16; i++)
 114     {
 115       tmp = a + F (b, c, d) + le32_to_cpu (x[i]) + T[i];
 116       tmp = ROTATE_LEFT (tmp, s1[i & 3]);
 117       tmp += b;
 118       a = d; d = c; c = b; b = tmp;
 119     }
 120   /* Round 2 */
 121   for (i = 0, j = 1; i < 16; i++, j += 5)
 122     {
 123       tmp = a + G (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+16];
 124       tmp = ROTATE_LEFT (tmp, s2[i & 3]);
 125       tmp += b;
 126       a = d; d = c; c = b; b = tmp;
 127     }
 128   /* Round 3 */
 129   for (i = 0, j = 5; i < 16; i++, j += 3)
 130     {
 131       tmp = a + H (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+32];
 132       tmp = ROTATE_LEFT (tmp, s3[i & 3]);
 133       tmp += b;
 134       a = d; d = c; c = b; b = tmp;
 135     }
 136   /* Round 4 */
 137   for (i = 0, j = 0; i < 16; i++, j += 7)
 138     {
 139       tmp = a + I (b, c, d) + le32_to_cpu (x[j & 15]) + T[i+48];
 140       tmp = ROTATE_LEFT (tmp, s4[i & 3]);
 141       tmp += b;
 142       a = d; d = c; c = b; b = tmp;
 143     }
 144
 145   state[0] += a;
 146   state[1] += b;
 147   state[2] += c;
 148   state[3] += d;
 149 }
 150
 151 static void
 152 md5_init(void)
 153 {
 154   memcpy ((char *) state, (char *) initstate, sizeof (initstate));
 155   length = 0;
 156 }
 157
 158 static void
 159 md5_update (const char *input, int inputlen)
 160 {
 161   int buflen = length & 63;
 162   length += inputlen;
 163   if (buflen + inputlen < 64)
 164     {
 165       memcpy (buffer + buflen, input, inputlen);
 166       buflen += inputlen;
 167       return;
 168     }
 169
 170   memcpy (buffer + buflen, input, 64 - buflen);
 171   md5_transform (buffer);
 172   input += 64 - buflen;
 173   inputlen -= 64 - buflen;
 174   while (inputlen >= 64)
 175     {
 176       md5_transform (input);
 177       input += 64;
 178       inputlen -= 64;
 179     }
 180   memcpy (buffer, input, inputlen);
 181   buflen = inputlen;
 182 }
 183
 184 static unsigned char *
 185 md5_final()
 186 {
 187   int i, buflen = length & 63;
 188
 189   buffer[buflen++] = 0x80;
 190   memset (buffer+buflen, 0, 64 - buflen);
 191   if (buflen > 56)
 192     {
 193       md5_transform (buffer);
 194       memset (buffer, 0, 64);
 195       buflen = 0;
 196     }
 197
 198   *(UINT4 *) (buffer + 56) = cpu_to_le32 (8 * length);
 199   *(UINT4 *) (buffer + 60) = 0;
 200   md5_transform (buffer);
 201
 202   for (i = 0; i < 4; i++)
 203     state[i] = cpu_to_le32 (state[i]);
 204   return (unsigned char *) state;
 205 }
 206
 207 #ifdef USE_MD5_PASSWORDS
 208 /* If CHECK is true, check a password for correctness. Returns 0
 209    if password was correct, and a value != 0 for error, similarly
 210    to strcmp.
 211    If CHECK is false, crypt KEY and save the result in CRYPTED.
 212    CRYPTED must have a salt.  */
 213 int
 214 md5_password (const char *key, char *crypted, int check)
 215 {
 216   int keylen = strlen (key);
 217   char *salt = crypted + 3; /* skip $1$ header */
 218   char *p;
 219   int saltlen;
 220   int i, n;
 221   unsigned char alt_result[16];
 222   unsigned char *digest;
 223
 224   if (check)
 225     saltlen = strstr (salt, "$") - salt;
 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