# sponge (crypto, 200)
> I've written a hash function. Come up with a string that collides with "I love> using sponges for crypto".
The hash function we were given in this task, was simply xoring the 16-byte state with 10-byte input block, and thenencrypting with AES. If the blocks were 16-byte, the collision would be trivial to find, as we know the AES key:```result = state2 = AES(block1 xor AES(block0 xor state0)) = AES(block1 xor AES(block0))AESd(result) = block1 xor AES(block0)block1 = AESd(result) xor AES(block0)```So, we would be able to choose any `block0` other than original, and xor it with AES-decrypted final state to get neededblock1 for collision.
Unfortunately, the blocks were 10-byte long, which meant we did not control the top 6 bytes supplied to the AES.While the attack above would still work in some cases, we would have to calculate approximately `2**48` AES en- or decryptions.This is not unreasonable, but we would probably run out of time during the CTF anyway. So, we wrote the stateof the hash after three blocks: (`a`, `b` and `c` are first three blocks, `D` is the final state)```AES(AES(a) xor b) xor c = DAES(AES(a) xor b) =       D xor c    AES(a) xor b  = AESd( D xor c )               b  = AESd( D xor c ) xor AES(a)```So the middle block is a xor of two pseudorandom values. We control most of `a` and `c`, so we can generate a lot of valuesof `AESd(D xor c)` and `AES(a)`. If they somehow end up with the same last 6 bytes, their xor with have 6 zeroes at theend, so we will find colliding `b`.
Naive random generation of `c` and `a` would still take too long (no speed improvement in fact), but we can use *meet in the middle* technique. We precalculate `2**24` values of `AESd(D xor c)` and remember them in an efficientdata structure, such as hashmap, and then proceed to randomly genrating `AES(a)`, checking for each value (in constant time!)if there is any corresponding element in the map that ends with the same 6 bytes. This takes reasonable amount of time(although implemented in Python, only around a minute or so). Finally, we paste together `a`, `b`, `c` and `'o'` (the lastcharacter of the original text) to get a final collision to submit.