Spooky Safebox
9 minutos de lectura
Se nos proporciona el código fuente del servidor en Python. Este archivo es app.py:
#!/usr/bin/env python3
import secrets
import os, sys, hmac
import cryptod
from proofofwork import challenge_proof_of_work
FLAG = os.environ.get("FLAG", "flag{FAKE_FLAG}") if "flag" in os.environ.get("FLAG","") else "flag{FAKE_FLAG}"
def main():
print("Welcome to the Spooky Safebox!")
if not challenge_proof_of_work():
return
kpriv, kpub = cryptod.make_keys()
order = cryptod.get_order()
encrypted_flag = cryptod.encrypt(kpub, FLAG)
print("Here is the encrypted flag:", encrypted_flag)
print("You've got 9 signatures, try to recover Satoshi's private key!")
for i in range(9):
msg_ = input("Enter a message to sign: >")
msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))
nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
sig = kpriv.sign(int(msg, 16) % order, nonce)
print("Signature",(cryptod.int_to_bytes(int(sig.r)) + bytes.fromhex("deadbeef") + cryptod.int_to_bytes(int(sig.s))).hex())
print("Goodbye!")
if __name__ == '__main__':
try:
main()
except EOFError:
pass
except KeyboardInterrupt:
pass
Y este es cryptod.py:
import ecdsa, ecdsa.ecdsa
from cryptography.hazmat.primitives.kdf.kbkdf import (
CounterLocation, KBKDFHMAC, Mode
)
from cryptography.hazmat.primitives import hashes
import secrets
from Crypto.Cipher import ChaCha20_Poly1305
def get_order(): return ecdsa.NIST256p.generator.order()
def encrypt_sym(input_bytes: bytes, key:bytes):
cipher = ChaCha20_Poly1305.new(key=key)
ciphertext, tag = cipher.encrypt_and_digest(input_bytes)
return ciphertext + tag + cipher.nonce
def derive_symkey(inp:bytes):
kdf = KBKDFHMAC(
algorithm=hashes.SHA3_256(),
mode=Mode.CounterMode,
length=32,
rlen=4,
llen=4,
location=CounterLocation.BeforeFixed,
label=b"safu",
context=b"funds are safu",
fixed=None,
)
return kdf.derive(inp)
def make_keys():
gen = ecdsa.NIST256p.generator
secret = secrets.randbelow(gen.order()-1) + 1
pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)
return priv_key, pub_key
def int_to_bytes(n: int) -> bytes:
return n.to_bytes((n.bit_length() + 7) // 8, 'big') or b'\0'
def encrypt(kpub_dest:ecdsa.ecdsa.Public_key, msg:str):
gen = ecdsa.NIST256p.generator
r = secrets.randbelow(gen.order()-1) + 1
R = gen * r
S = kpub_dest.point * r
key = derive_symkey(int_to_bytes(int(S.x())))
cp = encrypt_sym(msg.encode(), key).hex()
return cp + "deadbeef" + R.to_bytes().hex()
Análisis del código fuente
El código es difícil de leer, pero después de un poco de tiempo, podemos descubrir qué hace. El servidor usa ECC y ECDSA en la curva P256.
La flag está cifrada con ChaCha20 y la clave se deriva de un punto $S$ de la curva (realmente, de $S_x$). Este punto $S$ es solo $r \cdot Q$, donde $r$ es un valor aleatorio y $Q$ es la clave pública. Esta clave pública es $Q = x \cdot G$, donde $x$ es la clave privada y $G$ es un generador de la curva.
Todos estos conceptos están presentes en cryptod.py. Los datos cifrados son el texto cifrado por Chacha20 y el punto $R = r \cdot G$. Obsérvese que si tuviéramos la clave privada $x$, entonces $S = r \cdot Q = r \cdot (x \cdot G) = x \cdot (r \cdot G) = x \cdot R$. Por lo tanto, necesitamos encontrar la clave privada $x$ para poder descifrar la flag.
En main.py, después de pasar la prueba de trabajo, se nos dan los datos cifrados y se nos permite ingresar 9 mensajes que se firmarán con ECDSA de una manera extraña:
for i in range(9):
msg_ = input("Enter a message to sign: >")
msg = hmac.new(cryptod.int_to_bytes(kpub.point.x() * i), msg_.encode(), "sha224").hexdigest()
checksum = 2**224 + (int(hmac.new(cryptod.int_to_bytes(kpriv.secret_multiplier) , msg_.encode(), "sha224").hexdigest(), 16) % (order-2**224))
nonce = secrets.randbelow(2 ** 224 - 1) + 1 + checksum
sig = kpriv.sign(int(msg, 16) % order, nonce)
print("Signature",(cryptod.int_to_bytes(int(sig.r)) + bytes.fromhex("deadbeef") + cryptod.int_to_bytes(int(sig.s))).hex())
Nuestro mensaje de entrada se pasa a un HMAC usando $i \cdot Q_x$ como clave, donde $i$ es la variable de iteración. Como la clave pública $Q$ no se nos da, solo sabremos la clave he HMAC para el primer mensaje, ya que la clave será $0 \cdot Q_x = 0$. Además, usa SHA224 como función hash.
Después de eso, este hash se usa para generar un valor de checksum usando otro SHA224-HMAC y $x$ como clave.
Entonces, el nonce $k$ es solo un número aleatorio menor que $2^{224} + 1$ más el valor de checksum, que es un entero de 225 bits. Por lo tanto, los nonces son enteros de 225 bits.
Y finalmente, el servidor firma con ECDSA y salidas $r$ y $s$.
Implementación del ECDSA
El código para el ECDSA es casi correcto (más información aquí). Tenemos esta ecuación para $i \in \{0, \dots, 8\}$:
$$ s_i = k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \mod{n} $$
Donde $n$ es el orden de la curva, $k_i$ son los nonces, $h_i$ son los hashes de los mensajes, $x$ es la clave privada y $(r_i, s_i)$ son los pares de firma.
El fallo de seguridad
El problema aquí es que el servidor genera los nonces $k$ de manera incorrecta. Obsérvese que los $k$ son enteros aleatorios de 225 bits, mientras que la curva P256 tiene un orden de 256 bits.
Como resultado, podemos usar un ataque basado en retículo (lattice) y LLL para resolver el Hidden Number Problem. Encontré esta técnica en esta página web, que referencia a la sección 4 de este artículo.
Hidden Number Problem
El HNP generalmente se define como:
$$ t_i \cdot \alpha + a_i \equiv b_i \pmod{p} $$
Donde $\alpha$ ese el número oculto y los valores $t_i$ y $a_i$ son conocidos, dadas $i$ ecuaciones. Podemos transformar la fórmula de la firma ECDSA a este formato:
$$ s_i \equiv k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \pmod{n} $$
$$ s_i k_i \equiv h_i + x \cdot r_i \pmod{n} $$
$$ r_i \cdot x + h_i \equiv s_i k_i \pmod{n} $$
$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv k_i \pmod{n} $$
Podemos definir un retículo que contenga la solución del HNP. En la definición, podemos usar el retículo formado por las columnas de:
$$ M = \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} $$
Donde $X$ es una cota superior para los valores $b_i$. Obsérvese que el vector $(b_1, \dots, b_i, X \alpha / p, X)$ está en el retículo:
$$ \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} \cdot \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_i \\ \alpha \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 p + \alpha t_1 + a_1 \\ c_2 p + \alpha t_2 + a_2 \\ \vdots \\ c_i p + \alpha t_i + a_i \\ X \alpha / p \\ X \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ X \alpha / p \\ X \end{pmatrix} $$
Nótese que $c_i$ son solo números enteros arbitrarios, son irrelevantes porque estamos trabajando $\mod{p}$. El vector objetivo debe ser un vector corto para que aparezca en la base reducida al aplicar el algoritmo LLL.
Si aplicamos este procedimiento en las ecuaciones de ECDSA que tenemos, trataremos de encontrar el vector $(k_1, \dots, k_i, X x / n, X)$. Sabemos que este vector es corto dentro del retículo ya que todos los $k_i$ son números de 225 bits y el retículo involucra vectores con entradas de 256 bits.
Encontrar la clave pública
Para aplicar el HNP a esta situación de biased nonces, necesitamos saber los hashes $h_i$. Solo sabemos el primero porque es la salida de un SHA224-HMAC con clave $0$. Como resultado, obtenemos la ecuación:
$$ s_0 = k_0^{-1} \cdot \left(h_0 + x \cdot r_0\right) \mod{n} $$
Es posible extraer la clave pública $Q$ a partir de $(r_0, s_0)$. Podemos seguir los pasos de Wikipedia:
$$ Q = r_0^{-1} \cdot (s_0 P - h_0 G) $$
Donde $P$ es un punto en la curva de tal manera que $P_x = r_0$. Obsérvese que hay dos puntos que satisfacen esta condición, por lo que tendremos que probar ambos.
Implementación
Comencemos por definir algunas funciones auxiliares:
def sign(m: bytes) -> Tuple[int, int]:
io.sendlineafter(b'Enter a message to sign: >', m)
io.recvuntil(b'Signature ')
r, s = map(lambda x: int(x, 16), io.recvline().decode().split('deadbeef'))
return r, s
def decrypt_sym(ct: bytes, key: bytes, nonce: bytes, tag: bytes) -> bytes:
return ChaCha20_Poly1305.new(key=key, nonce=nonce).decrypt_and_verify(ct, tag)
Ahora, pasemos la prueba de trabajo (el código fuente del reto ya incluye un archivo proofofwork.py para resolver esto):
io = get_process()
io.recvuntil(b'Please provide a string that starts with ')
challenge = io.recvuntil(b' and whose sha256 hash starts with', drop=True).decode()
prefix = io.recvline().decode().strip()
result = solve_pow(challenge, prefix)
io.sendlineafter(b'POW: >', result.encode())
Luego, firmemos el primer mensaje e intentemos obtener la clave pública $Q$. Para verificar cuál de las dos posibilidades es correcta, firmamos un segundo mensaje:
io.recvuntil(b'Here is the encrypted flag: ')
enc_data = bytes.fromhex(io.recvline().decode())
m0 = b'asdf0'
r0, s0 = sign(m0)
h0 = int(hmac.new(b'\0', m0, 'sha224').hexdigest(), 16)
m1 = b'asdf1'
r1, s1 = sign(m1)
for P in E.lift_x(Fp(r0), all=True):
Q = pow(r0, -1, n) * (s0 * P - h0 * G)
h1 = int(hmac.new(long_to_bytes(int(Q[0])), m1, 'sha224').hexdigest(), 16)
if (pow(s1, -1, n) * (h1 * G + r1 * Q))[0] == r1:
break
else:
io.failure('Failed to find public ECDSA key')
exit(1)
io.info(f'Public ECDSA key: {Q}')
h, r, s = [h0, h1], [r0, r1], [s0, s1]
Ahora que tenemos la clave pública $Q$, podemos obtener todos los hashes $h_i$ y también recoger las firmas $(r_i, s_i)$:
h, r, s = [h0, h1], [r0, r1], [s0, s1]
for i in range(2, 9):
mi = f'asdf{i}'.encode()
ri, si = sign(mi)
hi = hmac.new(long_to_bytes(int(Q[0]) * i), mi, 'sha224').hexdigest()
h.append(int(hi, 16))
r.append(ri)
s.append(si)
En este punto, podemos modelar y resolver el HNP usando LLL de la siguiente manera ($9$ muestras son suficientes):
p = n
a = list(map(lambda s_i, h_i: pow(s_i, -1, p) * h_i % p, s, h))
t = list(map(lambda r_i, s_i: pow(s_i, -1, p) * r_i % p, r, s))
X = 2 ** 225
raw_matrix = []
for i in range(len(a)):
raw_matrix.append([0] * i + [p] + [0] * (len(a) - i + 1))
raw_matrix.append(t + [X / p, 0])
raw_matrix.append(a + [0, X])
M = Matrix(QQ, raw_matrix)
L = M.LLL()
Una vez que tenemos la base reducida del retículo, necesitamos encontrar vector objetivo. Podemos hacer esto mirando si la cota superior $X$ aparece en el vector. Luego, tomaremos la clave privada $x$ e intentaremos descifrar la flag derivando la clave simétrica del punto $S = x \cdot R$ y descifrando el texto cifrado con ChaCha20:
enc_flag, R_bytes = enc_data.split(b'\xde\xad\xbe\xef')
R_mpz = ellipticcurve.Point.from_bytes(NIST256p.curve, R_bytes)
R = E(R_mpz.x(), R_mpz.y())
ct, tag, nonce = enc_flag[:-28], enc_flag[-28:-12], enc_flag[-12:]
for row in L.rows():
if row[-1] == X:
k = list(map(int, row[:-2]))
x = (s[0] * k[0] - h[0]) * pow(r[0], -1, p) % p
io.info(f'Private key: {x}')
S = x * R
key = derive_symkey(long_to_bytes(int(S[0])))
try:
io.success(f'Flag: {decrypt_sym(ct, key, nonce, tag).decode()}')
exit(0)
except ValueError:
io.failure('MAC check failed')
continue
Flag
Si ejecutamos el script, obtendremos la flag:
$ python3 solve_safebox.py flu.xxx 10030
[+] Opening connection to flu.xxx on port 10030: Done
[*] Public ECDSA key: (2632898350580737258169039806927386431504104360833563771125317252526522550904 : 77026766777862121462475060111493786243486512461424268224672289571158997563209 : 1)
[*] Private key: 103023634815621571102628370470165979788796885143680181972239572475026982389573
[+] Flag: flag{s4tosh1s_Funds_4re_safu_safeB0x_isnt}
[*] Closed connection to flu.xxx port 10030
El script completo se puede encontrar aquí: solve.py.