<- HACKON CTF

RSACBC

6 minutos de lectura

Se nos proporciona el código fuente en Python del servidor que cifra la flag:

import os,json

from Crypto.Util.number import getPrime, bytes_to_long as b2l, long_to_bytes as l2b
from Crypto.Util.Padding import pad 


class RSA_CBC:
    def __init__(self, p,q):
        self.n = p*q
        self.e = 0x10001
        self.p = p
        self.q = q
        self.d = pow(self.e, -1,(p-1)*(q-1))
        self.BLOCK_LENGTH = 32

    def xor(self,a,b):
        return bytes([x^y for x,y in zip(a,b)])

    def _encrypt(self, m):
        return l2b(pow(b2l(m), self.e, self.n))

    def bytes2blocks(self, m):
        return [m[i:i+self.BLOCK_LENGTH] for i in range(0, len(m), self.BLOCK_LENGTH)]

    def encrypt(self,m):
        blocks = self.bytes2blocks(pad(m,self.BLOCK_LENGTH)) 
        enc = [int.to_bytes(self.p,32,"big")] 
        for i in range(len(blocks)):
            enc.append(self._encrypt(self.xor(enc[i],blocks[i])))
        return {"blocks":list(map(bytes.hex,enc[1:]))}


FLAG = os.getenv("FLAG", "HackOn{AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA}")

p = getPrime(256)
q = getPrime(256)
cipher = RSA_CBC(p,q)
print(f"n = {cipher.n}")
menu = """
1. Encrypt
2. ¿Flag?
3. Exit
"""

for _ in range(2):
    print(menu)
    option = int(input(">>> "))
    if option == 1:
        try:
            m = bytes.fromhex(input("Message: "))
        except:
            raise ValueError("Whaatt...")
        if len(m) > 192 or b"\x00"*32 in m:
            raise ValueError("Try harder...")
        print(json.dumps(cipher.encrypt(m)))

    elif option == 2:
        print(json.dumps(cipher.encrypt(FLAG.encode())))
        break

    else:
        exit()

Análisis del código fuente

Como sugiere el nombre del reto, está utilizando RSA en modo CBC para cifrar información:

    def encrypt(self,m):
        blocks = self.bytes2blocks(pad(m,self.BLOCK_LENGTH)) 
        enc = [int.to_bytes(self.p,32,"big")] 
        for i in range(len(blocks)):
            enc.append(self._encrypt(self.xor(enc[i],blocks[i])))
        return {"blocks":list(map(bytes.hex,enc[1:]))}

Esto es, se toma un mensaje en bytes, se divide en bloques de 32 bytes y se cifra cada bloque con RSA. El modo CBC agrega una operación XOR entre el bloque de texto cifrado y el siguiente bloque de texto claro, y un vector de inicialización (IV) para el primer bloque de texto claro. Una imagen vale más que mil palabras, solo considera RSA como “block cipher encryption”:

RSACBC 1

Tenemos dos opciones, pero solo tenemos dos oportunidades para consultar al servidor:

for _ in range(2):
    print(menu)
    option = int(input(">>> "))
    if option == 1:
        try:
            m = bytes.fromhex(input("Message: "))
        except:
            raise ValueError("Whaatt...")
        if len(m) > 192 or b"\x00"*32 in m:
            raise ValueError("Try harder...")
        print(json.dumps(cipher.encrypt(m)))

    elif option == 2:
        print(json.dumps(cipher.encrypt(FLAG.encode())))
        break

    else:
        exit()

Básicamente, podemos cifrar un mensaje arbitrario (opción 1) u obtener la flag cifrada (opción 2).

Por último, pero no menos importante, los parámetros RSA son suficientemente seguros:

p = getPrime(256)
q = getPrime(256)
cipher = RSA_CBC(p,q)
print(f"n = {cipher.n}")

Solución

Dado que queremos descifrar RSA, necesitamos encontrar una manera de factorizar el módulo público o encontrar el mensaje en texto claro de otra manera, pero es probable que eso no sea posible. Obsérvese que el IV de la implementación del modo CBC es el número primo en bytes:

        enc = [int.to_bytes(self.p,32,"big")]

Entonces, ¿qué pasa si enviamos un mensaje que sea solo 32 bytes nulos? El resultado debe ser el valor de en bytes XOR bytes nulos, que sería , cifrado usando RSA. Por lo tanto, deberíamos obtener , ¿verdad? Sí, pero el servidor bloquea esto:

        if len(m) > 192 or b"\x00"*32 in m:
            raise ValueError("Try harder...")

Entonces, mantengamos las cosas simples. ¿Qué sucede si enviamos 31 bytes nulos y un \x01? Esto es lo mismo que tener . Obsérvese que los números primos son impares (excepto el número ), por lo que un XOR con es lo mismo que restar . Por lo tanto, .

De esta manera, lo estaremos obteniendo . ¿Y qué podemos hacer con esto? Vamos a verlo con una pequeña demostración:

Demostración

Olvidemos el por un segundo. Podemos expandir la expresión binomial usando el teorema del binomio:

Tenemos el resultado anterior porque es impar. Entonces, obsérvese que para un cierto entero . Por lo tanto,

Ahora está claro que la expresión anterior es un múltiplo de , por lo que se puede encontrar usando el GCD con . ¿Pero qué pasa con ? Bueno, en realidad nada, y aquí está la prueba:

Este es solo un algoritmo de división, siendo el cociente y el resto, con . Si tomamos módulo en ambos lados, vemos que . Queremos probar que . Eso es lo mismo que decir que es un múltiplo de (ya sabemos que ). Podemos expresar como:

Y lo anterior muestra que es un múltiplo de , por lo que hemos terminado la demostración.

Observación

También podríamos haber usado un XOR con , que es equivalente a , siempre que (que es lo mismo que decir que termina en bits menos significativos, de forma que termina en bits). Análogamente, tendríamos que .

Implementación

Ahora, el código de solución debería ser fácil de seguir:

io = get_process()

io.recvuntil(b'n = ')
n = int(io.recvline())

io.sendlineafter(b'>>> ', b'1')
io.sendlineafter(b'Message: ', (b'\0' * 31 + b'\x01').hex().encode())
kp_minus_1 = int(json.loads(io.recvline().decode()).get('blocks', [])[0], 16)
p = gcd(kp_minus_1 + 1, n)

assert p.bit_length() == 256
io.info(f'{p = }')
q = n // p
d = pow(0x10001, -1, (p - 1) * (q - 1))

Una vez que tenemos esto, podemos descifrar RSA, solo necesitamos tener en cuenta que está usando modo CBC, por lo que debemos aplicar XOR a cada bloque consecuentemente y solo considerar bloques de 32 bytes (se está usando un RSA de 512 bits, por lo que los texto cifrados son de 64 bytes, pero los mensajes de texto claro son solo 32 bytes):

io.sendlineafter(b'>>> ', b'2')
blocks = json.loads(io.recvline().decode()).get('blocks', [])

flag = []
prev_block = p.to_bytes(32, 'big')

for b in blocks:
    m = pow(int(b, 16), d, n)
    flag.append(xor(m.to_bytes(32, 'big'), prev_block)[:32])
    prev_block = bytes.fromhex(b)

io.success(unpad(b''.join(flag), 32).decode())

Flag

En este punto, podemos capturar la flag:

$ python3 solve.py 0.cloud.chals.io 18923
[+] Opening connection to 0.cloud.chals.io on port 18923: Done
[*] p = 90741731438160432997006881358404031084898961947119721095507310157558171448997
[+] HackOn{Kn0w_i_und3rst4nd_why_n0b0dy_d1d_th1s_b3f0r3_gcd_1s_p0w3rful!!}
[*] Closed connection to 0.cloud.chals.io port 18923

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