git.maemo.org Git - busybox4maemo/blob - 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 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         {       \
 212           a += FF (b, c, d) + (*cwp++ = SWAP_LE32(*words)) + T; \
 213           ++words;      \
 214           CYCLIC (a, s);        \
 215           a += b;       \
 216         }       \
 217       while (0)
 218
 219                 /* It is unfortunate that C does not provide an operator for
 220                    cyclic rotation.  Hope the C compiler is smart enough.  */
 221                 /* gcc 2.95.4 seems to be --aaronl */
 222 #  define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
 223
 224                 /* Before we start, one word to the strange constants.
 225                    They are defined in RFC 1321 as
 226
 227                    T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
 228                  */
 229
 230 #  if MD5_SIZE_VS_SPEED == 1
 231                 const uint32_t *pc;
 232                 const char *pp;
 233                 int i;
 234 #  endif        /* MD5_SIZE_VS_SPEED */
 235
 236                 /* Round 1.  */
 237 #  if MD5_SIZE_VS_SPEED == 1
 238                 pc = C_array;
 239                 for (i = 0; i < 4; i++) {
 240                         OP(A, B, C, D, 7, *pc++);
 241                         OP(D, A, B, C, 12, *pc++);
 242                         OP(C, D, A, B, 17, *pc++);
 243                         OP(B, C, D, A, 22, *pc++);
 244                 }
 245 #  else
 246                 OP(A, B, C, D, 7, 0xd76aa478);
 247                 OP(D, A, B, C, 12, 0xe8c7b756);
 248                 OP(C, D, A, B, 17, 0x242070db);
 249                 OP(B, C, D, A, 22, 0xc1bdceee);
 250                 OP(A, B, C, D, 7, 0xf57c0faf);
 251                 OP(D, A, B, C, 12, 0x4787c62a);
 252                 OP(C, D, A, B, 17, 0xa8304613);
 253                 OP(B, C, D, A, 22, 0xfd469501);
 254                 OP(A, B, C, D, 7, 0x698098d8);
 255                 OP(D, A, B, C, 12, 0x8b44f7af);
 256                 OP(C, D, A, B, 17, 0xffff5bb1);
 257                 OP(B, C, D, A, 22, 0x895cd7be);
 258                 OP(A, B, C, D, 7, 0x6b901122);
 259                 OP(D, A, B, C, 12, 0xfd987193);
 260                 OP(C, D, A, B, 17, 0xa679438e);
 261                 OP(B, C, D, A, 22, 0x49b40821);
 262 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 263
 264                 /* For the second to fourth round we have the possibly swapped words
 265                    in CORRECT_WORDS.  Redefine the macro to take an additional first
 266                    argument specifying the function to use.  */
 267 #  undef OP
 268 #  define OP(f, a, b, c, d, k, s, T)    \
 269       do        \
 270         {       \
 271           a += f (b, c, d) + correct_words[k] + T;      \
 272           CYCLIC (a, s);        \
 273           a += b;       \
 274         }       \
 275       while (0)
 276
 277                 /* Round 2.  */
 278 #  if MD5_SIZE_VS_SPEED == 1
 279                 pp = P_array;
 280                 for (i = 0; i < 4; i++) {
 281                         OP(FG, A, B, C, D, (int) (*pp++), 5, *pc++);
 282                         OP(FG, D, A, B, C, (int) (*pp++), 9, *pc++);
 283                         OP(FG, C, D, A, B, (int) (*pp++), 14, *pc++);
 284                         OP(FG, B, C, D, A, (int) (*pp++), 20, *pc++);
 285                 }
 286 #  else
 287                 OP(FG, A, B, C, D, 1, 5, 0xf61e2562);
 288                 OP(FG, D, A, B, C, 6, 9, 0xc040b340);
 289                 OP(FG, C, D, A, B, 11, 14, 0x265e5a51);
 290                 OP(FG, B, C, D, A, 0, 20, 0xe9b6c7aa);
 291                 OP(FG, A, B, C, D, 5, 5, 0xd62f105d);
 292                 OP(FG, D, A, B, C, 10, 9, 0x02441453);
 293                 OP(FG, C, D, A, B, 15, 14, 0xd8a1e681);
 294                 OP(FG, B, C, D, A, 4, 20, 0xe7d3fbc8);
 295                 OP(FG, A, B, C, D, 9, 5, 0x21e1cde6);
 296                 OP(FG, D, A, B, C, 14, 9, 0xc33707d6);
 297                 OP(FG, C, D, A, B, 3, 14, 0xf4d50d87);
 298                 OP(FG, B, C, D, A, 8, 20, 0x455a14ed);
 299                 OP(FG, A, B, C, D, 13, 5, 0xa9e3e905);
 300                 OP(FG, D, A, B, C, 2, 9, 0xfcefa3f8);
 301                 OP(FG, C, D, A, B, 7, 14, 0x676f02d9);
 302                 OP(FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
 303 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 304
 305                 /* Round 3.  */
 306 #  if MD5_SIZE_VS_SPEED == 1
 307                 for (i = 0; i < 4; i++) {
 308                         OP(FH, A, B, C, D, (int) (*pp++), 4, *pc++);
 309                         OP(FH, D, A, B, C, (int) (*pp++), 11, *pc++);
 310                         OP(FH, C, D, A, B, (int) (*pp++), 16, *pc++);
 311                         OP(FH, B, C, D, A, (int) (*pp++), 23, *pc++);
 312                 }
 313 #  else
 314                 OP(FH, A, B, C, D, 5, 4, 0xfffa3942);
 315                 OP(FH, D, A, B, C, 8, 11, 0x8771f681);
 316                 OP(FH, C, D, A, B, 11, 16, 0x6d9d6122);
 317                 OP(FH, B, C, D, A, 14, 23, 0xfde5380c);
 318                 OP(FH, A, B, C, D, 1, 4, 0xa4beea44);
 319                 OP(FH, D, A, B, C, 4, 11, 0x4bdecfa9);
 320                 OP(FH, C, D, A, B, 7, 16, 0xf6bb4b60);
 321                 OP(FH, B, C, D, A, 10, 23, 0xbebfbc70);
 322                 OP(FH, A, B, C, D, 13, 4, 0x289b7ec6);
 323                 OP(FH, D, A, B, C, 0, 11, 0xeaa127fa);
 324                 OP(FH, C, D, A, B, 3, 16, 0xd4ef3085);
 325                 OP(FH, B, C, D, A, 6, 23, 0x04881d05);
 326                 OP(FH, A, B, C, D, 9, 4, 0xd9d4d039);
 327                 OP(FH, D, A, B, C, 12, 11, 0xe6db99e5);
 328                 OP(FH, C, D, A, B, 15, 16, 0x1fa27cf8);
 329                 OP(FH, B, C, D, A, 2, 23, 0xc4ac5665);
 330 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 331
 332                 /* Round 4.  */
 333 #  if MD5_SIZE_VS_SPEED == 1
 334                 for (i = 0; i < 4; i++) {
 335                         OP(FI, A, B, C, D, (int) (*pp++), 6, *pc++);
 336                         OP(FI, D, A, B, C, (int) (*pp++), 10, *pc++);
 337                         OP(FI, C, D, A, B, (int) (*pp++), 15, *pc++);
 338                         OP(FI, B, C, D, A, (int) (*pp++), 21, *pc++);
 339                 }
 340 #  else
 341                 OP(FI, A, B, C, D, 0, 6, 0xf4292244);
 342                 OP(FI, D, A, B, C, 7, 10, 0x432aff97);
 343                 OP(FI, C, D, A, B, 14, 15, 0xab9423a7);
 344                 OP(FI, B, C, D, A, 5, 21, 0xfc93a039);
 345                 OP(FI, A, B, C, D, 12, 6, 0x655b59c3);
 346                 OP(FI, D, A, B, C, 3, 10, 0x8f0ccc92);
 347                 OP(FI, C, D, A, B, 10, 15, 0xffeff47d);
 348                 OP(FI, B, C, D, A, 1, 21, 0x85845dd1);
 349                 OP(FI, A, B, C, D, 8, 6, 0x6fa87e4f);
 350                 OP(FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
 351                 OP(FI, C, D, A, B, 6, 15, 0xa3014314);
 352                 OP(FI, B, C, D, A, 13, 21, 0x4e0811a1);
 353                 OP(FI, A, B, C, D, 4, 6, 0xf7537e82);
 354                 OP(FI, D, A, B, C, 11, 10, 0xbd3af235);
 355                 OP(FI, C, D, A, B, 2, 15, 0x2ad7d2bb);
 356                 OP(FI, B, C, D, A, 9, 21, 0xeb86d391);
 357 #  endif        /* MD5_SIZE_VS_SPEED == 1 */
 358 # endif /* MD5_SIZE_VS_SPEED > 1 */
 359
 360                 /* Add the starting values of the context.  */
 361                 A += A_save;
 362                 B += B_save;
 363                 C += C_save;
 364                 D += D_save;
 365
 366         /* Put checksum in context given as argument.  */
 367         ctx->A = A;
 368         ctx->B = B;
 369         ctx->C = C;
 370         ctx->D = D;
 371 }
 372
 373 /* Feed data through a temporary buffer to call md5_hash_aligned_block()
 374  * with chunks of data that are 4-byte aligned and a multiple of 64 bytes.
 375  * This function's internal buffer remembers previous data until it has 64
 376  * bytes worth to pass on.  Call md5_end() to flush this buffer. */
 377
 378 void md5_hash(const void *buffer, size_t len, md5_ctx_t *ctx)
 379 {
 380         char *buf=(char *)buffer;
 381
 382         /* RFC 1321 specifies the possible length of the file up to 2^64 bits,
 383          * Here we only track the number of bytes.  */
 384
 385         ctx->total += len;
 386
 387         // Process all input.
 388
 389         while (len) {
 390                 int i = 64 - ctx->buflen;
 391
 392                 // Copy data into aligned buffer.
 393
 394                 if (i > len) i = len;
 395                 memcpy(ctx->buffer + ctx->buflen, buf, i);
 396                 len -= i;
 397                 ctx->buflen += i;
 398                 buf += i;
 399
 400                 // When buffer fills up, process it.
 401
 402                 if (ctx->buflen == 64) {
 403                         md5_hash_block(ctx->buffer, ctx);
 404                         ctx->buflen = 0;
 405                 }
 406         }
 407 }
 408
 409 /* Process the remaining bytes in the buffer and put result from CTX
 410  * in first 16 bytes following RESBUF.  The result is always in little
 411  * endian byte order, so that a byte-wise output yields to the wanted
 412  * ASCII representation of the message digest.
 413  *
 414  * IMPORTANT: On some systems it is required that RESBUF is correctly
 415  * aligned for a 32 bits value.
 416  */
 417 void *md5_end(void *resbuf, md5_ctx_t *ctx)
 418 {
 419         char *buf = ctx->buffer;
 420         int i;
 421
 422         /* Pad data to block size.  */
 423
 424         buf[ctx->buflen++] = 0x80;
 425         memset(buf + ctx->buflen, 0, 128 - ctx->buflen);
 426
 427         /* Put the 64-bit file length in *bits* at the end of the buffer.  */
 428         ctx->total <<= 3;
 429         if (ctx->buflen > 56) buf += 64;
 430         for (i = 0; i < 8; i++)  buf[56 + i] = ctx->total >> (i*8);
 431
 432         /* Process last bytes.  */
 433         if (buf != ctx->buffer) md5_hash_block(ctx->buffer, ctx);
 434         md5_hash_block(buf, ctx);
 435
 436         /* Put result from CTX in first 16 bytes following RESBUF.  The result is
 437          * always in little endian byte order, so that a byte-wise output yields
 438          * to the wanted ASCII representation of the message digest.
 439          *
 440          * IMPORTANT: On some systems it is required that RESBUF is correctly
 441          * aligned for a 32 bits value.
 442          */
 443         ((uint32_t *) resbuf)[0] = SWAP_LE32(ctx->A);
 444         ((uint32_t *) resbuf)[1] = SWAP_LE32(ctx->B);
 445         ((uint32_t *) resbuf)[2] = SWAP_LE32(ctx->C);
 446         ((uint32_t *) resbuf)[3] = SWAP_LE32(ctx->D);
 447
 448         return resbuf;
 449 }
 450