Black Alps 2022 - Custom GCM

This is the solution of the challenge “Custom GCM” given during the Black Alps 2022 CTF. It was an implementation error of the nonce usage in AES GCM computation lead to forgery attack.

Description

You came across a custom GCM implementation. You are also given ciphertexts $(iv_j, c_j, t_j)$, where $iv$ is the IV, $c$ the ciphertext, and $t$ the tag. For one of them, you are also given the corresponding plaintext. Everything is given in base64. Your goal is to create a valid ciphertext (ivChall, cChall, tChall) of the message “IBr0keGCMD1dntI?”. The flag should be “BA22{” + MD5(ivChall + cChall + tChall) + “}”. A function computing the flag given the ciphertext is given for convenience.

gcm.sage

parameters.txt

Details

Points: 500

Category: Cryptography

Solution

I did not have the time to finish this challenge during the CTF but I was able to complete it afterwards. I give here my solution.

I first noticed a problem with the counter increment of the counter:

1
2
3
4
5
6
7

sage: attach("gcm.sage")
sage: ctr = b"\x00"*16
sage: for i in range(256):
....:     ctr = increaseCounter(ctr)
....: 
sage: ctr
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\xff'

I would expect to have the value \x01\x00 at the end of the counter. This problem seems not exploitable since we have short messages.

The second issue I noticed was in the function GCM_Encrypt. It sets the first counter value $Y_0$ to be $IV || 0^{32}$. Whereas in the specification this value must be set to $IV || 0^{31} || 1$. This seems to be a minor problem but when I looked at the IV values given in parameters.txt, I noticed that the values are 12 bytes long and start from the value 0 up to 4. Another difference with the standard is the absence of length authentication. For AES GCM, the last block authenticates the lengths of the ciphertext and the additional data.

For authentication, GCM uses a value called the hash key which is the encryption of the zero block $E_k(0^{128})$ with the secret key $k$. The computations for authentication are done in the Galois field $\mathbb{F}_{128}$ with a polynomial $H$ representing this hash key. Thus for the first ciphertext $C_0$ which is only one block long we would have the authentication tag $T_0$ such that $$T_0 = C_0 \cdot H \oplus E_k(Y_0)$$ But since $Y_0$ is also the zero block the equation simplify in: $$T_0 = C_0 \cdot H \oplus H = H \cdot (C_0 \oplus 1)$$ Since we know both $T_0$ and $C_0$ we are able to recover $H$ which would allow us to authenticate other ciphertexts:

1
2
3
4
5
6
7

sage: G.<y> = PolynomialRing(GF(2))
sage: F.<x> = GF(2^128, modulus = y^128 + y^7 + y^2 + y + 1)
sage: C0 = strToPoly(f(c0), x)
sage: T0 = strToPoly(f(t0), x)
sage: H = T0 / (C0 + 1)
sage: print(polyToStr(H).hex())
78c16a92e55d755bcf7122a841f26b66

The challenge message to encrypt is one block long. To encrypt it we need the key stream of AES GCM. Since we know both the plaintext $M_3$ and and the ciphertext $C_3$ we can extract the key stream by XORing them together and XOR it again with the challenge message.

1
2
3
4
5

sage: mChall = b'IBr0keGCMD1dntI?'
sage: stream = xor(C3, M3)
sage: cChall = xor(stream[0:16], mChall)
sage: cChall.hex()
09a614ca74d5ca88856e514dfef3e7b8

Then we would reuse the corresponding $IV_2$ for authentication. For that, we need to recover $E_k(Y_0) = E_k(IV_2 || 0^{32})$. From the authentication tag $T_2$ we have: $$ T_2 = \left(\sum^{4}_{j=1} C_j \cdot H^{4-j+1}\right) \oplus E_k(Y_0) $$ Since we know $H$, $T_2$ and the ciphertext we hare able to compute $E_k(Y_0)$

1
2
3
4
5
6
7

sage: tag = b"\x00"*16
sage: for i in range(len(c3)//16):
....:   tag = xor(tag, f(c3[16*i: 16*(i+1)]))
....:   tag = multByH(tag, H, x)
sage: Y0_enc = xor(tag, f(t3))
sage: print(Y0_enc.hex())
39dcd7c532fe849298d221c60fda6b46

Now we have everything to compute the new tag $T_{chall}$:

1
2
3
4

sage: tag = multByH(f(cChall), H, x)
sage: tChall = xor(tag, Y0_enc)
sage: print(tChall.hex())
df8f16e1b432dae1d46a53d429f113f7

With the ciphertext and the tag we are able to compute the flag:

1
2

sage: print(computeFlag(iv3, cChall, tChall))
BA22{3285f23063d6c684a8d753098e3fe53f}