申请邀请码，，，本人才疏学浅，发帖申请邀请码，，请大牛脚下留情。。发邀请码一枚

最近在看MD5碰撞这一块。。。

学到一些与大家分享下，在linux下完成。。。

全部基于王小云教授的《How to Break MD5 and other Hash Functions》

得到的启示如下：

（未注释，贴出部分源码分享）
鸽巢原理:
void find_block1_stevens_11(uint32 block[], const uint32 IV[])
{
        uint32 Q[68] = { IV[0], IV[3], IV[2], IV[1] };

        std::vector<uint32> q9q10mask(1<<5);
        for (unsigned k = 0; k < q9q10mask.size(); ++k)
                q9q10mask[k] = ((k<<5) ^ (k<<6) ^ (k<<7) ^ (k<<24) ^ (k<<27)) & 0x880002a0;
       
        std::vector<uint32> q9mask(1<<9);
        for (unsigned k = 0; k < q9mask.size(); ++k)
                q9mask[k] = ((k<<1) ^ (k<<3) ^ (k<<8) ^ (k<<12) ^ (k<<15) ^ (k<<18)) & 0x04710c12;
       
        while (true)
        {
                uint32 aa = Q[Qoff] & 0x80000000;

                Q[Qoff + 2] = (xrng64() & 0x75bef63e) | 0x0a410041 | aa;
                Q[Qoff + 3] = (xrng64() & 0x10345614) | 0x0202a9e1 | (Q[Qoff + 2] & 0x84000002);
                Q[Qoff + 4] = (xrng64() & 0x00145400) | 0xe84ba909 | (Q[Qoff + 3] & 0x00000014);
                Q[Qoff + 5] = (xrng64() & 0x80000000) | 0x75e90b1d | (Q[Qoff + 4] & 0x00145400);
                Q[Qoff + 6] = 0x7c23ff5a | (Q[Qoff + 5] & 0x80000000);
                Q[Qoff + 7] = (xrng64() & 0x40000880) | 0x114bf41a;
                Q[Qoff + 8] = (xrng64() & 0x00002090) | 0xb352dd01;
                Q[Qoff + 9] = (xrng64() & 0x00044000) | 0x7a803124;
                Q[Qoff +10] = (xrng64() & 0x00002000) | 0xf28a92c9 | (Q[Qoff + 9] & 0x00044000);
                Q[Qoff +11] = (xrng64() & 0x128a8108) | 0xc5710ed7 | (Q[Qoff + 10] & 0x00002000);
                Q[Qoff +12] = (xrng64() & 0x9edb8d7f) | 0x20003080 | (~Q[Qoff + 11] & 0x00200000);
                Q[Qoff +13] = (xrng64() & 0x3efb1d77) | 0x4004c008 | (Q[Qoff + 12] & 0x80000000);
                Q[Qoff +14] = (xrng64() & 0x1fff5d77) | 0x0000a288;
                Q[Qoff +15] = (xrng64() & 0x1efe7ff7) | 0x20008000 | (~Q[Qoff + 14] & 0x00010000);
                Q[Qoff +16] = (xrng64() & 0x1ffdffff) | 0x20000000 | (~Q[Qoff + 15] & 0x40020000);
               
                MD5_REVERSE_STEP(5, 0x4787c62a, 12);
                MD5_REVERSE_STEP(6, 0xa8304613, 17);
                MD5_REVERSE_STEP(7, 0xfd469501, 22);
                MD5_REVERSE_STEP(11, 0x895cd7be, 22);
                MD5_REVERSE_STEP(14, 0xa679438e, 17);
                MD5_REVERSE_STEP(15, 0x49b40821, 22);

                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];
                const uint32 tt19 = Q[Qoff + 15] + 0x265e5a51 + block[11];

                const uint32 tt0 = FF(Q[Qoff + 0], Q[Qoff - 1], Q[Qoff - 2]) + Q[Qoff - 3] + 0xd76aa478;
                const uint32 tt1 = Q[Qoff - 2] + 0xe8c7b756;               

                const uint32 q1a = 0x02000861 ^ (Q[Qoff + 0] & 0x80000020);
               
                unsigned counter = 0;
                while (counter < (1 << 12))
                {
                        ++counter;

                        uint32 q1 = q1a | (xrng64() & 0x7dfff79e);
                        uint32 m1 = Q[Qoff+2] - q1;
                        m1 = RR(m1, 12) - FF(q1, Q[Qoff+0], Q[Qoff-1]) - tt1;

                        const uint32 q16 = Q[Qoff+16];
                        uint32 q17 = tt17 + m1;
                        q17 = RL(q17, 5) + q16;
                        if (0x40000000 != ((q17^q16) & 0xc0008008)) continue;
                        if (0 != (q17 & 0x00020000)) continue;

                        uint32 q18 = GG(q17, q16, Q[Qoff+15]) + tt18;
                        q18 = RL(q18, 9); q18 += q17;
                        if (0x80020000 != ((q18^q17) & 0xa0020000)) continue;

                        uint32 q19 = GG(q18, q17, q16) + tt19;
                        q19 = RL(q19, 14); q19 += q18;
                        if (0x80000000 != (q19 & 0x80020000)) continue;

                        uint32 m0 = q1 - Q[Qoff + 0];
                        m0 = RR(m0, 7) - tt0;

                        uint32 q20 = GG(q19, q18, q17) + q16 + 0xe9b6c7aa + m0;
                        q20 = RL(q20, 20); q20 += q19;
                        if (0x00040000 != ((q20^q19) & 0x80040000))        continue;
                       
                        Q[Qoff + 1] = q1;
                        Q[Qoff + 17] = q17;
                        Q[Qoff + 18] = q18;
                        Q[Qoff + 19] = q19;
                        Q[Qoff + 20] = q20;

                        block[0] = m0;
                        block[1] = m1;

                        MD5_REVERSE_STEP(5, 0x4787c62a, 12);
                        uint32 q21 = GG(Q[Qoff+20], Q[Qoff+19], Q[Qoff+18]) + Q[Qoff+17] + 0xd62f105d + block[5];
                        q21 = RL(q21, 5); q21 += Q[Qoff+20];
                        if (0 != ((q21^Q[Qoff+20]) & 0x80020000)) continue;

                        Q[Qoff+21] = q21;

                        counter = 0;
                        break;
                }
                if (counter != 0)
                        continue;

                const uint32 q9b = Q[Qoff + 9];
                const uint32 q10b = Q[Qoff + 10];

                MD5_REVERSE_STEP(2, 0x242070db, 17);
                MD5_REVERSE_STEP(3, 0xc1bdceee, 22);
                MD5_REVERSE_STEP(4, 0xf57c0faf, 7);
                MD5_REVERSE_STEP(7, 0xfd469501, 22);

                const uint32 tt10 = Q[Qoff + 7] + 0xffff5bb1;
                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];
                const uint32 tt24 = Q[Qoff + 20] + 0xe7d3fbc8 + block[4];
         
                for (unsigned k10 = 0; k10 < (1<<5); ++k10)
                {
                        uint32 q10 = q10b | (q9q10mask[k10]&0x08000040);
                        uint32 m10 = RR(Q[Qoff+11]-q10,17);
                        uint32 q9 = q9b | (q9q10mask[k10]&0x80000280);

                        m10 -= FF(q10, q9, Q[Qoff+8]) + tt10;

                        uint32 aa = Q[Qoff + 21];
                        uint32 dd = tt22+m10; dd = RL(dd, 9) + aa;
                        if (0 == (dd & 0x80000000)) continue;                       

                        uint32 bb = Q[Qoff + 20];
                        uint32 cc = tt23 + GG(dd, aa, bb);
                        if (0 != (cc & 0x20000)) continue;
                        cc = RL(cc, 14) + dd;
                        if (0 != (cc & 0x80000000)) continue;

                        bb = tt24 + GG(cc, dd, aa); bb = RL(bb, 20) + cc;
                        if (0 == (bb & 0x80000000)) continue;

                        block[10] = m10;
                        Q[Qoff + 9] = q9;
                        Q[Qoff + 10] = q10;
                        MD5_REVERSE_STEP(13, 0xfd987193, 12);

                        for (unsigned k9 = 0; k9 < (1<<9); ++k9)
                        {
                                uint32 a = aa, b = bb, c = cc, d = dd;
                                Q[Qoff + 9] = q9 ^ q9mask[k9];
                                MD5_REVERSE_STEP(8, 0x698098d8, 7);
                                MD5_REVERSE_STEP(9, 0x8b44f7af, 12);
                                MD5_REVERSE_STEP(12, 0x6b901122, 7);

                                MD5_STEP(GG, a, b, c, d, block[9], 0x21e1cde6, 5);
                                MD5_STEP(GG, d, a, b, c, block[14], 0xc33707d6, 9);
                                MD5_STEP(GG, c, d, a, b, block[3], 0xf4d50d87, 14);
                                MD5_STEP(GG, b, c, d, a, block[8], 0x455a14ed, 20);
                                MD5_STEP(GG, a, b, c, d, block[13], 0xa9e3e905, 5);
                                MD5_STEP(GG, d, a, b, c, block[2], 0xfcefa3f8, 9);
                                MD5_STEP(GG, c, d, a, b, block[7], 0x676f02d9, 14);
                                MD5_STEP(GG, b, c, d, a, block[12], 0x8d2a4c8a, 20);
                                MD5_STEP(HH, a, b, c, d, block[5], 0xfffa3942, 4);
                                MD5_STEP(HH, d, a, b, c, block[8], 0x8771f681, 11);

                                c += HH(d, a, b) + block[11] + 0x6d9d6122;
                                if (0 != (c & (1 << 15)))
                                        continue;
                                c = (c<<16 | c>>16) + d;
                                       
                                MD5_STEP(HH, b, c, d, a, block[14], 0xfde5380c, 23);
                                MD5_STEP(HH, a, b, c, d, block[1], 0xa4beea44, 4);
                                MD5_STEP(HH, d, a, b, c, block[4], 0x4bdecfa9, 11);
                                MD5_STEP(HH, c, d, a, b, block[7], 0xf6bb4b60, 16);
                                MD5_STEP(HH, b, c, d, a, block[10], 0xbebfbc70, 23);
                                MD5_STEP(HH, a, b, c, d, block[13], 0x289b7ec6, 4);
                                MD5_STEP(HH, d, a, b, c, block[0], 0xeaa127fa, 11);
                                MD5_STEP(HH, c, d, a, b, block[3], 0xd4ef3085, 16);
                                MD5_STEP(HH, b, c, d, a, block[6], 0x04881d05, 23);
                                MD5_STEP(HH, a, b, c, d, block[9], 0xd9d4d039, 4);
                                MD5_STEP(HH, d, a, b, c, block[12], 0xe6db99e5, 11);
                                MD5_STEP(HH, c, d, a, b, block[15], 0x1fa27cf8, 16);
                                MD5_STEP(HH, b, c, d, a, block[2], 0xc4ac5665, 23);
                                if (0 != ((b^d) & 0x80000000))
                                        continue;

                                MD5_STEP(II, a, b, c, d, block[0], 0xf4292244, 6);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, d, a, b, c, block[7], 0x432aff97, 10);
                                if (0 == ((b^d) >> 31)) continue;
                                MD5_STEP(II, c, d, a, b, block[14], 0xab9423a7, 15);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, b, c, d, a, block[5], 0xfc93a039, 21);
                                if (0 != ((b^d) >> 31)) continue;
                                MD5_STEP(II, a, b, c, d, block[12], 0x655b59c3, 6);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, d, a, b, c, block[3], 0x8f0ccc92, 10);
                                if (0 != ((b^d) >> 31)) continue;
                                MD5_STEP(II, c, d, a, b, block[10], 0xffeff47d, 15);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, b, c, d, a, block[1], 0x85845dd1, 21);
                                if (0 != ((b^d) >> 31)) continue;
                                MD5_STEP(II, a, b, c, d, block[8], 0x6fa87e4f, 6);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, d, a, b, c, block[15], 0xfe2ce6e0, 10);
                                if (0 != ((b^d) >> 31)) continue;
                                MD5_STEP(II, c, d, a, b, block[6], 0xa3014314, 15);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, b, c, d, a, block[13], 0x4e0811a1, 21);
                                if (0 == ((b^d) >> 31)) continue;
                                MD5_STEP(II, a, b, c, d, block[4], 0xf7537e82, 6);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, d, a, b, c, block[11], 0xbd3af235, 10);
                                if (0 != ((b^d) >> 31)) continue;
                                MD5_STEP(II, c, d, a, b, block[2], 0x2ad7d2bb, 15);
                                if (0 != ((a^c) >> 31)) continue;
                                MD5_STEP(II, b, c, d, a, block[9], 0xeb86d391, 21);

                                std::cout << "." << std::flush;

                                uint32 block2[16];
                                uint32 IV1[4], IV2[4];
                                for (int t = 0; t < 4; ++t)
                                {
                                        IV1[t] = IV[t];
                                        IV2[t] = IV[t] + (1 << 31);
                                }
                                IV2[1] -= (1 << 25);
                                IV2[2] -= (1 << 25);
                                IV2[3] -= (1 << 25);

                                for (int t = 0; t < 16; ++t)
                                        block2[t] = block[t];
                                block2[4] += 1<<31;
                                block2[11] += 1<<15;
                                block2[14] += 1<<31;

                                md5_compress(IV1, block);
                                md5_compress(IV2, block2);
                                if (IV2[0]==IV1[0] && IV2[1]==IV1[1] && IV2[2]==IV1[2] && IV2[3]==IV1[3])
                                        return;
                                if (IV2[0] != IV1[0])
                                                std::cout << "!" << std::flush;
                        }
                }
        }
}

void test_md5iv(bool single = false);
void test_rndiv(bool single = false);
void test_reciv(bool single = false);
void test_all();

int main(int argc, char** argv)
{
        seed32_1 = uint32(time(NULL));
        seed32_2 = 0x12345678;

        uint32 IV[4] = { MD5IV[0], MD5IV[1], MD5IV[2], MD5IV[3] };

        string outfn1 = "msg1.bin";
        string outfn2 = "msg2.bin";
        string ihv;
        string prefixfn;
        bool verbose = true;

        cout <<
                "MD5 collision generator v1.5\n"
                "by Marc Stevens (http://www.win.tue.nl/hashclash/)\n"
                << endl;

        try
        {
                boost::timer runtime;

                po::options_description desc("Allowed options");
                desc.add_options()
                        ("help,h", "Show options.")
                        ("quiet,q", "Be less verbose.")
                        ("ihv,i", po::value<string>(&ihv), "Use specified initial value. Default is MD5 initial value.")
                        ("prefixfile,p", po::value<string>(&prefixfn), "Calculate initial value using given prefixfile. Also copies data to output files.")                       
                        ("out,o", po::value<vector<string> >()->multitoken(), "Set output filenames. This must be the last option and exactly 2 filenames must be specified. \nDefault: -o msg1.bin msg2.bin")
                        ;

                po::options_description hidden;
                hidden.add_options()
                        ("testmd5iv", "Endlessly time collision generation using MD5 initial value.")
                        ("testrndiv", "Endlessly time collision generation using arbitrary random initial values.")
                        ("testreciv", "Endlessly time collision generation using recommended random initial values.")
                        ("testall", "Endlessly time collision generation for each case.")
                        ;

                po::options_description cmdline;
                cmdline.add(desc).add(hidden);
                po::positional_options_description p;
                p.add("prefixfile", 1);
                po::variables_map vm;
                po::store(po::command_line_parser(argc, argv).options(cmdline).positional(p).run(), vm);
                po::notify(vm);

                if (vm.count("quiet"))
                        verbose = false;

                if (vm.count("help") || argc == 1) {
                        cout << desc << endl;
                        return 1;
                }

                if (vm.count("testmd5iv"))
                        test_md5iv();
                if (vm.count("testrndiv"))
                        test_rndiv();
                if (vm.count("testreciv"))
                        test_reciv();
                if (vm.count("testall"))
                        test_all();

                if (vm.count("prefixfile"))
                {
                        unsigned l = prefixfn.size();
                        if (l >= 4 && prefixfn[l-4]=='.' && prefixfn[l-3]!='.' && prefixfn[l-2]!='.' && prefixfn[l-1]!='.')
                        {
                                outfn1 = prefixfn.substr(0, l-4) + "_msg1" + prefixfn.substr(l-4);
                                outfn2 = prefixfn.substr(0, l-4) + "_msg2" + prefixfn.substr(l-4);
                                unsigned i = 1;
                                while ( fs::exists(fs::path(outfn1, fs::native))
                                         || fs::exists(fs::path(outfn2, fs::native)))
                                {
                                        outfn1 = prefixfn.substr(0, l-4) + "_msg1_" + lexical_cast<string>(i) + prefixfn.substr(l-4);
                                        outfn2 = prefixfn.substr(0, l-4) + "_msg2_" + lexical_cast<string>(i) + prefixfn.substr(l-4);
                                        ++i;
                                }
                        }
                }

                if (vm.count("out"))
                {
                        vector<string> outfns = vm["out"].as< vector<string> >();
                        if (outfns.size() != 2)
                        {
                                cerr << "Error: exactly two output filenames should be specified." << endl;
                                return 1;
                        }
                        outfn1 = outfns[0];
                        outfn2 = outfns[1];
                }

                if (verbose)
                        cout << "Using output filenames: '" << outfn1 << "' and '" << outfn2 << "'" << endl;
                ofstream ofs1(outfn1.c_str(), ios::binary);
                if (!ofs1)
                {
                        cerr << "Error: cannot open outfile: '" << outfn1 << "'" << endl;
                        return 1;
                }
                ofstream ofs2(outfn2.c_str(), ios::binary);
                if (!ofs2)
                {
                        cerr << "Error: cannot open outfile: '" << outfn2 << "'" << endl;
                        return 1;
                }

                if (vm.count("prefixfile"))
                {
                        if (verbose)
                                cout << "Using prefixfile: '" << prefixfn << "'" << endl;
                        ifstream ifs(prefixfn.c_str(), ios::binary);
                        if (!ifs)
                        {
                                cerr << "Error: cannot open inputfile: '" << prefixfn << "'" << endl;
                                return 1;
                        }
                        uint32 block[16];
                        while (true)
                        {
                                unsigned len = load_block(ifs, block);
                                if (len)
                                {
                                        save_block(ofs1, block);
                                        save_block(ofs2, block);
                                        md5_compress(IV, block);
                                } else
                                        break;
                        }
                }
                else
                {
                        if (vm.count("ihv") == 0)
                                ihv = "0123456789abcdeffedcba9876543210";
                        if (ihv.size() != 32)
                        {
                                cerr << "Error: an initial value must be specified as a hash value of 32 hexadecimal characters." << endl;
                                return 1;
                        } else
                        {
                                uint32 c;
                                for (unsigned i = 0; i < 4; ++i)
                                {
                                        IV[i] = 0;
                                        for (unsigned b = 0; b < 4; ++b)
                                        {
                                                stringstream ss;
                                                ss << ihv.substr(i*8+b*2,2);
                                                ss >> hex >> c;                                       
                                                IV[i] += c << (b*8);
                                        }
                                }

                        }
                }
                if (verbose)
                {
                        cout << "Using initial value: " << hex;
                        unsigned oldwidth = cout.width(2);
                        char oldfill = cout.fill('0');
                       
                        for (unsigned i = 0; i < 4; ++i)
                        {
                                for (unsigned b = 0; b < 4; ++b)
                                {
                                        cout.width(2);
                                        cout.fill('0');
                                        cout << ((IV[i]>>(b*8))&0xFF);
                                }
                        }
                        cout.width(oldwidth);
                        cout.fill(oldfill);
                        cout << dec << endl;
                }

                if (verbose)
                        cout << endl;

                uint32 msg1block0[16];
                uint32 msg1block1[16];
                uint32 msg2block0[16];
                uint32 msg2block1[16];
                find_collision(IV, msg1block0, msg1block1, msg2block0, msg2block1, true);

                save_block(ofs1, msg1block0);
                save_block(ofs1, msg1block1);
                save_block(ofs2, msg2block0);
                save_block(ofs2, msg2block1);
                if (verbose)
                        cout << "Running time: " << runtime.elapsed() << " s" << endl;
                return 0;
        } catch (exception& e)
        {
                cerr << "\nException caught:\n" << e.what() << endl;
                return 1;
        } catch (...)
        {
                cerr << "\nUnknown exception caught!" << endl;
                return 1;
        }
}

void test_md5iv(bool single)
{
        uint32 IV[4] = { MD5IV[0], MD5IV[1], MD5IV[2], MD5IV[3] };
        uint32 msg1block0[16];
        uint32 msg1block1[16];
        uint32 msg2block0[16];
        uint32 msg2block1[16];

        boost::timer runtime;
        while (true)
        {
                runtime.restart();
                find_collision(IV, msg1block0, msg1block1, msg2block0, msg2block1);
                double time = runtime.elapsed();
                cout << endl << "Running time: " << time << " s" << endl;
                ofstream of_timings("timings_md5iv.txt", ios::app);
                of_timings << time << endl;
                if (single) return;
        }
}

void test_rndiv(bool single)
{
        uint32 IV[4];
        uint32 msg1block0[16];
        uint32 msg1block1[16];
        uint32 msg2block0[16];
        uint32 msg2block1[16];

        boost::timer runtime;
        while (true)
        {
                runtime.restart();
                IV[0] = xrng64(); IV[1] = xrng64(); IV[2] = xrng64(); IV[3] = xrng64();
                find_collision(IV, msg1block0, msg1block1, msg2block0, msg2block1);
                double time = runtime.elapsed();
                cout << endl << "Running time: " << time << " s" << endl;
                ofstream of_timings("timings_rndiv.txt", ios::app);
                of_timings << time << endl;
                if (single) return;
        }
}

void test_reciv(bool single)
{
        uint32 IV[4];
        uint32 msg1block0[16];
        uint32 msg1block1[16];
        uint32 msg2block0[16];
        uint32 msg2block1[16];

        boost::timer runtime;
        while (true)
        {
                runtime.restart();
                IV[0] = xrng64(); IV[1] = xrng64(); IV[2] = xrng64(); IV[3] = xrng64();
                IV[2] |= 1<<25; IV[2] ^= ((IV[2] & (1<<24))<<1);
                IV[3] &= ~(1<<25); IV[3] ^= ((IV[3] & (1<<24))<<1);

                find_collision(IV, msg1block0, msg1block1, msg2block0, msg2block1);
                double time = runtime.elapsed();
                cout << endl << "Running time: " << time << " s" << endl;
                ofstream of_timings("timings_reciv.txt", ios::app);
                of_timings << time << endl;
                if (single) return;
        }
}

void test_all()
{
        while (true)
        {
                test_md5iv(true);
                test_reciv(true);
                test_rndiv(true);
        }
}

以上是部分代码，，，希望有相同研究方向的，多多交流。。。

求邀请码一枚，不胜感激！本人邮箱：931948882@qq.com

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法