md5.c

   1 /*
   2   Copyright (C) 1999 Aladdin Enterprises.  All rights reserved.
   3
   4   This software is provided 'as-is', without any express or implied
   5   warranty.  In no event will the authors be held liable for any damages
   6   arising from the use of this software.
   7
   8   Permission is granted to anyone to use this software for any purpose,
   9   including commercial applications, and to alter it and redistribute it
  10   freely, subject to the following restrictions:
  11
  12   1. The origin of this software must not be misrepresented; you must not
  13      claim that you wrote the original software. If you use this software
  14      in a product, an acknowledgment in the product documentation would be
  15      appreciated but is not required.
  16   2. Altered source versions must be plainly marked as such, and must not be
  17      misrepresented as being the original software.
  18   3. This notice may not be removed or altered from any source distribution.
  19
  20   L. Peter Deutsch
  21   ghost@aladdin.com
  22
  23  */
  24 /*$Id$ */
  25 /*
  26   Independent implementation of MD5 (RFC 1321).
  27
  28   This code implements the MD5 Algorithm defined in RFC 1321.
  29   It is derived directly from the text of the RFC and not from the
  30   reference implementation.
  31
  32   The original and principal author of md5.c is L. Peter Deutsch
  33   <ghost@aladdin.com>.  Other authors are noted in the change history
  34   that follows (in reverse chronological order):
  35
  36   1999-11-04 lpd Edited comments slightly for automatic TOC extraction.
  37   1999-10-18 lpd Fixed typo in header comment (ansi2knr rather than md5).
  38   1999-05-03 lpd Original version.
  39  */
  40
  41 #include "md5.h"
  42 #include <string.h>
  43
  44 #ifdef TEST
  45 /*
  46  * Compile with -DTEST to create a self-contained executable test program.
  47  * The test program should print out the same values as given in section
  48  * A.5 of RFC 1321, reproduced below.
  49  */
  50 #include <string.h>
  51 main()
  52 {
  53     static const char *const test[7] = {
  54         "", /*d41d8cd98f00b204e9800998ecf8427e*/
  55         "945399884.61923487334tuvga", /*0cc175b9c0f1b6a831c399e269772661*/
  56         "abc", /*900150983cd24fb0d6963f7d28e17f72*/
  57         "message digest", /*f96b697d7cb7938d525a2f31aaf161d0*/
  58         "abcdefghijklmnopqrstuvwxyz", /*c3fcd3d76192e4007dfb496cca67e13b*/
  59         "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
  60                                 /*d174ab98d277d9f5a5611c2c9f419d9f*/
  61         "12345678901234567890123456789012345678901234567890123456789012345678901234567890" /*57edf4a22be3c955ac49da2e2107b67a*/
  62     };
  63     int i;
  64
  65     for (i = 0; i < 7; ++i) {
  66         md5_state_t state;
  67         md5_byte_t digest[16];
  68         int di;
  69
  70         md5_init(&state);
  71         md5_append(&state, (const md5_byte_t *)test[i], strlen(test[i]));
  72         md5_finish(&state, digest);
  73         printf("MD5 (\"%s\") = ", test[i]);
  74         for (di = 0; di < 16; ++di)
  75             printf("%02x", digest[di]);
  76         printf("\n");
  77     }
  78     return 0;
  79 }
  80 #endif /* TEST */
  81
  82
  83 /*
  84  * For reference, here is the program that computed the T values.
  85  */
  86 #if 0
  87 #include <math.h>
  88 main()
  89 {
  90     int i;
  91     for (i = 1; i <= 64; ++i) {
  92         unsigned long v = (unsigned long)(4294967296.0 * fabs(sin((double)i)));
  93         printf("#define T%d 0x%08lx\n", i, v);
  94     }
  95     return 0;
  96 }
  97 #endif
  98 /*
  99  * End of T computation program.
 100  */
 101 #define T1 0xd76aa478
 102 #define T2 0xe8c7b756
 103 #define T3 0x242070db
 104 #define T4 0xc1bdceee
 105 #define T5 0xf57c0faf
 106 #define T6 0x4787c62a
 107 #define T7 0xa8304613
 108 #define T8 0xfd469501
 109 #define T9 0x698098d8
 110 #define T10 0x8b44f7af
 111 #define T11 0xffff5bb1
 112 #define T12 0x895cd7be
 113 #define T13 0x6b901122
 114 #define T14 0xfd987193
 115 #define T15 0xa679438e
 116 #define T16 0x49b40821
 117 #define T17 0xf61e2562
 118 #define T18 0xc040b340
 119 #define T19 0x265e5a51
 120 #define T20 0xe9b6c7aa
 121 #define T21 0xd62f105d
 122 #define T22 0x02441453
 123 #define T23 0xd8a1e681
 124 #define T24 0xe7d3fbc8
 125 #define T25 0x21e1cde6
 126 #define T26 0xc33707d6
 127 #define T27 0xf4d50d87
 128 #define T28 0x455a14ed
 129 #define T29 0xa9e3e905
 130 #define T30 0xfcefa3f8
 131 #define T31 0x676f02d9
 132 #define T32 0x8d2a4c8a
 133 #define T33 0xfffa3942
 134 #define T34 0x8771f681
 135 #define T35 0x6d9d6122
 136 #define T36 0xfde5380c
 137 #define T37 0xa4beea44
 138 #define T38 0x4bdecfa9
 139 #define T39 0xf6bb4b60
 140 #define T40 0xbebfbc70
 141 #define T41 0x289b7ec6
 142 #define T42 0xeaa127fa
 143 #define T43 0xd4ef3085
 144 #define T44 0x04881d05
 145 #define T45 0xd9d4d039
 146 #define T46 0xe6db99e5
 147 #define T47 0x1fa27cf8
 148 #define T48 0xc4ac5665
 149 #define T49 0xf4292244
 150 #define T50 0x432aff97
 151 #define T51 0xab9423a7
 152 #define T52 0xfc93a039
 153 #define T53 0x655b59c3
 154 #define T54 0x8f0ccc92
 155 #define T55 0xffeff47d
 156 #define T56 0x85845dd1
 157 #define T57 0x6fa87e4f
 158 #define T58 0xfe2ce6e0
 159 #define T59 0xa3014314
 160 #define T60 0x4e0811a1
 161 #define T61 0xf7537e82
 162 #define T62 0xbd3af235
 163 #define T63 0x2ad7d2bb
 164 #define T64 0xeb86d391
 165
 166 static void
 167 md5_process(md5_state_t *pms, const md5_byte_t *data /*[64]*/)
 168 {
 169     md5_word_t
 170         a = pms->abcd[0], b = pms->abcd[1],
 171         c = pms->abcd[2], d = pms->abcd[3];
 172     md5_word_t t;
 173
 174 #ifndef ARCH_IS_BIG_ENDIAN
 175 # define ARCH_IS_BIG_ENDIAN 1   /* slower, default implementation */
 176 #endif
 177 #if ARCH_IS_BIG_ENDIAN
 178
 179     /*
 180      * On big-endian machines, we must arrange the bytes in the right
 181      * order.  (This also works on machines of unknown byte order.)
 182      */
 183     md5_word_t X[16];
 184     const md5_byte_t *xp = data;
 185     int i;
 186
 187     for (i = 0; i < 16; ++i, xp += 4)
 188         X[i] = xp[0] + (xp[1] << 8) + (xp[2] << 16) + (xp[3] << 24);
 189
 190 #else  /* !ARCH_IS_BIG_ENDIAN */
 191
 192     /*
 193      * On little-endian machines, we can process properly aligned data
 194      * without copying it.
 195      */
 196     md5_word_t xbuf[16];
 197     const md5_word_t *X;
 198
 199     if (!((data - (const md5_byte_t *)0) & 3)) {
 200         /* data are properly aligned */
 201         X = (const md5_word_t *)data;
 202     } else {
 203         /* not aligned */
 204         memcpy(xbuf, data, 64);
 205         X = xbuf;
 206     }
 207 #endif
 208
 209 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
 210
 211     /* Round 1. */
 212     /* Let [abcd k s i] denote the operation
 213        a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
 214 #define F(x, y, z) (((x) & (y)) | (~(x) & (z)))
 215 #define SET(a, b, c, d, k, s, Ti)\
 216   t = a + F(b,c,d) + X[k] + Ti;\
 217   a = ROTATE_LEFT(t, s) + b
 218     /* Do the following 16 operations. */
 219     SET(a, b, c, d,  0,  7,  T1);
 220     SET(d, a, b, c,  1, 12,  T2);
 221     SET(c, d, a, b,  2, 17,  T3);
 222     SET(b, c, d, a,  3, 22,  T4);
 223     SET(a, b, c, d,  4,  7,  T5);
 224     SET(d, a, b, c,  5, 12,  T6);
 225     SET(c, d, a, b,  6, 17,  T7);
 226     SET(b, c, d, a,  7, 22,  T8);
 227     SET(a, b, c, d,  8,  7,  T9);
 228     SET(d, a, b, c,  9, 12, T10);
 229     SET(c, d, a, b, 10, 17, T11);
 230     SET(b, c, d, a, 11, 22, T12);
 231     SET(a, b, c, d, 12,  7, T13);
 232     SET(d, a, b, c, 13, 12, T14);
 233     SET(c, d, a, b, 14, 17, T15);
 234     SET(b, c, d, a, 15, 22, T16);
 235 #undef SET
 236
 237      /* Round 2. */
 238      /* Let [abcd k s i] denote the operation
 239           a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
 240 #define G(x, y, z) (((x) & (z)) | ((y) & ~(z)))
 241 #define SET(a, b, c, d, k, s, Ti)\
 242   t = a + G(b,c,d) + X[k] + Ti;\
 243   a = ROTATE_LEFT(t, s) + b
 244      /* Do the following 16 operations. */
 245     SET(a, b, c, d,  1,  5, T17);
 246     SET(d, a, b, c,  6,  9, T18);
 247     SET(c, d, a, b, 11, 14, T19);
 248     SET(b, c, d, a,  0, 20, T20);
 249     SET(a, b, c, d,  5,  5, T21);
 250     SET(d, a, b, c, 10,  9, T22);
 251     SET(c, d, a, b, 15, 14, T23);
 252     SET(b, c, d, a,  4, 20, T24);
 253     SET(a, b, c, d,  9,  5, T25);
 254     SET(d, a, b, c, 14,  9, T26);
 255     SET(c, d, a, b,  3, 14, T27);
 256     SET(b, c, d, a,  8, 20, T28);
 257     SET(a, b, c, d, 13,  5, T29);
 258     SET(d, a, b, c,  2,  9, T30);
 259     SET(c, d, a, b,  7, 14, T31);
 260     SET(b, c, d, a, 12, 20, T32);
 261 #undef SET
 262
 263      /* Round 3. */
 264      /* Let [abcd k s t] denote the operation
 265           a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
 266 #define H(x, y, z) ((x) ^ (y) ^ (z))
 267 #define SET(a, b, c, d, k, s, Ti)\
 268   t = a + H(b,c,d) + X[k] + Ti;\
 269   a = ROTATE_LEFT(t, s) + b
 270      /* Do the following 16 operations. */
 271     SET(a, b, c, d,  5,  4, T33);
 272     SET(d, a, b, c,  8, 11, T34);
 273     SET(c, d, a, b, 11, 16, T35);
 274     SET(b, c, d, a, 14, 23, T36);
 275     SET(a, b, c, d,  1,  4, T37);
 276     SET(d, a, b, c,  4, 11, T38);
 277     SET(c, d, a, b,  7, 16, T39);
 278     SET(b, c, d, a, 10, 23, T40);
 279     SET(a, b, c, d, 13,  4, T41);
 280     SET(d, a, b, c,  0, 11, T42);
 281     SET(c, d, a, b,  3, 16, T43);
 282     SET(b, c, d, a,  6, 23, T44);
 283     SET(a, b, c, d,  9,  4, T45);
 284     SET(d, a, b, c, 12, 11, T46);
 285     SET(c, d, a, b, 15, 16, T47);
 286     SET(b, c, d, a,  2, 23, T48);
 287 #undef SET
 288
 289      /* Round 4. */
 290      /* Let [abcd k s t] denote the operation
 291           a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
 292 #define I(x, y, z) ((y) ^ ((x) | ~(z)))
 293 #define SET(a, b, c, d, k, s, Ti)\
 294   t = a + I(b,c,d) + X[k] + Ti;\
 295   a = ROTATE_LEFT(t, s) + b
 296      /* Do the following 16 operations. */
 297     SET(a, b, c, d,  0,  6, T49);
 298     SET(d, a, b, c,  7, 10, T50);
 299     SET(c, d, a, b, 14, 15, T51);
 300     SET(b, c, d, a,  5, 21, T52);
 301     SET(a, b, c, d, 12,  6, T53);
 302     SET(d, a, b, c,  3, 10, T54);
 303     SET(c, d, a, b, 10, 15, T55);
 304     SET(b, c, d, a,  1, 21, T56);
 305     SET(a, b, c, d,  8,  6, T57);
 306     SET(d, a, b, c, 15, 10, T58);
 307     SET(c, d, a, b,  6, 15, T59);
 308     SET(b, c, d, a, 13, 21, T60);
 309     SET(a, b, c, d,  4,  6, T61);
 310     SET(d, a, b, c, 11, 10, T62);
 311     SET(c, d, a, b,  2, 15, T63);
 312     SET(b, c, d, a,  9, 21, T64);
 313 #undef SET
 314
 315      /* Then perform the following additions. (That is increment each
 316         of the four registers by the value it had before this block
 317         was started.) */
 318     pms->abcd[0] += a;
 319     pms->abcd[1] += b;
 320     pms->abcd[2] += c;
 321     pms->abcd[3] += d;
 322 }
 323
 324 void
 325 md5_init(md5_state_t *pms)
 326 {
 327     pms->count[0] = pms->count[1] = 0;
 328     pms->abcd[0] = 0x67452301;
 329     pms->abcd[1] = 0xefcdab89;
 330     pms->abcd[2] = 0x98badcfe;
 331     pms->abcd[3] = 0x10325476;
 332 }
 333
 334 void
 335 md5_append(md5_state_t *pms, const md5_byte_t *data, int nbytes)
 336 {
 337     const md5_byte_t *p = data;
 338     int left = nbytes;
 339     int offset = (pms->count[0] >> 3) & 63;
 340     md5_word_t nbits = (md5_word_t)(nbytes << 3);
 341
 342     if (nbytes <= 0)
 343         return;
 344
 345     /* Update the message length. */
 346     pms->count[1] += nbytes >> 29;
 347     pms->count[0] += nbits;
 348     if (pms->count[0] < nbits)
 349         pms->count[1]++;
 350
 351     /* Process an initial partial block. */
 352     if (offset) {
 353         int copy = (offset + nbytes > 64 ? 64 - offset : nbytes);
 354
 355         memcpy(pms->buf + offset, p, copy);
 356         if (offset + copy < 64)
 357             return;
 358         p += copy;
 359         left -= copy;
 360         md5_process(pms, pms->buf);
 361     }
 362
 363     /* Process full blocks. */
 364     for (; left >= 64; p += 64, left -= 64)
 365         md5_process(pms, p);
 366
 367     /* Process a final partial block. */
 368     if (left)
 369         memcpy(pms->buf, p, left);
 370 }
 371
 372 void
 373 md5_finish(md5_state_t *pms, md5_byte_t digest[16])
 374 {
 375     static const md5_byte_t pad[64] = {
 376         0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 377         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 378         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 379         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 380     };
 381     md5_byte_t data[8];
 382     int i;
 383
 384     /* Save the length before padding. */
 385     for (i = 0; i < 8; ++i)
 386         data[i] = (md5_byte_t)(pms->count[i >> 2] >> ((i & 3) << 3));
 387     /* Pad to 56 bytes mod 64. */
 388     md5_append(pms, pad, ((55 - (pms->count[0] >> 3)) & 63) + 1);
 389     /* Append the length. */
 390     md5_append(pms, data, 8);
 391     for (i = 0; i < 16; ++i)
 392         digest[i] = (md5_byte_t)(pms->abcd[i >> 2] >> ((i & 3) << 3));
 393 }