chiark - git - mdw - become/blob - src/md5.c

   1 /* -*-c-*-
   2  *
   3  * $Id: md5.c,v 1.3 1998/01/12 16:46:11 mdw Exp $
   4  *
   5  * MD-5 secure hash routines
   6  *  Based on RSA MD-5 code
   7  *
   8  * (c) 1996-1998 Mark Wooding
   9  */
  10
  11 /*----- Licensing notice --------------------------------------------------*
  12  *
  13  * This file is part of `become'
  14  *
  15  * `Become' is free software; you can redistribute it and/or modify
  16  * it under the terms of the GNU General Public License as published by
  17  * the Free Software Foundation; either version 2 of the License, or
  18  * (at your option) any later version.
  19  *
  20  * `Become' is distributed in the hope that it will be useful,
  21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23  * GNU General Public License for more details.
  24  *
  25  * You should have received a copy of the GNU General Public License
  26  * along with `become'; if not, write to the Free Software Foundation,
  27  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: md5.c,v $
  33  * Revision 1.3  1998/01/12 16:46:11  mdw
  34  * Fix copyright date.
  35  *
  36  * Revision 1.2  1997/08/04 10:24:23  mdw
  37  * Sources placed under CVS control.
  38  *
  39  * Revision 1.1  1997/07/21  13:47:47  mdw
  40  * Initial revision
  41  *
  42  */
  43
  44 /*----- Header files ------------------------------------------------------*/
  45
  46 #include <stdio.h>
  47 #include <string.h>
  48
  49 #include "config.h"
  50 #include "md5.h"
  51 #include "utils.h"
  52
  53 /*----- Define MD-5 transform ---------------------------------------------*/
  54
  55 /* --- Low-level nonlinear functions --- */
  56
  57 #define f(x,y,z) (((x) & (y)) | ((~x) & (z)))
  58 #define g(x,y,z) (((x) & (z)) | ((y) & (~z)))
  59 #define h(x,y,z) ((x) ^ (y) ^ (z))
  60 #define i(x,y,z) ((y) ^ ((x) | (~z)))
  61
  62 #define rol(x,b) (((x) << (b)) | ((x) >> (32-(b))))
  63
  64 /* --- Rotations applied at various stages --- */
  65
  66 #define S11 7u
  67 #define S12 12u
  68 #define S13 17
  69 #define S14 22u
  70 #define S21 5u
  71 #define S22 9u
  72 #define S23 14u
  73 #define S24 20u
  74 #define S31 4u
  75 #define S32 11u
  76 #define S33 16u
  77 #define S34 23u
  78 #define S41 6u
  79 #define S42 10u
  80 #define S43 15u
  81 #define S44 21u
  82
  83 /* --- Higher level nonlinear functions --- */
  84
  85 #define ff(a, b, c, d, x, s, m) ( a += f(b, c, d) + x + m,              \
  86                                   a = rol(a, s), a += b )
  87
  88 #define gg(a, b, c, d, x, s, m) ( a += g(b, c, d) + x + m,              \
  89                                   a = rol(a, s), a += b )
  90
  91 #define hh(a, b, c, d, x, s, m) ( a += h(b, c, d) + x + m,              \
  92                                   a = rol(a, s), a += b )
  93
  94 #define ii(a, b, c, d, x, s, m) ( a += i(b, c, d) + x + m,              \
  95                                   a = rol(a, s), a += b )
  96
  97 /*----- Main code ---------------------------------------------------------*/
  98
  99 /* --- @md5__trans@ --- *
 100  *
 101  * Arguments:   @uint_32 *v@ = pointer to chaining variables (updated)
 102  *              @const unsigned char *buf@ = pointer to a 64-byte block
 103  *
 104  * Returns:     ---
 105  *
 106  * Use:         Performs the main MD5 transform on a block of data.
 107  */
 108
 109 static void md5__trans(uint_32 *v, const unsigned char *buf)
 110 {
 111   uint_32 a, b, c, d;
 112   uint_32 ib[16];
 113   size_t i;
 114
 115   /* --- Initialise my internal registers --- */
 116
 117   a = v[0], b = v[1], c = v[2], d = v[3];
 118
 119   /* --- Turn the buffer into 32-bit words --- */
 120
 121   for (i = 0; i < 16; i++)
 122     ib[i] = load32_l(buf + (i << 2));
 123
 124   /* --- Round one --- */
 125
 126   ff(a, b, c, d, ib[ 0], S11, 0xd76aa478);      /* 1 */
 127   ff(d, a, b, c, ib[ 1], S12, 0xe8c7b756);      /* 2 */
 128   ff(c, d, a, b, ib[ 2], S13, 0x242070db);      /* 3 */
 129   ff(b, c, d, a, ib[ 3], S14, 0xc1bdceee);      /* 4 */
 130   ff(a, b, c, d, ib[ 4], S11, 0xf57c0faf);      /* 5 */
 131   ff(d, a, b, c, ib[ 5], S12, 0x4787c62a);      /* 6 */
 132   ff(c, d, a, b, ib[ 6], S13, 0xa8304613);      /* 7 */
 133   ff(b, c, d, a, ib[ 7], S14, 0xfd469501);      /* 8 */
 134   ff(a, b, c, d, ib[ 8], S11, 0x698098d8);      /* 9 */
 135   ff(d, a, b, c, ib[ 9], S12, 0x8b44f7af);      /* 10 */
 136   ff(c, d, a, b, ib[10], S13, 0xffff5bb1);      /* 11 */
 137   ff(b, c, d, a, ib[11], S14, 0x895cd7be);      /* 12 */
 138   ff(a, b, c, d, ib[12], S11, 0x6b901122);      /* 13 */
 139   ff(d, a, b, c, ib[13], S12, 0xfd987193);      /* 14 */
 140   ff(c, d, a, b, ib[14], S13, 0xa679438e);      /* 15 */
 141   ff(b, c, d, a, ib[15], S14, 0x49b40821);      /* 16 */
 142
 143   /* --- Round two --- */
 144
 145   gg(a, b, c, d, ib[ 1], S21, 0xf61e2562);      /* 17 */
 146   gg(d, a, b, c, ib[ 6], S22, 0xc040b340);      /* 18 */
 147   gg(c, d, a, b, ib[11], S23, 0x265e5a51);      /* 19 */
 148   gg(b, c, d, a, ib[ 0], S24, 0xe9b6c7aa);      /* 20 */
 149   gg(a, b, c, d, ib[ 5], S21, 0xd62f105d);      /* 21 */
 150   gg(d, a, b, c, ib[10], S22, 0x02441453);      /* 22 */
 151   gg(c, d, a, b, ib[15], S23, 0xd8a1e681);      /* 23 */
 152   gg(b, c, d, a, ib[ 4], S24, 0xe7d3fbc8);      /* 24 */
 153   gg(a, b, c, d, ib[ 9], S21, 0x21e1cde6);      /* 25 */
 154   gg(d, a, b, c, ib[14], S22, 0xc33707d6);      /* 26 */
 155   gg(c, d, a, b, ib[ 3], S23, 0xf4d50d87);      /* 27 */
 156   gg(b, c, d, a, ib[ 8], S24, 0x455a14ed);      /* 28 */
 157   gg(a, b, c, d, ib[13], S21, 0xa9e3e905);      /* 29 */
 158   gg(d, a, b, c, ib[ 2], S22, 0xfcefa3f8);      /* 30 */
 159   gg(c, d, a, b, ib[ 7], S23, 0x676f02d9);      /* 31 */
 160   gg(b, c, d, a, ib[12], S24, 0x8d2a4c8a);      /* 32 */
 161
 162   /* --- Round three --- */
 163
 164   hh(a, b, c, d, ib[ 5], S31, 0xfffa3942);      /* 33 */
 165   hh(d, a, b, c, ib[ 8], S32, 0x8771f681);      /* 34 */
 166   hh(c, d, a, b, ib[11], S33, 0x6d9d6122);      /* 35 */
 167   hh(b, c, d, a, ib[14], S34, 0xfde5380c);      /* 36 */
 168   hh(a, b, c, d, ib[ 1], S31, 0xa4beea44);      /* 37 */
 169   hh(d, a, b, c, ib[ 4], S32, 0x4bdecfa9);      /* 38 */
 170   hh(c, d, a, b, ib[ 7], S33, 0xf6bb4b60);      /* 39 */
 171   hh(b, c, d, a, ib[10], S34, 0xbebfbc70);      /* 40 */
 172   hh(a, b, c, d, ib[13], S31, 0x289b7ec6);      /* 41 */
 173   hh(d, a, b, c, ib[ 0], S32, 0xeaa127fa);      /* 42 */
 174   hh(c, d, a, b, ib[ 3], S33, 0xd4ef3085);      /* 43 */
 175   hh(b, c, d, a, ib[ 6], S34, 0x04881d05);      /* 44 */
 176   hh(a, b, c, d, ib[ 9], S31, 0xd9d4d039);      /* 45 */
 177   hh(d, a, b, c, ib[12], S32, 0xe6db99e5);      /* 46 */
 178   hh(c, d, a, b, ib[15], S33, 0x1fa27cf8);      /* 47 */
 179   hh(b, c, d, a, ib[ 2], S34, 0xc4ac5665);      /* 48 */
 180
 181   /* --- Round four --- */
 182
 183   ii(a, b, c, d, ib[ 0], S41, 0xf4292244);      /* 49 */
 184   ii(d, a, b, c, ib[ 7], S42, 0x432aff97);      /* 50 */
 185   ii(c, d, a, b, ib[14], S43, 0xab9423a7);      /* 51 */
 186   ii(b, c, d, a, ib[ 5], S44, 0xfc93a039);      /* 52 */
 187   ii(a, b, c, d, ib[12], S41, 0x655b59c3);      /* 53 */
 188   ii(d, a, b, c, ib[ 3], S42, 0x8f0ccc92);      /* 54 */
 189   ii(c, d, a, b, ib[10], S43, 0xffeff47d);      /* 55 */
 190   ii(b, c, d, a, ib[ 1], S44, 0x85845dd1);      /* 56 */
 191   ii(a, b, c, d, ib[ 8], S41, 0x6fa87e4f);      /* 57 */
 192   ii(d, a, b, c, ib[15], S42, 0xfe2ce6e0);      /* 58 */
 193   ii(c, d, a, b, ib[ 6], S43, 0xa3014314);      /* 59 */
 194   ii(b, c, d, a, ib[13], S44, 0x4e0811a1);      /* 60 */
 195   ii(a, b, c, d, ib[ 4], S41, 0xf7537e82);      /* 61 */
 196   ii(d, a, b, c, ib[11], S42, 0xbd3af235);      /* 62 */
 197   ii(c, d, a, b, ib[ 2], S43, 0x2ad7d2bb);      /* 63 */
 198   ii(b, c, d, a, ib[ 9], S44, 0xeb86d391);      /* 64 */
 199
 200   /* --- Update the context --- */
 201
 202   v[0] += a, v[1] += b, v[2] += c, v[3] += d;
 203 }
 204
 205 /* --- @md5_trans@ --- *
 206  *
 207  * Arguments:   @unsigned char *v@ = pointer to chaining block (updated)
 208  *              @const unsigned char *buf@ = pointer to input buffer
 209  *
 210  * Returns:     ---
 211  *
 212  * Use:         Performs the MD5 transformation on a chunk of data.  This may
 213  *              be useful for using MD5 in MDC-type cipher constructions.
 214  */
 215
 216 void md5_trans(unsigned char *v, const unsigned char *buf)
 217 {
 218   uint_32 vv[4];
 219
 220   vv[0] = load32_l(v +  0);
 221   vv[1] = load32_l(v +  4);
 222   vv[2] = load32_l(v +  8);
 223   vv[3] = load32_l(v + 12);
 224   md5__trans(vv, buf);
 225   store32_l(v +  0, vv[0]);
 226   store32_l(v +  4, vv[1]);
 227   store32_l(v +  8, vv[2]);
 228   store32_l(v + 12, vv[3]);
 229 }
 230
 231 /* --- @md5_buffer@ --- *
 232  *
 233  * Arguments:   @md5 *m@ = pointer to an MD5 context
 234  *              @const void *buff@ = pointer to buffer of data
 235  *              @size_t size@ = size of buffer
 236  *
 237  * Returns:     ---
 238  *
 239  * Use:         Hashes the buffer of data.  You can call @md5_buffer@
 240  *              lots of times during an MD5 job, to allow big files to be
 241  *              split into little ones.
 242  */
 243
 244 void md5_buffer(md5 *m, const void *buff, size_t size)
 245 {
 246   long int s = size;
 247   const unsigned char *b = buff;
 248   unsigned long x, y;
 249
 250   /* --- Maybe there's some data already in the buffer --- */
 251
 252   if (x = m->size & 63, x) {
 253     y = 64 - x;
 254     if (y > s) {
 255       memcpy(x + m->buf, b, s);
 256       m->size += s;
 257       return;
 258     }
 259     memcpy(x + m->buf, b, y);
 260     md5__trans(m->val, m->buf);
 261     s -= y, b += y;
 262   }
 263
 264   /* --- Now do whole buffers-full --- */
 265
 266   while (s >= 64) {
 267     md5__trans(m->val, b);
 268     s -= 64, b += 64;
 269   }
 270
 271   /* --- Tidy up the tail end --- */
 272
 273   if (s)
 274     memcpy(m->buf, b, s);
 275   m->size += size;
 276 }
 277
 278 /* --- @md5_key@ --- *
 279  *
 280  * Arguments:   @md5 *m@ = pointer to an MD5 context
 281  *              @const unsigned char *k@ = pointer to a 4-word `key'
 282  *
 283  * Returns:     ---
 284  *
 285  * Use:         Initialises a context buffer, with a chosen initialisation
 286  *              string (instead of the standard MD5 value).  This allows you
 287  *              to use NMAC message authentication, should the urge take you.
 288  */
 289
 290 void md5_key(md5 *m, const unsigned char *k)
 291 {
 292   m->size = 0;
 293   m->val[0] = load32_l(k +  0);
 294   m->val[0] = load32_l(k +  4);
 295   m->val[0] = load32_l(k +  8);
 296   m->val[0] = load32_l(k + 12);
 297 }
 298
 299 /* --- @md5_init@ --- *
 300  *
 301  * Arguments:   @md5 *m@ = pointer to an MD5 context
 302  *
 303  * Returns:     ---
 304  *
 305  * Use:         Initialises the context buffer, so that you can do an
 306  *              MD5 job.
 307  */
 308
 309 void md5_init(md5 *m)
 310 {
 311   m->size = 0;
 312   m->val[0] = 0x67452301;
 313   m->val[1] = 0xefcdab89;
 314   m->val[2] = 0x98badcfe;
 315   m->val[3] = 0x10325476;
 316 }
 317
 318 /* --- @md5_final@ --- *
 319  *
 320  * Arguments:   @md5 *m@ = pointer to context buffer
 321  *              @unsigned char *v@ = where to store the value
 322  *
 323  * Returns:     ---
 324  *
 325  * Use:         Finalises an MD5 buffer, so that you can use the result.
 326  */
 327
 328 void md5_final(md5 *m, unsigned char *v)
 329 {
 330   int s = m->size;
 331
 332   /* --- Pad out the block --- */
 333
 334   {
 335     const static unsigned char pad[64] = { 0x80 };
 336     int p = m->size & 63;
 337     p = (p < 56) ? (p = 56 - p) : (p = 120 - p);
 338     md5_buffer(m, pad, p);
 339   }
 340
 341   /* --- Append the length --- */
 342
 343   {
 344     unsigned char b[8];
 345
 346     store32_l(b + 0, s << 3);
 347     store32_l(b + 4, s >> 29);
 348     md5_buffer(m, b, 8);
 349   }
 350
 351   /* --- Write out the value --- */
 352
 353   if (v) {
 354     store32_l(v +  0, m->val[0]);
 355     store32_l(v +  4, m->val[1]);
 356     store32_l(v +  8, m->val[2]);
 357     store32_l(v + 12, m->val[3]);
 358   }
 359 }
 360
 361 /*----- Test driver -------------------------------------------------------*/
 362
 363 #ifdef TEST_RIG
 364
 365 int main(int argc, char *argv[])
 366 {
 367   if (argc > 1 && strcmp(argv[1], "-x") == 0) {
 368
 369     static struct {
 370       const char *string;
 371       uint_32 md[4];
 372     } table[] = {
 373       "",               { 0xd98c1dd4, 0x04b2008f, 0x980980e9, 0x7e42f8ec },
 374       "a",              { 0xb975c10c, 0xa8b6f1c0, 0xe299c331, 0x61267769 },
 375       "abc",            { 0x98500190, 0xb04fd23c, 0x7d3f96d6, 0x727fe128 },
 376       "message digest", { 0x7d696bf9, 0x8d93b77c, 0x312f5a52, 0xd061f1aa },
 377       "abcdefghijklmnopqrstuvwxyz",
 378                         { 0xd7d3fcc3, 0x00e49261, 0x6c49fb7d, 0x3be167ca },
 379       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
 380                         { 0x98ab74d1, 0xf5d977d2, 0x2c1c61a5, 0x9f9d419f },
 381       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 382       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 383       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 384       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 385       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 386       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 387       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 388       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 389       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 390       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 391       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 392       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 393       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 394       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 395       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 396       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 397       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 398       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 399       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 400       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 401       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 402       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n"
 403       "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\n",
 404                         { 0xbaa7652b, 0x5e10cd4a, 0xde9acbf2, 0xfa0b9fbd }
 405     };
 406     int steptbl[] = { 3, 18, 32, 37, 63, 64, 65, 256, 1024, -1 };
 407
 408     md5 m;
 409     int i, j;
 410     const char *p;
 411     size_t sz, a, d;
 412     int f = 1;
 413
 414     for (i = 0; i < sizeof(table) / sizeof(table[0]); i++) {
 415       sz = strlen(table[i].string);
 416       for (j = 0; steptbl[j] < sz && steptbl[j] != -1; j++) {
 417         p = table[i].string;
 418         d = steptbl[j];
 419         md5_init(&m);
 420         for (a = sz; a > d; a -= d) {
 421           md5_buffer(&m, p, d);
 422           p += d;
 423         }
 424         md5_buffer(&m, p, a);
 425         md5_final(&m, 0);
 426         if (m.val[0] != table[i].md[0] ||
 427             m.val[1] != table[i].md[1] ||
 428             m.val[2] != table[i].md[2] ||
 429             m.val[3] != table[i].md[3]) {
 430           printf("!!! bad value, string == `%s', step size == %i\n"
 431                  "!!! expected %08lx-%08lx-%08lx-%08lx, found "
 432                  "%08lx-%08lx-%08lx-%08lx\n\n",
 433                  table[i].string, d,
 434                  (unsigned long)table[i].md[0],
 435                  (unsigned long)table[i].md[1],
 436                  (unsigned long)table[i].md[2],
 437                  (unsigned long)table[i].md[3],
 438                  (unsigned long)m.val[0],
 439                  (unsigned long)m.val[1],
 440                  (unsigned long)m.val[2],
 441                  (unsigned long)m.val[3]);
 442           f = 0;
 443         }
 444       }
 445       md5_init(&m);
 446       md5_buffer(&m, table[i].string, sz);
 447       md5_final(&m, 0);
 448       if (m.val[0] != table[i].md[0] ||
 449           m.val[1] != table[i].md[1] ||
 450           m.val[2] != table[i].md[2] ||
 451           m.val[3] != table[i].md[3]) {
 452         printf("!!! bad value, string == `%s', step size == entire string\n"
 453                "!!! expected %08lx-%08lx-%08lx-%08lx, found "
 454                "%08lx-%08lx-%08lx-%08lx\n\n",
 455                table[i].string,
 456                (unsigned long)table[i].md[0],
 457                (unsigned long)table[i].md[1],
 458                (unsigned long)table[i].md[2],
 459                (unsigned long)table[i].md[3],
 460                (unsigned long)m.val[0],
 461                (unsigned long)m.val[1],
 462                (unsigned long)m.val[2],
 463                (unsigned long)m.val[3]);
 464         f = 0;
 465       } else {
 466         printf("`%s' => %08lx-%08lx-%08lx-%08lx\n",
 467                table[i].string,
 468                (unsigned long)m.val[0],
 469                (unsigned long)m.val[1],
 470                (unsigned long)m.val[2],
 471                (unsigned long)m.val[3]);
 472       }
 473     }
 474
 475   } else {
 476
 477     char buff[4096];
 478     md5 m;
 479     int i;
 480     int read;
 481
 482     md5_init(&m);
 483     while (read = fread(buff, 1, 4096, stdin), read)
 484       md5_buffer(&m, buff, read);
 485     md5_final(&m, 0);
 486
 487     for (i = 0; i < 4; i++)
 488       printf("%02lx%02lx%02lx%02lx",
 489              (unsigned long)( (m.val[i] & 0x000000FF) >>  0 ),
 490              (unsigned long)( (m.val[i] & 0x0000FF00) >>  8 ),
 491              (unsigned long)( (m.val[i] & 0x00FF0000) >> 16 ),
 492              (unsigned long)( (m.val[i] & 0xFF000000) >> 24 ));
 493     putc('\n', stdout);
 494
 495   }
 496
 497   return (0);
 498 }
 499
 500 #endif
 501
 502 /*----- That's all, folks -------------------------------------------------*/