Hashing
One-way functions that generate a unique hash of some data
Last updated
One-way functions that generate a unique hash of some data
Last updated
Collisions in hashing functions mean multiple different inputs result in the same hash. In a perfect hash function, this should not be feasible. There are a few types of collisions with varying exploitability:
Identical Prefix: The prefix of two files are the same, then there are a few collision blocks with different data
Chosen Prefix: The prefix of the two files can be anything you want, and may differ. Then after there are some collision blocks, and finally it ends in an identical suffix
For lots of details on how these attacks work and how to exploit them see the following GitHub repository:
When looking at collisions MD5 is very broken. Nowadays it's trivial to create your own Identical Prefix attack within minutes. We can use a tool like HashClash with very efficient code to do the work for us:
With MD5 you can create any identical blocks consisting of 64 bytes as the prefix, then two collision blocks that differ, and finally any identical suffix.
An example of two files you could create with this is the following:
To create such a file you can use the poc_no.sh script from the HashClash repository. It takes one argument which is the prefix for the collision. It can contain:
Any exact multiple of 64 bytes, as the identical prefix
A multiple of 4 bytes, with a maximum of 12 bytes in total. These will be the starting bytes for the collision blocks
In the example above I used a file containing "A"*64 + "B"*64 + "C"*64 + "test" as the prefix. This will make sure the identical prefix starts with AAA...CCC and the collision blocks start with "test".
Then after this, I added "D"*64 + "E"*64 + "F"*64 to the generated collisions because any data after will only change the hash, but the collision will remain.
The chosen prefix attack is a lot more powerful but also takes quite a bit longer to compute. It takes about one day to do one collision between files, depending on your computer.
With such a collision you could make two completely different files have the same md5 sum, only having a few collision blocks at the end, and allowing an identical suffix.
To create a collision like this, you could use the cpc.sh script from HashClash. It takes two different prefix files as input and creates two files with those prefixes and some collisions block appended. Then you can manually add an identical suffix to it later because the collision will remain.
I've let a VPS with 24 cores run for 1.5 days to find a chosen-prefix collision like this. I chose one prefix of a simple 256x256 png image, and the other prefix to be an XSS and PHP shell payload. So I could leave the terminal and look back at it later I used the screen command to start a session, and used screen -r every once in a while to check back into it. Another way would be to redirect the output to some log file to check.
The cpc.sh script will then find a collision by appending collision blocks to both prefixes, which is why I added a <!-- comment tag to the shell, and I made sure to add the IEND and CRC to the PNG image to signify the end of the PNG. Some tools like pngcheck complain about data after the IEND, but all other things I've tried parse the PNG completely fine. Here are the original prefixes:
Then after the collision, there were 9 blocks of 64 bytes added. You can see the raw collision files below:
In March 2024, Marc Stevens shared on Twitter a proof of concept for two alphanumeric strings that hash to the same value. Previously, this was only ever done with random bytes as shown in the paragraphs above.
The textcoll.sh script allows you to generate such collisions yourself. There is a surprising amount of control possible with the prefix and around the +4 byte in the 21st place. To configure it, the global variables can be changed, and an optional prefix file is given as the first argument.
ALPHABET will choose what random characters an attempt may contain.
FIRSTBLOCKBYTES will force certain byte positions in the first collision block (64 bytes) of the collision. Byte 21 here will become the collision difference and gets +4 added in the other string. While it does not matter for the value before, the value after +4 must be within the ALPHABET.
SECONDBLOCKBYTES will force certain byte positions in the second collision block. These will be identical for both strings, but can otherwise contain random characters from the ALPHABET. It can be commented out to be faster.
argv[1] will optionally be a file used as the prefix blocks when searching for a collision. This does not impact performance. Make sure its length is aligned to 64 bytes.
The code below can be used to quickly generate correct ...BLOCKBYTES variables at a certain position. Keep in mind that you can add multiple characters to a single byte to make it more flexible and faster to compute. This can be useful if you don't care about casing, for example.
In the GoogleCTF 2024 - pycalc challenge, the player was required to make two Python payloads of the same MD5 hash where one is benign and the other is malicious. There was a strict sandbox that only allowed simple calculation or string concatenation. By changing a " to & using the +4 on the 21st byte, it was possible to end a string in one payload, while continuing it in the other. This separates the code flow and allows one payload to be a simple string, while the other executes any code.
The exploit idea looks like this:
This can be configured in hashclash with the following variables:
After a few hours, you should get lucky and find a collision like the following:
More blocks can now be added to these two strings while maintaining the same hash:
Google Research has found an identical prefix collision in the SHA1 hashing algorithm, and so far is the only one to do so. It still takes 110 years of single-GPU computations to compute a collision yourself, so the only practical way right now is to use the prefix from Google.
SHA1 works by splitting the input into blocks of 512 bits (64 bytes). For every block, it does its operations, and if the two blocks are the same, the two outputs of that block are the same. It keeps going taking the previous block and continuing on it with the next block.
A collision in SHA1 means that there were 2 sets of 5 blocks (320 bytes) found, that when SHA1 hashed give the same hash, while actually being different.
Because of the way SHA1 works, we can start off by using the first 5 blocks from SHAttered, and then if the rest of the files have identical content, their hashes will be the same.
To get different behavior from the two files, a common idea is to check if a certain byte that is different in the collision blocks. This way both files contain both pieces of code, but only one is chosen in both.
In HTML, this can be done by looking at the innerHTML with charCodeAt(102) in JavaScript. For a simple example see:
Hashing algorithms are sometimes used for verifying messages. This can be done by appending a secret "salt" value in front of the data that only the server knows. If the server then generates a hash of this value, it is the only party that is able to do so. If you don't have the salt value you cannot generate a hash that starts with that salt.
But the length-extension attack makes this semi-possible. It allows you to add data to an existing hash, with the catch that there will be some data prepended to your addition.
Hashing functions like SHA256 or SHA512 might sound secure, but without proper precautions to this attack, they may be vulnerable to it. The following hashing algorithms are all vulnerable to this attack:
MD4
MD5
RIPEMD-160
SHA-0
SHA-1
SHA-256
SHA-512
WHIRLPOOL
To see an example of this attack look at the script below:
I also made a writeup of a challenge that uses this attack to perform SQL Injection:
