I love using sponges for crypto
Who doesn’t, right?
This past weekend was the Boston Key Party (BKP) CTF which was a fun and challenging event. The challenge I spent the most time working on was the Crypto 200 point challenge titled “Sponge”. The challenge was to find a collision with the known value “I love using sponges for crypto” using a custom hashing algorithm implemented in Python. The original challenge code provided is available here. The idea was to identify a value that could be passed to the webserver as the resource which would cause it to display the flag. The value was encoded using hex so there were no character limitations.
While looking through the hashing algorithm, the first thing I noticed was that the input value was processed in 10-byte chunks. These chunks were then fed to the “ingest” function which update the internal 16-byte state. This particular function was the primary focus of the remainder of the solution. The initial state used by the algorithm was 16 NULL bytes. Each call to ingest would append 6 NULL bytes to the end of the 10 byte input, and XOR the NULL padded input with the current state value. The result of this operation was then used as the input to the AES algorithm which was also keyed with 16 NULL bytes. As configured in the challenge, the AES algorithm did not use any kind of state. Thus any 16 byte value would always be encrypted to the same ciphertext value.
One of the first steps to solve this challenge was to isolate the code responsible for the hashing operations. Once it was isolated and easily callable as a command line script, I added debugging messages in key locations to print out the value of the state after each call to ingest. The following is the output of this debug version of the code showing the value of the state each time it is updated:
python sponges_debug.py "49206c6f766520757369\ 6e672073706f6e676573 20666f72206372797074 6f" ingest state: d940564a6f9b46249a94cfe6c3d582c6 ingest state: ebc3be61bc5708451fbcafcfecd21a8d ingest state: 80c3cd0580d0491c117f7740560a1d64 final block: 6f ingest state: 11153c85d1b549e58b1b6fd6609e5464 ingest state: 40eeb0fd7e34d53a48ba395445452f3e ingest state: 956e116d90d5ae3df8ae2688417445f1 result: 11153c85d1b549e58b1b40eeb0fd7e34d53a48ba
Determining the Approach
What I ended up doing to find a collision was setting the value of the state to one of the “known good” values prior to the final ingest taking place. With the state set to a known value through some prepended data, the remainder of the initial data corresponding to the state at which I was able to reproduce could be used to obtain the same final value. Because the first 10 bytes are XORed with the unmodified input, setting these bytes is no issue. The final 6 bytes of the input is however the trick since those are XORed with the 6 bytes of the previous state.
Setting the State
Ideally we could insert values A and B into the AES algorithm and obtain value Z such that the following constraints are satisfied:
- The last 6 bytes of value A are NULL bytes because it is the initial input
- The last 6 bytes of value AES_Enctype(A) are the last 6 bytes of AES_Decrypt(Z)
- The XOR(B[:10], AES(A)[:10]) == Z[:10]
To set the state to a known value this way would take at least 3 rounds. The goal is to have full control over all 16 bytes of the value passed to the AES cipher. To accomplish this I needed a value ending in 6 NULL bytes that when encrypted would result in a value whose last 6 bytes could be prepended and encrypted to end with 000000000000, cfe6c3d582c6, afcfecd21a8d as corresponds to the last 6 bytes of the output from the above debug states. Any of these values would let me control the first 10 bytes to have full control over the next input value. Note that the last state of 7740560a1d64 is not listed because another iteration of ingest could not be used to obtain control of the first 16 bytes.
I opted to use a Jupyter Notebook to compute some values that would satisfy these constraints. I started by creating a pool of 750,000 targets by prepending 10 random bytes to each of the target states and decrypting them, yielding possible interim-state values to reach them. With a pool of 2.25 million possible input values, I started bruteforcing the 10 byte character space to find a value that ended in 6 NULL bytes that would reach one of those in the pool. On my (admittedly pretty beefy) laptop, the pool generation took seconds and finding a matched input value took closer to 40 minutes. At this point I could calculate input values totaling in 30 bytes that would fully set the state to a known value.
Calculations Complete
With the completion of the calculations, I found the initial value of 0000000000001db5785d that when passed to ingest as the first chunk would set the state to 0899e8f5e397b96cba6247249bfc6d22. This matched one of the 2.25 million potential interim-states, specifically b52da0d8f7d6111006e247249bfc6d22 which when encrypted equals 5236011727a6c8320daccfe6c3d582c6. At this point the last 6 bytes match one of the target states. Because I have full control to set the first 10 bytes, I can now have all 16 set to the input necessary to set the state to the following known value.
Using this method, after 3 carefully crafted input chunks of 10 bytes each, the state is finally set to ebc3be61bc5708451fbcafcfecd21a8d. This value corresponds to the state that the original input value used after the first 2 input chunks were ingested. From here we add the remaining bytes to the end of our new 30 and follow the calculations through to completion.
python sponges_debug.py "0000000000001db5785d bdb4482d1441a87cbc80\ e511772e3852e071f24b 20666f72206372797074 6f" ingest state: 0899e8f5e397b96cba6247249bfc6d22 ingest state: 5236011727a6c8320daccfe6c3d582c6 ingest state: ebc3be61bc5708451fbcafcfecd21a8d ingest state: 80c3cd0580d0491c117f7740560a1d64 final block: 6f ingest state: 11153c85d1b549e58b1b6fd6609e5464 ingest state: 40eeb0fd7e34d53a48ba395445452f3e ingest state: 956e116d90d5ae3df8ae2688417445f1 result: 11153c85d1b549e58b1b40eeb0fd7e34d53a48ba
