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