source: trunk/CrypPlugins/MD5Collider/Algorithm/StevensCollider.cs @ 1183

Last change on this file since 1183 was 1183, checked in by pretzsch, 12 years ago

+ MD5Collider: Added description
+ MD5Collider: Added new optional input allowing user to specify prefix of generated colliding data blocks
o MD5Collider: Made RandomSeed input optional

File size: 93.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Security.Cryptography;
6using System.Threading;
7
8namespace Cryptool.Plugins.MD5Collider.Algorithm
9{
10    class StevensCollider : MD5ColliderBase
11    {
12        protected override void PerformFindCollision()
13        {
14            IsStopped = false;
15
16            byte[] seedBytesMd5 = MD5.Create().ComputeHash(RandomSeed);
17            seed32_1 = (UInt32)(BitConverter.ToInt32(seedBytesMd5, 0) ^ BitConverter.ToInt32(seedBytesMd5, 4));
18            seed32_2 = (UInt32)(BitConverter.ToInt32(seedBytesMd5, 8) ^ BitConverter.ToInt32(seedBytesMd5, 12));
19
20            UInt32[] startIV = new UInt32[4];
21            startIV[0] = toLittleEndianInteger(IHV, 0);
22            startIV[1] = toLittleEndianInteger(IHV, 4);
23            startIV[2] = toLittleEndianInteger(IHV, 8);
24            startIV[3] = toLittleEndianInteger(IHV, 12);
25
26            UInt32[] m1b0 = new UInt32[16], m1b1 = new UInt32[16], m2b0 = new UInt32[16], m2b1 = new UInt32[16];
27            find_collision(startIV, m1b0, m1b1, m2b0, m2b1);
28
29            if (IsStopped)
30                return;
31
32            byte[] firstMessage = new byte[128];
33            byte[] secondMessage = new byte[128];
34
35            dumpLittleEndianIntegers(m1b0, firstMessage, 0);
36            dumpLittleEndianIntegers(m1b1, firstMessage, 64);
37
38            dumpLittleEndianIntegers(m2b0, secondMessage, 0);
39            dumpLittleEndianIntegers(m2b1, secondMessage, 64);
40
41            FirstCollidingData = firstMessage;
42            SecondCollidingData = secondMessage;
43        }
44
45        private void dumpLittleEndianIntegers(UInt32[] sourceArray, byte[] targetArray, int targetOffset)
46        {
47            for (int i = 0; i < sourceArray.Length; i++)
48                dumpLittleEndianInteger(sourceArray[i], targetArray, targetOffset + i * 4);
49        }
50
51        private void dumpLittleEndianInteger(UInt32 integerValue, byte[] targetArray, int targetOffset)
52        {
53            byte[] result = BitConverter.GetBytes(integerValue);
54            if (!BitConverter.IsLittleEndian)
55                Array.Reverse(result);
56
57            Array.Copy(result, 0, targetArray, targetOffset, 4);
58        }
59
60        private UInt32 toLittleEndianInteger(byte[] bytes, int offset)
61        {
62            byte[] bytesInProperOrder = new byte[4];
63            Array.Copy(bytes, offset, bytesInProperOrder, 0, 4);
64            if (!BitConverter.IsLittleEndian)
65                Array.Reverse(bytesInProperOrder);
66
67            return BitConverter.ToUInt32(bytesInProperOrder, 0);
68        }
69        private UInt32 toLittleEndianInteger(byte[] bytes)
70        {
71            return toLittleEndianInteger(bytes, 0);
72        }
73
74        void find_collision(UInt32[] IV, UInt32[] msg1block0, UInt32[] msg1block1, UInt32[] msg2block0, UInt32[] msg2block1)
75        {
76            find_block0(msg1block0, IV);
77
78            if (IsStopped)
79                return;
80
81            UInt32[] IHV = new[] { IV[0], IV[1], IV[2], IV[3] };
82            md5_compress(IHV, msg1block0);
83
84            find_block1(msg1block1, IHV);
85
86            if (IsStopped)
87                return;
88
89            for (int t = 0; t < 16; ++t)
90            {
91                msg2block0[t] = msg1block0[t];
92                msg2block1[t] = msg1block1[t];
93            }
94
95            msg2block0[4] += (UInt32)1 << 31; msg2block0[11] += 1 << 15; msg2block0[14] += (UInt32)1 << 31;
96            msg2block1[4] += (UInt32)1 << 31; msg2block1[11] -= 1 << 15; msg2block1[14] += (UInt32)1 << 31;
97        }
98
99        UInt32 xrng64()
100        {
101            UInt32 t = seed32_1 ^ (seed32_1 << 10);
102            seed32_1 = seed32_2;
103            seed32_2 = (seed32_2 ^ (seed32_2 >> 10)) ^ (t ^ (t >> 13));
104
105            return seed32_1;
106        }
107
108        UInt32 seed32_1, seed32_2;
109
110        private readonly int Qoff = 3;
111        delegate UInt32 RoundFunctionDelegate(UInt32 b, UInt32 c, UInt32 d);
112
113        UInt32 FF(UInt32 b, UInt32 c, UInt32 d)
114        { return d ^ (b & (c ^ d)); }
115
116        UInt32 GG(UInt32 b, UInt32 c, UInt32 d)
117        { return c ^ (d & (b ^ c)); }
118
119        UInt32 HH(UInt32 b, UInt32 c, UInt32 d)
120        { return b ^ c ^ d; }
121
122        UInt32 II(UInt32 b, UInt32 c, UInt32 d)
123        { return c ^ (b | ~d); }
124
125        UInt32 RL(UInt32 x, int n)
126        { return (x << n) | (x >> (32 - n)); }
127
128        UInt32 RR(UInt32 x, int n)
129        { return (x >> n) | (x << (32 - n)); }
130
131
132        void MD5_REVERSE_STEP(UInt32[] block, UInt32[] Q, int t, UInt32 AC, int RC)
133        {
134            block[t] = Q[Qoff + t + 1] - Q[Qoff + t];
135            block[t] = RR(block[t], RC) - FF(Q[Qoff + t], Q[Qoff + t - 1], Q[Qoff + t - 2]) - Q[Qoff + t - 3] - AC;
136        }
137
138        void find_block0(UInt32[] block, UInt32[] IV)
139        {
140            MatchProgressMax = 9;
141            MatchProgress = 0;
142
143            UInt32[] Q = new UInt32[68];
144            Q[0] = IV[0];
145            Q[1] = IV[3];
146            Q[2] = IV[2];
147            Q[3] = IV[1];
148
149            UInt32[] q4mask = new UInt32[1 << 4];
150            for (UInt32 k = 0; k < q4mask.Length; ++k)
151                q4mask[k] = ((k << 2) ^ (k << 26)) & 0x38000004;
152
153            UInt32[] q9q10mask = new UInt32[1 << 3];
154            for (UInt32 k = 0; k < q9q10mask.Length; ++k)
155                q9q10mask[k] = ((k << 13) ^ (k << 4)) & 0x2060;
156
157            UInt32[] q9mask = new UInt32[1 << 16];
158            for (UInt32 k = 0; k < q9mask.Length; ++k)
159                q9mask[k] = ((k << 1) ^ (k << 2) ^ (k << 5) ^ (k << 7) ^ (k << 8) ^ (k << 10) ^ (k << 11) ^ (k << 13)) & 0x0eb94f16;
160           
161            while (true)
162            {
163                if (IsStopped)
164                    return;
165
166                MatchProgress = 1;
167
168                Q[Qoff + 1] = xrng64();
169                Q[Qoff + 3] = (xrng64() & 0xfe87bc3f) | 0x017841c0;
170                Q[Qoff + 4] = (xrng64() & 0x44000033) | 0x000002c0 | (Q[Qoff + 3] & 0x0287bc00);
171                Q[Qoff + 5] = 0x41ffffc8 | (Q[Qoff + 4] & 0x04000033);
172                Q[Qoff + 6] = 0xb84b82d6;
173                Q[Qoff + 7] = (xrng64() & 0x68000084) | 0x02401b43;
174                Q[Qoff + 8] = (xrng64() & 0x2b8f6e04) | 0x005090d3 | (~Q[Qoff + 7] & 0x40000000);
175                Q[Qoff + 9] = 0x20040068 | (Q[Qoff + 8] & 0x00020000) | (~Q[Qoff + 8] & 0x40000000);
176                Q[Qoff + 10] = (xrng64() & 0x40000000) | 0x1040b089;
177                Q[Qoff + 11] = (xrng64() & 0x10408008) | 0x0fbb7f16 | (~Q[Qoff + 10] & 0x40000000);
178                Q[Qoff + 12] = (xrng64() & 0x1ed9df7f) | 0x00022080 | (~Q[Qoff + 11] & 0x40200000);
179                Q[Qoff + 13] = (xrng64() & 0x5efb4f77) | 0x20049008;
180                Q[Qoff + 14] = (xrng64() & 0x1fff5f77) | 0x0000a088 | (~Q[Qoff + 13] & 0x40000000);
181                Q[Qoff + 15] = (xrng64() & 0x5efe7ff7) | 0x80008000 | (~Q[Qoff + 14] & 0x00010000);
182                Q[Qoff + 16] = (xrng64() & 0x1ffdffff) | 0xa0000000 | (~Q[Qoff + 15] & 0x40020000);
183
184                MD5_REVERSE_STEP(block, Q, 0, 0xd76aa478, 7);
185                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
186                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
187                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
188                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
189                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
190
191                UInt32 tt1 = FF(Q[Qoff + 1], Q[Qoff + 0], Q[Qoff - 1]) + Q[Qoff - 2] + 0xe8c7b756;
192                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
193                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
194                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
195                UInt32 tt20 = Q[Qoff + 16] + 0xe9b6c7aa + block[0];
196                UInt32 tt5 = RR(Q[Qoff + 6] - Q[Qoff + 5], 12) - FF(Q[Qoff + 5], Q[Qoff + 4], Q[Qoff + 3]) - 0x4787c62a;
197
198                // change q17 until conditions are met on q18, q19 and q20
199                UInt32 counter = 0;
200                while (counter < (1 << 7))
201                {
202                    if (IsStopped)
203                        return;
204
205                    MatchProgress = 2;
206
207                    UInt32 q16 = Q[Qoff + 16];
208                    UInt32 q17 = ((xrng64() & 0x3ffd7ff7) | (q16 & 0xc0008008)) ^ 0x40000000;
209                    ++counter;
210
211                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
212                    q18 = RL(q18, 9); q18 += q17;
213                    if (0x00020000 != ((q18 ^ q17) & 0xa0020000))
214                        continue;
215
216                    UInt32 q19 = GG(q18, q17, q16) + tt19;
217                    q19 = RL(q19, 14); q19 += q18;
218                    if (0x80000000 != (q19 & 0x80020000))
219                        continue;
220
221                    UInt32 q20 = GG(q19, q18, q17) + tt20;
222                    q20 = RL(q20, 20); q20 += q19;
223                    if (0x00040000 != ((q20 ^ q19) & 0x80040000))
224                        continue;
225
226                    block[1] = q17 - q16; block[1] = RR(block[1], 5); block[1] -= tt17;
227                    UInt32 q2 = block[1] + tt1; q2 = RL(q2, 12); q2 += Q[Qoff + 1];
228                    block[5] = tt5 - q2;
229
230                    Q[Qoff + 2] = q2;
231                    Q[Qoff + 17] = q17;
232                    Q[Qoff + 18] = q18;
233                    Q[Qoff + 19] = q19;
234                    Q[Qoff + 20] = q20;
235                    MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
236
237                    counter = 0;
238                    break;
239                }
240                if (counter != 0)
241                    continue;
242
243                UInt32 q4 = Q[Qoff + 4];
244                UInt32 q9backup = Q[Qoff + 9];
245                UInt32 tt21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d;
246
247                // iterate over possible changes of q4
248                // while keeping all conditions on q1-q20 intact
249                // this changes m3, m4, m5 and m7
250                UInt32 counter2 = 0;
251                while (counter2 < (1 << 4))
252                {
253                    if (IsStopped)
254                        return;
255
256                    MatchProgress = 3;
257
258                    Q[Qoff + 4] = q4 ^ q4mask[counter2];
259                    ++counter2;
260                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
261                    UInt32 q21 = tt21 + block[5];
262                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
263                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000))
264                        continue;
265
266                    Q[Qoff + 21] = q21;
267                    MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
268                    MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
269                    MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
270
271                    UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
272                    UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
273                    UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
274
275                    UInt32 tt9 = Q[Qoff + 6] + 0x8b44f7af;
276                    UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
277                    UInt32 tt8 = FF(Q[Qoff + 8], Q[Qoff + 7], Q[Qoff + 6]) + Q[Qoff + 5] + 0x698098d8;
278                    UInt32 tt12 = RR(Q[Qoff + 13] - Q[Qoff + 12], 7) - 0x6b901122;
279                    UInt32 tt13 = RR(Q[Qoff + 14] - Q[Qoff + 13], 12) - FF(Q[Qoff + 13], Q[Qoff + 12], Q[Qoff + 11]) - 0xfd987193;
280
281                    // iterate over possible changes of q9 and q10
282                    // while keeping conditions on q1-q21 intact
283                    // this changes m8, m9, m10, m12 and m13 (and not m11!)
284                    // the possible changes of q9 that also do not change m10 are used below
285                    for (UInt32 counter3 = 0; counter3 < (1 << 3); )
286                    {
287                        if (IsStopped)
288                            return;
289
290                        MatchProgress = 4;
291
292                        UInt32 q10 = Q[Qoff + 10] ^ (q9q10mask[counter3] & 0x60);
293                        Q[Qoff + 9] = q9backup ^ (q9q10mask[counter3] & 0x2000);
294                        ++counter3;
295                        UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
296                        m10 -= FF(q10, Q[Qoff + 9], Q[Qoff + 8]) + tt10;
297
298                        UInt32 aa = Q[Qoff + 21];
299                        UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
300                        if (0x80000000 != (dd & 0x80000000)) continue;
301
302                        UInt32 bb = Q[Qoff + 20];
303                        UInt32 cc = tt23 + GG(dd, aa, bb);
304                        if (0 != (cc & 0x20000)) continue;
305                        cc = RL(cc, 14) + dd;
306                        if (0 != (cc & 0x80000000)) continue;
307
308                        bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
309                        if (0 == (bb & 0x80000000)) continue;
310
311                        block[10] = m10;
312                        block[13] = tt13 - q10;
313
314                        // iterate over possible changes of q9
315                        // while keeping intact conditions on q1-q24
316                        // this changes m8, m9 and m12 (but not m10!)
317                        for (UInt32 counter4 = 0; counter4 < (1 << 16); ++counter4)
318                        {
319                            if (IsStopped)
320                                return;
321
322                            MatchProgress = 5;
323
324                            UInt32 q9 = Q[Qoff + 9] ^ q9mask[counter4];
325                            block[12] = tt12 - FF(Q[Qoff + 12], Q[Qoff + 11], q10) - q9;
326                            UInt32 m8 = q9 - Q[Qoff + 8];
327                            block[8] = RR(m8, 7) - tt8;
328                            UInt32 m9 = q10 - q9;
329                            block[9] = RR(m9, 12) - FF(q9, Q[Qoff + 8], Q[Qoff + 7]) - tt9;
330
331                            UInt32 a = aa, b = bb, c = cc, d = dd;
332                            MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
333                            MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
334                            MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
335                            MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
336                            MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
337                            MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
338                            MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
339                            MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
340                            MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
341                            MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
342
343                            c += HH(d, a, b) + block[11] + 0x6d9d6122;
344                            if (0 != (c & (1 << 15)))
345                                continue;
346                            c = (c << 16 | c >> 16) + d;
347
348                            MatchProgress = 6;
349
350                            MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
351                            MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
352                            MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
353                            MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
354                            MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
355                            MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
356                            MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
357                            MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
358                            MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
359                            MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
360                            MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
361                            MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
362                            MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
363                            if (0 != ((b ^ d) & 0x80000000))
364                                continue;
365
366                            MatchProgress = 7;
367
368                            MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
369                            if (0 != ((a ^ c) >> 31)) continue;
370                            MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
371                            if (0 == ((b ^ d) >> 31)) continue;
372                            MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
373                            if (0 != ((a ^ c) >> 31)) continue;
374                            MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
375                            if (0 != ((b ^ d) >> 31)) continue;
376                            MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
377                            if (0 != ((a ^ c) >> 31)) continue;
378                            MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
379                            if (0 != ((b ^ d) >> 31)) continue;
380                            MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
381                            if (0 != ((a ^ c) >> 31)) continue;
382                            MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
383                            if (0 != ((b ^ d) >> 31)) continue;
384                            MD5_STEP(II, ref a, b, c, d, block[8], 0x6fa87e4f, 6);
385                            if (0 != ((a ^ c) >> 31)) continue;
386                            MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
387                            if (0 != ((b ^ d) >> 31)) continue;
388                            MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
389                            if (0 != ((a ^ c) >> 31)) continue;
390                            MD5_STEP(II, ref b, c, d, a, block[13], 0x4e0811a1, 21);
391                            if (0 == ((b ^ d) >> 31)) continue;
392                            MD5_STEP(II, ref a, b, c, d, block[4], 0xf7537e82, 6);
393                            if (0 != ((a ^ c) >> 31)) continue;
394                            MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
395                            if (0 != ((b ^ d) >> 31)) continue;
396                            MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
397                            if (0 != ((a ^ c) >> 31)) continue;
398                            MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
399
400                            UInt32 IHV1 = b + IV[1];
401                            UInt32 IHV2 = c + IV[2];
402                            UInt32 IHV3 = d + IV[3];
403
404                            bool wang = true;
405                            if (0x02000000 != ((IHV2 ^ IHV1) & 0x86000000)) wang = false;
406                            if (0 != ((IHV1 ^ IHV3) & 0x82000000)) wang = false;
407                            if (0 != (IHV1 & 0x06000020)) wang = false;
408
409                            bool stevens = true;
410                            if (((IHV1 ^ IHV2) >> 31) != 0 || ((IHV1 ^ IHV3) >> 31) != 0) stevens = false;
411                            if ((IHV3 & (1 << 25)) != 0 || (IHV2 & (1 << 25)) != 0 || (IHV1 & (1 << 25)) != 0
412                                || ((IHV2 ^ IHV1) & 1) != 0) stevens = false;
413
414                            if (!(wang || stevens)) continue;
415                            MatchProgress = 8;
416
417                            UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
418                            for (int t = 0; t < 4; ++t)
419                                IV2[t] = IV1[t] = IV[t];
420
421                            UInt32[] block2 = new UInt32[16];
422                            for (int t = 0; t < 16; ++t)
423                                block2[t] = block[t];
424                            block2[4] += (UInt32)1 << 31;
425                            block2[11] += 1 << 15;
426                            block2[14] += (UInt32)1 << 31;
427
428                            md5_compress(IV1, block);
429                            md5_compress(IV2, block2);
430                            if ((IV2[0] == IV1[0] + (1 << 31))
431                                    && (IV2[1] == IV1[1] + (1 << 31) + (1 << 25))
432                                    && (IV2[2] == IV1[2] + (1 << 31) + (1 << 25))
433                                    && (IV2[3] == IV1[3] + (1 << 31) + (1 << 25)))
434                            {
435                                MatchProgress = 9;
436                                return;
437                            }
438
439                            //if (IV2[0] != IV1[0] + (1<<31))
440                            //  std::cout << "!" << std::flush;
441                        }
442                    }
443                }
444            }
445        }
446
447
448        void md5_compress(UInt32[] ihv, UInt32[] block)
449        {
450            UInt32 a = ihv[0];
451            UInt32 b = ihv[1];
452            UInt32 c = ihv[2];
453            UInt32 d = ihv[3];
454
455            MD5_STEP(FF, ref a, b, c, d, block[0], 0xd76aa478, 7);
456            MD5_STEP(FF, ref d, a, b, c, block[1], 0xe8c7b756, 12);
457            MD5_STEP(FF, ref c, d, a, b, block[2], 0x242070db, 17);
458            MD5_STEP(FF, ref b, c, d, a, block[3], 0xc1bdceee, 22);
459            MD5_STEP(FF, ref a, b, c, d, block[4], 0xf57c0faf, 7);
460            MD5_STEP(FF, ref d, a, b, c, block[5], 0x4787c62a, 12);
461            MD5_STEP(FF, ref c, d, a, b, block[6], 0xa8304613, 17);
462            MD5_STEP(FF, ref b, c, d, a, block[7], 0xfd469501, 22);
463            MD5_STEP(FF, ref a, b, c, d, block[8], 0x698098d8, 7);
464            MD5_STEP(FF, ref d, a, b, c, block[9], 0x8b44f7af, 12);
465            MD5_STEP(FF, ref c, d, a, b, block[10], 0xffff5bb1, 17);
466            MD5_STEP(FF, ref b, c, d, a, block[11], 0x895cd7be, 22);
467            MD5_STEP(FF, ref a, b, c, d, block[12], 0x6b901122, 7);
468            MD5_STEP(FF, ref d, a, b, c, block[13], 0xfd987193, 12);
469            MD5_STEP(FF, ref c, d, a, b, block[14], 0xa679438e, 17);
470            MD5_STEP(FF, ref b, c, d, a, block[15], 0x49b40821, 22);
471            MD5_STEP(GG, ref a, b, c, d, block[1], 0xf61e2562, 5);
472            MD5_STEP(GG, ref d, a, b, c, block[6], 0xc040b340, 9);
473            MD5_STEP(GG, ref c, d, a, b, block[11], 0x265e5a51, 14);
474            MD5_STEP(GG, ref b, c, d, a, block[0], 0xe9b6c7aa, 20);
475            MD5_STEP(GG, ref a, b, c, d, block[5], 0xd62f105d, 5);
476            MD5_STEP(GG, ref d, a, b, c, block[10], 0x02441453, 9);
477            MD5_STEP(GG, ref c, d, a, b, block[15], 0xd8a1e681, 14);
478            MD5_STEP(GG, ref b, c, d, a, block[4], 0xe7d3fbc8, 20);
479            MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
480            MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
481            MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
482            MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
483            MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
484            MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
485            MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
486            MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
487            MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
488            MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
489            MD5_STEP(HH, ref c, d, a, b, block[11], 0x6d9d6122, 16);
490            MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
491            MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
492            MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
493            MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
494            MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
495            MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
496            MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
497            MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
498            MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
499            MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
500            MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
501            MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
502            MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
503            MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
504            MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
505            MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
506            MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
507            MD5_STEP(II, ref  a, b, c, d, block[12], 0x655b59c3, 6);
508            MD5_STEP(II, ref  d, a, b, c, block[3], 0x8f0ccc92, 10);
509            MD5_STEP(II, ref  c, d, a, b, block[10], 0xffeff47d, 15);
510            MD5_STEP(II, ref  b, c, d, a, block[1], 0x85845dd1, 21);
511            MD5_STEP(II, ref  a, b, c, d, block[8], 0x6fa87e4f, 6);
512            MD5_STEP(II, ref  d, a, b, c, block[15], 0xfe2ce6e0, 10);
513            MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
514            MD5_STEP(II, ref b, c, d, a, block[13], 0x4e0811a1, 21);
515            MD5_STEP(II, ref a, b, c, d, block[4], 0xf7537e82, 6);
516            MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
517            MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
518            MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
519
520            ihv[0] += a;
521            ihv[1] += b;
522            ihv[2] += c;
523            ihv[3] += d;
524        }
525
526        void MD5_STEP(RoundFunctionDelegate f, ref UInt32 a, UInt32 b, UInt32 c, UInt32 d, UInt32 m, UInt32 ac, Int32 rc)
527        {
528            a += f(b, c, d) + m + ac;
529            a = (a << rc | a >> (32 - rc)) + b;
530        }
531
532
533        void find_block1(UInt32[] block, UInt32[] IV)
534        {
535            if (((IV[1] ^ IV[2]) & (1 << 31)) == 0 && ((IV[1] ^ IV[3]) & (1 << 31)) == 0
536                && (IV[3] & (1 << 25)) == 0 && (IV[2] & (1 << 25)) == 0 && (IV[1] & (1 << 25)) == 0 && ((IV[2] ^ IV[1]) & 1) == 0
537               )
538            {
539                UInt32[] IV2 = new UInt32[] { (UInt32)(IV[0] + (1 << 31)), (UInt32)(IV[1] + (1 << 31) + (1 << 25)), (UInt32)(IV[2] + (1 << 31) + (1 << 25)), (UInt32)(IV[3] + (1 << 31) + (1 << 25)) };
540                if ((IV[1] & (1 << 6)) != 0 && (IV[1] & 1) != 0)
541                {
542                    find_block1_stevens_11(block, IV2);
543                }
544                else if ((IV[1] & (1 << 6)) != 0 && (IV[1] & 1) == 0)
545                {
546                    find_block1_stevens_10(block, IV2);
547                }
548                else if ((IV[1] & (1 << 6)) == 0 && (IV[1] & 1) != 0)
549                {
550                    find_block1_stevens_01(block, IV2);
551                }
552                else
553                {
554                    find_block1_stevens_00(block, IV2);
555                }
556                block[4] += (UInt32)1 << 31;
557                block[11] += 1 << 15;
558                block[14] += (UInt32)1 << 31;
559            }
560            else
561            {
562                find_block1_wang(block, IV);
563            }
564        }
565
566
567        void find_block1_stevens_00(UInt32[] block, UInt32[] IV)
568        {
569            MatchProgressMax = 5;
570            MatchProgress = 0;
571
572            UInt32[] Q = new UInt32[68];
573            Q[0] = IV[0];
574            Q[1] = IV[3];
575            Q[2] = IV[2];
576            Q[3] = IV[1];
577
578            UInt32[] q9q10mask = new UInt32[1 << 3];
579            for (UInt32 k = 0; k < q9q10mask.Length; ++k)
580                q9q10mask[k] = ((k << 5) ^ (k << 12) ^ (k << 25)) & 0x08002020;
581
582            UInt32[] q9mask = new UInt32[1 << 9];
583            for (UInt32 k = 0; k < q9mask.Length; ++k)
584                q9mask[k] = ((k << 1) ^ (k << 3) ^ (k << 6) ^ (k << 8) ^ (k << 11) ^ (k << 14) ^ (k << 18)) & 0x04310d12;
585
586            while (true)
587            {
588                if (IsStopped)
589                    return;
590
591                MatchProgress = 1;
592
593                UInt32 aa1 = Q[Qoff] & 0x80000000;
594
595                Q[Qoff + 2] = (xrng64() & 0x49a0e73e) | 0x221f00c1 | aa1;
596                Q[Qoff + 3] = (xrng64() & 0x0000040c) | 0x3fce1a71 | (Q[Qoff + 2] & 0x8000e000);
597                Q[Qoff + 4] = (xrng64() & 0x00000004) | (0xa5f281a2 ^ (Q[Qoff + 3] & 0x80000008));
598                Q[Qoff + 5] = (xrng64() & 0x00000004) | 0x67fd823b;
599                Q[Qoff + 6] = (xrng64() & 0x00001044) | 0x15e5829a;
600                Q[Qoff + 7] = (xrng64() & 0x00200806) | 0x950430b0;
601                Q[Qoff + 8] = (xrng64() & 0x60050110) | 0x1bd29ca2 | (Q[Qoff + 7] & 0x00000004);
602                Q[Qoff + 9] = (xrng64() & 0x40044000) | 0xb8820004;
603                Q[Qoff + 10] = 0xf288b209 | (Q[Qoff + 9] & 0x00044000);
604                Q[Qoff + 11] = (xrng64() & 0x12888008) | 0x85712f57;
605                Q[Qoff + 12] = (xrng64() & 0x1ed98d7f) | 0xc0023080 | (~Q[Qoff + 11] & 0x00200000);
606                Q[Qoff + 13] = (xrng64() & 0x0efb1d77) | 0x1000c008;
607                Q[Qoff + 14] = (xrng64() & 0x0fff5d77) | 0xa000a288;
608                Q[Qoff + 15] = (xrng64() & 0x0efe7ff7) | 0xe0008000 | (~Q[Qoff + 14] & 0x00010000);
609                Q[Qoff + 16] = (xrng64() & 0x0ffdffff) | 0xf0000000 | (~Q[Qoff + 15] & 0x00020000);
610
611                MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
612                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
613                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
614                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
615                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
616                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
617
618                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
619                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
620                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
621
622                UInt32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
623                UInt32 tt1 = Q[Qoff - 2] + 0xe8c7b756;
624                UInt32 q1a = 0x02020801 | (Q[Qoff + 0] & 0x80000000);
625
626                UInt32 counter = 0;
627                while (counter < (1 << 12))
628                {
629                    if (IsStopped)
630                        return;
631
632                    MatchProgress = 2;
633
634                    ++counter;
635
636                    UInt32 q1 = q1a | (xrng64() & 0x7dfdf7be);
637                    UInt32 m1 = Q[Qoff + 2] - q1;
638                    m1 = RR(m1, 12) - FF(q1, Q[Qoff + 0], Q[Qoff - 1]) - tt1;
639
640                    UInt32 q16 = Q[Qoff + 16];
641                    UInt32 q17 = tt17 + m1;
642                    q17 = RL(q17, 5) + q16;
643                    if (0x80000000 != ((q17 ^ q16) & 0x80008008)) continue;
644                    if (0 != (q17 & 0x00020000)) continue;
645
646                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
647                    q18 = RL(q18, 9); q18 += q17;
648                    if (0x80020000 != ((q18 ^ q17) & 0xa0020000)) continue;
649
650                    UInt32 q19 = GG(q18, q17, q16) + tt19;
651                    q19 = RL(q19, 14); q19 += q18;
652                    if (0x80000000 != (q19 & 0x80020000)) continue;
653
654                    UInt32 m0 = q1 - Q[Qoff + 0];
655                    m0 = RR(m0, 7) - tt0;
656
657                    UInt32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
658                    q20 = RL(q20, 20); q20 += q19;
659                    if (0x00040000 != ((q20 ^ q19) & 0x80040000)) continue;
660
661                    Q[Qoff + 1] = q1;
662                    Q[Qoff + 17] = q17;
663                    Q[Qoff + 18] = q18;
664                    Q[Qoff + 19] = q19;
665                    Q[Qoff + 20] = q20;
666
667                    block[0] = m0;
668                    block[1] = m1;
669
670                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
671                    UInt32 q21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d + block[5];
672                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
673                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000)) continue;
674                    Q[Qoff + 21] = q21;
675
676                    counter = 0;
677                    break;
678                }
679                if (counter != 0)
680                    continue;
681
682                UInt32 q9b = Q[Qoff + 9];
683                UInt32 q10b = Q[Qoff + 10];
684
685                MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
686                MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
687                MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
688                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
689
690                UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
691                UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
692                UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
693                UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
694
695                for (UInt32 k10 = 0; k10 < (1 << 3); ++k10)
696                {
697                    if (IsStopped)
698                        return;
699
700                    MatchProgress = 3;
701
702                    UInt32 q10 = q10b | (q9q10mask[k10] & 0x08000020);
703                    UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
704                    UInt32 q9 = q9b | (q9q10mask[k10] & 0x00002000);
705
706                    m10 -= FF(q10, q9, Q[Qoff + 8]) + tt10;
707
708                    UInt32 aa = Q[Qoff + 21];
709                    UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
710                    if (0 == (dd & 0x80000000)) continue;
711
712                    UInt32 bb = Q[Qoff + 20];
713                    UInt32 cc = tt23 + GG(dd, aa, bb);
714                    if (0 != (cc & 0x20000)) continue;
715                    cc = RL(cc, 14) + dd;
716                    if (0 != (cc & 0x80000000)) continue;
717
718                    bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
719                    if (0 == (bb & 0x80000000)) continue;
720
721                    block[10] = m10;
722                    Q[Qoff + 9] = q9;
723                    Q[Qoff + 10] = q10;
724                    MD5_REVERSE_STEP(block, Q, 13, 0xfd987193, 12);
725
726                    for (UInt32 k9 = 0; k9 < (1 << 9); ++k9)
727                    {
728                        if (IsStopped)
729                            return;
730
731                        MatchProgress = 4;
732
733                        UInt32 a = aa, b = bb, c = cc, d = dd;
734                        Q[Qoff + 9] = q9 ^ q9mask[k9];
735                        MD5_REVERSE_STEP(block, Q, 8, 0x698098d8, 7);
736                        MD5_REVERSE_STEP(block, Q, 9, 0x8b44f7af, 12);
737                        MD5_REVERSE_STEP(block, Q, 12, 0x6b901122, 7);
738
739                        MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
740                        MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
741                        MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
742                        MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
743                        MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
744                        MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
745                        MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
746                        MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
747                        MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
748                        MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
749
750                        c += HH(d, a, b) + block[11] + 0x6d9d6122;
751                        if (0 != (c & (1 << 15)))
752                            continue;
753                        c = (c << 16 | c >> 16) + d;
754
755                        MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
756                        MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
757                        MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
758                        MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
759                        MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
760                        MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
761                        MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
762                        MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
763                        MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
764                        MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
765                        MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
766                        MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
767                        MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
768                        if (0 != ((b ^ d) & 0x80000000))
769                            continue;
770
771                        MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
772                        if (0 != ((a ^ c) >> 31)) continue;
773                        MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
774                        if (0 == ((b ^ d) >> 31)) continue;
775                        MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
776                        if (0 != ((a ^ c) >> 31)) continue;
777                        MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
778                        if (0 != ((b ^ d) >> 31)) continue;
779                        MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
780                        if (0 != ((a ^ c) >> 31)) continue;
781                        MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
782                        if (0 != ((b ^ d) >> 31)) continue;
783                        MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
784                        if (0 != ((a ^ c) >> 31)) continue;
785                        MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
786                        if (0 != ((b ^ d) >> 31)) continue;
787                        MD5_STEP(II, ref a, b, c, d, block[8], 0x6fa87e4f, 6);
788                        if (0 != ((a ^ c) >> 31)) continue;
789                        MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
790                        if (0 != ((b ^ d) >> 31)) continue;
791                        MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
792                        if (0 != ((a ^ c) >> 31)) continue;
793                        MD5_STEP(II, ref b, c, d, a, block[13], 0x4e0811a1, 21);
794                        if (0 == ((b ^ d) >> 31)) continue;
795                        MD5_STEP(II, ref  a, b, c, d, block[4], 0xf7537e82, 6);
796                        if (0 != ((a ^ c) >> 31)) continue;
797                        MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
798                        if (0 != ((b ^ d) >> 31)) continue;
799                        MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
800                        if (0 != ((a ^ c) >> 31)) continue;
801                        MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
802
803                        UInt32[] block2 = new UInt32[16];
804                        UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
805                        for (int t = 0; t < 4; ++t)
806                        {
807                            IV1[t] = IV[t];
808                            IV2[t] = IV[t] + ((UInt32)1 << 31);
809                        }
810                        IV2[1] -= (1 << 25);
811                        IV2[2] -= (1 << 25);
812                        IV2[3] -= (1 << 25);
813
814                        for (int t = 0; t < 16; ++t)
815                            block2[t] = block[t];
816                        block2[4] += (UInt32)1 << 31;
817                        block2[11] += 1 << 15;
818                        block2[14] += (UInt32)1 << 31;
819
820                        md5_compress(IV1, block);
821                        md5_compress(IV2, block2);
822                        if (IV2[0] == IV1[0] && IV2[1] == IV1[1] && IV2[2] == IV1[2] && IV2[3] == IV1[3])
823                        {
824                            MatchProgress = 5;
825                            return;
826                        }
827
828                        //if (IV2[0] != IV1[0])
829                        //              std::cout << "!" << std::flush;
830                    }
831                }
832            }
833        }
834
835        void find_block1_stevens_01(UInt32[] block, UInt32[] IV)
836        {
837            MatchProgressMax = 5;
838            MatchProgress = 0;
839
840            UInt32[] Q = new UInt32[68];
841            Q[0] = IV[0];
842            Q[1] = IV[3];
843            Q[2] = IV[2];
844            Q[3] = IV[1];
845
846            UInt32[] q9q10mask = new UInt32[1 << 5];
847            for (UInt32 k = 0; k < q9q10mask.Length; ++k)
848                q9q10mask[k] = ((k << 4) ^ (k << 11) ^ (k << 24) ^ (k << 27)) & 0x88002030;
849
850            UInt32[] q9mask = new UInt32[1 << 9];
851            for (UInt32 k = 0; k < q9mask.Length; ++k)
852                q9mask[k] = ((k << 1) ^ (k << 7) ^ (k << 9) ^ (k << 12) ^ (k << 15) ^ (k << 19) ^ (k << 22)) & 0x44310d02;
853
854            while (true)
855            {
856                if (IsStopped)
857                    return;
858
859                MatchProgress = 1;
860
861                UInt32 aa1 = Q[Qoff] & 0x80000000;
862
863                Q[Qoff + 2] = (xrng64() & 0x4db0e03e) | 0x32460441 | aa1;
864                Q[Qoff + 3] = (xrng64() & 0x0c000008) | 0x123c3af1 | (Q[Qoff + 2] & 0x80800002);
865                Q[Qoff + 4] = 0xe398f812 ^ (Q[Qoff + 3] & 0x88000000);
866                Q[Qoff + 5] = (xrng64() & 0x82000000) | 0x4c66e99e;
867                Q[Qoff + 6] = (xrng64() & 0x80000000) | 0x27180590;
868                Q[Qoff + 7] = (xrng64() & 0x00010130) | 0x51ea9e47;
869                Q[Qoff + 8] = (xrng64() & 0x40200800) | 0xb7c291e5;
870                Q[Qoff + 9] = (xrng64() & 0x00044000) | 0x380002b4;
871                Q[Qoff + 10] = 0xb282b208 | (Q[Qoff + 9] & 0x00044000);
872                Q[Qoff + 11] = (xrng64() & 0x12808008) | 0xc5712f47;
873                Q[Qoff + 12] = (xrng64() & 0x1ef18d7f) | 0x000a3080;
874                Q[Qoff + 13] = (xrng64() & 0x1efb1d77) | 0x4004c008;
875                Q[Qoff + 14] = (xrng64() & 0x1fff5d77) | 0x6000a288;
876                Q[Qoff + 15] = (xrng64() & 0x1efe7ff7) | 0xa0008000 | (~Q[Qoff + 14] & 0x00010000);
877                Q[Qoff + 16] = (xrng64() & 0x1ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000);
878
879                MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
880                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
881                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
882                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
883                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
884                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
885
886                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
887                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
888                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
889
890                UInt32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
891                UInt32 tt1 = Q[Qoff - 2] + 0xe8c7b756;
892
893                UInt32 q1a = 0x02000021 ^ (Q[Qoff + 0] & 0x80000020);
894
895                UInt32 counter = 0;
896                while (counter < (1 << 12))
897                {
898                    if (IsStopped)
899                        return;
900
901                    MatchProgress = 2;
902
903                    ++counter;
904
905                    UInt32 q1 = q1a | (xrng64() & 0x7dfff39e);
906                    UInt32 m1 = Q[Qoff + 2] - q1;
907                    m1 = RR(m1, 12) - FF(q1, Q[Qoff + 0], Q[Qoff - 1]) - tt1;
908
909                    UInt32 q16 = Q[Qoff + 16];
910                    UInt32 q17 = tt17 + m1;
911                    q17 = RL(q17, 5) + q16;
912                    if (0x80000000 != ((q17 ^ q16) & 0x80008008)) continue;
913                    if (0 != (q17 & 0x00020000)) continue;
914
915                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
916                    q18 = RL(q18, 9); q18 += q17;
917                    if (0x80020000 != ((q18 ^ q17) & 0xa0020000)) continue;
918
919                    UInt32 q19 = GG(q18, q17, q16) + tt19;
920                    q19 = RL(q19, 14); q19 += q18;
921                    if (0 != (q19 & 0x80020000)) continue;
922
923                    UInt32 m0 = q1 - Q[Qoff + 0];
924                    m0 = RR(m0, 7) - tt0;
925
926                    UInt32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
927                    q20 = RL(q20, 20); q20 += q19;
928                    if (0x00040000 != ((q20 ^ q19) & 0x80040000)) continue;
929
930                    Q[Qoff + 1] = q1;
931                    Q[Qoff + 17] = q17;
932                    Q[Qoff + 18] = q18;
933                    Q[Qoff + 19] = q19;
934                    Q[Qoff + 20] = q20;
935
936                    block[0] = m0;
937                    block[1] = m1;
938
939                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
940                    UInt32 q21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d + block[5];
941                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
942                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000)) continue;
943
944                    Q[Qoff + 21] = q21;
945
946                    counter = 0;
947                    break;
948                }
949                if (counter != 0)
950                    continue;
951
952                UInt32 q9b = Q[Qoff + 9];
953                UInt32 q10b = Q[Qoff + 10];
954
955                MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
956                MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
957                MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
958                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
959
960                UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
961                UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
962                UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
963                UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
964
965                for (UInt32 k10 = 0; k10 < (1 << 5); ++k10)
966                {
967                    if (IsStopped)
968                        return;
969
970                    MatchProgress = 3;
971
972                    UInt32 q10 = q10b | (q9q10mask[k10] & 0x08000030);
973                    UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
974                    UInt32 q9 = q9b | (q9q10mask[k10] & 0x80002000);
975
976                    m10 -= FF(q10, q9, Q[Qoff + 8]) + tt10;
977
978                    UInt32 aa = Q[Qoff + 21];
979                    UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
980                    if (0 != (dd & 0x80000000)) continue;
981
982                    UInt32 bb = Q[Qoff + 20];
983                    UInt32 cc = tt23 + GG(dd, aa, bb);
984                    if (0 != (cc & 0x20000)) continue;
985                    cc = RL(cc, 14) + dd;
986                    if (0 != (cc & 0x80000000)) continue;
987
988                    bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
989                    if (0 == (bb & 0x80000000)) continue;
990
991                    block[10] = m10;
992                    Q[Qoff + 9] = q9;
993                    Q[Qoff + 10] = q10;
994                    MD5_REVERSE_STEP(block, Q, 13, 0xfd987193, 12);
995
996                    for (UInt32 k9 = 0; k9 < (1 << 9); ++k9)
997                    {
998                        if (IsStopped)
999                            return;
1000
1001                        MatchProgress = 4;
1002
1003                        UInt32 a = aa, b = bb, c = cc, d = dd;
1004                        Q[Qoff + 9] = q9 ^ q9mask[k9];
1005                        MD5_REVERSE_STEP(block, Q, 8, 0x698098d8, 7);
1006                        MD5_REVERSE_STEP(block, Q, 9, 0x8b44f7af, 12);
1007                        MD5_REVERSE_STEP(block, Q, 12, 0x6b901122, 7);
1008
1009                        MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
1010                        MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
1011                        MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
1012                        MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
1013                        MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
1014                        MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
1015                        MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
1016                        MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
1017                        MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
1018                        MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
1019
1020                        c += HH(d, a, b) + block[11] + 0x6d9d6122;
1021                        if (0 != (c & (1 << 15)))
1022                            continue;
1023                        c = (c << 16 | c >> 16) + d;
1024
1025                        MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
1026                        MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
1027                        MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
1028                        MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
1029                        MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
1030                        MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
1031                        MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
1032                        MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
1033                        MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
1034                        MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
1035                        MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
1036                        MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
1037                        MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
1038                        if (0 != ((b ^ d) & 0x80000000))
1039                            continue;
1040
1041                        MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
1042                        if (0 != ((a ^ c) >> 31)) continue;
1043                        MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
1044                        if (0 == ((b ^ d) >> 31)) continue;
1045                        MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
1046                        if (0 != ((a ^ c) >> 31)) continue;
1047                        MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
1048                        if (0 != ((b ^ d) >> 31)) continue;
1049                        MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
1050                        if (0 != ((a ^ c) >> 31)) continue;
1051                        MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
1052                        if (0 != ((b ^ d) >> 31)) continue;
1053                        MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
1054                        if (0 != ((a ^ c) >> 31)) continue;
1055                        MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
1056                        if (0 != ((b ^ d) >> 31)) continue;
1057                        MD5_STEP(II, ref a, b, c, d, block[8], 0x6fa87e4f, 6);
1058                        if (0 != ((a ^ c) >> 31)) continue;
1059                        MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
1060                        if (0 != ((b ^ d) >> 31)) continue;
1061                        MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
1062                        if (0 != ((a ^ c) >> 31)) continue;
1063                        MD5_STEP(II, ref b, c, d, a, block[13], 0x4e0811a1, 21);
1064                        if (0 == ((b ^ d) >> 31)) continue;
1065                        MD5_STEP(II, ref a, b, c, d, block[4], 0xf7537e82, 6);
1066                        if (0 != ((a ^ c) >> 31)) continue;
1067                        MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
1068                        if (0 != ((b ^ d) >> 31)) continue;
1069                        MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
1070                        if (0 != ((a ^ c) >> 31)) continue;
1071                        MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
1072
1073                        UInt32[] block2 = new UInt32[16];
1074                        UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
1075                        for (int t = 0; t < 4; ++t)
1076                        {
1077                            IV1[t] = IV[t];
1078                            IV2[t] = IV[t] + ((UInt32)1 << 31);
1079                        }
1080                        IV2[1] -= (1 << 25);
1081                        IV2[2] -= (1 << 25);
1082                        IV2[3] -= (1 << 25);
1083
1084                        for (int t = 0; t < 16; ++t)
1085                            block2[t] = block[t];
1086                        block2[4] += (UInt32)1 << 31;
1087                        block2[11] += 1 << 15;
1088                        block2[14] += (UInt32)1 << 31;
1089
1090                        md5_compress(IV1, block);
1091                        md5_compress(IV2, block2);
1092                        if (IV2[0] == IV1[0] && IV2[1] == IV1[1] && IV2[2] == IV1[2] && IV2[3] == IV1[3])
1093                        {
1094                            MatchProgress = 5;
1095                            return;
1096                        }
1097
1098                        //if (IV2[0] != IV1[0])
1099                        //              std::cout << "!" << std::flush;
1100                    }
1101                }
1102            }
1103        }
1104
1105
1106        void find_block1_stevens_10(UInt32[] block, UInt32[] IV)
1107        {
1108            MatchProgressMax = 5;
1109            MatchProgress = 0;
1110
1111            UInt32[] Q = new UInt32[68];
1112            Q[0] = IV[0];
1113            Q[1] = IV[3];
1114            Q[2] = IV[2];
1115            Q[3] = IV[1];
1116
1117            UInt32[] q9q10mask = new UInt32[1 << 4];
1118            for (UInt32 k = 0; k < q9q10mask.Length; ++k)
1119                q9q10mask[k] = ((k << 2) ^ (k << 8) ^ (k << 11) ^ (k << 25)) & 0x08004204;
1120
1121            UInt32[] q9mask = new UInt32[1 << 10];
1122            for (UInt32 k = 0; k < q9mask.Length; ++k)
1123                q9mask[k] = ((k << 1) ^ (k << 2) ^ (k << 3) ^ (k << 7) ^ (k << 12) ^ (k << 15) ^ (k << 18) ^ (k << 20)) & 0x2471042a;
1124           
1125            while (true)
1126            {
1127                if (IsStopped)
1128                    return;
1129
1130                MatchProgress = 1;
1131
1132                UInt32 aa1 = Q[Qoff] & 0x80000000;
1133
1134                Q[Qoff + 2] = (xrng64() & 0x79b0c6ba) | 0x024c3841 | aa1;
1135                Q[Qoff + 3] = (xrng64() & 0x19300210) | 0x2603096d | (Q[Qoff + 2] & 0x80000082);
1136                Q[Qoff + 4] = (xrng64() & 0x10300000) | 0xe4cae30c | (Q[Qoff + 3] & 0x01000030);
1137                Q[Qoff + 5] = (xrng64() & 0x10000000) | 0x63494061 | (Q[Qoff + 4] & 0x00300000);
1138                Q[Qoff + 6] = 0x7deaff68;
1139                Q[Qoff + 7] = (xrng64() & 0x20444000) | 0x09091ee0;
1140                Q[Qoff + 8] = (xrng64() & 0x09040000) | 0xb2529f6d;
1141                Q[Qoff + 9] = (xrng64() & 0x00040000) | 0x10885184;
1142                Q[Qoff + 10] = (xrng64() & 0x00000080) | 0x428afb11 | (Q[Qoff + 9] & 0x00040000);
1143                Q[Qoff + 11] = (xrng64() & 0x128a8110) | 0x6571266b | (Q[Qoff + 10] & 0x0000080);
1144                Q[Qoff + 12] = (xrng64() & 0x3ef38d7f) | 0x00003080 | (~Q[Qoff + 11] & 0x00080000);
1145                Q[Qoff + 13] = (xrng64() & 0x3efb1d77) | 0x0004c008;
1146                Q[Qoff + 14] = (xrng64() & 0x5fff5d77) | 0x8000a288;
1147                Q[Qoff + 15] = (xrng64() & 0x1efe7ff7) | 0xe0008000 | (~Q[Qoff + 14] & 0x00010000);
1148                Q[Qoff + 16] = (xrng64() & 0x5ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000);
1149
1150                MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1151                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
1152                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1153                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
1154                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
1155                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
1156
1157                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
1158                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
1159                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
1160
1161                UInt32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
1162                UInt32 tt1 = Q[Qoff - 2] + 0xe8c7b756;
1163
1164                UInt32 q1a = 0x02000941 ^ (Q[Qoff + 0] & 0x80000000);
1165
1166                UInt32 counter = 0;
1167                while (counter < (1 << 12))
1168                {
1169                    if (IsStopped)
1170                        return;
1171
1172                    MatchProgress = 2;
1173
1174                    ++counter;
1175
1176                    UInt32 q1 = q1a | (xrng64() & 0x7dfdf6be);
1177                    UInt32 m1 = Q[Qoff + 2] - q1;
1178                    m1 = RR(m1, 12) - FF(q1, Q[Qoff + 0], Q[Qoff - 1]) - tt1;
1179
1180                    UInt32 q16 = Q[Qoff + 16];
1181                    UInt32 q17 = tt17 + m1;
1182                    q17 = RL(q17, 5) + q16;
1183                    if (0x80000000 != ((q17 ^ q16) & 0x80008008)) continue;
1184                    if (0 != (q17 & 0x00020000)) continue;
1185
1186                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
1187                    q18 = RL(q18, 9); q18 += q17;
1188                    if (0x80020000 != ((q18 ^ q17) & 0xa0020000)) continue;
1189
1190                    UInt32 q19 = GG(q18, q17, q16) + tt19;
1191                    q19 = RL(q19, 14); q19 += q18;
1192                    if (0 != (q19 & 0x80020000)) continue;
1193
1194                    UInt32 m0 = q1 - Q[Qoff + 0];
1195                    m0 = RR(m0, 7) - tt0;
1196
1197                    UInt32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
1198                    q20 = RL(q20, 20); q20 += q19;
1199                    if (0x00040000 != ((q20 ^ q19) & 0x80040000)) continue;
1200
1201                    Q[Qoff + 1] = q1;
1202                    Q[Qoff + 17] = q17;
1203                    Q[Qoff + 18] = q18;
1204                    Q[Qoff + 19] = q19;
1205                    Q[Qoff + 20] = q20;
1206
1207                    block[0] = m0;
1208                    block[1] = m1;
1209
1210                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1211                    UInt32 q21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d + block[5];
1212                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
1213                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000)) continue;
1214                    Q[Qoff + 21] = q21;
1215
1216                    counter = 0;
1217                    break;
1218                }
1219                if (counter != 0)
1220                    continue;
1221
1222                UInt32 q9b = Q[Qoff + 9];
1223                UInt32 q10b = Q[Qoff + 10];
1224
1225                MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
1226                MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
1227                MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
1228                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1229
1230                UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
1231                UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
1232                UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
1233                UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
1234
1235                for (UInt32 k10 = 0; k10 < (1 << 4); ++k10)
1236                {
1237                    if (IsStopped)
1238                        return;
1239
1240                    MatchProgress = 3;
1241
1242                    UInt32 q10 = q10b | (q9q10mask[k10] & 0x08000004);
1243                    UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
1244                    UInt32 q9 = q9b | (q9q10mask[k10] & 0x00004200);
1245
1246                    m10 -= FF(q10, q9, Q[Qoff + 8]) + tt10;
1247
1248                    UInt32 aa = Q[Qoff + 21];
1249                    UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
1250                    if (0 != (dd & 0x80000000)) continue;
1251
1252                    UInt32 bb = Q[Qoff + 20];
1253                    UInt32 cc = tt23 + GG(dd, aa, bb);
1254                    if (0 != (cc & 0x20000)) continue;
1255                    cc = RL(cc, 14) + dd;
1256                    if (0 != (cc & 0x80000000)) continue;
1257
1258                    bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
1259                    if (0 == (bb & 0x80000000)) continue;
1260
1261                    block[10] = m10;
1262                    Q[Qoff + 9] = q9;
1263                    Q[Qoff + 10] = q10;
1264                    MD5_REVERSE_STEP(block, Q, 13, 0xfd987193, 12);
1265
1266                    for (UInt32 k9 = 0; k9 < (1 << 10); ++k9)
1267                    {
1268                        if (IsStopped)
1269                            return;
1270
1271                        MatchProgress = 4;
1272
1273                        UInt32 a = aa, b = bb, c = cc, d = dd;
1274                        Q[Qoff + 9] = q9 ^ q9mask[k9];
1275                        MD5_REVERSE_STEP(block, Q, 8, 0x698098d8, 7);
1276                        MD5_REVERSE_STEP(block, Q, 9, 0x8b44f7af, 12);
1277                        MD5_REVERSE_STEP(block, Q, 12, 0x6b901122, 7);
1278
1279                        MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
1280                        MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
1281                        MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
1282                        MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
1283                        MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
1284                        MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
1285                        MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
1286                        MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
1287                        MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
1288                        MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
1289
1290                        c += HH(d, a, b) + block[11] + 0x6d9d6122;
1291                        if (0 != (c & (1 << 15)))
1292                            continue;
1293                        c = (c << 16 | c >> 16) + d;
1294
1295                        MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
1296                        MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
1297                        MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
1298                        MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
1299                        MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
1300                        MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
1301                        MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
1302                        MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
1303                        MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
1304                        MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
1305                        MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
1306                        MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
1307                        MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
1308                        if (0 != ((b ^ d) & 0x80000000))
1309                            continue;
1310
1311                        MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
1312                        if (0 != ((a ^ c) >> 31)) continue;
1313                        MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
1314                        if (0 == ((b ^ d) >> 31)) continue;
1315                        MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
1316                        if (0 != ((a ^ c) >> 31)) continue;
1317                        MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
1318                        if (0 != ((b ^ d) >> 31)) continue;
1319                        MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
1320                        if (0 != ((a ^ c) >> 31)) continue;
1321                        MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
1322                        if (0 != ((b ^ d) >> 31)) continue;
1323                        MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
1324                        if (0 != ((a ^ c) >> 31)) continue;
1325                        MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
1326                        if (0 != ((b ^ d) >> 31)) continue;
1327                        MD5_STEP(II, ref  a, b, c, d, block[8], 0x6fa87e4f, 6);
1328                        if (0 != ((a ^ c) >> 31)) continue;
1329                        MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
1330                        if (0 != ((b ^ d) >> 31)) continue;
1331                        MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
1332                        if (0 != ((a ^ c) >> 31)) continue;
1333                        MD5_STEP(II, ref b, c, d, a, block[13], 0x4e0811a1, 21);
1334                        if (0 == ((b ^ d) >> 31)) continue;
1335                        MD5_STEP(II, ref a, b, c, d, block[4], 0xf7537e82, 6);
1336                        if (0 != ((a ^ c) >> 31)) continue;
1337                        MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
1338                        if (0 != ((b ^ d) >> 31)) continue;
1339                        MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
1340                        if (0 != ((a ^ c) >> 31)) continue;
1341                        MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
1342
1343                        //std::cout << "." << std::flush;
1344
1345                        UInt32[] block2 = new UInt32[16];
1346                        UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
1347                        for (int t = 0; t < 4; ++t)
1348                        {
1349                            IV1[t] = IV[t];
1350                            IV2[t] = IV[t] + ((UInt32)1 << 31);
1351                        }
1352                        IV2[1] -= (1 << 25);
1353                        IV2[2] -= (1 << 25);
1354                        IV2[3] -= (1 << 25);
1355
1356                        for (int t = 0; t < 16; ++t)
1357                            block2[t] = block[t];
1358                        block2[4] += (UInt32)1 << 31;
1359                        block2[11] += 1 << 15;
1360                        block2[14] += (UInt32)1 << 31;
1361
1362                        md5_compress(IV1, block);
1363                        md5_compress(IV2, block2);
1364                        if (IV2[0] == IV1[0] && IV2[1] == IV1[1] && IV2[2] == IV1[2] && IV2[3] == IV1[3])
1365                        {
1366                            MatchProgress = 5;
1367                            return;
1368                        }
1369
1370                        //if (IV2[0] != IV1[0])
1371                        //              std::cout << "!" << std::flush;
1372                    }
1373                }
1374            }
1375        }
1376
1377
1378        void find_block1_stevens_11(UInt32[] block, UInt32[] IV)
1379        {
1380            MatchProgressMax = 5;
1381            MatchProgress = 0;
1382
1383            UInt32[] Q = new UInt32[68];
1384            Q[0] = IV[0];
1385            Q[1] = IV[3];
1386            Q[2] = IV[2];
1387            Q[3] = IV[1];
1388
1389            UInt32[] q9q10mask = new UInt32[1 << 5];
1390            for (UInt32 k = 0; k < q9q10mask.Length; ++k)
1391                q9q10mask[k] = ((k << 5) ^ (k << 6) ^ (k << 7) ^ (k << 24) ^ (k << 27)) & 0x880002a0;
1392
1393            UInt32[] q9mask = new UInt32[1 << 9];
1394            for (UInt32 k = 0; k < q9mask.Length; ++k)
1395                q9mask[k] = ((k << 1) ^ (k << 3) ^ (k << 8) ^ (k << 12) ^ (k << 15) ^ (k << 18)) & 0x04710c12;
1396
1397            while (true)
1398            {
1399                if (IsStopped)
1400                    return;
1401
1402                MatchProgress = 1;
1403
1404                UInt32 aa1 = Q[Qoff] & 0x80000000;
1405
1406                Q[Qoff + 2] = (xrng64() & 0x75bef63e) | 0x0a410041 | aa1;
1407                Q[Qoff + 3] = (xrng64() & 0x10345614) | 0x0202a9e1 | (Q[Qoff + 2] & 0x84000002);
1408                Q[Qoff + 4] = (xrng64() & 0x00145400) | 0xe84ba909 | (Q[Qoff + 3] & 0x00000014);
1409                Q[Qoff + 5] = (xrng64() & 0x80000000) | 0x75e90b1d | (Q[Qoff + 4] & 0x00145400);
1410                Q[Qoff + 6] = 0x7c23ff5a | (Q[Qoff + 5] & 0x80000000);
1411                Q[Qoff + 7] = (xrng64() & 0x40000880) | 0x114bf41a;
1412                Q[Qoff + 8] = (xrng64() & 0x00002090) | 0xb352dd01;
1413                Q[Qoff + 9] = (xrng64() & 0x00044000) | 0x7a803124;
1414                Q[Qoff + 10] = (xrng64() & 0x00002000) | 0xf28a92c9 | (Q[Qoff + 9] & 0x00044000);
1415                Q[Qoff + 11] = (xrng64() & 0x128a8108) | 0xc5710ed7 | (Q[Qoff + 10] & 0x00002000);
1416                Q[Qoff + 12] = (xrng64() & 0x9edb8d7f) | 0x20003080 | (~Q[Qoff + 11] & 0x00200000);
1417                Q[Qoff + 13] = (xrng64() & 0x3efb1d77) | 0x4004c008 | (Q[Qoff + 12] & 0x80000000);
1418                Q[Qoff + 14] = (xrng64() & 0x1fff5d77) | 0x0000a288;
1419                Q[Qoff + 15] = (xrng64() & 0x1efe7ff7) | 0x20008000 | (~Q[Qoff + 14] & 0x00010000);
1420                Q[Qoff + 16] = (xrng64() & 0x1ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x40020000);
1421
1422                MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1423                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
1424                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1425                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
1426                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
1427                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
1428
1429                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
1430                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
1431                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
1432
1433                UInt32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
1434                UInt32 tt1 = Q[Qoff - 2] + 0xe8c7b756;
1435
1436                UInt32 q1a = 0x02000861 ^ (Q[Qoff + 0] & 0x80000020);
1437
1438                UInt32 counter = 0;
1439                while (counter < (1 << 12))
1440                {
1441                    if (IsStopped)
1442                        return;
1443
1444                    MatchProgress = 2;
1445
1446                    ++counter;
1447
1448                    UInt32 q1 = q1a | (xrng64() & 0x7dfff79e);
1449                    UInt32 m1 = Q[Qoff + 2] - q1;
1450                    m1 = RR(m1, 12) - FF(q1, Q[Qoff + 0], Q[Qoff - 1]) - tt1;
1451
1452                    UInt32 q16 = Q[Qoff + 16];
1453                    UInt32 q17 = tt17 + m1;
1454                    q17 = RL(q17, 5) + q16;
1455                    if (0x40000000 != ((q17 ^ q16) & 0xc0008008)) continue;
1456                    if (0 != (q17 & 0x00020000)) continue;
1457
1458                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
1459                    q18 = RL(q18, 9); q18 += q17;
1460                    if (0x80020000 != ((q18 ^ q17) & 0xa0020000)) continue;
1461
1462                    UInt32 q19 = GG(q18, q17, q16) + tt19;
1463                    q19 = RL(q19, 14); q19 += q18;
1464                    if (0x80000000 != (q19 & 0x80020000)) continue;
1465
1466                    UInt32 m0 = q1 - Q[Qoff + 0];
1467                    m0 = RR(m0, 7) - tt0;
1468
1469                    UInt32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
1470                    q20 = RL(q20, 20); q20 += q19;
1471                    if (0x00040000 != ((q20 ^ q19) & 0x80040000)) continue;
1472
1473                    Q[Qoff + 1] = q1;
1474                    Q[Qoff + 17] = q17;
1475                    Q[Qoff + 18] = q18;
1476                    Q[Qoff + 19] = q19;
1477                    Q[Qoff + 20] = q20;
1478
1479                    block[0] = m0;
1480                    block[1] = m1;
1481
1482                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1483                    UInt32 q21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d + block[5];
1484                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
1485                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000)) continue;
1486
1487                    Q[Qoff + 21] = q21;
1488
1489                    counter = 0;
1490                    break;
1491                }
1492                if (counter != 0)
1493                    continue;
1494
1495                UInt32 q9b = Q[Qoff + 9];
1496                UInt32 q10b = Q[Qoff + 10];
1497
1498                MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
1499                MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
1500                MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
1501                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1502
1503                UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
1504                UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
1505                UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
1506                UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
1507
1508                for (UInt32 k10 = 0; k10 < (1 << 5); ++k10)
1509                {
1510                    if (IsStopped)
1511                        return;
1512
1513                    MatchProgress = 3;
1514
1515                    UInt32 q10 = q10b | (q9q10mask[k10] & 0x08000040);
1516                    UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
1517                    UInt32 q9 = q9b | (q9q10mask[k10] & 0x80000280);
1518
1519                    m10 -= FF(q10, q9, Q[Qoff + 8]) + tt10;
1520
1521                    UInt32 aa = Q[Qoff + 21];
1522                    UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
1523                    if (0 == (dd & 0x80000000)) continue;
1524
1525                    UInt32 bb = Q[Qoff + 20];
1526                    UInt32 cc = tt23 + GG(dd, aa, bb);
1527                    if (0 != (cc & 0x20000)) continue;
1528                    cc = RL(cc, 14) + dd;
1529                    if (0 != (cc & 0x80000000)) continue;
1530
1531                    bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
1532                    if (0 == (bb & 0x80000000)) continue;
1533
1534                    block[10] = m10;
1535                    Q[Qoff + 9] = q9;
1536                    Q[Qoff + 10] = q10;
1537                    MD5_REVERSE_STEP(block, Q, 13, 0xfd987193, 12);
1538
1539                    for (UInt32 k9 = 0; k9 < (1 << 9); ++k9)
1540                    {
1541                        if (IsStopped)
1542                            return;
1543
1544                        MatchProgress = 4;
1545
1546                        UInt32 a = aa, b = bb, c = cc, d = dd;
1547                        Q[Qoff + 9] = q9 ^ q9mask[k9];
1548                        MD5_REVERSE_STEP(block, Q, 8, 0x698098d8, 7);
1549                        MD5_REVERSE_STEP(block, Q, 9, 0x8b44f7af, 12);
1550                        MD5_REVERSE_STEP(block, Q, 12, 0x6b901122, 7);
1551
1552                        MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
1553                        MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
1554                        MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
1555                        MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
1556                        MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
1557                        MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
1558                        MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
1559                        MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
1560                        MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
1561                        MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
1562
1563                        c += HH(d, a, b) + block[11] + 0x6d9d6122;
1564                        if (0 != (c & (1 << 15)))
1565                            continue;
1566                        c = (c << 16 | c >> 16) + d;
1567
1568                        MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
1569                        MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
1570                        MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
1571                        MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
1572                        MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
1573                        MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
1574                        MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
1575                        MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
1576                        MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
1577                        MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
1578                        MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
1579                        MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
1580                        MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
1581                        if (0 != ((b ^ d) & 0x80000000))
1582                            continue;
1583
1584                        MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
1585                        if (0 != ((a ^ c) >> 31)) continue;
1586                        MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
1587                        if (0 == ((b ^ d) >> 31)) continue;
1588                        MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
1589                        if (0 != ((a ^ c) >> 31)) continue;
1590                        MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
1591                        if (0 != ((b ^ d) >> 31)) continue;
1592                        MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
1593                        if (0 != ((a ^ c) >> 31)) continue;
1594                        MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
1595                        if (0 != ((b ^ d) >> 31)) continue;
1596                        MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
1597                        if (0 != ((a ^ c) >> 31)) continue;
1598                        MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
1599                        if (0 != ((b ^ d) >> 31)) continue;
1600                        MD5_STEP(II, ref a, b, c, d, block[8], 0x6fa87e4f, 6);
1601                        if (0 != ((a ^ c) >> 31)) continue;
1602                        MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
1603                        if (0 != ((b ^ d) >> 31)) continue;
1604                        MD5_STEP(II, ref c, d, a, b, block[6], 0xa3014314, 15);
1605                        if (0 != ((a ^ c) >> 31)) continue;
1606                        MD5_STEP(II, ref  b, c, d, a, block[13], 0x4e0811a1, 21);
1607                        if (0 == ((b ^ d) >> 31)) continue;
1608                        MD5_STEP(II, ref  a, b, c, d, block[4], 0xf7537e82, 6);
1609                        if (0 != ((a ^ c) >> 31)) continue;
1610                        MD5_STEP(II, ref  d, a, b, c, block[11], 0xbd3af235, 10);
1611                        if (0 != ((b ^ d) >> 31)) continue;
1612                        MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
1613                        if (0 != ((a ^ c) >> 31)) continue;
1614                        MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
1615
1616                        //std::cout << "." << std::flush;
1617
1618                        UInt32[] block2 = new UInt32[16];
1619                        UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
1620                        for (int t = 0; t < 4; ++t)
1621                        {
1622                            IV1[t] = IV[t];
1623                            IV2[t] = IV[t] + ((UInt32)1 << 31);
1624                        }
1625                        IV2[1] -= (1 << 25);
1626                        IV2[2] -= (1 << 25);
1627                        IV2[3] -= (1 << 25);
1628
1629                        for (int t = 0; t < 16; ++t)
1630                            block2[t] = block[t];
1631                        block2[4] += (UInt32)1 << 31;
1632                        block2[11] += 1 << 15;
1633                        block2[14] += (UInt32)1 << 31;
1634
1635                        md5_compress(IV1, block);
1636                        md5_compress(IV2, block2);
1637                        if (IV2[0] == IV1[0] && IV2[1] == IV1[1] && IV2[2] == IV1[2] && IV2[3] == IV1[3])
1638                        {
1639                            MatchProgress = 5;
1640                            return;
1641                        }
1642
1643                        //if (IV2[0] != IV1[0])
1644                        //              std::cout << "!" << std::flush;
1645                    }
1646                }
1647            }
1648        }
1649
1650
1651        void find_block1_wang(UInt32[] block, UInt32[] IV)
1652        {
1653            MatchProgressMax = 6;
1654            MatchProgress = 0;
1655
1656            UInt32[] Q = new UInt32[68];
1657            Q[0] = IV[0];
1658            Q[1] = IV[3];
1659            Q[2] = IV[2];
1660            Q[3] = IV[1];
1661
1662            UInt32[] q4mask = new UInt32[1 << 6];
1663            for (UInt32 k = 0; k < q4mask.Length; ++k)
1664                q4mask[k] = ((k << 13) ^ (k << 19)) & 0x01c0e000;
1665
1666            UInt32[] q9mask = new UInt32[1 << 5], q10mask = new UInt32[1 << 5];
1667            for (UInt32 k = 0; k < q9mask.Length; ++k)
1668            {
1669                UInt32 msk = (k << 5) ^ (k << 13) ^ (k << 17) ^ (k << 24);
1670                q9mask[k] = msk & 0x00084000;
1671                q10mask[k] = msk & 0x18000020;
1672            }
1673
1674            UInt32[] q9mask2 = new UInt32[1 << 10];
1675            for (UInt32 k = 0; k < q9mask2.Length; ++k)
1676                q9mask2[k] = ((k << 1) ^ (k << 7) ^ (k << 14) ^ (k << 15) ^ (k << 22)) & 0x6074041c;
1677           
1678            while (true)
1679            {
1680                if (IsStopped)
1681                    return;
1682
1683                MatchProgress = 1;
1684
1685                UInt32 aa1 = Q[Qoff] & 0x80000000;
1686                UInt32 bb1 = 0x80000000 ^ aa1;
1687
1688                Q[Qoff + 2] = (xrng64() & 0x71de7799) | 0x0c008840 | bb1;
1689                Q[Qoff + 3] = (xrng64() & 0x01c06601) | 0x3e1f0966 | (Q[Qoff + 2] & 0x80000018);
1690                Q[Qoff + 4] = 0x3a040010 | (Q[Qoff + 3] & 0x80000601);
1691                Q[Qoff + 5] = (xrng64() & 0x03c0e000) | 0x482f0e50 | aa1;
1692                Q[Qoff + 6] = (xrng64() & 0x600c0000) | 0x05e2ec56 | aa1;
1693                Q[Qoff + 7] = (xrng64() & 0x604c203e) | 0x16819e01 | bb1 | (Q[Qoff + 6] & 0x01000000);
1694                Q[Qoff + 8] = (xrng64() & 0x604c7c1c) | 0x043283e0 | (Q[Qoff + 7] & 0x80000002);
1695                Q[Qoff + 9] = (xrng64() & 0x00002800) | 0x1c0101c1 | (Q[Qoff + 8] & 0x80001000);
1696                Q[Qoff + 10] = 0x078bcbc0 | bb1;
1697                Q[Qoff + 11] = (xrng64() & 0x07800000) | 0x607dc7df | bb1;
1698                Q[Qoff + 12] = (xrng64() & 0x00f00f7f) | 0x00081080 | (Q[Qoff + 11] & 0xe7000000);
1699                Q[Qoff + 13] = (xrng64() & 0x00701f77) | 0x3f0fe008 | aa1;
1700                Q[Qoff + 14] = (xrng64() & 0x00701f77) | 0x408be088 | aa1;
1701                Q[Qoff + 15] = (xrng64() & 0x00ff3ff7) | 0x7d000000;
1702                Q[Qoff + 16] = (xrng64() & 0x4ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000);
1703
1704                MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1705                MD5_REVERSE_STEP(block, Q, 6, 0xa8304613, 17);
1706                MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1707                MD5_REVERSE_STEP(block, Q, 11, 0x895cd7be, 22);
1708                MD5_REVERSE_STEP(block, Q, 14, 0xa679438e, 17);
1709                MD5_REVERSE_STEP(block, Q, 15, 0x49b40821, 22);
1710
1711                UInt32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
1712                UInt32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
1713                UInt32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];
1714
1715                UInt32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
1716                UInt32 tt1 = Q[Qoff - 2] + 0xe8c7b756;
1717
1718                UInt32 q1a = 0x04200040 | (Q[Qoff + 2] & 0xf01e1080);
1719
1720                UInt32 counter = 0;
1721                while (counter < (1 << 12))
1722                {
1723                    if (IsStopped)
1724                        return;
1725
1726                    MatchProgress = 2;
1727
1728                    ++counter;
1729
1730                    UInt32 q1 = q1a | (xrng64() & 0x01c0e71f);
1731                    UInt32 m1 = Q[Qoff + 2] - q1;
1732                    m1 = RR(m1, 12) - FF(q1, Q[Qoff + 0], Q[Qoff - 1]) - tt1;
1733
1734                    UInt32 q16 = Q[Qoff + 16];
1735                    UInt32 q17 = tt17 + m1;
1736                    q17 = RL(q17, 5) + q16;
1737                    if (0x40000000 != ((q17 ^ q16) & 0xc0008008)) continue;
1738                    if (0 != (q17 & 0x00020000)) continue;
1739
1740                    UInt32 q18 = GG(q17, q16, Q[Qoff + 15]) + tt18;
1741                    q18 = RL(q18, 9); q18 += q17;
1742                    if (0x00020000 != ((q18 ^ q17) & 0xa0020000)) continue;
1743
1744                    UInt32 q19 = GG(q18, q17, q16) + tt19;
1745                    q19 = RL(q19, 14); q19 += q18;
1746                    if (0 != (q19 & 0x80020000)) continue;
1747
1748                    UInt32 m0 = q1 - Q[Qoff + 0];
1749                    m0 = RR(m0, 7) - tt0;
1750
1751                    UInt32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
1752                    q20 = RL(q20, 20); q20 += q19;
1753                    if (0x00040000 != ((q20 ^ q19) & 0x80040000)) continue;
1754
1755                    Q[Qoff + 1] = q1;
1756                    Q[Qoff + 17] = q17;
1757                    Q[Qoff + 18] = q18;
1758                    Q[Qoff + 19] = q19;
1759                    Q[Qoff + 20] = q20;
1760
1761                    block[0] = m0;
1762                    block[1] = m1;
1763                    MD5_REVERSE_STEP(block, Q, 2, 0x242070db, 17);
1764
1765                    counter = 0;
1766                    break;
1767                }
1768                if (counter != 0)
1769                    continue;
1770
1771                UInt32 q4b = Q[Qoff + 4];
1772                UInt32 q9b = Q[Qoff + 9];
1773                UInt32 q10b = Q[Qoff + 10];
1774                UInt32 tt21 = GG(Q[Qoff + 20], Q[Qoff + 19], Q[Qoff + 18]) + Q[Qoff + 17] + 0xd62f105d;
1775
1776                counter = 0;
1777                while (counter < (1 << 6))
1778                {
1779                    if (IsStopped)
1780                        return;
1781
1782                    MatchProgress = 3;
1783
1784                    Q[Qoff + 4] = q4b ^ q4mask[counter];
1785                    ++counter;
1786                    MD5_REVERSE_STEP(block, Q, 5, 0x4787c62a, 12);
1787                    UInt32 q21 = tt21 + block[5];
1788                    q21 = RL(q21, 5); q21 += Q[Qoff + 20];
1789                    if (0 != ((q21 ^ Q[Qoff + 20]) & 0x80020000)) continue;
1790
1791                    Q[Qoff + 21] = q21;
1792                    MD5_REVERSE_STEP(block, Q, 3, 0xc1bdceee, 22);
1793                    MD5_REVERSE_STEP(block, Q, 4, 0xf57c0faf, 7);
1794                    MD5_REVERSE_STEP(block, Q, 7, 0xfd469501, 22);
1795
1796                    UInt32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
1797                    UInt32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
1798                    UInt32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
1799                    UInt32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
1800
1801                    UInt32 counter2 = 0;
1802                    while (counter2 < (1 << 5))
1803                    {
1804                        if (IsStopped)
1805                            return;
1806
1807                        MatchProgress = 4;
1808
1809                        UInt32 q10 = q10b ^ q10mask[counter2];
1810                        UInt32 m10 = RR(Q[Qoff + 11] - q10, 17);
1811                        UInt32 q9 = q9b ^ q9mask[counter2];
1812                        ++counter2;
1813
1814                        m10 -= FF(q10, q9, Q[Qoff + 8]) + tt10;
1815
1816                        UInt32 aa = Q[Qoff + 21];
1817                        UInt32 dd = tt22 + m10; dd = RL(dd, 9) + aa;
1818                        if (0 != (dd & 0x80000000)) continue;
1819
1820                        UInt32 bb = Q[Qoff + 20];
1821                        UInt32 cc = tt23 + GG(dd, aa, bb);
1822                        if (0 != (cc & 0x20000)) continue;
1823                        cc = RL(cc, 14) + dd;
1824                        if (0 != (cc & 0x80000000)) continue;
1825
1826                        bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
1827                        if (0 == (bb & 0x80000000)) continue;
1828
1829                        block[10] = m10;
1830                        Q[Qoff + 9] = q9;
1831                        Q[Qoff + 10] = q10;
1832                        MD5_REVERSE_STEP(block, Q, 13, 0xfd987193, 12);
1833
1834                        for (UInt32 k9 = 0; k9 < (1 << 10); )
1835                        {
1836                            if (IsStopped)
1837                                return;
1838
1839                            MatchProgress = 5;
1840
1841                            UInt32 a = aa, b = bb, c = cc, d = dd;
1842                            Q[Qoff + 9] = q9 ^ q9mask2[k9]; ++k9;
1843                            MD5_REVERSE_STEP(block, Q, 8, 0x698098d8, 7);
1844                            MD5_REVERSE_STEP(block, Q, 9, 0x8b44f7af, 12);
1845                            MD5_REVERSE_STEP(block, Q, 12, 0x6b901122, 7);
1846
1847                            MD5_STEP(GG, ref a, b, c, d, block[9], 0x21e1cde6, 5);
1848                            MD5_STEP(GG, ref d, a, b, c, block[14], 0xc33707d6, 9);
1849                            MD5_STEP(GG, ref c, d, a, b, block[3], 0xf4d50d87, 14);
1850                            MD5_STEP(GG, ref b, c, d, a, block[8], 0x455a14ed, 20);
1851                            MD5_STEP(GG, ref a, b, c, d, block[13], 0xa9e3e905, 5);
1852                            MD5_STEP(GG, ref d, a, b, c, block[2], 0xfcefa3f8, 9);
1853                            MD5_STEP(GG, ref c, d, a, b, block[7], 0x676f02d9, 14);
1854                            MD5_STEP(GG, ref b, c, d, a, block[12], 0x8d2a4c8a, 20);
1855                            MD5_STEP(HH, ref a, b, c, d, block[5], 0xfffa3942, 4);
1856                            MD5_STEP(HH, ref d, a, b, c, block[8], 0x8771f681, 11);
1857
1858                            c += HH(d, a, b) + block[11] + 0x6d9d6122;
1859                            if (0 == (c & (1 << 15)))
1860                                continue;
1861                            c = (c << 16 | c >> 16) + d;
1862
1863                            MD5_STEP(HH, ref b, c, d, a, block[14], 0xfde5380c, 23);
1864                            MD5_STEP(HH, ref a, b, c, d, block[1], 0xa4beea44, 4);
1865                            MD5_STEP(HH, ref d, a, b, c, block[4], 0x4bdecfa9, 11);
1866                            MD5_STEP(HH, ref c, d, a, b, block[7], 0xf6bb4b60, 16);
1867                            MD5_STEP(HH, ref b, c, d, a, block[10], 0xbebfbc70, 23);
1868                            MD5_STEP(HH, ref a, b, c, d, block[13], 0x289b7ec6, 4);
1869                            MD5_STEP(HH, ref d, a, b, c, block[0], 0xeaa127fa, 11);
1870                            MD5_STEP(HH, ref c, d, a, b, block[3], 0xd4ef3085, 16);
1871                            MD5_STEP(HH, ref b, c, d, a, block[6], 0x04881d05, 23);
1872                            MD5_STEP(HH, ref a, b, c, d, block[9], 0xd9d4d039, 4);
1873                            MD5_STEP(HH, ref d, a, b, c, block[12], 0xe6db99e5, 11);
1874                            MD5_STEP(HH, ref c, d, a, b, block[15], 0x1fa27cf8, 16);
1875                            MD5_STEP(HH, ref b, c, d, a, block[2], 0xc4ac5665, 23);
1876                            if (0 != ((b ^ d) & 0x80000000))
1877                                continue;
1878
1879                            MD5_STEP(II, ref a, b, c, d, block[0], 0xf4292244, 6);
1880                            if (0 != ((a ^ c) >> 31)) continue;
1881                            MD5_STEP(II, ref d, a, b, c, block[7], 0x432aff97, 10);
1882                            if (0 == ((b ^ d) >> 31)) continue;
1883                            MD5_STEP(II, ref c, d, a, b, block[14], 0xab9423a7, 15);
1884                            if (0 != ((a ^ c) >> 31)) continue;
1885                            MD5_STEP(II, ref b, c, d, a, block[5], 0xfc93a039, 21);
1886                            if (0 != ((b ^ d) >> 31)) continue;
1887                            MD5_STEP(II, ref a, b, c, d, block[12], 0x655b59c3, 6);
1888                            if (0 != ((a ^ c) >> 31)) continue;
1889                            MD5_STEP(II, ref d, a, b, c, block[3], 0x8f0ccc92, 10);
1890                            if (0 != ((b ^ d) >> 31)) continue;
1891                            MD5_STEP(II, ref c, d, a, b, block[10], 0xffeff47d, 15);
1892                            if (0 != ((a ^ c) >> 31)) continue;
1893                            MD5_STEP(II, ref b, c, d, a, block[1], 0x85845dd1, 21);
1894                            if (0 != ((b ^ d) >> 31)) continue;
1895                            MD5_STEP(II, ref a, b, c, d, block[8], 0x6fa87e4f, 6);
1896                            if (0 != ((a ^ c) >> 31)) continue;
1897                            MD5_STEP(II, ref d, a, b, c, block[15], 0xfe2ce6e0, 10);
1898                            if (0 != ((b ^ d) >> 31)) continue;
1899                            MD5_STEP(II, ref  c, d, a, b, block[6], 0xa3014314, 15);
1900                            if (0 != ((a ^ c) >> 31)) continue;
1901                            MD5_STEP(II, ref  b, c, d, a, block[13], 0x4e0811a1, 21);
1902                            if (0 == ((b ^ d) >> 31)) continue;
1903                            MD5_STEP(II, ref a, b, c, d, block[4], 0xf7537e82, 6);
1904                            if (0 != ((a ^ c) >> 31)) continue;
1905                            MD5_STEP(II, ref d, a, b, c, block[11], 0xbd3af235, 10);
1906                            if (0 != ((b ^ d) >> 31)) continue;
1907                            MD5_STEP(II, ref c, d, a, b, block[2], 0x2ad7d2bb, 15);
1908                            if (0 != ((a ^ c) >> 31)) continue;
1909                            MD5_STEP(II, ref b, c, d, a, block[9], 0xeb86d391, 21);
1910
1911                            //std::cout << "." << std::flush;
1912
1913                            UInt32[] block2 = new UInt32[16];
1914                            UInt32[] IV1 = new UInt32[4], IV2 = new UInt32[4];
1915                            for (int t = 0; t < 4; ++t)
1916                            {
1917                                IV1[t] = IV[t];
1918                                IV2[t] = IV[t] + ((UInt32)1 << 31);
1919                            }
1920                            IV2[1] += (1 << 25);
1921                            IV2[2] += (1 << 25);
1922                            IV2[3] += (1 << 25);
1923
1924                            for (int t = 0; t < 16; ++t)
1925                                block2[t] = block[t];
1926                            block2[4] += (UInt32)1 << 31;
1927                            block2[11] -= 1 << 15;
1928                            block2[14] += (UInt32)1 << 31;
1929
1930                            md5_compress(IV1, block);
1931                            md5_compress(IV2, block2);
1932                            if (IV2[0] == IV1[0] && IV2[1] == IV1[1] && IV2[2] == IV1[2] && IV2[3] == IV1[3])
1933                            {
1934                                MatchProgress = 6;
1935                                return;
1936                            }
1937
1938                            //if (IV2[0] != IV1[0])
1939                            //  std::cout << "!" << std::flush;
1940                        }
1941                    }
1942                }
1943            }
1944        }
1945
1946        private bool IsStopped { get; set; }
1947
1948        protected override void PerformStop()
1949        {
1950            IsStopped = true;
1951        }
1952    }
1953}
Note: See TracBrowser for help on using the repository browser.