Insomni'hack teaser 2023 - GCM

2023-01-21 463 words 3 minutes

Contents

This is the solution of the challenge “GCM” given during the Insomni’hack teaser 2023. It was an example of nonce re-use in AES GCM computation.

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. You also know the corresponding messages. Everything is given in base64.

Your goal is to create a valid ciphertext (ivChall, cChall, tChall) of the message “IBr0keGCMD1dntI?At1EastIcanAuth3nT1C413Wh41IWant”. The flag should be “INS{” + MD5(ivChall + cChall + tChall) + “}” A function computing the flag given the ciphertext is given for convenience.

gcm.sage

parameters.py

Details

Points: 151

Category: Crypto

Author: Alex

Solution

This challenge was the next level of the challenge Custom GCM given during Black Alps CTF by the same author. This time it appears that the counter is only two byte long and we have a message which is $2^{16}$ blocks. Thus, the counter warps and the value of the IV is incremented until it matches the value of the next counter value $Y_2 = E_k(IV_2 || 0^{15} || 1)$. We can recover $Y_2$ simply by XORing the last block of the first plaintext with the last block of the first ciphertext.

We have the following equation for $T_2$ representing the second tag and $H$ representing the hash key: $$T_2 = C_2 \cdot H \oplus E_k(Y_2)$$ Since we know all the values except $H$ we can compute it. Then we can encrypt and authenticate any messages. Here is the full solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


import parameters

from base64 import b64decode

load("gcm.sage")

G.<y> = PolynomialRing(GF(2))
F.<x> = GF(2^128, modulus = y^128 + y^7 + y^2 + y + 1)

def get_counter0(H, ct, t): 
    tag = b"\x00"*16
    for i in range(len(ct)//16):
        tag = xor(tag, f(ct[16*i: 16*(i+1)]))
        tag = multByH(tag, H, x)

    tag = xor(tag, f(t))
    return tag

def rogue_authenticate(H, ct, counter0): 
    tag = b"\x00"*16
    for i in range(len(ct)//16):
        tag = xor(tag, f(ct[16*i: 16*(i+1)]))
        tag = multByH(tag, H, x)

    tag = xor(tag, counter0)
    return f(tag)

if __name__ == "__main__":
    mChall = b'IBr0keGCMD1dntI?At1EastIcanAuth3nT1C413Wh41IWant'

    # Authentication key
    m1 = b64decode(parameters.m1)
    iv1 = b64decode(parameters.iv1)
    iv2 = b64decode(parameters.iv2)
    c1 = b64decode(parameters.c1)
    c2 = b64decode(parameters.c2)
    t1 = b64decode(parameters.t1)
    t2 = b64decode(parameters.t2)

    counter0 = xor(c1[-16:], m1[-16:])

    # Authentication key
    Counter0 = strToPoly(f(counter0), x)
    T2 = strToPoly(f(t2), x)
    C2 = strToPoly(f(c2), x)
    H = (T2 + Counter0) / (C2)

    counter0 = get_counter0(H, c1, t1)
    stream = xor(c1, m1)
    cChall = xor(stream[0:48], mChall)
    tChall = rogue_authenticate(H, cChall, counter0)
    print(computeFlag(iv1, cChall, tChall))