Skip to content

Instantly share code, notes, and snippets.

@ngg

ngg/fastcoll.patch

Created April 7, 2019 18:07
Show Gist options
  • Save ngg/12a550679eac2ad6ff4dfc574a2b41a4 to your computer and use it in GitHub Desktop.
Save ngg/12a550679eac2ad6ff4dfc574a2b41a4 to your computer and use it in GitHub Desktop.
Download ZIP
fastcoll patch for md5suffix
Raw
fastcoll.patch
diff --git a/block0.cpp b/block0.cpp
index ad99358..e92eb04 100644
--- a/block0.cpp
+++ b/block0.cpp
@@ -83,11 +83,18 @@ void find_block0(uint32 block[], const uint32 IV[])
Q[Qoff + 16] = (xrng64() & 0x1ffdffff) | 0xa0000000 | (~Q[Qoff + 15] & 0x40020000);
MD5_REVERSE_STEP(0, 0xd76aa478, 7);
+ if (!ok_uint32(block[0])) continue;
MD5_REVERSE_STEP(6, 0xa8304613, 17);
+ if (!ok_uint32(block[6])) continue;
MD5_REVERSE_STEP(7, 0xfd469501, 22);
MD5_REVERSE_STEP(11, 0x895cd7be, 22);
+ if (!ok_uint32(block[11])) continue;
+ if (!ok_uint32(block[11] + (1 << 15))) continue;
MD5_REVERSE_STEP(14, 0xa679438e, 17);
+ if (!ok_uint32(block[14])) continue;
+ if (!ok_uint32(block[14] + (1 << 31))) continue;
MD5_REVERSE_STEP(15, 0x49b40821, 22);
+ if (!ok_uint32(block[15])) continue;
const uint32 tt1 = FF(Q[Qoff + 1], Q[Qoff + 0], Q[Qoff - 1]) + Q[Qoff - 2] + 0xe8c7b756;
const uint32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
@@ -120,6 +127,7 @@ void find_block0(uint32 block[], const uint32 IV[])
continue;
block[1] = q17-q16; block[1] = RR(block[1], 5); block[1] -= tt17;
+ if (!ok_uint32(block[1])) continue;
uint32 q2 = block[1] + tt1; q2 = RL(q2, 12); q2 += Q[Qoff + 1];
block[5] = tt5 - q2;
@@ -129,6 +137,7 @@ void find_block0(uint32 block[], const uint32 IV[])
Q[Qoff + 19] = q19;
Q[Qoff + 20] = q20;
MD5_REVERSE_STEP(2, 0x242070db, 17);
+ if (!ok_uint32(block[2])) continue;
counter = 0;
break;
@@ -149,6 +158,7 @@ void find_block0(uint32 block[], const uint32 IV[])
Q[Qoff+4] = q4 ^ q4mask[counter2];
++counter2;
MD5_REVERSE_STEP(5, 0x4787c62a, 12);
+ if (!ok_uint32(block[5])) continue;
uint32 q21 = tt21 + block[5];
q21 = RL(q21,5); q21 += Q[Qoff+20];
if (0 != ((q21^Q[Qoff+20]) & 0x80020000))
@@ -156,8 +166,12 @@ void find_block0(uint32 block[], const uint32 IV[])
Q[Qoff + 21] = q21;
MD5_REVERSE_STEP(3, 0xc1bdceee, 22);
+ if (!ok_uint32(block[3])) continue;
MD5_REVERSE_STEP(4, 0xf57c0faf, 7);
+ if (!ok_uint32(block[4])) continue;
+ if (!ok_uint32(block[4] + (1 << 31))) continue;
MD5_REVERSE_STEP(7, 0xfd469501, 22);
+ if (!ok_uint32(block[7])) continue;
const uint32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
const uint32 tt23 = Q[Qoff + 19] + 0xd8a1e681 + block[15];
@@ -178,8 +192,10 @@ void find_block0(uint32 block[], const uint32 IV[])
uint32 q10 = Q[Qoff+10] ^ (q9q10mask[counter3] & 0x60);
Q[Qoff + 9] = q9backup ^ (q9q10mask[counter3] & 0x2000);
++counter3;
+ if (!ok_uint32(tt13-q10)) continue;
uint32 m10 = RR(Q[Qoff+11]-q10,17);
m10 -= FF(q10, Q[Qoff+9], Q[Qoff+8]) + tt10;
+ if (!ok_uint32(m10)) continue;
uint32 aa = Q[Qoff + 21];
uint32 dd = tt22+m10; dd = RL(dd, 9) + aa;
@@ -204,10 +220,13 @@ void find_block0(uint32 block[], const uint32 IV[])
{
uint32 q9 = Q[Qoff + 9] ^ q9mask[counter4];
block[12] = tt12 - FF(Q[Qoff + 12], Q[Qoff + 11], q10) - q9;
+ if (!ok_uint32(block[12])) continue;
uint32 m8 = q9 - Q[Qoff + 8];
block[8] = RR(m8, 7) - tt8;
+ if (!ok_uint32(block[8])) continue;
uint32 m9 = q10 - q9;
block[9] = RR(m9, 12) - FF(q9, Q[Qoff + 8], Q[Qoff + 7]) - tt9;
+ if (!ok_uint32(block[9])) continue;
uint32 a = aa, b = bb, c = cc, d = dd;
MD5_STEP(GG, a, b, c, d, block[9], 0x21e1cde6, 5);
@@ -288,7 +307,12 @@ void find_block0(uint32 block[], const uint32 IV[])
if ( (IHV3&(1<<25))!=0 || (IHV2&(1<<25))!=0 || (IHV1&(1<<25))!=0
|| ((IHV2^IHV1)&1)!=0) stevens = false;
- if (!(wang || stevens)) continue;
+ //if (!(wang || stevens)) continue;
+ if (!wang) {
+ if (stevens)
+ std::cout << "S" << std::flush;
+ continue;
+ }
std::cout << "." << std::flush;
@@ -302,6 +326,12 @@ void find_block0(uint32 block[], const uint32 IV[])
block2[4] += 1<<31;
block2[11] += 1<<15;
block2[14] += 1<<31;
+ for (int t = 0; t < 16; ++t)
+ if (!ok_uint32(block[t]))
+ std::cout << "REALLY BAD " << t << std::endl;
+ for (int t = 0; t < 16; ++t)
+ if (!ok_uint32(block2[t]))
+ std::cout << "REALLY BAD2 " << t << std::endl;
md5_compress(IV1, block);
md5_compress(IV2, block2);
diff --git a/block1.cpp b/block1.cpp
index bb612d9..36bcc26 100644
--- a/block1.cpp
+++ b/block1.cpp
@@ -55,7 +55,7 @@ void find_block1_stevens_00(uint32 block[], const uint32 IV[]);
void find_block1(uint32 block[], const uint32 IV[])
{
- if ( ((IV[1]^IV[2])&(1<<31))==0 && ((IV[1]^IV[3])&(1<<31))==0
+ if (false && ((IV[1]^IV[2])&(1<<31))==0 && ((IV[1]^IV[3])&(1<<31))==0
&& (IV[3]&(1<<25))==0 && (IV[2]&(1<<25))==0 && (IV[1]&(1<<25))==0 && ((IV[2]^IV[1])&1)==0
)
{
diff --git a/block1wang.cpp b/block1wang.cpp
index e559390..9ac11ae 100644
--- a/block1wang.cpp
+++ b/block1wang.cpp
@@ -46,15 +46,17 @@ notice and the version number should be present.
#include <vector>
#include "main.hpp"
+uint32 tab[128] = {0};
+uint32 good16 = 0, num16 = 0;
void find_block1_wang(uint32 block[], const uint32 IV[])
{
uint32 Q[68] = { IV[0], IV[3], IV[2], IV[1] };
- std::vector<uint32> q4mask(1<<6);
+ std::vector<uint32> q4mask(1<<10);
for (unsigned k = 0; k < q4mask.size(); ++k)
q4mask[k] = ((k<<13) ^ (k<<19)) & 0x01c0e000;
- std::vector<uint32> q9mask(1<<5), q10mask(1<<5);
+ std::vector<uint32> q9mask(1<<7), q10mask(1<<7);
for (unsigned k = 0; k < q9mask.size(); ++k)
{
uint32 msk = (k<<5) ^ (k<<13) ^ (k<<17) ^ (k<<24);
@@ -62,7 +64,7 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
q10mask[k] = msk & 0x18000020;
}
- std::vector<uint32> q9mask2(1<<10);
+ std::vector<uint32> q9mask2(1<<13);
for (unsigned k = 0; k < q9mask2.size(); ++k)
q9mask2[k] = ((k<<1) ^ (k<<7) ^ (k<<14) ^ (k<<15) ^ (k<<22)) & 0x6074041c;
@@ -77,23 +79,47 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
Q[Qoff + 4] = 0x3a040010 | (Q[Qoff + 3] & 0x80000601);
Q[Qoff + 5] = (xrng64() & 0x03c0e000) | 0x482f0e50 | aa;
Q[Qoff + 6] = (xrng64() & 0x600c0000) | 0x05e2ec56 | aa;
- Q[Qoff + 7] = (xrng64() & 0x604c203e) | 0x16819e01 | bb | (Q[Qoff + 6] & 0x01000000);
- Q[Qoff + 8] = (xrng64() & 0x604c7c1c) | 0x043283e0 | (Q[Qoff + 7] & 0x80000002);
- Q[Qoff + 9] = (xrng64() & 0x00002800) | 0x1c0101c1 | (Q[Qoff + 8] & 0x80001000);
- Q[Qoff + 10] = 0x078bcbc0 | bb;
- Q[Qoff + 11] = (xrng64() & 0x07800000) | 0x607dc7df | bb;
- Q[Qoff + 12] = (xrng64() & 0x00f00f7f) | 0x00081080 | (Q[Qoff + 11] & 0xe7000000);
- Q[Qoff + 13] = (xrng64() & 0x00701f77) | 0x3f0fe008 | aa;
- Q[Qoff + 14] = (xrng64() & 0x00701f77) | 0x408be088 | aa;
- Q[Qoff + 15] = (xrng64() & 0x00ff3ff7) | 0x7d000000;
- Q[Qoff + 16] = (xrng64() & 0x4ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000);
-
MD5_REVERSE_STEP(5, 0x4787c62a, 12);
+ Q[Qoff + 7] = (xrng64() & 0x604c203e) | 0x16819e01 | bb | (Q[Qoff + 6] & 0x01000000);
MD5_REVERSE_STEP(6, 0xa8304613, 17);
+ if (!ok_uint32(block[6])) continue;
+ Q[Qoff + 8] = (xrng64() & 0x604c7c1c) | 0x043283e0 | (Q[Qoff + 7] & 0x80000002);
MD5_REVERSE_STEP(7, 0xfd469501, 22);
- MD5_REVERSE_STEP(11, 0x895cd7be, 22);
- MD5_REVERSE_STEP(14, 0xa679438e, 17);
+ if (!ok_uint32(block[7])) continue;
+ int block14t;
+ for (block14t = 1000; block14t > 0; block14t--) {
+ Q[Qoff + 9] = (xrng64() & 0x00002800) | 0x1c0101c1 | (Q[Qoff + 8] & 0x80001000);
+ Q[Qoff + 10] = 0x078bcbc0 | bb;
+ Q[Qoff + 11] = (xrng64() & 0x07800000) | 0x607dc7df | bb;
+ Q[Qoff + 12] = (xrng64() & 0x00f00f7f) | 0x00081080 | (Q[Qoff + 11] & 0xe7000000);
+ MD5_REVERSE_STEP(11, 0x895cd7be, 22);
+ if (!ok_uint32(block[11])) continue;
+ if (!ok_uint32(block[11] - (1 << 15))) continue;
+ Q[Qoff + 13] = (xrng64() & 0x00701f77) | 0x3f0fe008 | aa;
+ Q[Qoff + 14] = (xrng64() & 0x00701f77) | 0x408be088 | aa;
+ //Q[Qoff + 15] = (xrng64() & 0x00ff3ff7) | 0x7d000000;
+ Q[Qoff + 15] = (xrng64() & 0x00ff3ff7) | 0x7d020000;
+ MD5_REVERSE_STEP(14, 0xa679438e, 17);
+ if (!ok_uint32(block[14])) continue;
+ if (!ok_uint32(block[14] + (1 << 31))) continue;
+ if (((block[14] >> 24) & 0x7F) != 'g') continue;
+ break;
+ }
+ if (block14t == 0) continue;
+ if (((block[14] >> 24) & 0x7F) != 'g') {
+ std::cout << "REALLY BAD14" << std::endl;
+ }
+ const uint32 block15 = 0x20657669; // "ive "
+ //Q[Qoff + 16] = (xrng64() & 0x4ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000);
+ Q[Qoff + 16] = RL(block15 + 0x49b40821 + Q[Qoff + 12] + FF(Q[Qoff + 15], Q[Qoff + 14], Q[Qoff + 13]), 22) + Q[Qoff + 15];
+ if (Q[Qoff + 16] != ((Q[Qoff + 16] & 0x4ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x00020000))) {
+ continue;
+ }
MD5_REVERSE_STEP(15, 0x49b40821, 22);
+ if (block[15] != block15) {
+ std::cout << "REALLY BAD15" << std::endl;
+ }
+ if (!ok_uint32(block[15])) continue;
const uint32 tt17 = GG(Q[Qoff + 16], Q[Qoff + 15], Q[Qoff + 14]) + Q[Qoff + 13] + 0xf61e2562;
const uint32 tt18 = Q[Qoff + 14] + 0xc040b340 + block[6];
@@ -105,13 +131,14 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
const uint32 q1a = 0x04200040 | (Q[Qoff + 2] & 0xf01e1080);
unsigned counter = 0;
- while (counter < (1 << 12))
+ while (counter < (1 << 15))
{
++counter;
uint32 q1 = q1a | (xrng64() & 0x01c0e71f);
uint32 m1 = Q[Qoff+2] - q1;
m1 = RR(m1, 12) - FF(q1, Q[Qoff+0], Q[Qoff-1]) - tt1;
+ if (!ok_uint32(m1)) continue;
const uint32 q16 = Q[Qoff+16];
uint32 q17 = tt17 + m1;
@@ -129,6 +156,7 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
uint32 m0 = q1 - Q[Qoff + 0];
m0 = RR(m0, 7) - tt0;
+ if (!ok_uint32(m0)) continue;
uint32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
q20 = RL(q20, 20); q20 += q19;
@@ -143,6 +171,7 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
block[0] = m0;
block[1] = m1;
MD5_REVERSE_STEP(2, 0x242070db, 17);
+ if (!ok_uint32(block[2])) continue;
counter = 0;
break;
@@ -156,19 +185,24 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
const uint32 tt21 = GG(Q[Qoff+20], Q[Qoff+19], Q[Qoff+18]) + Q[Qoff+17] + 0xd62f105d;
counter = 0;
- while (counter < (1<<6))
+ while (counter < (1<<10))
{
Q[Qoff + 4] = q4b ^ q4mask[counter];
++counter;
MD5_REVERSE_STEP(5, 0x4787c62a, 12);
+ if (!ok_uint32(block[5])) continue;
uint32 q21 = tt21 + block[5];
q21 = RL(q21, 5); q21 += Q[Qoff+20];
if (0 != ((q21^Q[Qoff+20]) & 0x80020000)) continue;
Q[Qoff+21] = q21;
MD5_REVERSE_STEP(3, 0xc1bdceee, 22);
+ if (!ok_uint32(block[3])) continue;
MD5_REVERSE_STEP(4, 0xf57c0faf, 7);
+ if (!ok_uint32(block[4])) continue;
+ if (!ok_uint32(block[4] + (1 << 31))) continue;
MD5_REVERSE_STEP(7, 0xfd469501, 22);
+ if (!ok_uint32(block[7])) continue;
const uint32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
const uint32 tt22 = GG(Q[Qoff + 21], Q[Qoff + 20], Q[Qoff + 19]) + Q[Qoff + 18] + 0x02441453;
@@ -176,7 +210,7 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
const uint32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
unsigned counter2 = 0;
- while (counter2 < (1<<5))
+ while (counter2 < (1<<7))
{
uint32 q10 = q10b ^ q10mask[counter2];
uint32 m10 = RR(Q[Qoff+11]-q10,17);
@@ -184,6 +218,7 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
++counter2;
m10 -= FF(q10, q9, Q[Qoff+8]) + tt10;
+ if (!ok_uint32(m10)) continue;
uint32 aa = Q[Qoff + 21];
uint32 dd = tt22+m10; dd = RL(dd, 9) + aa;
@@ -202,14 +237,18 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
Q[Qoff + 9] = q9;
Q[Qoff + 10] = q10;
MD5_REVERSE_STEP(13, 0xfd987193, 12);
+ if (!ok_uint32(block[13])) continue;
- for (unsigned k9 = 0; k9 < (1<<10);)
+ for (unsigned k9 = 0; k9 < (1<<13);)
{
uint32 a = aa, b = bb, c = cc, d = dd;
Q[Qoff + 9] = q9 ^ q9mask2[k9]; ++k9;
MD5_REVERSE_STEP(8, 0x698098d8, 7);
+ if (!ok_uint32(block[8])) continue;
MD5_REVERSE_STEP(9, 0x8b44f7af, 12);
+ if (!ok_uint32(block[9])) continue;
MD5_REVERSE_STEP(12, 0x6b901122, 7);
+ if (!ok_uint32(block[12])) continue;
MD5_STEP(GG, a, b, c, d, block[9], 0x21e1cde6, 5);
MD5_STEP(GG, d, a, b, c, block[14], 0xc33707d6, 9);
@@ -293,6 +332,12 @@ void find_block1_wang(uint32 block[], const uint32 IV[])
block2[4] += 1<<31;
block2[11] -= 1<<15;
block2[14] += 1<<31;
+ for (int t = 0; t < 16; ++t)
+ if (!ok_uint32(block[t]))
+ std::cout << "REALLY BAD " << t << std::endl;
+ for (int t = 0; t < 16; ++t)
+ if (!ok_uint32(block2[t]))
+ std::cout << "REALLY BAD2 " << t << std::endl;
md5_compress(IV1, block);
md5_compress(IV2, block2);
diff --git a/main.cpp b/main.cpp
index b964560..24ddb5c 100644
--- a/main.cpp
+++ b/main.cpp
@@ -289,8 +289,10 @@ int main(int argc, char** argv)
save_block(ofs1, msg1block0);
save_block(ofs1, msg1block1);
+ ofs1 << "me the flag!";
save_block(ofs2, msg2block0);
save_block(ofs2, msg2block1);
+ ofs2 << "me the flag!";
if (verbose)
cout << "Running time: " << runtime.elapsed() << " s" << endl;
return 0;
diff --git a/main.hpp b/main.hpp
index fd972e4..5385f63 100644
--- a/main.hpp
+++ b/main.hpp
@@ -85,3 +85,15 @@ inline uint32 RR(uint32 x, unsigned int n)
block[t] = RR(block[t], RC) - FF(Q[Qoff + t], Q[Qoff + t - 1], Q[Qoff + t - 2]) - Q[Qoff + t - 3] - AC )
#define Qoff 3
+
+inline bool ok_uint8(unsigned char c) {
+ if (c < 0xa1) return c != '\n' && c != '\r';
+ //return true;
+ if (c < 0xc1) return c == 0xa4 || c == 0xac || c == 0xad || c == 0xbb || c == 0xbf;
+ if (c < 0xe0) return c < 0xdb;
+ return c < 0xf3;
+}
+
+inline bool ok_uint32(uint32 c) {
+ return ok_uint8(c) && ok_uint8(c >> 8) && ok_uint8(c >> 16) && ok_uint8(c >> 24);
+}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment