libbb/md5.c

   1 /*
   2  *  md5.c - Compute MD5 checksum of strings according to the
   3  *          definition of MD5 in RFC 1321 from April 1992.
   4  *
   5  *  Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
   6  *
   7  *  Copyright (C) 1995-1999 Free Software Foundation, Inc.
   8  *  Copyright (C) 2001 Manuel Novoa III
   9  *  Copyright (C) 2003 Glenn L. McGrath
  10  *  Copyright (C) 2003 Erik Andersen
  11  *
  12  *  Licensed under the GPL v2 or later, see the file LICENSE in this tarball.
  13  */
  14 #include <fcntl.h>
  15 #include <limits.h>
  16 #include <stdio.h>
  17 #include <stdint.h>
  18 #include <stdlib.h>
  19 #include <string.h>
  20 #include <unistd.h>
  21
  22 #include "libbb.h"
  23
  24 # if CONFIG_MD5_SIZE_VS_SPEED < 0 || CONFIG_MD5_SIZE_VS_SPEED > 3
  25 # define MD5_SIZE_VS_SPEED 2
  26 # else
  27 # define MD5_SIZE_VS_SPEED CONFIG_MD5_SIZE_VS_SPEED
  28 # endif
  29
  30 /* Handle endian-ness */
  31 # if !BB_BIG_ENDIAN
  32 #  define SWAP(n) (n)
  33 # elif defined(bswap_32)
  34 #  define SWAP(n) bswap_32(n)
  35 # else
  36 #  define SWAP(n) ((n << 24) | ((n&0xFF00)<<8) | ((n&0xFF0000)>>8) | (n>>24))
  37 # endif
  38
  39 /* Initialize structure containing state of computation.
  40  * (RFC 1321, 3.3: Step 3)
  41  */
  42 void md5_begin(md5_ctx_t *ctx)
  43 {
  44         ctx->A = 0x67452301;
  45         ctx->B = 0xefcdab89;
  46         ctx->C = 0x98badcfe;
  47         ctx->D = 0x10325476;
  48
  49         ctx->total = 0;
  50         ctx->buflen = 0;
  51 }
  52
  53 /* These are the four functions used in the four steps of the MD5 algorithm
  54  * and defined in the RFC 1321.  The first function is a little bit optimized
  55  * (as found in Colin Plumbs public domain implementation).
  56  * #define FF(b, c, d) ((b & c) | (~b & d))
  57  */
  58 # define FF(b, c, d) (d ^ (b & (c ^ d)))
  59 # define FG(b, c, d) FF (d, b, c)
  60 # define FH(b, c, d) (b ^ c ^ d)
  61 # define FI(b, c, d) (c ^ (b | ~d))
  62
  63 /* Hash a single block, 64 bytes long and 4-byte aligned. */
  64 static void md5_hash_block(const void *buffer, md5_ctx_t *ctx)
  65 {
  66         uint32_t correct_words[16];
  67         const uint32_t *words = buffer;
  68
  69 # if MD5_SIZE_VS_SPEED > 0
  70         static const uint32_t C_array[] = {
  71                 /* round 1 */
  72                 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
  73                 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
  74                 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
  75                 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
  76                 /* round 2 */
  77                 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
  78                 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
  79                 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
  80                 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
  81                 /* round 3 */
  82                 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
  83                 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
  84                 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
  85                 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
  86                 /* round 4 */
  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 P_array[] = {
  94 #  if MD5_SIZE_VS_SPEED > 1
  95                 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,   /* 1 */
  96 #  endif        /* MD5_SIZE_VS_SPEED > 1 */
  97                 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,   /* 2 */
  98                 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,   /* 3 */
  99                 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9    /* 4 */
 100         };
 101
 102 #  if MD5_SIZE_VS_SPEED > 1
 103         static const char S_array[] = {
 104                 7, 12, 17, 22,
 105                 5, 9, 14, 20,
 106                 4, 11, 16, 23,
 107                 6, 10, 15, 21
 108         };
 109 #  endif        /* MD5_SIZE_VS_SPEED > 1 */
 110 # endif
 111
 112         uint32_t A = ctx->A;
 113         uint32_t B = ctx->B;
 114         uint32_t C = ctx->C;
 115         uint32_t D = ctx->D;
 116
 117         /* Process all bytes in the buffer with 64 bytes in each round of
 118            the loop.  */
 119                 uint32_t *cwp = correct_words;
 120                 uint32_t A_save = A;
 121                 uint32_t B_save = B;
 122                 uint32_t C_save = C;
 123                 uint32_t D_save = D;
 124
 125 # if MD5_SIZE_VS_SPEED > 1
 126 #  define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
 127
 128                 const uint32_t *pc;
 129                 const char *pp;
 130                 const char *ps;
 131                 int i;
 132                 uint32_t temp;
 133
 134                 for (i = 0; i < 16; i++) {
 135                         cwp[i] = SWAP(words[i]);
 136                 }
 137                 words += 16;
 138
 139 #  if MD5_SIZE_VS_SPEED > 2
 140                 pc = C_array;
 141                 pp = P_array;
 142                 ps = S_array - 4;
 143
 144                 for (i = 0; i < 64; i++) {
 145                         if ((i & 0x0f) == 0)
 146                                 ps += 4;
 147                         temp = A;
 148                         switch (i >> 4) {
 149                         case 0:
 150                                 temp += FF(B, C, D);
 151                                 break;
 152                         case 1:
 153                                 temp += FG(B, C, D);
 154                                 break;
 155                         case 2:
 156                                 temp += FH(B, C, D);
 157                                 break;
 158                         case 3:
 159                                 temp += FI(B, C, D);
 160                         }
 161                         temp += cwp[(int) (*pp++)] + *pc++;
 162                         CYCLIC(temp, ps[i & 3]);
 163                         temp += B;
 164                         A = D;
 165                         D = C;
 166                         C = B;
 167                         B = temp;
 168                 }
 169 #  else
 170                 pc = C_array;
 171                 pp = P_array;
 172                 ps = S_array;
 173
 174                 for (i = 0; i < 16; i++) {
 175                         temp = A + FF(B, C, D) + cwp[(int) (*pp++)] + *pc++;
 176                         CYCLIC(temp, ps[i & 3]);
 177                         temp += B;
 178                         A = D;
 179                         D = C;
 180                         C = B;
 181                         B = temp;
 182                 }
 183
 184                 ps += 4;
 185                 for (i = 0; i < 16; i++) {
 186                         temp = A + FG(B, C, D) + cwp[(int) (*pp++)] + *pc++;
 187                         CYCLIC(temp, ps[i & 3]);
 188                         temp += B;
 189                         A = D;
 190                         D = C;
 191                         C = B;
 192                         B = temp;
 193                 }
 194                 ps += 4;
 195                 for (i = 0; i < 16; i++) {
 196                         temp = A + FH(B, C, D) + cwp[(int) (*pp++)] + *pc++;
 197                         CYCLIC(temp, ps[i & 3]);
 198                         temp += B;
 199                         A = D;
 200                         D = C;
 201                         C = B;
 202                         B = temp;
 203                 }
 204                 ps += 4;
 205                 for (i = 0; i < 16; i++) {
 206                         temp = A + FI(B, C, D) + cwp[(int) (*pp++)] + *pc++;
 207                         CYCLIC(temp, ps[i & 3]);
 208                         temp += B;
 209                         A = D;
 210                         D = C;
 211                         C = B;
 212                         B = temp;
 213                 }
 214
 215 #  endif        /* MD5_SIZE_VS_SPEED > 2 */
 216 # else
 217                 /* First round: using the given function, the context and a constant
 218                    the next context is computed.  Because the algorithms processing
 219                    unit is a 32-bit word and it is determined to work on words in
 220                    little endian byte order we perhaps have to change the byte order
 221                    before the computation.  To reduce the work for the next steps
 222                    we store the swapped words in the array CORRECT_WORDS.  */
 223
 224 #  define OP(a, b, c, d, s, T)  \
 225       do        \
 226         {       \
 227           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;     \
 228           ++words;      \
 229           CYCLIC (a, s);        \
 230           a += b;       \
 231         }       \
 232       while (0)
 233
 234                 /* It is unfortunate that C does not provide an operator for
 235                    cyclic rotation.  Hope the C compiler is smart enough.  */
 236                 /* gcc 2.95.4 seems to be --aaronl */
 237 #  define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
 238
 239                 /* Before we start, one word to the strange constants.
 240                    They are defined in RFC 1321 as
 241
 242                    T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
 243                  */
 244
 245 #  if MD5_SIZE_VS_SPEED == 1
 246                 const uint32_t *pc;
 247                 const char *pp;
 248                 int i;
 249 #  endif        /* MD5_SIZE_VS_SPEED */
 250
 251                 /* Round 1.  */
 252 #  if MD5_SIZE_VS_SPEED == 1
 253                 pc = C_array;
 254                 for (i = 0; i < 4; i++) {
 255                         OP(A, B, C, D, 7, *pc++);
 256                         OP(D, A, B, C, 12, *pc++);
 257                         OP(C, D, A, B, 17, *pc++);
 258                         OP(B, C, D, A, 22, *pc++);
 259                 }
 260 #  else
 261                 OP(A, B, C, D, 7, 0xd76aa478);
 262                 OP(D, A, B, C, 12, 0xe8c7b756);
 263                 OP(C, D, A, B, 17, 0x242070db);
 264                 OP(B, C, D, A, 22, 0xc1bdceee);
 265                 OP(A, B, C, D, 7, 0xf57c0faf);
 266                 OP(D, A, B, C, 12, 0x4787c62a);
 267                 OP(C, D, A, B, 17, 0xa8304613);
 268                 OP(B, C, D, A, 22, 0xfd469501);
 269                 OP(A, B, C, D, 7, 0x698098d8);
 270                 OP(D, A, B, C, 12, 0x8b44f7af);
 271                 OP(C, D, A, B, 17, 0xffff5bb1);
 272                 OP(B, C, D, A, 22, 0x895cd7be);
 273                 OP(A, B, C, D, 7, 0x6b901122);
 274                 OP(D, A, B, C, 12, 0xfd987193);
 275                 OP(C, D, A, B, 17, 0xa679438e);
 276                 OP(B, C, D, A, 22, 0x49b40821);
 277 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 278
 279                 /* For the second to fourth round we have the possibly swapped words
 280                    in CORRECT_WORDS.  Redefine the macro to take an additional first
 281                    argument specifying the function to use.  */
 282 #  undef OP
 283 #  define OP(f, a, b, c, d, k, s, T)    \
 284       do        \
 285         {       \
 286           a += f (b, c, d) + correct_words[k] + T;      \
 287           CYCLIC (a, s);        \
 288           a += b;       \
 289         }       \
 290       while (0)
 291
 292                 /* Round 2.  */
 293 #  if MD5_SIZE_VS_SPEED == 1
 294                 pp = P_array;
 295                 for (i = 0; i < 4; i++) {
 296                         OP(FG, A, B, C, D, (int) (*pp++), 5, *pc++);
 297                         OP(FG, D, A, B, C, (int) (*pp++), 9, *pc++);
 298                         OP(FG, C, D, A, B, (int) (*pp++), 14, *pc++);
 299                         OP(FG, B, C, D, A, (int) (*pp++), 20, *pc++);
 300                 }
 301 #  else
 302                 OP(FG, A, B, C, D, 1, 5, 0xf61e2562);
 303                 OP(FG, D, A, B, C, 6, 9, 0xc040b340);
 304                 OP(FG, C, D, A, B, 11, 14, 0x265e5a51);
 305                 OP(FG, B, C, D, A, 0, 20, 0xe9b6c7aa);
 306                 OP(FG, A, B, C, D, 5, 5, 0xd62f105d);
 307                 OP(FG, D, A, B, C, 10, 9, 0x02441453);
 308                 OP(FG, C, D, A, B, 15, 14, 0xd8a1e681);
 309                 OP(FG, B, C, D, A, 4, 20, 0xe7d3fbc8);
 310                 OP(FG, A, B, C, D, 9, 5, 0x21e1cde6);
 311                 OP(FG, D, A, B, C, 14, 9, 0xc33707d6);
 312                 OP(FG, C, D, A, B, 3, 14, 0xf4d50d87);
 313                 OP(FG, B, C, D, A, 8, 20, 0x455a14ed);
 314                 OP(FG, A, B, C, D, 13, 5, 0xa9e3e905);
 315                 OP(FG, D, A, B, C, 2, 9, 0xfcefa3f8);
 316                 OP(FG, C, D, A, B, 7, 14, 0x676f02d9);
 317                 OP(FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
 318 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 319
 320                 /* Round 3.  */
 321 #  if MD5_SIZE_VS_SPEED == 1
 322                 for (i = 0; i < 4; i++) {
 323                         OP(FH, A, B, C, D, (int) (*pp++), 4, *pc++);
 324                         OP(FH, D, A, B, C, (int) (*pp++), 11, *pc++);
 325                         OP(FH, C, D, A, B, (int) (*pp++), 16, *pc++);
 326                         OP(FH, B, C, D, A, (int) (*pp++), 23, *pc++);
 327                 }
 328 #  else
 329                 OP(FH, A, B, C, D, 5, 4, 0xfffa3942);
 330                 OP(FH, D, A, B, C, 8, 11, 0x8771f681);
 331                 OP(FH, C, D, A, B, 11, 16, 0x6d9d6122);
 332                 OP(FH, B, C, D, A, 14, 23, 0xfde5380c);
 333                 OP(FH, A, B, C, D, 1, 4, 0xa4beea44);
 334                 OP(FH, D, A, B, C, 4, 11, 0x4bdecfa9);
 335                 OP(FH, C, D, A, B, 7, 16, 0xf6bb4b60);
 336                 OP(FH, B, C, D, A, 10, 23, 0xbebfbc70);
 337                 OP(FH, A, B, C, D, 13, 4, 0x289b7ec6);
 338                 OP(FH, D, A, B, C, 0, 11, 0xeaa127fa);
 339                 OP(FH, C, D, A, B, 3, 16, 0xd4ef3085);
 340                 OP(FH, B, C, D, A, 6, 23, 0x04881d05);
 341                 OP(FH, A, B, C, D, 9, 4, 0xd9d4d039);
 342                 OP(FH, D, A, B, C, 12, 11, 0xe6db99e5);
 343                 OP(FH, C, D, A, B, 15, 16, 0x1fa27cf8);
 344                 OP(FH, B, C, D, A, 2, 23, 0xc4ac5665);
 345 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 346
 347                 /* Round 4.  */
 348 #  if MD5_SIZE_VS_SPEED == 1
 349                 for (i = 0; i < 4; i++) {
 350                         OP(FI, A, B, C, D, (int) (*pp++), 6, *pc++);
 351                         OP(FI, D, A, B, C, (int) (*pp++), 10, *pc++);
 352                         OP(FI, C, D, A, B, (int) (*pp++), 15, *pc++);
 353                         OP(FI, B, C, D, A, (int) (*pp++), 21, *pc++);
 354                 }
 355 #  else
 356                 OP(FI, A, B, C, D, 0, 6, 0xf4292244);
 357                 OP(FI, D, A, B, C, 7, 10, 0x432aff97);
 358                 OP(FI, C, D, A, B, 14, 15, 0xab9423a7);
 359                 OP(FI, B, C, D, A, 5, 21, 0xfc93a039);
 360                 OP(FI, A, B, C, D, 12, 6, 0x655b59c3);
 361                 OP(FI, D, A, B, C, 3, 10, 0x8f0ccc92);
 362                 OP(FI, C, D, A, B, 10, 15, 0xffeff47d);
 363                 OP(FI, B, C, D, A, 1, 21, 0x85845dd1);
 364                 OP(FI, A, B, C, D, 8, 6, 0x6fa87e4f);
 365                 OP(FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
 366                 OP(FI, C, D, A, B, 6, 15, 0xa3014314);
 367                 OP(FI, B, C, D, A, 13, 21, 0x4e0811a1);
 368                 OP(FI, A, B, C, D, 4, 6, 0xf7537e82);
 369                 OP(FI, D, A, B, C, 11, 10, 0xbd3af235);
 370                 OP(FI, C, D, A, B, 2, 15, 0x2ad7d2bb);
 371                 OP(FI, B, C, D, A, 9, 21, 0xeb86d391);
 372 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 373 # endif /* MD5_SIZE_VS_SPEED > 1 */
 374
 375                 /* Add the starting values of the context.  */
 376                 A += A_save;
 377                 B += B_save;
 378                 C += C_save;
 379                 D += D_save;
 380
 381         /* Put checksum in context given as argument.  */
 382         ctx->A = A;
 383         ctx->B = B;
 384         ctx->C = C;
 385         ctx->D = D;
 386 }
 387
 388 /* Feed data through a temporary buffer to call md5_hash_aligned_block()
 389  * with chunks of data that are 4-byte aligned and a multiple of 64 bytes.
 390  * This function's internal buffer remembers previous data until it has 64
 391  * bytes worth to pass on.  Call md5_end() to flush this buffer. */
 392
 393 void md5_hash(const void *buffer, size_t len, md5_ctx_t *ctx)
 394 {
 395         char *buf=(char *)buffer;
 396
 397         /* RFC 1321 specifies the possible length of the file up to 2^64 bits,
 398          * Here we only track the number of bytes.  */
 399
 400         ctx->total += len;
 401
 402         // Process all input.
 403
 404         while (len) {
 405                 int i = 64 - ctx->buflen;
 406
 407                 // Copy data into aligned buffer.
 408
 409                 if (i > len) i = len;
 410                 memcpy(ctx->buffer + ctx->buflen, buf, i);
 411                 len -= i;
 412                 ctx->buflen += i;
 413                 buf += i;
 414
 415                 // When buffer fills up, process it.
 416
 417                 if (ctx->buflen == 64) {
 418                         md5_hash_block(ctx->buffer, ctx);
 419                         ctx->buflen = 0;
 420                 }
 421         }
 422 }
 423
 424 /* Process the remaining bytes in the buffer and put result from CTX
 425  * in first 16 bytes following RESBUF.  The result is always in little
 426  * endian byte order, so that a byte-wise output yields to the wanted
 427  * ASCII representation of the message digest.
 428  *
 429  * IMPORTANT: On some systems it is required that RESBUF is correctly
 430  * aligned for a 32 bits value.
 431  */
 432 void *md5_end(void *resbuf, md5_ctx_t *ctx)
 433 {
 434         char *buf = ctx->buffer;
 435         int i;
 436
 437         /* Pad data to block size.  */
 438
 439         buf[ctx->buflen++] = 0x80;
 440         memset(buf + ctx->buflen, 0, 128 - ctx->buflen);
 441
 442         /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 443         ctx->total <<= 3;
 444         if (ctx->buflen > 56) buf += 64;
 445         for (i = 0; i < 8; i++)  buf[56 + i] = ctx->total >> (i*8);
 446
 447         /* Process last bytes.  */
 448         if (buf != ctx->buffer) md5_hash_block(ctx->buffer, ctx);
 449         md5_hash_block(buf, ctx);
 450
 451         /* Put result from CTX in first 16 bytes following RESBUF.  The result is
 452          * always in little endian byte order, so that a byte-wise output yields
 453          * to the wanted ASCII representation of the message digest.
 454          *
 455          * IMPORTANT: On some systems it is required that RESBUF is correctly
 456          * aligned for a 32 bits value.
 457          */
 458         ((uint32_t *) resbuf)[0] = SWAP(ctx->A);
 459         ((uint32_t *) resbuf)[1] = SWAP(ctx->B);
 460         ((uint32_t *) resbuf)[2] = SWAP(ctx->C);
 461         ((uint32_t *) resbuf)[3] = SWAP(ctx->D);
 462
 463         return resbuf;
 464 }
 465