UTCTF Galois. Remember kids, never repeat a nonce!

Code can be found here

As you probably read in the title, this is a writeup about a crypto challenge involving nonce repeition. Namely an AES-GCM challenge, where we are given an encrypted ciphertext and a encryption/decrpytion oracle, but no tag to go along with our ciphertext.

GCM Mode

What is GCM mode? Well as I learned last weekend, GCM (Galois counting mode) mode is a cool little cipher mode that generates 2 things at once using your symmetric cipher 1. A ciphertext
2. A tag which can be used to verify both identity and integrity

The ciphertext is fairly straightforward, it’s just the ciphertext that you would get from CTR mode, namely the plaintext XOR the keystream generated by encrypting a counter.

The tag is a bit more complex, it’s generated using the ciphertext and the encryption key as follows. (I’m going to ignore the auth-data, but it just adds more clutter and not much elses)

Consider a ciphertext C 10 bytes long.
1. Calculate the length v = bitlen(last block of C, split into 8 byte blocks), so in our case the last block is 2 bytes so the bitlen is 16
2. Calculate the following polynomial under GF(2^128), the Galois field with 128 elements. I’ll explain in a bit more detail what that means later.
\[ f(x) = C_1x^3 + C_2x^2 + vx + E_k(nonce)\] Where C_1 and C_2 are the two ciphertext blocks, with C_2 padded to 8 bytes and E_k represents encryption using the cipher and key
3. The tag T is then just f(H), where H is the encryption key and H = E_k(A string of 128 0’s)

So how does one evaluate things in GF(2^128)? I have no fucking clue. Just kidding I know a little bit.

Galois fields

A Galois field or finite field is just that, a field (a set with addition and multiplication operators) with a finite number of elements. I honestly don’t have the math chops to really give a good explanation, but what I do understand is that addition under this field is XOR, which will be important for the attack. Google a 3b1b video or smth. I might update this after I take my algerbra course next year.

The attack

So one look at the code and you’ll see that the nonce and key are generated at the same time, and never changed. The attack we want to employ is nicknamed The forbidden attack, probably because if you mess up your crypto this badly you deserve to be banished into the shadow realm.

Here’s the attack in a nutshell. Assume we’ve sent and collected 8 byte ciphertexts C_a and C_b and their corresponding tags T_a and T_b.
Our tags will be generated using \[ f(x) = C_ax^2 + v_ax + E_k(nonce)\] So \[ T_a = f(H) = C_{a}H^2 + v_aH + E_k(nonce)\] Unfortunately, we don’t know what H is, but what we can do is search for roots of this polynomial, so lets modify f. Let \[ f’(x) = C_ax^2 + v_ax + E_k(nonce) + T_a\] So now the root of f’ will be our encryption key \[ f’(H) = C_aH^2 + v_aH + E_k(nonce) + T_a = T_a + T_a = 0\] Note: Why does T_a + T_a = 0, because (+) in the field is XOR as mentioned earlier

The problem is that we don’t know all of f’, namely we don’t know what E_k(nonce) is. If only it was constant and there was some way of elimiating it…
Let \[ g’(x) = C_bx^2 + v_bx + E_k(nonce) + T_b\] \[ h(x) = g’(x) + f’(x)\] \[ h(x) = (C_a + C_b)x^2 + v_ax + v_bx + E_k(nonce) + E_k(nonce) + T_a + T_b\] \[ h(x) = (C_a + C_b)x^2 + (v_a + v_b)x + T_a + T_b\]

Well that was easy! So the attack is then very straightforward
1. Collect pairs of ciphertexts and their tags encrypted under the same nonce
2. Generate h(x) for each pair and find the root(s)
3. Decide that the root that appeared the most times must be the correct value of H

So now what do we do with the hash_key H? What we would love to do is generate a tag for the flag, but looking at the tag equation \[ T_{flag} = f_{flag}(H) = C_{flag}H^2 + v_{flag}H + E_k(nonce)\]

We still don’t know the value of the encrypted nonce. Now if only that nonce was constant and there was some way of eliminating it…

Let g be the tag function for a known ciphertext/tag pair
\[ g(x) + f_{flag}(x) = (C_a + C_{flag})x^2 + (v_a + v_{flag})x\] \[ g(H) + f_{flag}(H) = (C_a + C_{flag})H^2 + (v_a + v_{flag})H\] \[ T_{flag} = (C_a + C_{flag})H^2 + (v_a + v_{flag})H - T_a\]

Well that was also easy wasn’t it.

utflag{6cm_f0rb1dd3n_4774ck_777}

Note: I used nonce-disrespect’s recover and forge to actually recover H and generate the tag for the flag. Source

Other resources:
* Paper
* Nonce disrespect presentation