Breaking MD5
Deep dive into MD5 Collisions
When downloading a file from the internet it is not uncommon to see an "MD9 hash" next to it. That long string of characters is like a digital fingerprint, meant to guarantee that the file you downloaded is identical to the original. But what if a completely different file, one safe, one malicious, could have the very same fingerprint?
This concept is known as a Hash Collision which has led to the downfall of the most common hashing algorithm used online MD5. This is a report on the Seed Labs MD5 Collision Attack Lab
MD5
For the MD5 algorithm, this "fingerprint" is always 128 bits long (represented as 32 hexadecimal characters). A good hash function should have a few key properties:
- It's fast to compute.
- It's impossible to go from the hash back to the original input.
- Even a tiny change in the input should produce a wildly different hash.
- It should be practically impossible for two different inputs to produce the same hash.
That last point is where MD5 fails spectacularly.
How MD5 is Weak to Collisions
The weakness is rooted in the algorithm's design, specifically its Merkle–Damgård construction. Here’s a simplified explanation:
- Processing in Blocks: MD5 doesn't look at a file all at once. It breaks the data into fixed-size 512-bit blocks.
- Iterative Chaining: It processes the first block to produce an intermediate hash value. This value is then combined with the second block to produce a new intermediate hash. This process repeats, chaining along until the final block is processed and the final hash is produced.
- Mathematical Shortcuts: Cryptographers discovered that the mathematical operations inside MD5 have weaknesses. These weaknesses allow an attacker to make specific, calculated changes to two different data blocks. While the blocks themselves are different, these changes effectively "cancel each other out" during the hashing process, leading to the exact same intermediate hash value.
(Kasgar et al., 2013)
Once an attacker finds two such "colliding blocks," they can place them inside two otherwise different files. Because the hash state is identical after processing these blocks, they can then append the same suffix to both, and the final MD5 hashes will be identical.
Task 1: Creating Two Different Files with the Same MD5 Hash
The first example of md5 collisions uses the md5collgen program to create two different files with the same hash. The program takes in an input file and appends a 128 byte suffix that seemingly makes each file have the same hash value.
The md5collgen tool generates collisions by generating two separate blocks. These two separate blocks are then prefixed by the same piece of data and the difference of these two hashes is calculated. The second block is then created using this difference calculated to generate a collision which allows for two separate files to contain the same hash.
Task 2: MD5 Suffix Behavior
Hash functions produce a fixed length output for any sized input. This behavior means mechanisms must be in place in the algorithm to ensure shorter messages are extended and longer messages are reduced. The MD5 algorithm will pad the input with 0’s if the output is smaller than 128 bits and if it is larger use a compression function to ensure the resulting hash value is 128 bits. The compression function divides the input data and combines it with the previous hash value for the previous block of data. This property of building the hash iteratively based on the previous data encountered leads to the next behavior of the MD5 algorithm explored. By appending a piece of data to two files with the same hash value we can observe this behavior.
Task 3: Generating Two Executable Files with the Same MD5 Hash
By using the previous MD5 behavior of the intermediate hash value one can create a collision using md5collgen and a chosen prefix. Such chosen prefix collision is described as
“A method to construct MD5 collisions starting from two arbitrary IHVs. Given this method one can take any two chosen message prefixes and construct bitstrings that, when appended to the prefixes, turn them into two messages that collide under MD5."(Stevens et al., 2012)
This approach allows for complex data manipulations. In this example a c program which prints out a large array of values, that must be larger than the 128 bytes needed for the collision generation, is hijacked by generating two different collision values when is then placed back into the original file leaving two different files with the same hash value. By taking the property in which any two files with the same hash can be given the same suffix and each resulting file will also have identical hash values one can split the hash value where the array starts in the c code.
In this example we split the output binary at the byte location where the array lives into our shared prefix which the md5collgen tool will then generate two separate collisions based on this input prefix. These two resulting files will have different data in the area where the array is supposed to reside as well as the same MD5 hash value. Then by appending the rest of the original binary, minus the 128 bytes generated by the collision, one can create two executables each with the same hash value that output two separate pieces of data.
Task 4: Making the Two Programs Behave Differently
This behavior of the MD5 algorithm can be manipulated even further by making another executable in which instead of different data being printed out different code paths can be executed. This is demonstrated in this example by the use of two separate arrays in which if the arrays are identical one branch executes, and another executes if they are different. These two separate arrays should end up in separate places in the generated executable.
Unlike in the previous example there is now an array of ‘Z’ characters instead of just ‘A’ characters. This allows for easy identification of which array is which. The process for manipulating this executable is similar to before, however, combines behavior from all the sections covered so far. Firstly the executable is split at the first array as in task 3, however, instead of appending the suffix of the original file we take advantage of the fact that two files appended with the same suffix will have the same hash value and manipulate the original suffix. Since the collision generation tool will essentially create two different arrays in the ‘A’ array space, by copying the generated data in the same place into the ‘Z’ space and appending this modified suffix to each file leaves one file in which the arrays are identical and one in which they differ. This demonstrates that it is possible to create two different executables with the same MD5 hash that have two completely different sets of behaviors.
References
Stevens, M., Lenstra, A. K., & Weger, B. D. (2012). _Chosen-prefix collisions for MD5 and applications. International Journal of Applied Cryptography, 2(4), 322. https://doi.org/10.1504/ijact.2012.048084_
Kasgar, A. K., Dhariwal, M. K., Tantubay, N., & Malviya, H. (2013).A review paper of message digest 5 (MD5). International Journal of Modern Engineering & Management Research, 1(4), 29–35.