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