2 * Fast implementation of the MD5 message-digest algorithm as per RFC
3 * (see http://tools.ietf.org/html/rfc1321)
5 * Author: Joao Inacio <jcinacio at gmail.com>
6 * License: Use and share as you wish at your own risk, please keep this header ;)
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.
13 * rcracki_mt is a multithreaded implementation and fork of the original
16 * Copyright 2009, 2010 Daniƫl Niggebrugge <niggebrugge@fox-it.com>
17 * Copyright 2009, 2010 James Nobis <frt@quelrod.net>
19 * This file is part of rcracki_mt.
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.
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.
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/>.
37 /* MD5 defines as per RFC reference implementation */
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
121 #define Ca 0x67452301
122 #define Cb 0xefcdab89
123 #define Cc 0x98badcfe
124 #define Cd 0x10325476
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)))
133 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
136 #define MD5STEP(f, a, b, c, d, AC, x, s) { \
137 (a) += f ((b), (c), (d)); \
139 (a) = ROTATE_LEFT ((a), (s)); \
143 // full MD5 transformation
144 #define MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
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);\
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);\
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);\
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);\
216 #define MD5_transform_add(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
218 a = wOut[0]; b = wOut[1]; c = wOut[2]; d = wOut[3];\
220 MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15);\
222 wOut[0] += a; wOut[1] += b; wOut[2] += c; wOut[3] += d;\
226 #define MD5_transform_single(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15) { \
228 a = CC[0]; b=CC[1]; c=CC[2]; d=CC[3];\
230 MD5_steps(w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15);\
232 wOut[0] = a+Ca; wOut[1] = b+Cb; wOut[2] = c+Cc; wOut[3] = d+Cd;\
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);
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)
248 static inline uint32 MD5_pad_w1(uint32 data)
252 "movb %%al, %%cl \n\t"
254 "orb $128, %%ah \n\t"
255 "movb %%cl, %%al \n\t"
266 static inline uint32 MD5_pad_w3(uint32 data)
271 "movb $128, %%al \n\t"
282 static inline void MD5_copy_pad_block(uint32 *dData, uint32 *wIn, int blocklen, int len)
287 for (cl = 0; cl < blocklen; cl++)
291 switch (len & 0x03) {
293 dData[cl] = MD5_pad_w0();
296 dData[cl] = MD5_pad_w1(wIn[cl]);
299 dData[cl] = MD5_pad_w2(wIn[cl]);
302 dData[cl] = MD5_pad_w3(wIn[cl]);
306 for (cl++; cl < 14; cl++)
309 dData[cl++] = (len << 3);
310 dData[cl] = (len >> 29);
313 // fast initializer array
314 //__attribute__((aligned(16)))
315 //__declspec(align(16))
316 static const uint32 CC[4] = {Ca, Cb, Cc, Cd};
324 void fast_MD5(unsigned char *pData, int len, unsigned char *pDigest)
326 #define wIn ((uint32 *)pData)
327 #define wOut ((uint32 *)pDigest)
336 MD5_transform_16(MD5_pad_w0(), 0, 0, 0, 8*0);
339 MD5_transform_16(MD5_pad_w1(wIn[0]), 0, 0, 0, 8*1);
342 MD5_transform_16(MD5_pad_w2(wIn[0]), 0, 0, 0, 8*2);
345 MD5_transform_16(MD5_pad_w3(wIn[0]), 0, 0, 0, 8*3);
348 MD5_transform_16(wIn[0], MD5_pad_w0(), 0, 0, 8*4);
351 MD5_transform_16(wIn[0], MD5_pad_w1(wIn[1]), 0, 0, 8*5);
354 MD5_transform_16(wIn[0], MD5_pad_w2(wIn[1]), 0, 0, 8*6);
357 MD5_transform_16(wIn[0], MD5_pad_w3(wIn[1]), 0, 0, 8*7);
360 MD5_transform_16(wIn[0], wIn[1], MD5_pad_w0(), 0, 8*8);
363 MD5_transform_16(wIn[0], wIn[1], MD5_pad_w1(wIn[2]), 0, 8*9);
366 MD5_transform_16(wIn[0], wIn[1], MD5_pad_w2(wIn[2]), 0, 8*10);
369 MD5_transform_16(wIn[0], wIn[1], MD5_pad_w3(wIn[2]), 0, 8*11);
372 MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w0(), 8*12);
375 MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w1(wIn[3]), 8*13);
378 MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w2(wIn[3]), 8*14)
381 MD5_transform_16(wIn[0], wIn[1], wIn[2], MD5_pad_w3(wIn[3]), 8*15)
385 // data block used for padding
391 MD5_copy_pad_block(dData, wIn, (len >> 2), len);
393 // redefine data input, point to padded data
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]
407 #define wIn ((uint32 *)pData)
412 // init digest for long lens
413 wOut[0] = Ca; wOut[1] = Cb; wOut[2] = Cc; wOut[3] = Cd;
416 // Process 64-byte chunks
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]
427 // Process > 56-byte chunk
429 int cl = (tlen >> 2);
430 // perform padding on last 2 byte
436 // copy 1 word with padding byte
437 switch (len & 0x03) {
439 dData[cl] = MD5_pad_w0();
442 dData[cl] = MD5_pad_w1(wIn[cl]);
445 dData[cl] = MD5_pad_w2(wIn[cl]);
448 dData[cl] = MD5_pad_w3(wIn[cl]);
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]
458 #define w14 (len << 3)
459 #define w15 (len >> 29)
461 0, 0, 0, 0, 0, 0, 0, 0,
462 0, 0, 0, 0, 0, 0, w14, w15
470 MD5_copy_pad_block(dData, wIn, (tlen >> 2), len);
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]
482 #define wIn ((uint32 *)pData)
487 /* end of fast_MD5() */