15
\$\begingroup\$

MD5 checksums are relatively easy to crack. For this challenge you will create two separate programs, the first one writing Hello, World! and the second one writing Goodbye Cruel World! but with the source code having identical MD5 hashes.

  • The source code of both programs must not be identical.
  • The programs can use the same or different languages.
  • Trailing newlines are allowed, but the programs cannot write anything else to the output.
  • Shortest combined byte code wins.

The following TIO can be used to calculate the MD5 hashes for your programs.

\$\endgroup\$
3
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – jdt
    Commented Oct 16, 2022 at 13:52
  • 2
    \$\begingroup\$ Relevant example code for a similar problem: mscs.dal.ca/~selinger/md5collision \$\endgroup\$
    – mousetail
    Commented Oct 16, 2022 at 16:54
  • \$\begingroup\$ Let's write same binary that read different in different encoding \$\endgroup\$
    – l4m2
    Commented Dec 14, 2022 at 17:28

1 Answer 1

18
\$\begingroup\$

Python, 360 + 360 = 720 bytes 206 + 206 = 412 bytes 201 + 201 = 402

Hi, my two cents. This answer is inspired by this blog by Nat McHugh.

A short introduction to explain the idea behind the code.

MD5 hash collision and exploitation.

MD5 works with blocks of 64 bytes. If two blocks (with a length multiple of 64 bytes) A & B have the same hash, then appending the same contents C to both will keep the same hash.

hash(A) = hash(B) -> hash(A + C) = hash(B + C)

Exploiting this simple principle is possible to get two different files with the same MD5.

There are several attacks to generate MD5 collision, here we are interested in attacks for files having identical prefixes.

These are the steps of the attack:

  1. Define an arbitrary prefix with any content and length.
  2. Pad the prefix to the next 64-byte block.
  3. Compute collision blocks based on the prefix. The differences between the blocks are predetermined by the attack.
  4. Concatenate the prefix with each of the two blocks to get two different sequences: the hash is the same for the two sequences despite the differences.
  5. Add any arbitrary identical suffix to the sequences: the hash will remain the same for the two sequences.

The final structure of the two files will be the following:

GOOD FILE EVIL FILE
Prefix
[n * 64 bytes]
= Prefix
[n * 64 bytes]
Collision A
[128 bytes]
Collision B
[128 bytes]
Suffix
[any length]
= Suffix
[any length]

In the end, the files are almost identical, except for a few bits.

For the exploitation, we use an approach called data exploit: run code that looks for differences and displays one content or the other (typically trivial since differences are known in advance).

In particular, we use FastColl to generate the two collision blocks, given the prefix. Each collision block needs two MDS blocks (so it is 128 bytes long). This is the difference mask for the two collision blocks:

................
...X............
.............XX.
...........X....
................
...X............
.............XX.
...........X....

Looking at the difference mask, the 20th byte is the first byte that shows a difference (each . represents one byte). So, we can use this information to trigger a different behavior in the two files. Knowing the expected value of the 20th byte in the collision block, we can create an if based on this value.

Look at the following example showing two collision blocks (courtesy of https://github.com/corkami/collisions):

00:  37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26  7u┴±─ºZτ£α▐z[►Ç&
10:  02 AB D9 39-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0  ☻½┘9╔l_☻↕┬⌂┌═♪ú░
20:  8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 C3 99 1D  îφ·≤ßú²┤∩○τ√▒├Ö↔
30:  CD 91 C8 45-E6 6E FD 3D-C7 BB 61 52-3E F4 E0 38  ═æ╚Eµn²=╟╗aR>⌠α8  \
40:  49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20  I◄àiδ╠↨£ôO@δ3☻¡ 
50:  A4 09 2D FB-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E  ñ○-√§· ↔╤█↨═▌)Y▲    ................
60:  39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE 42 4F 46  9ë₧÷yFƒµïà┼∩▐BOF    ...X............
70:  C2 78 75 9D-8B 65 F4 50-EA 21 C5 59-18 62 FF 7B  ┬xu¥ïe⌠PΩ!┼Y↑b {    .............XX.
                                                                          ...........X....
                                                                          ................
00:  37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26  7u┴±─ºZτ£α▐z[►Ç&    ...X............
10:  02 AB D9 B9-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0  ☻½┘╣╔l_☻↕┬⌂┌═♪ú░    .............XX.
20:  8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 43 9A 1D  îφ·≤ßú²┤∩○τ√▒CÜ↔    ...........X....
30:  CD 91 C8 45-E6 6E FD 3D-C7 BB 61 D2-3E F4 E0 38  ═æ╚Eµn²=╟╗a╥>⌠α8
40:  49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20  I◄àiδ╠↨£ôO@δ3☻¡   /
50:  A4 09 2D 7B-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E  ñ○-{§· ↔╤█↨═▌)Y▲
60:  39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE C2 4E 46  9ë₧÷yFƒµïà┼∩▐┬NF
70:  C2 78 75 9D-8B 65 F4 50-EA 21 C5 D9-18 62 FF 7B  ┬xu¥ïe⌠PΩ!┼┘↑b {

In the first collision block, the value of the 20th byte is 0x39, while in the second 0xB9. We can exploit this difference by writing something like this:

if collision_block[20] = 0x39 then:
    do a good thing
else:
    do a bad thing

This is the idea used in the code to create the two source files with the same MD5 hash, but different behavior.

References:

[1] https://natmchugh.blogspot.com/2014/10/how-i-made-two-php-files-with-same-md5.html?m=1

[2] https://github.com/corkami/collisions

Files generated for this answer

These are two files with the same md5 hash:

MD5 (good.py) = 120909f9a5185bcbd7ef716d6c1f3787
MD5 (evil.py) = 120909f9a5185bcbd7ef716d6c1f3787

good.py

#coding: L1
# coding: L1
print('%s World!'%('Hello','Goodbye Cruel')['Z'>"""úzžù
WjmEò÷Sïå#nî˜ê-Z<fi #ûòûûîðŒ    ‡k×T,­qK=®=ˆÄ†ä7vÒ2¯áWü§›(0ã¢dÞåÅA4æø+tÐWOLeÁí-Åéòå«·Ùµë0š4zgqß?Í…fÿ¦¼Ôh¨îx"""[19]])

evil.py

# coding: L1
print('%s World!'%('Hello','Goodbye Cruel')['Z'>"""úzžù
WjmEò÷Sïå#nî˜ê-Z<fi #ûòûûîðŒ    ‡k×T,­qK=®=ˆÄ†ä7öÒ2¯áWü§›(0ã¢dÞåÅA4Žæø+tÐWOLeÁí-Åéòå«·Ùµë0š´ygqß?Í…fÿ¦¼Ôè¨îx"""[19]])

If you run good.py, you get:

>> python good.py 
Hello World!

while for evil.py:

>> python evil.py 
Goodbye Cruel World!

The length of the two files is the same, i.e., 201 bytes.

Note that, due to the presence of non-ASCII characters in the Python code, I cannot guarantee that a copy and paste of the above text can reproduce the results. So, here is the C code to create the two files:

#include <stdio.h>

// The number of bytes for the prefix and for the collision block
// must be 64 and 128 respectively to generate an MD5 collision
#define N_PREFIX_BYTES 64
#define N_COLLISION_BYTES 128

#define BYTE_TYPE unsigned char

void write_binary_file(
    char *filepath, 
    BYTE_TYPE *prefix,
    BYTE_TYPE *collision,
    BYTE_TYPE *suffix,
    size_t prefix_nbytes, size_t collision_nbytes, size_t suffix_nbytes
){
    FILE *ptr;
     
    ptr = fopen(filepath, "wb");
    fwrite(prefix, sizeof(BYTE_TYPE), prefix_nbytes, ptr);
    fwrite(collision, sizeof(BYTE_TYPE), collision_nbytes, ptr);
    fwrite(suffix, sizeof(BYTE_TYPE), suffix_nbytes, ptr);
    fclose (ptr);
}

int main(){
    size_t n_suffix_bytes;
    char *code_filepaths[2] = {"good.py", "evil.py"};
    unsigned long tot_len=0, curr_len=0;

    // Here the initial and final part of the output code;
    // mind that the prefix must have a length of 64 bytes.
    // The idea here is to take advantage of the slightly 
    // difference between the two collission blocks to generate
    // different outputs in the two programs.
    BYTE_TYPE source_code_prefix[N_PREFIX_BYTES] = "# coding: L1\nprint('%s World!'%('Hello','Goodbye Cruel')['Z'>\"\"\"";
    // As you can see, the output code is in Python language.
    //
    // The different output string is created choosing its initial part 
    // between the elements of a tuple two strings ('Hello','Goodbye Cruel').
    // In particular, the index is a condition on the first different character 
    // between the two collision blocks, i.e., the 20th.
    // If this characher is less than 'Z', the condition is True, 
    // (i.e. it is equivalent to 1), so the second element of the 
    // tuple is selected; otherwise the condition 
    // is False (0), so the first element of the tuple is selected
    // To recap, this is the ungolfed sketch of the code:
    //  is_evil = 'Z' > collision_block[19] 
    //  initial_part = ('Hello','Goodbye Cruel')[is_evil]
    //  print('%s World!'%initial_part)
    BYTE_TYPE source_code_suffix[9] = "\"\"\"[19]])";

    // You can put one this two binary blocks between source_code_prefix and source_code_suffix
    // and get the same MD5 hash, even if the two blocks are slightly different
    BYTE_TYPE collision_blocks[2][N_COLLISION_BYTES] = {
        {
            0xfa, 0x7a, 0x9e, 0x18, 0xf9, 0x0a, 0x57, 0x6a, 0x11, 0x6d, 0x45, 0xf2, 0xf7, 0x53, 0xef, 0xe5,
            0x23, 0x6e, 0xee, 0x8f, 0x98, 0xea, 0x2d, 0x15, 0x5a, 0x16, 0x3c, 0x66, 0x69, 0x20, 0x23, 0xfb,
            0xf2, 0xfb, 0xfb, 0xee, 0xf0, 0x8c, 0x09, 0x87, 0x6b, 0x02, 0xd7, 0x54, 0x18, 0x10, 0x2c, 0xad,
            0x71, 0x4b, 0x3d, 0xae, 0x3d, 0x88, 0xc4, 0x86, 0xe4, 0x19, 0x37, 0x76, 0xd2, 0x32, 0xaf, 0x15,
            0x1c, 0xe1, 0x0c, 0x57, 0xfc, 0xa7, 0x9b, 0x1b, 0x28, 0x30, 0xe3, 0xa2, 0x64, 0xde, 0xe5, 0xc5,
            0x41, 0x34, 0x1e, 0x0e, 0xe6, 0xf8, 0x18, 0x2b, 0x74, 0x0b, 0xd0, 0x57, 0x4f, 0x4c, 0x65, 0xc1,
            0xed, 0x2d, 0xc5, 0xe9, 0xf2, 0xe5, 0xab, 0xb7, 0xd9, 0xb5, 0xeb, 0x30, 0x9a, 0x34, 0x7a, 0x67,
            0x71, 0xdf, 0x3f, 0xcd, 0x85, 0x1e, 0x66, 0xff, 0xa6, 0xbc, 0xd4, 0x68, 0xa8, 0xee, 0x08, 0x78
        },
        {
            0xfa, 0x7a, 0x9e, 0x18, 0xf9, 0x0a, 0x57, 0x6a, 0x11, 0x6d, 0x45, 0xf2, 0xf7, 0x53, 0xef, 0xe5,
            0x23, 0x6e, 0xee, 0x0f, 0x98, 0xea, 0x2d, 0x15, 0x5a, 0x16, 0x3c, 0x66, 0x69, 0x20, 0x23, 0xfb,
            0xf2, 0xfb, 0xfb, 0xee, 0xf0, 0x8c, 0x09, 0x87, 0x6b, 0x02, 0xd7, 0x54, 0x18, 0x90, 0x2c, 0xad,
            0x71, 0x4b, 0x3d, 0xae, 0x3d, 0x88, 0xc4, 0x86, 0xe4, 0x19, 0x37, 0xf6, 0xd2, 0x32, 0xaf, 0x15,
            0x1c, 0xe1, 0x0c, 0x57, 0xfc, 0xa7, 0x9b, 0x1b, 0x28, 0x30, 0xe3, 0xa2, 0x64, 0xde, 0xe5, 0xc5,
            0x41, 0x34, 0x1e, 0x8e, 0xe6, 0xf8, 0x18, 0x2b, 0x74, 0x0b, 0xd0, 0x57, 0x4f, 0x4c, 0x65, 0xc1,
            0xed, 0x2d, 0xc5, 0xe9, 0xf2, 0xe5, 0xab, 0xb7, 0xd9, 0xb5, 0xeb, 0x30, 0x9a, 0xb4, 0x79, 0x67,
            0x71, 0xdf, 0x3f, 0xcd, 0x85, 0x1e, 0x66, 0xff, 0xa6, 0xbc, 0xd4, 0xe8, 0xa8, 0xee, 0x08, 0x78
        }
    };

    // The number of bytes in the suffix can vary, depending on 
    // the code needed to make the source file meaningful
    n_suffix_bytes=sizeof(source_code_suffix) / sizeof(BYTE_TYPE);

    // Write good and evil files. The only thing different is the collision block
    tot_len=0;
    for(int i=0; i<2; ++i){
        write_binary_file(
            code_filepaths[i],
            source_code_prefix, collision_blocks[i], source_code_suffix, 
            N_PREFIX_BYTES, N_COLLISION_BYTES, n_suffix_bytes
        );

        curr_len = N_PREFIX_BYTES + N_COLLISION_BYTES + n_suffix_bytes;
        tot_len += curr_len; 

        printf("\nBytes in %s: %lu", code_filepaths[i], curr_len);
    }
    printf("\nTotal length: %lu\n", tot_len);

    return(0);
}

You can download all the previous files from this Github repo.

Update 1 Thanks to xnor and Arnauld for the comment and suggestions to improve the answer.

Update 2 Refactor the code and improve of some bits

\$\endgroup\$
5
  • \$\begingroup\$ I think you can shorten this by cutting out repeating the long string a second time by replacing the == check with checking the character value at a position where the two strings differ. \$\endgroup\$
    – xnor
    Commented Oct 18, 2022 at 0:51
  • \$\begingroup\$ @xnor Would it be even shorter by using either < or >? \$\endgroup\$
    – Arnauld
    Commented Oct 18, 2022 at 10:33
  • \$\begingroup\$ @Arnauld Good call, that would be shorter. \$\endgroup\$
    – xnor
    Commented Oct 18, 2022 at 11:10
  • 1
    \$\begingroup\$ Interestingly, since the payload needs to start on the 64th byte, the important thing to shorten (other than the payload size) is bytes after to payload. The Python code still seems to work without # coding: latin-1 -- though the byte values are different than with the default encoding, they still differ between the good/bad string. Something of this form would be great, if you can guess the ? character for the prefix. \$\endgroup\$
    – xnor
    Commented Oct 18, 2022 at 11:19
  • \$\begingroup\$ Hi, thanks for the suggestions. I've improved the code, based on your ideas. I had to keep the encoding because the Python interpreter needed it to run the code correctly; anyway I shortened it. Moreover, I removed the comparison between the two 128-byte blocks, in favor of a check based on the value of the first different character between the two blocks. As a final improvement, I refactored the creation of the string to be printed, so that its whole template is in the first 64 bytes. \$\endgroup\$
    – PieCot
    Commented Oct 18, 2022 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.