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.
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:


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:


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.


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^{4j+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)$


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


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

