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:

• The server picks a random IV and sends it to us.
• We provide a plaintext (at least 100 bytes).
• The server encrypts it under a random key and gives us the authentication tag (but not the ciphertext).
• The server gives us \(E(iv)\) with the last four bits redacted, and asks us to guess the redacted bits.

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.

Summary

In short, the exploit is:

• Send 255 blocks \(-1, -2, ..., -255\) to make all ciphertext blocks equal to \(E(iv)\).
• Receive \(T = E(iv) (1+H)^{255}\).
• For each of the 16 possible values of \(E(iv)\), compute \(h = T \cdot E(iv)^{-1}\) and test if \(h^{(2^{128}-1)/255} = 1\).
• Assuming no false positives, only one value will pass the test – output it and proceed to the next round.
  • If we have multiple positives, just guess and hope we are lucky to speed things up a bit.

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