In this challenge, we are given a hash function, which essentially splits the input into chunks of ten bytes. It then appends six bytes of null data to it and XORs with the current state. The state is encrypted with the all-zero key and updated. This process is repeated until all blocks have been exhausted.
A simple case is to consider what happens when we hash ten bytes of null data.
If we can bring it back to the same state, we have a local collision. Here is an example of such a collision:
So, how did we create the above collision? Well, actually, it is not too complicated… first, note that we cannot control the last six bytes. Recall that . Let us reorder the function as follows:
If we force the trailing six bytes to null and then decrypt that block for different values on , since we can control . Equivalently, we can encrypt for different values of , where the trailing six bits will be the trailing six bits of .
Utilizing the birthday paradox, we can find a collision in the six bytes in time and space. This is done by putting about values of the encryption (or decryption) in a table. Then, we generate the decryptions (or encryptions, respectively) and look in the table.
In Python, it could look something like:
trailing_bytes_first = AES.new('\x00'*16).encrypt('\x00'*16)[-6:] for i in range(0, 2**24): plaintext = os.urandom(10) + trailing_bytes_first data[AES.new('\x00'*16).encrypt(plaintext)[-6:]] = plaintext for i in range(0, 2**24): ciphertext = os.urandom(10) + '\x00\x00\x00\x00\x00\x00' if AES.new('\x00'*16).decrypt(ciphertext)[-6:] in data: print [data[AES.new('\x00'*16).decrypt(ciphertext)[-6:]]], [ciphertext]
Two such values are
local_collision_blocks = ['!\x0e\x7f=\xc8\xb6$\xd4\x108\xfaY\xca4+.', '\xd9y\xb8\xa8RgG4\xc8U\x00\x00\x00\x00\x00\x00']
Finally, we generate a collision as follows
GIVEN = 'I love using sponges for crypto' A = AES.new('\x00'*16).encrypt(local_collision_blocks) B = AES.new('\x00'*16).decrypt(local_collision_blocks) local_collision = '\x00'*10 + xorstring(local_collision_blocks[:10], AES.new('\x00'*16).encrypt('\x00'*16)) + xorstring(A,B)[:10] + xorstring(local_collision_blocks[:10], GIVEN[:10])