It's not so difficult to produce two md5-collided exe files

[BlackWhite]

It's well known that for a given md5 hash, we have no way to
calculate its message. And for the same reason, for a given file,
we have no way to produce another file whose md5 hash equals
to the given one.
According to Wang Xiaoyun's theory, we can produce two
128-bit data blocks whose md5 hashes collide. So why don't
we exploit these 128-bit collisions to produce two md5-collided
exe files?
Here is my method. Let's assume the first exe file is exe1, and
the other is exe2, then these two files are composed as follows:
exe1 = if(condition) func1(); else func2(); + func1() + func2() + md5_1
exe2 = if(condition) func1(); else func2(); + func1() + func2() + md5_2
Here "if(condition) func1(); else func2(); + func1() + func2()" is the
compiled exe file corresponding to exe1 or exe2(actually their source codes
are the same), while md5_1 & md5_2 are overlays appended to the compiled
exe file. And, md5_1 and md5_2 are two 128-bit md5-collided data blocks
calculated by applying Wang's theory, and on producing these collided
blocks, we should not use MD5's default seed values(0x67452301,
0xEFCDAB89, 0x98BADCFE, 0x10325476), in stead, we should use
md5(compiled exe file) as md5's seed value where the final step called
md5_final() should be removed, so that the collision between
md5_1 and md5_2 can be enlarged and finally results in the collision between
exe1 and exe2.
The "condition" mentioned above is to check one bit of the overlay.
The attachment is a zip file containing the source code and 2 md5-collided exe files.

[BlackWhite]

Someone may think that this technique is useless.
Actually, it can be used to construct a fraudulent
digital signature. Because md5(exe1) == md5(exe2),
the digital signatures for exe1 & exe2 based on md5
are surely equivalent.

[Kerlingen]

I don't really get it. In order to produce two EXE with identical MD5, the two EXE must be identical before appending the overlay. This way it's not possible to produce one fraudulent EXE with the same MD5 as the original EXE.

You can only append different random data producing the same MD5, but this cannot influence the execution of the EXE since it doesn't rely on that information in it's unmodified state (the overlay is not present in the unmodified state).

[BlackWhite]

Originally Posted by Kerlingen

I don't really get it. In order to produce two EXE with identical MD5, the two EXE must be identical before appending the overlay. This way it's not possible to produce one fraudulent EXE with the same MD5 as the original EXE.

You can only append different random data producing the same MD5, but this cannot influence the execution of the EXE since it doesn't rely on that information in it's unmodified state (the overlay is not present in the unmodified state).

1. You may take func1() as exe1, and func2() as exe2

2. Though md5_1 & md5_2 seem random and their values rely on the
compiled exe file, yet there are rules in the variation according to Wang's
theory, and you can rely on the difference of one bit located at some position say byte 0x13 bit 7
between md5_1 & md5_2 to control the execution of func1() or func2().

[Kerlingen]

You only influence the execution from an external source. If the software you're trying does not rely on an external source (and why would it ever do that?), you have no way to change the execution path, since you cannot modify any code without blowing up the hash.

[Git]

B&W - I don't know Wangs stuff yet, but I did some collaborative work on this a few years ago, and it most definitely was not easy to match the CRC's of two exes, where one is an arbitrarily hacked version of the other. It is possible under some fairly simple circumstances but far from easy. We did produce a tool, but it's use was so limited it was not worth doing anything with it. My dim memory reminds me it involved adding a resource to the hacked exe and then altering specific bytes in that resource to match the good exes CRC. I'll see if I still have any source or notes.

Git

[BlackWhite]

Originally Posted by Kerlingen

You only influence the execution from an external source. If the software you're trying does not rely on an external source (and why would it ever do that?), you have no way to change the execution path, since you cannot modify any code without blowing up the hash.

Given two actual exe files say 1.exe & 2.exe, you can put them into the
combined exe's resources, and the combined exe can choose to run
1.exe or 2.exe according to the bit difference between md5_1 & md5_2,
thus the combined exe runs as if 1.exe or 2.exe is running.

[BlackWhite]

Originally Posted by Git

B&W - I don't know Wangs stuff yet, but I did some collaborative work on this a few years ago, and it most definitely was not easy to match the CRC's of two exes, where one is an arbitrarily hacked version of the other. It is possible under some fairly simple circumstances but far from easy. We did produce a tool, but it's use was so limited it was not worth doing anything with it. My dim memory reminds me it involved adding a resource to the hacked exe and then altering specific bytes in that resource to match the good exes CRC. I'll see if I still have any source or notes.

Git

Yes, to build two different EXE files with the same CRC or the same MD5
is nearly impossible.
My method is actually the combination of two exe files, the combined
exe choose to run the internal exe1 or exe2 according to the bit difference
between md5_1 & md5_2. So it's much easier.

[mcp]

Maybe I don't follow the discussion properly, but crafting two executables that have the same CRC is definitely not "nearly impossible". Same is of course not true for any true hashing function (like MD5)

[BlackWhite]

Originally Posted by mcp

Maybe I don't follow the discussion properly, but crafting two executables that have the same CRC is definitely not "nearly impossible". Same is of course not true for any true hashing function (like MD5)

If one exe file is specified by others, not crafted by yourself,
I think it's much hard to produce another exe file with the same
CRC or md5 hash.

If you can, would you please share your idea with us? Thanks.

[Kerlingen]

The point is that you don't modify any existing code to a specific value, you just add some random data without any meaning while leaving the original EXE completely untouched.

This is just a normal collision of random data which has been done many times by many people and has nothing to do with EXE file. (and which cannot be used to create "bad" EXE files with the same hash as existing "good" EXE files)

[BlackWhite]

Originally Posted by Kerlingen

The point is that you don't modify any existing code to a specific value, you just add some random data without any meaning while leaving the original EXE completely untouched.

This is just a normal collision of random data which has been done many times by many people and has nothing to do with EXE file. (and which cannot be used to create "bad" EXE files with the same hash as existing "good" EXE files)

Yes. No one can create a "bad" EXE with the same hash as the
existing "good" EXE if this "good" EXE is specified by others.

But if you craft that "good" EXE yourself, you can create a "bad" one,
and under some circumstances, you can defraud sb of a digital signature for
the "good" EXE and then apply to the "bad" one.

So my method is to some degrees concerned with EXE file. If you append
the collision data to a .doc file, it will not affect the contents of that
doc file, yet if you append the collision data to an exe, it can affect
the results of that exe.

[mcp]

This paper describes the process of reversing a CRC32 checksum

Here is some C# code that should do what you want:

public class Crc32
{
    public const uint poly = 0xedb88320;
    public const uint startxor = 0xffffffff;

    static uint[] table = null;
    static uint[] revtable = null;

    public void FixChecksum(byte[] bytes, int length, int fixpos, uint wantcrc)
    {
        if (fixpos + 4 > length) return;

        uint crc = startxor;
        for (int i = 0; i < fixpos; i++) {
            crc = (crc >> 8) ^ table[(crc ^ bytes[i]) & 0xff];
        }

        Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 4);

        crc = wantcrc ^ startxor;
        for (int i = length - 1; i >= fixpos; i--) {
            crc = (crc << 8) ^ revtable[crc >> (3 * 8)] ^ bytes[i];
        }

        Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 4);
    }

    public Crc32()
    {
        if (Crc32.table == null) {
            uint[] table = new uint[256];
            uint[] revtable = new uint[256];

            uint fwd, rev;
            for (int i = 0; i < table.Length; i++) {
                fwd = (uint)i;
                rev = (uint)(i) << (3 * 8);
                for (int j = 8; j > 0; j--) {
                    if ((fwd & 1) == 1) {
                        fwd = (uint)((fwd >> 1) ^ poly);
                    } else {
                        fwd >>= 1;
                    }

                    if ((rev & 0x80000000) != 0) {
                        rev = ((rev ^ poly) << 1) | 1;
                    } else {
                        rev <<= 1;
                    }
                }
                table[i] = fwd;
                revtable[i] = rev;
            }

            Crc32.table = table;
            Crc32.revtable = revtable;
        }
    }
}

[mcp]

did that answer your question?

[Shub-Nigurrath]

Essential literature for MD5 and other collisions is quite simple

First episode: Instantaneous generation of colliding MD5
rodevitoyem: eprint.iacr.org/2006/104.pdf
Poter omgpet: eprint.iacr.org/2006/105.pdf
The used method is called "bit tunneling“
*nix source: web.mit.edu/AFS/sipb/project/fastcoll/
win32 source: www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
win32 binary: www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Real-time generation of different files with the same MD5
Quite useless still because the files are fuzzy bloat of bits.

Second episode: Also other hash algorithms are colliding (2005)
How to Break MD5 and Other Hash Functions(Xiaoyun Wang and Hongbo Yu)
http://www.iacr.org/cryptodb/archive/2005/EUROCRYPT/2868/2868.pdf
Colliding X.509 Certificates (Arjen Lenstra, Xiaoyun Wang and Benne de Weger)
www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf


Third Episode:different exe with the same MD5, CRC32, cksum16 e cksum32 (2005/2006)
EXEs with the same CRC32, and also 8 different files with the same MD5.
These are real exe with different functions
hexale.blogspot.com/2005/12/taking-advantage-of-md5-for-real.html
final url seems to not be anymore available anyway.. there were two interesting PoC launchers also provided

Fourth episode: the list of colliding things gets longer .. see attach