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