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