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