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