HackTM CTF Finals 2020 / Birthday

As soon as reading the challenge name, I started to think whether I can perform a Birthday Attack.

Let’s take a look at the source first:

#!/usr/bin/env python3

import os, sys
import binascii
from speck import SpeckCipher

rand_int = lambda x: int.from_bytes(os.urandom(x), 'little')
cipher = SpeckCipher(rand_int(8), key_size=64, block_size=32, mode='CBC', init=rand_int(4))

FLAG = 'REAL_FLAG_GOES_HERE'
content = FLAG.ljust(4*50, '!')

while True:
  for i in range(0, len(content), 4):
    v = cipher.encrypt(int.from_bytes(content[i:i+4].encode(), 'big'))
    sys.stdout.write('{:x}'.format(v).rjust(8, '0'))

As you can see above, the flag gets encrypted with 32-bit block cipher. The key and the iv are both randomized. Note that we can get lots of encrypted blocks from the remote server since the encryption happens in an infinite loop.

According to the birthday attack, we expect to have at least one collision in approximately 2¹⁶ blocks.

Let C_i be the ith ciphertext block and M_i be the ith plaintext block. CBC mode implies the equation:

C_i = E(key, M_i XOR C_i-1)

Let’s assume C_i and C_j collides where i != j.

C_i = C_j
E(key, M_i XOR C_i-1) = E(key, M_j XOR C_j-1)
M_i XOR C_i-1 = M_j XOR C_j-1
M_i XOR M_j = C_i-1 XOR C_j-1

If we know either M_i or M_j, we can calculate the other one using the above equation. Since the flag is padded with exclamation marks, we can assume that we know the last block of the plaintext.

In order to perform the attack, we can collect a million encrypted blocks and store the collision indexes. Then, we will try to find plaintext blocks and repeat this process until there are no unknown blocks left.

Here is the full attack script:

#!/usr/bin/env python3
from pwn import *
from binascii import a2b_hex

r = remote('34.107.97.76', 60003)
c_to_index = {}
ciphers = []
for i in range(1000000):
    c = int.from_bytes(a2b_hex(r.recvn(8)), 'big')
    if c not in c_to_index:
        c_to_index[c] = list()
    c_to_index[c].append(i)
    ciphers.append(c)

messages = [None] * 50
messages[49] = int.from_bytes(b'!!!!', 'big')
while None in messages:
    for mi in range(50):
        if messages[mi] is None:
            continue
        for ci in range(mi, len(ciphers), 50):
            if ci == 0:
                continue
            for cj in c_to_index[ciphers[ci]]:
                if cj == 0 or ci == cj:
                    continue
                mj = cj % 50
                if mi == mj or messages[mj] is not None:
                    continue
                c1 = ciphers[ci - 1]
                c2 = ciphers[cj - 1]
                messages[mj] = messages[mi] ^ c1 ^ c2

flag = b''
for m in messages:
    flag += m.to_bytes(4, 'big')
print(flag)