libbb/md5.c

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