<- SEKAICTF

Noisy CRC

8 minutos de lectura

Se nos proporciona el código fuente en Python del servidor:

import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

from flag import FLAG

def getCRC16(msg, gen_poly):
    assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
    msglen = msg.bit_length()

    msg <<= 16
    for i in range(msglen - 1, -1, -1):
        if (msg >> (i + 16)) & 1:
            msg ^= (gen_poly << i)

    return msg

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)] 
    res[secrets.randbelow(3)] = getCRC16(secret, gen_poly)
    return res


def main():
    key = secrets.randbits(512)
    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")  
    enc_flag = cipher.encrypt(FLAG)
    print(f"Encrypted flag: {enc_flag.hex()}")

    used = set({})

    while True:
        gen_poly = int(input("Give me your generator polynomial: "))
        assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16

        if gen_poly in used:
            print("No cheating")
            exit(1)

        used.add(gen_poly)

        print(oracle(key, gen_poly))

main()

Análisis del código fuente

Básicamente, crea una clave aleatoria de 512 bits que se utiliza para cifrar la flag con AES y se nos da la flag cifrada. La clave de AES se genera a partir del hash SHA256 de la clave, por lo que necesitamos encontrar la clave de 512 bits para descifrar la flag:

def main():
    key = secrets.randbits(512)
    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")  
    enc_flag = cipher.encrypt(FLAG)
    print(f"Encrypted flag: {enc_flag.hex()}")

El servidor nos permite calcular el CRC (Cyclic Redundancy Check) de la clave de 512 bits con cualquier polinomio de grado 16 (representado por un número entero de 16 bits). En concreto, estamos ante CRC-16, ya que la salida será un número de 16 bits:

    used = set({})

    while True:
        gen_poly = int(input("Give me your generator polynomial: "))
        assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16  

        if gen_poly in used:
            print("No cheating")
            exit(1)

        used.add(gen_poly)

        print(oracle(key, gen_poly))

Desafortunadamente, el servidor no devuelve sólo el código CRC de la clave, sino dos valores aleatorios adicionales:

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)] 
    res[secrets.randbelow(3)] = getCRC16(secret, gen_poly)  
    return res

El algoritmo del CRC-16 es correcto:

def getCRC16(msg, gen_poly):
    assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16  
    msglen = msg.bit_length()

    msg <<= 16
    for i in range(msglen - 1, -1, -1):
        if (msg >> (i + 16)) & 1:
            msg ^= (gen_poly << i)

    return msg

CRC

Al leer sobre CRC, descubrí que tenía mucha relación con el Álgebra. De hecho, el código CRC es el resto de dividir los datos de entrada entre el polinomio generador. Si codificamos los bits de cada número como un polinomio con coeficientes en $\mathbb{F}_2$, el CRC es equivalente a calcular:

$$ c(x) = x^N \cdot k(x) \mod{p(x)} $$

Donde, $c(x)$ es el código CRC (la salida), $k(x)$ son los datos de entrada (la clave), $N = 16$ (CRC-16) y $p(x)$ es el polinomio generador.

Intuición

Suponiendo que sabemos qué salida es el código CRC real y qué salidas son aleatorias, podríamos construir un sistema de congruencias como este:

$$ \begin{cases} x^N \cdot k(x) \equiv c_1(x) \pmod{p_1(x)} \\\\ x^N \cdot k(x) \equiv c_2(x) \pmod{p_2(x)} \\\\ \dots \\\\ x^N \cdot k(x) \equiv c_n(x) \pmod{p_n(x)} \end{cases} $$

El sistema de congruencias anterior debería resultar familiar… Se puede resolver usando el Teorema Chino del Resto (CRT), pero usando polinomios en $\mathbb{F}_2[x]$ en lugar de números enteros. La solución será un polinomio

$$ x^N \cdot k(x) \mod{\prod_{i=1}^n p_i(x)} $$

Si $\prod_{i=1}^n p_i(x)$ es suficientemente grande (en $\mathbb{F}_2[x]$ esto equivale a que el grado del polinomio sea suficientemente grande), entonces $x^N \cdot k(x)$ será un polinomio de grado $N + 511$ (la clave tiene 512 bits, por lo que el polinomio asociado tiene grado 511).

Solución

Entonces, vamos a programar la solución en Python y SageMath. Comenzaremos definiendo algunas funciones auxiliares:

x = PolynomialRing(GF(2), names='x').gens()[0]


def num_to_poly(num):
    i, poly = 0, 0 * x

    while num >> i:
        poly += ((num >> i) & 1) * x ** i
        i += 1

    return poly


def get_crc(poly):
    io.sendlineafter(b'Give me your generator polynomial: ', str(poly).encode())  
    return eval(io.recvline().decode())

Sin aleatoriedad

Ahora, modificaremos el script del reto para poner el código CRC verdadero en el índice 1 de la lista:

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)]   
    res[1] = getCRC16(secret, gen_poly)
    return res

Entonces, sabemos exactamente dónde está el código CRC correcto y podemos intentar resolver el reto usando el CRT:

io = process(['python3', 'chall copy.py'])
io.recvuntil(b'Encrypted flag: ')
enc_flag = bytes.fromhex(io.recvline().decode())

res = num_to_poly(0)
poly = 2 ** 16

crcs, polys = [], []

while (res // (x ** 16)).degree() < 511 and poly < 2 ** 16 + 50:  
    crc = get_crc(poly)[1]
    crcs.append(num_to_poly(crc))
    polys.append(num_to_poly(poly))

    try:
        res = CRT(crcs, polys)
        if res % (x ** 16) != 0:
            io.failure('This should not happen')
    except ValueError as e:
        io.failure('This should not be reached')
        pass

    poly += 1

if poly == 2 ** 16 + 50:
    io.failure('FAIL')
    exit(1)

Si se encuentra la solución, entonces debemos dividir por $x^N$ y tomar los coeficientes del polinomio, que deberían ser los 512 bits de la clave utilizada para generar la clave de AES:

res //= x ** 16
io.info(f'Total results needed: {len(polys)}')
coeffs = list(reversed(res.coefficients(sparse=False)))
coeffs += [0] * (512 - len(coeffs))
key = int(''.join(map(str, coeffs)), 2)

cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b'12345678')  
io.success(cipher.decrypt(enc_flag).decode())

Con este script, podemos encontrar la flag de prueba con nuestra versión modificada del reto:

$ while true; do python3 solve_no_random.py && break; done  
[+] Starting local process '/usr/bin/python3': pid 2871946
[-] FAIL
[*] Stopped process '/usr/bin/python3' (pid 2871946)
[+] Starting local process '/usr/bin/python3': pid 2871975
[*] Total results needed: 44
[+] SEKAI{flag}
[*] Stopped process '/usr/bin/python3' (pid 2871975)

El valor hard-coded 2 ** 16 + 50 viene de saber que el número de consultas necesarias para encontrar una solución es de 44, para evitar iteraciones innecesarias.

Adaptación

Ahora que sabemos que el reto se puede resolver cuando sabemos dónde está el código CRC, debemos encontrar una manera de determinar todos los códigos CRC correctos a partir de las listas de tres valores (dos aleatorios y uno válido).

Después de resolver la serie de retos de cryptoGRAPHy, estaba muy metido en la teoría de grafos. Dado que solo uno de cada tres resultados es válido y necesitamos al menos 44 resultados correctos, pensé en usar un algoritmo de búsqueda como búsqueda en profundidad (DFS) o búsqueda en anchura (BFS). Sin embargo, fueron difíciles de implementar porque los tres nodos (las tres salidas) de un paso están conectados con los tres nodos del siguiente paso, y no hay una manera clara de determinar si un nodo ha sido visitado o no, y cómo determinar los nodos adyacentes y validar si la ruta se mantiene…

Estaba tratando de evitar hacer un enfoque de fuerza bruta, porque eso sería un máximo de $3^{44}$ posibilidades, lo cual no es asequible. Sin embargo, podemos comenzar con fuerza bruta y cortar un camino siempre que el resultado del CRT no sea válido o no exista (en realidad, esto es una especie de DFS).

Pongamos un ejemplo donde la ruta correcta es [0, 2, 1]: Empezamos a probar con [0, 0]. Si el CRT es válido, entonces continuamos por [0, 0, 0], [0, 0, 1] y [0, 0, 2]; de lo contrario, saltaríamos directamente a [0, 1] y luego a [0, 1, 0], [0, 1, 1] y [0, 1, 2]. Digamos que [0, 1, 1] da un CRT correcto, así que lo guardaremos en una lista. Al final, probaremos todas las combinaciones posibles (eliminando las que ya no son posibles) y obtendremos una lista de resultados válidos (que incluye la combinación que contiene los índices de los códigos CRC verdaderos).

Este es el código relevante para este enfoque:

def brute_force(valid, index):
    new_valid = []

    for crc_list, poly_list in valid:
        for crc in queries[index]:
            new_crc_list = crc_list + [num_to_poly(crc)]
            new_poly_list = poly_list + [num_to_poly(2 ** 16 + index)]
            try:
                CRT(new_crc_list, new_poly_list)
                new_valid.append((new_crc_list, new_poly_list))
            except ValueError:
                continue

    return new_valid


valid_queries = [
    ([num_to_poly(queries[0][0])], [num_to_poly(2 ** 16)]),
    ([num_to_poly(queries[0][1])], [num_to_poly(2 ** 16)]),
    ([num_to_poly(queries[0][2])], [num_to_poly(2 ** 16)])
]

round_prog = io.progress('Round')

for r in range(1, 44):
    valid_queries = brute_force(valid_queries, r)
    round_prog.status(f'{r + 1} / 44. Current amount: {len(valid_queries)}')  
    if len(valid_queries) > 10000:
        round_prog.failure()
        exit(1)

Luego, sólo necesitamos tomar las listas válidas (una de ellas debería ser la que tenga todos los códigos CRC verdaderos) e intentar obtener la clave de AES a partir de los 512 coeficientes del polinomio resultado del CRT para descifrar la flag:

for crc_list, poly_list in valid_queries:
    res = CRT(crc_list, poly_list)

    if res % (x ** 16):
        continue

    res //= x ** 16

    coeffs = list(reversed(res.coefficients(sparse=False)))
    coeffs += [0] * (512 - len(coeffs))
    key = int(''.join(map(str, coeffs)), 2)

    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b'12345678')  
    pt = cipher.decrypt(enc_flag)

    if b'SEKAI' in pt:
        io.success(f'Flag: {pt.decode()}')
        break
else:
    io.failure('FAIL')
    exit(1)

Me sorprendió que el enfoque de fuerza bruta / DFS tardara alrededor de 2 minutos cuando se encontraba la respuesta. Sin embargo, estoy bastante seguro de que hay una manera de determinar qué salidas son códigos CRC válidos y cuáles no.

Flag

De todos modos, podemos ejecutar el script y obtener la flag después de un tiempo:

$ while true; do time python3 solve.py chals.sekai.team 3005 && break; done
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 4608
[-] FAIL
python3 solve.py chals.sekai.team 3005  116,84s user 0,63s system 96% cpu 2:01,11 total  
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 864
[-] FAIL
python3 solve.py chals.sekai.team 3005  52,71s user 0,58s system 93% cpu 57,000 total
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[-] Round: Failed
python3 solve.py chals.sekai.team 3005  261,03s user 0,72s system 98% cpu 4:25,42 total
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 2916
[+] Flag: SEKAI{CrCrCRcRCRcrcrcRCrCrC}
python3 solve.py chals.sekai.team 3005  72,01s user 0,62s system 95% cpu 1:16,35 total

El script completo se puede encontrar aquí: solve.py.