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