# Boston Key Party 2017 – Sponge

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.

$\begin{array}{lcll} \textbf{State}_{i} & & \textbf{State}_{i+1} & \textbf{Input}\\ \texttt{00000000000000000000~000000000000}&\rightarrow&\texttt{66e94bd4ef8a2c3b884c~fa59ca342b2e}&\texttt{00000000000000000000}\\ \texttt{e6e94bd4ef8a2c3b884d~fa59ca342b2e} &\rightarrow& \texttt{cccb674e90ee226bea81~557bff1e7123} & \texttt{80000000000000000001} \end{array}$

If we can bring it back to the same state, we have a local collision. Here is an example of such a collision:

$\begin{array}{lcll} \textbf{State}_{i} & & \textbf{State}_{i+1} & \textbf{Input}\\ \texttt{00000000000000000000~000000000000}&\rightarrow&\texttt{66e94bd4ef8a2c3b884c~fa59ca342b2e}&\texttt{00000000000000000000}\\ \texttt{210e7f3dc8b624d41038 fa59ca342b2e} &\rightarrow& \texttt{26e1e20ccd3ce8e975a6 33c3d2824408} &\texttt{47e734e9273c08ef9874}\\ \texttt{0f809b9375310b0656cf 33c3d2824408}& & \texttt{d979b8a852674734c855 000000000000} & \texttt{2961799fb80de3ef2369}\\ \texttt{00000000000000000000 000000000000} & \rightarrow &\texttt{66e94bd4ef8a2c3b884c~fa59ca342b2e}&\texttt{d979b8a852674734c855}\\ \texttt{e6e94bd4ef8a2c3b884d~fa59ca342b2e} &\rightarrow& \texttt{cccb674e90ee226bea81~557bff1e7123} & \texttt{80000000000000000001} \end{array}$

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 $\textsf{Enc}(\textsf{Enc}(x \oplus a \| \texttt{0x00}^6) \oplus b \| \texttt{0x00}^6) \oplus c \| \texttt{0x00}^6 = y$. Let us reorder the function as follows:

$\textsf{Enc}(x \oplus a \| \texttt{0x00}^6) = \textsf{Dec}(y \oplus c \| \texttt{0x00}^6) \oplus b \| \texttt{0x00}^6$

If we force the trailing six bytes to null and then decrypt that block for different values on $y \oplus c \| \texttt{0x00}^6$, since we can control $c$. Equivalently, we can encrypt for different values of $x \oplus a \| \texttt{0x00}^6$, where the trailing six bits will be the trailing six bits of $\textsf{Enc}(\texttt{0x00}^{16})$.

Utilizing the birthday paradox, we can find a collision in the six bytes in $\sim \sqrt{256^6}$ time and space. This is done by putting about $2^{24}$ 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[0])
B = AES.new('\x00'*16).decrypt(local_collision_blocks[1])
local_collision = '\x00'*10 + xorstring(local_collision_blocks[0][:10], AES.new('\x00'*16).encrypt('\x00'*16)) + xorstring(A,B)[:10] + xorstring(local_collision_blocks[1][:10], GIVEN[:10])