git.sesse.net Git - freerainbowtables/blob - Client Applications/rcracki_mt/fast_md5.cpp

   1 /*
   2  * Fast implementation of the MD5 message-digest algorithm as per RFC
   3  * (see http://tools.ietf.org/html/rfc1321)
   4  *
   5  * Author: Joao Inacio <jcinacio at gmail.com>
   6  * License: Use and share as you wish at your own risk, please keep this header ;)
   7  *
   8  * Optimizations:
   9  *  - For lengths < 16, transformation steps are "unrolled" using macros/defines
  10  *  - Constants used whenever possible, it's the compiler's job to sort them out
  11  *  - Padding is done on 4-byte words, and memory copied as last resort.
  12  */
  13
  14
  15 typedef unsigned int UINT4;
  16
  17
  18 /* MD5 defines as per RFC reference implementation */
  19
  20 #define AC1                             0xd76aa478
  21 #define AC2                             0xe8c7b756
  22 #define AC3                             0x242070db
  23 #define AC4                             0xc1bdceee
  24 #define AC5                             0xf57c0faf
  25 #define AC6                             0x4787c62a
  26 #define AC7                             0xa8304613
  27 #define AC8                             0xfd469501
  28 #define AC9                             0x698098d8
  29 #define AC10                    0x8b44f7af
  30 #define AC11                    0xffff5bb1
  31 #define AC12                    0x895cd7be
  32 #define AC13                    0x6b901122
  33 #define AC14                    0xfd987193
  34 #define AC15                    0xa679438e
  35 #define AC16                    0x49b40821
  36 #define AC17                    0xf61e2562
  37 #define AC18                    0xc040b340
  38 #define AC19                    0x265e5a51
  39 #define AC20                    0xe9b6c7aa
  40 #define AC21                    0xd62f105d
  41 #define AC22                    0x02441453
  42 #define AC23                    0xd8a1e681
  43 #define AC24                    0xe7d3fbc8
  44 #define AC25                    0x21e1cde6
  45 #define AC26                    0xc33707d6
  46 #define AC27                    0xf4d50d87
  47 #define AC28                    0x455a14ed
  48 #define AC29                    0xa9e3e905
  49 #define AC30                    0xfcefa3f8
  50 #define AC31                    0x676f02d9
  51 #define AC32                    0x8d2a4c8a
  52 #define AC33                    0xfffa3942
  53 #define AC34                    0x8771f681
  54 #define AC35                    0x6d9d6122
  55 #define AC36                    0xfde5380c
  56 #define AC37                    0xa4beea44
  57 #define AC38                    0x4bdecfa9
  58 #define AC39                    0xf6bb4b60
  59 #define AC40                    0xbebfbc70
  60 #define AC41                    0x289b7ec6
  61 #define AC42                    0xeaa127fa
  62 #define AC43                    0xd4ef3085
  63 #define AC44                    0x04881d05
  64 #define AC45                    0xd9d4d039
  65 #define AC46                    0xe6db99e5
  66 #define AC47                    0x1fa27cf8
  67 #define AC48                    0xc4ac5665
  68 #define AC49                    0xf4292244
  69 #define AC50                    0x432aff97
  70 #define AC51                    0xab9423a7
  71 #define AC52                    0xfc93a039
  72 #define AC53                    0x655b59c3
  73 #define AC54                    0x8f0ccc92
  74 #define AC55                    0xffeff47d
  75 #define AC56                    0x85845dd1
  76 #define AC57                    0x6fa87e4f
  77 #define AC58                    0xfe2ce6e0
  78 #define AC59                    0xa3014314
  79 #define AC60                    0x4e0811a1
  80 #define AC61                    0xf7537e82
  81 #define AC62                    0xbd3af235
  82 #define AC63                    0x2ad7d2bb
  83 #define AC64                    0xeb86d391
  84
  85 #define S11                              7
  86 #define S12                             12
  87 #define S13                             17
  88 #define S14                             22
  89 #define S21                              5
  90 #define S22                              9
  91 #define S23                             14
  92 #define S24                             20
  93 #define S31                              4
  94 #define S32                             11
  95 #define S33                             16
  96 #define S34                             23
  97 #define S41                              6
  98 #define S42                             10
  99 #define S43                             15
 100 #define S44                             21
 101
 102 #define Ca                              0x67452301
 103 #define Cb                              0xefcdab89
 104 #define Cc                              0x98badcfe
 105 #define Cd                              0x10325476
 106
 107
 108 #define F(x, y, z)                      ((z) ^ ((x) & ((y) ^ (z))))
 109 #define G(x, y, z)                      ((y) ^ ((z) & ((x) ^ (y))))
 110 //#define G(x, y, z)                    F((z), (x), (y))
 111 #define H(x, y, z)                      ((x) ^ (y) ^ (z))
 112 #define I(x, y, z)                      ((y) ^ ((x) | ~(z)))
 113
 114 #define ROTATE_LEFT(x, n)       (((x) << (n)) | ((x) >> (32-(n))))
 115
 116 // md5 step
 117 #define MD5STEP(f, a, b, c, d, AC, x, s) {      \
 118     (a) += f ((b), (c), (d));           \
 119         (a) += (AC) + (x);                              \
 120     (a) = ROTATE_LEFT ((a), (s));       \
 121         (a) += (b);                                             \
 122 }
 123
 124 // full MD5 transformation
 125 #define MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
 126         \
 127         MD5STEP(F, a, b, c, d,  AC1,  w0, S11);\
 128         MD5STEP(F, d, a, b, c,  AC2,  w1, S12);\
 129         MD5STEP(F, c, d, a, b,  AC3,  w2, S13);\
 130         MD5STEP(F, b, c, d, a,  AC4,  w3, S14);\
 131         MD5STEP(F, a, b, c, d,  AC5,  w4, S11);\
 132         MD5STEP(F, d, a, b, c,  AC6,  w5, S12);\
 133         MD5STEP(F, c, d, a, b,  AC7,  w6, S13);\
 134         MD5STEP(F, b, c, d, a,  AC8,  w7, S14);\
 135         MD5STEP(F, a, b, c, d,  AC9,  w8, S11);\
 136         MD5STEP(F, d, a, b, c, AC10,  w9, S12);\
 137         MD5STEP(F, c, d, a, b, AC11, w10, S13);\
 138         MD5STEP(F, b, c, d, a, AC12, w11, S14);\
 139         MD5STEP(F, a, b, c, d, AC13, w12, S11);\
 140         MD5STEP(F, d, a, b, c, AC14, w13, S12);\
 141         MD5STEP(F, c, d, a, b, AC15, w14, S13);\
 142         MD5STEP(F, b, c, d, a, AC16, w15, S14);\
 143         \
 144         MD5STEP(G, a, b, c, d, AC17,  w1, S21);\
 145         MD5STEP(G, d, a, b, c, AC18,  w6, S22);\
 146         MD5STEP(G, c, d, a, b, AC19, w11, S23);\
 147         MD5STEP(G, b, c, d, a, AC20,  w0, S24);\
 148         MD5STEP(G, a, b, c, d, AC21,  w5, S21);\
 149         MD5STEP(G, d, a, b, c, AC22, w10, S22);\
 150         MD5STEP(G, c, d, a, b, AC23, w15, S23);\
 151         MD5STEP(G, b, c, d, a, AC24,  w4, S24);\
 152         MD5STEP(G, a, b, c, d, AC25,  w9, S21);\
 153         MD5STEP(G, d, a, b, c, AC26, w14, S22);\
 154         MD5STEP(G, c, d, a, b, AC27,  w3, S23);\
 155         MD5STEP(G, b, c, d, a, AC28,  w8, S24);\
 156         MD5STEP(G, a, b, c, d, AC29, w13, S21);\
 157         MD5STEP(G, d, a, b, c, AC30,  w2, S22);\
 158         MD5STEP(G, c, d, a, b, AC31,  w7, S23);\
 159         MD5STEP(G, b, c, d, a, AC32, w12, S24);\
 160         \
 161         MD5STEP(H, a, b, c, d, AC33,  w5, S31);\
 162         MD5STEP(H, d, a, b, c, AC34,  w8, S32);\
 163         MD5STEP(H, c, d, a, b, AC35, w11, S33);\
 164         MD5STEP(H, b, c, d, a, AC36, w14, S34);\
 165         MD5STEP(H, a, b, c, d, AC37,  w1, S31);\
 166         MD5STEP(H, d, a, b, c, AC38,  w4, S32);\
 167         MD5STEP(H, c, d, a, b, AC39,  w7, S33);\
 168         MD5STEP(H, b, c, d, a, AC40, w10, S34);\
 169         MD5STEP(H, a, b, c, d, AC41, w13, S31);\
 170         MD5STEP(H, d, a, b, c, AC42,  w0, S32);\
 171         MD5STEP(H, c, d, a, b, AC43,  w3, S33);\
 172         MD5STEP(H, b, c, d, a, AC44,  w6, S34);\
 173         MD5STEP(H, a, b, c, d, AC45,  w9, S31);\
 174         MD5STEP(H, d, a, b, c, AC46, w12, S32);\
 175         MD5STEP(H, c, d, a, b, AC47, w15, S33);\
 176         MD5STEP(H, b, c, d, a, AC48,  w2, S34);\
 177         \
 178         MD5STEP(I, a, b, c, d, AC49,  w0, S41);\
 179         MD5STEP(I, d, a, b, c, AC50,  w7, S42);\
 180         MD5STEP(I, c, d, a, b, AC51, w14, S43);\
 181         MD5STEP(I, b, c, d, a, AC52,  w5, S44);\
 182         MD5STEP(I, a, b, c, d, AC53, w12, S41);\
 183         MD5STEP(I, d, a, b, c, AC54,  w3, S42);\
 184         MD5STEP(I, c, d, a, b, AC55, w10, S43);\
 185         MD5STEP(I, b, c, d, a, AC56,  w1, S44);\
 186         MD5STEP(I, a, b, c, d, AC57,  w8, S41);\
 187         MD5STEP(I, d, a, b, c, AC58, w15, S42);\
 188         MD5STEP(I, c, d, a, b, AC59,  w6, S43);\
 189         MD5STEP(I, b, c, d, a, AC60, w13, S44);\
 190         MD5STEP(I, a, b, c, d, AC61,  w4, S41);\
 191         MD5STEP(I, d, a, b, c, AC62, w11, S42);\
 192         MD5STEP(I, c, d, a, b, AC63,  w2, S43);\
 193         MD5STEP(I, b, c, d, a, AC64,  w9, S44);\
 194 }
 195
 196 // len >= 56
 197 #define MD5_transform_add(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
 198         \
 199         a = wOut[0]; b = wOut[1]; c = wOut[2]; d = wOut[3];\
 200         \
 201         MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15);\
 202         \
 203         wOut[0] += a; wOut[1] += b; wOut[2] += c; wOut[3] += d;\
 204 }
 205
 206 // len < 56
 207 #define MD5_transform_single(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
 208         \
 209         a = CC[0]; b=CC[1]; c=CC[2]; d=CC[3];\
 210         \
 211         MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15);\
 212         \
 213         wOut[0] = a+Ca; wOut[1] = b+Cb; wOut[2] = c+Cc; wOut[3] = d+Cd;\
 214 }
 215
 216 // len < 16
 217 #define MD5_transform_16(w0, w1, w2, w3, w14) \
 218          MD5_transform_single(w0, w1, w2, w3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, w14, 0);
 219
 220
 221 // pad word and append 0x80 at appropriate location
 222 #define MD5_pad_w0()            (0x00000080)
 223 #define MD5_pad_w1(data)        (((data) & 0x000000FF) | 0x00008000)
 224 #define MD5_pad_w2(data)        (((data) & 0x0000FFFF) | 0x00800000)
 225 #define MD5_pad_w3(data)        (((data) & 0x00FFFFFF) | 0x80000000)
 226
 227
 228 #ifndef MD5_pad_w1
 229 static inline UINT4 MD5_pad_w1(UINT4 data)
 230 {
 231         __asm__ (
 232                 "movb   %%al,   %%cl    \n\t"
 233                 "xorl   %1,             %1              \n\t"
 234                 "orb    $128,   %%ah    \n\t"
 235                 "movb   %%cl,   %%al    \n\t"
 236                 "movl   %1,     %0              \n\t"
 237                 : "=r" (data)
 238                 : "a" (data)
 239                 : "cl"
 240         );
 241         return data;
 242 }
 243 #endif
 244
 245 #ifndef MD5_pad_w3
 246 static inline UINT4 MD5_pad_w3(UINT4 data)
 247 {
 248         __asm__ (
 249                 "roll   $8,             %1              \n\t"
 250                 "movb   $128,   %%al    \n\t"
 251                 "rorl   $8,             %1              \n\t"
 252                 "movl   %1,     %0              \n\t"
 253                 : "=r" (data)
 254                 : "a" (data)
 255         );
 256         return data;
 257 }
 258 #endif
 259
 260
 261 static inline void MD5_copy_pad_block(UINT4 *dData, UINT4 *wIn, int blocklen, int len)
 262 {
 263         register int cl;
 264
 265         // copy full words
 266         for (cl = 0; cl < blocklen; cl++)
 267                 dData[cl] = wIn[cl];
 268
 269         // copy with padding
 270         switch (len & 0x03) {
 271                 case 0:
 272                         dData[cl] = MD5_pad_w0();
 273                         break;
 274                 case 1:
 275                         dData[cl] = MD5_pad_w1(wIn[cl]);
 276                         break;
 277                 case 2:
 278                         dData[cl] = MD5_pad_w2(wIn[cl]);
 279                         break;
 280                 case 3:
 281                         dData[cl] = MD5_pad_w3(wIn[cl]);
 282                         break;
 283         }
 284         // append 0's
 285         for (cl++; cl < 14; cl++)
 286                 dData[cl] = 0;
 287         // append len
 288         dData[cl++] = (len << 3);
 289         dData[cl] = (len >> 29);
 290 }
 291
 292 // fast initializer array
 293 //__attribute__((aligned(16)))
 294 //__declspec(align(16))
 295 static const UINT4 CC[4] = {Ca, Cb, Cc, Cd};
 296
 297
 298
 299 /*
 300  * fast_MD5()
 301  *
 302  */
 303 void fast_MD5(unsigned char *pData, int len, unsigned char *pDigest)
 304 {
 305         #define wIn             ((UINT4 *)pData)
 306         #define wOut    ((UINT4 *)pDigest)
 307
 308         register UINT4 a;
 309         register UINT4 b;
 310         register UINT4 c;
 311         register UINT4 d;
 312
 313         switch (len) {
 314                 case 0:
 315                         MD5_transform_16(MD5_pad_w0(), 0, 0, 0, 8*0);
 316                         return;
 317                 case 1:
 318                         MD5_transform_16(MD5_pad_w1(wIn[0]), 0, 0, 0, 8*1);
 319                         return;
 320                 case 2:
 321                         MD5_transform_16(MD5_pad_w2(wIn[0]), 0, 0, 0, 8*2);
 322                         return;
 323                 case 3:
 324                         MD5_transform_16(MD5_pad_w3(wIn[0]), 0, 0, 0, 8*3);
 325                         return;
 326                 case 4:
 327                         MD5_transform_16(wIn[0], MD5_pad_w0(), 0, 0, 8*4);
 328                         return;
 329                 case 5:
 330                         MD5_transform_16(wIn[0], MD5_pad_w1(wIn[1]), 0, 0, 8*5);
 331                         return;
 332                 case 6:
 333                         MD5_transform_16(wIn[0], MD5_pad_w2(wIn[1]), 0, 0, 8*6);
 334                         return;
 335                 case 7:
 336                         MD5_transform_16(wIn[0], MD5_pad_w3(wIn[1]), 0, 0, 8*7);
 337                         return;
 338                 case 8:
 339                         MD5_transform_16(wIn[0], wIn[1], MD5_pad_w0(), 0, 8*8);
 340                         return;
 341                 case 9:
 342                         MD5_transform_16(wIn[0], wIn[1], MD5_pad_w1(wIn[2]), 0, 8*9);
 343                         return;
 344                 case 10:
 345                         MD5_transform_16(wIn[0], wIn[1], MD5_pad_w2(wIn[2]), 0, 8*10);
 346                         return;
 347                 case 11:
 348                         MD5_transform_16(wIn[0], wIn[1], MD5_pad_w3(wIn[2]), 0, 8*11);
 349                         return;
 350                 case 12:
 351                         MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w0(), 8*12);
 352                         return;
 353                 case 13:
 354                         MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w1(wIn[3]), 8*13);
 355                         return;
 356                 case 14:
 357                         MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w2(wIn[3]), 8*14)
 358                         return;
 359                 case 15:
 360                         MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w3(wIn[3]), 8*15)
 361                         return;
 362         }
 363
 364         // data block used for padding
 365         UINT4 dData[16];
 366
 367         if (len < 56) {
 368                 // 16 < length < 56
 369
 370                 MD5_copy_pad_block(dData, wIn, (len >> 2), len);
 371
 372                 // redefine data input, point to padded data
 373                 #undef  wIn
 374                 #define wIn             dData
 375
 376                 MD5_transform_single (
 377                         wIn[ 0], wIn[ 1], wIn[ 2], wIn[ 3], wIn[ 4], wIn[ 5], wIn[ 6], wIn[ 7],
 378                         wIn[ 8], wIn[ 9], wIn[10], wIn[11], wIn[12], wIn[13], wIn[14], wIn[15]
 379                 );
 380
 381                 #undef  wIn
 382                 return;
 383         } else {
 384                 // len >= 56
 385
 386                 #define wIn             ((UINT4 *)pData)
 387
 388                 // original len
 389                 int tlen = len;
 390
 391                 // init digest for long lens
 392                 wOut[0] = Ca; wOut[1] = Cb; wOut[2] = Cc; wOut[3] = Cd;
 393
 394                 while (tlen >= 64) {
 395                         // Process 64-byte chunks
 396                         MD5_transform_add(
 397                                 wIn[ 0], wIn[ 1], wIn[ 2], wIn[ 3], wIn[ 4], wIn[ 5], wIn[ 6], wIn[ 7],
 398                                 wIn[ 8], wIn[ 9], wIn[10], wIn[11], wIn[12], wIn[13], wIn[14], wIn[15]
 399                         );
 400
 401                         tlen -= 64;
 402                         pData += 64;
 403                 }
 404
 405                 if (tlen >= 56) {
 406                         // Process > 56-byte chunk
 407
 408                         int cl = (tlen >> 2);
 409                         // perform padding on last 2 byte
 410                         if (cl > 14) {
 411                                 dData[14] = wIn[14];
 412                         } else {
 413                                 dData[15] = 0;
 414                         }
 415                         // copy 1 word with padding byte
 416                         switch (len & 0x03) {
 417                                 case 0:
 418                                         dData[cl] = MD5_pad_w0();
 419                                         break;
 420                                 case 1:
 421                                         dData[cl] = MD5_pad_w1(wIn[cl]);
 422                                         break;
 423                                 case 2:
 424                                         dData[cl] = MD5_pad_w2(wIn[cl]);
 425                                         break;
 426                                 case 3:
 427                                         dData[cl] = MD5_pad_w3(wIn[cl]);
 428                                         break;
 429                         }
 430
 431                         // transform
 432                         MD5_transform_add(
 433                                 wIn[ 0], wIn[ 1], wIn[ 2], wIn[ 3], wIn[ 4], wIn[ 5], wIn[ 6], wIn[ 7],
 434                                 wIn[ 8], wIn[ 9], wIn[10], wIn[11], wIn[12], wIn[13], dData[14], dData[15]
 435                         );
 436                         // final transform
 437                         #define w14             (len << 3)
 438                         #define w15             (len >> 29)
 439                         MD5_transform_add(
 440                                         0,          0,          0,              0,              0,              0,              0,              0,
 441                                         0,              0,              0,              0,              0,              0,    w14,        w15
 442                         );
 443                         #undef  w14
 444                         #undef  w15
 445                         return;
 446                 } else {
 447                         // (len mod 64) < 56
 448
 449                         MD5_copy_pad_block(dData, wIn, (tlen >> 2), len);
 450
 451                         #undef  wIn
 452                         #define wIn             dData
 453
 454                         // transform
 455                         MD5_transform_add(
 456                                 wIn[ 0], wIn[ 1], wIn[ 2], wIn[ 3], wIn[ 4], wIn[ 5], wIn[ 6], wIn[ 7],
 457                                 wIn[ 8], wIn[ 9], wIn[10], wIn[11], wIn[12], wIn[13], wIn[14], wIn[15]
 458                         );
 459
 460                         #undef  wIn
 461                         #define wIn             ((UINT4 *)pData)
 462                         return;
 463                 }
 464         }
 465
 466         /* end of fast_MD5() */
 467 }
 468