leaky block cipher (PlaidCTF 2021)

This completely legitimate™ block cipher looks a bit like GCM, but my computer plumber keeps complaining about water residue. Can you help me spot the leak?

The challenge authors came up with a custom block cipher mode that claims to provide authenticated encryption and looks very similar to GCM. The challenge is:

To make sure we didn’t just get lucky, this is repeated 20 times.

Cipher mode

Let the plaintext blocks we provided be \(M_1, M_2, \dots, M_n\). The encryption is some sort of bizarre-world CTR mode: \(C_i = E(M_i \oplus (iv + i))\), instead of the usual \(M_i \oplus E(iv + i)\).

Other than this, the authentication tag is computed as a normal GCM tag (multiplication is in \(\text{GF}(2^{128})\)):

T = 0
H = E(0)
foreach block Mi:
    Ci = Mi ^ (iv + i)
    T = (T ^ Ci) * H
T = T ^ E(iv)

We can write this as a sum in \(\text{GF}(2^{128})\) (so \(+\) represents XOR):

\[ T = E(iv) + \sum_{i=1}^n E(M_i + (iv+i)) H^{n+1-i} \]

Note the slight misuse of notation: the addition \(iv+i\) is actual integer addition.

The exploit

Since we (almost) know what the IV encrypts to, and don’t know anything about other values, let’s try setting all blocks to \(M_i = -i\), so that all coefficients in the polynomial above turn into \(E(iv)\). This turns the tag into \(T = E(iv)\sum_{i=0}^n H^n\).

If we set \(n\) to 255, this sum can be factored into \(T = E(iv)(1+H)^{255}\). The proof is relatively simple: we can factor out \(1+H^{128}\), then \(1+H^{64}\), and so on, and repeatedly apply \(1 + x^2 = (1 + x)^2\).

We will try each of the 16 possible values of \(E(iv)\), and for each compute \(T \cdot E(iv)^{-1}\). For the correct value, this will have a 255th root; otherwise, the value is effectively random and will have a root with probability \(1/255\).

We can test for this property using something similar to Euler’s criterion for quadratic residues: a value \(x\) has a 255th root if and only if \(x^{(2^{128} - 1) / 255} = 1\).

Note that this only works because 255 divides the group order \(2^{128} - 1\). In theory, we can choose any divisor that is of the form \(2^n - 1\) (otherwise the factorisation doesn’t work), such as 15. Smaller values risk having too many false positives, however – there are a total of 300 incorrect candidates for \(E(iv)\) we have to reject, and a false positive probability of \(1/15\) would mean we need millions of attempts to solve the challenge. With 255 blocks, the probability of finishing all 20 rounds without a single false positive is around \(30\%\), which is enough to solve the challenge in a few attempts.


In short, the exploit is:

After a few tries, we get the flag: PCTF{you_found_the_residues!_db2f6ade22d73a90b15e8d1b06167393}.