babysponge writeup by NGG (!SpamAndHex)

babysponge.md

The task was to create a collision for Keccak where the capacity of the sponge was reduced to 48 bits. This way the rate is 194 bytes which means the text is chunked into 194 byte long parts and these chunks are XORed into the first 194 bytes of the state (out of 200 byte) before the Keccak-f[1600] permutation function is called. First I searched for two 194-byte long chunks for which the last 6 bytes of the state are the same. This needs around 2^24 tries because of the birthday paradox. After this we can append the new states' first 194 byte to each message that will zero these bytes leaving only the last 6 bytes non-zero which we know are identical. This way the inner state of the hash function is the same after 2*194 bytes, the padding will not make a difference.

I used KeccakF from https://github.com/KeccakTeam/KeccakTools to find the first chunks using the following C++ code:

KeccakF keccakF(1600);
unordered_map<uint64_t, int> last48;
last48.reserve(1<<25);
UINT8 state[200+2] = {0};
for (int n = 0;; n++) {
   	for(unsigned int i=0; i<194; i++)
       	state[i] = (i < 32 && (n&(1ULL << i))) ? 'B' : 'A';
	for (int i = 194; i < 200; i++)
		state[i] = 0;
   	keccakF(state);
	uint64_t x = *(uint64_t*)(state+194);
	if (!last48.emplace(x, n).second)
		cerr << last48[x] << " " << n << endl;
}

After finding the collision, my script looked like:

from pwn import *
from CompactFIPS202 import *
import hashlib, binascii, itertools, time

a, b = 824302, 21208162
ma = ''.join(['B' if (i < 32 and (a&(2**i))) else 'A' for i in range(194)])
mb = ''.join(['B' if (i < 32 and (b&(2**i))) else 'A' for i in range(194)])
ma += KeccakF1600(bytearray(ma + '\0'*6))
mb += KeccakF1600(bytearray(mb + '\0'*6))

r = remote('111.186.63.14', 10001)
l = r.recvline().strip()
print l, l[12:28], l[33:]
for x in itertools.product(string.ascii_letters + string.digits, repeat=4):
    h = hashlib.sha256(''.join(x) + l[12:28]).hexdigest()
    if h == l[33:]:
        print 'OK', ''.join(x), h
        r.sendline(''.join(x))
        break
time.sleep(1)
r.sendline(binascii.hexlify(ma))
time.sleep(1)
r.sendline(binascii.hexlify(mb))
r.interactive()