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