# 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}.