Blessed
23 minutos de lectura
Este es un reto que diseñé para Hack the Box. Se nos proporciona el código fuente en Python del servidor que contiene la flag:
import json
from eth_typing import BLSPrivateKey, BLSPubkey, BLSSignature
from secrets import randbelow
from typing import Dict, Generator, List
from Crypto.PublicKey import ECC
from py_ecc.bls.ciphersuites import G2ProofOfPossession as bls
from py_ecc.bls.g2_primitives import pubkey_to_G1
from py_ecc.bls.point_compression import decompress_G1
from py_ecc.bls.typing import G1Compressed
from py_ecc.optimized_bls12_381.optimized_curve import add, curve_order, G1, multiply, neg, normalize
try:
with open('flag.txt') as f:
FLAG = f.read().strip()
except FileNotFoundError:
FLAG = 'HTB{f4k3_fl4g_f0r_t3st1ng}'
def rng() -> Generator[int, None, None]:
seed = randbelow(curve_order)
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
G = ECC.EccPoint(Gx, Gy, curve='p256')
B = ECC.generate(curve='p256').pointQ
W0 = G * seed + B
Wn = W0
while True:
Wn += G
yield Wn.x >> 32
yield Wn.y >> 32
class Robot:
def __init__(self, robot_id: int, verified: bool = True):
self.robot_id: int = robot_id
self.verified: bool = verified
self.pk: BLSPubkey = BLSPubkey(b'')
self._sk: BLSPrivateKey = BLSPrivateKey(0)
if self.verified:
self._sk = BLSPrivateKey(randbelow(curve_order))
self.pk = bls.SkToPk(self._sk)
def json(self) -> Dict[str, str]:
return {'robot_id': hex(self.robot_id)[2:], 'pk': self.pk.hex()}
class SuperComputer:
def __init__(self, n: int):
self.rand: Generator[int, None, None] = rng()
self.robots: List[Robot] = []
for _ in range(n):
self.create()
def _find_robot_by_id(self, robot_id: int) -> Robot | None:
for r in self.robots:
if r.robot_id == robot_id:
return r
def create(self) -> Dict[str, str]:
r = Robot(next(self.rand))
self.robots.append(r)
return {'msg': 'Do not lose your secret key!', 'sk': hex(r._sk)[2:], **r.json()}
def join(self, pk: BLSPubkey) -> Dict[str, str]:
if not pk:
return {'error': 'This command requires a public key'}
r = Robot(next(self.rand), verified=False)
r.pk = pk
self.robots.append(r)
return {'msg': 'Robot joined but not verified', 'robot_id': hex(r.robot_id)[2:]}
def verify(self, robot_id: int) -> Dict[str, str]:
r = self._find_robot_by_id(robot_id)
if not r:
return {'error': 'No robot found'}
if r.verified:
return {'error': 'User already verified'}
print(json.dumps({'msg': 'Prove that you have the secret key that corresponds to your public key: pk = sk * G1'}))
Pk = pubkey_to_G1(r.pk)
for _ in range(64):
C_hex = input('Take a random value x and send me C = x * G1 (hex): ')
C = decompress_G1(G1Compressed(int(C_hex, 16)))
if next(self.rand) & 1:
x = int(input('Give me x (hex): '), 16)
if normalize(multiply(G1, x)) != normalize(C):
return {'error': 'Proof failed!'}
else:
sk_x = int(input('Give me (sk + x) (hex): '), 16)
if normalize(add(multiply(G1, sk_x), neg(Pk))) != normalize(C):
return {'error': 'Proof failed!'}
r.verified = True
return {'msg': 'Robot verified'}
def list(self, robot_id: int, sig: BLSSignature) -> Dict[str, str] | List[Dict[str, str]]:
if not sig:
return {'error': 'This command requires a signature'}
r = self._find_robot_by_id(robot_id)
if not r:
return {'error': 'No robot found'}
if not bls.Verify(r.pk, b'list', sig):
return {'error': 'Invalid signature'}
return [r.json() for r in self.robots]
def unveil_secrets(self, agg_sig: BLSSignature) -> Dict[str, str]:
agg_pk = [r.pk for r in self.robots if r.verified]
if not agg_sig:
return {'error': 'This command requires an aggregated signature'}
elif bls.FastAggregateVerify(agg_pk, b'unveil_secrets', agg_sig):
return {'msg': 'Secrets have been unveiled!', 'flag': FLAG}
else:
return {'error': 'Invalid aggregated signature'}
def help(self) -> Dict[str, str]:
return {
'help': 'Show this panel',
'create': 'Generate a new robot, already verified',
'join': 'Add a new robot, given a public key and a signature',
'verify': 'Start interactive process to verify a robot given an ID',
'list': 'Return a list of all existing robots',
'unveil_secrets': 'Show the secrets given an aggregated signature of all registered robots',
'exit': 'Shutdown the SuperComputer',
}
def run_cmd(self, data: Dict[str, str]) -> Dict[str, str] | List[Dict[str, str]]:
cmd = data.get('cmd')
pk = BLSPubkey(bytes.fromhex(data.get('pk', '')))
sig = BLSSignature(bytes.fromhex(data.get('sig', '')))
robot_id = int(data.get('robot_id', '0'), 16)
if cmd == 'create':
return self.create()
elif cmd == 'join':
return self.join(pk)
elif cmd == 'verify':
return self.verify(robot_id)
elif cmd == 'list':
return self.list(robot_id, sig)
elif cmd == 'unveil_secrets':
return self.unveil_secrets(sig)
elif cmd == 'exit':
return {'error': 'exit'}
return self.help()
def main():
print('Welcome! You have been invited to use our SuperComputer, which is very powerful and totally secure. Only sophisticated robots are able to use it, so you need to create a robot to interact with the SuperComputer or maybe join an existing one. The key to our success is that critical operations need the approval of all registered robots. Hackers cannot beat our security!\n')
crew = {
'Architects/Engineers',
'Explosives Experts/Demolition Specialists',
'Hackers',
'Stealth/Infiltration specialists',
'Scavengers',
}
sc = SuperComputer(len(crew - {'Hackers'})) # No hackers here...
print(json.dumps(sc.help(), indent=2), end='\n\n')
while True:
res = sc.run_cmd(json.loads(input('> ')))
print(json.dumps(res), end='\n\n')
if 'error' in res:
break
if __name__ == '__main__':
main()
Análisis del código fuente
El servidor define una instancia de SuperComputer, y nos permite interactuar con él usando estos comandos:
def help(self) -> Dict[str, str]:
return {
'help': 'Show this panel',
'create': 'Generate a new robot, already verified',
'join': 'Add a new robot, given a public key and a signature',
'verify': 'Start interactive process to verify a robot given an ID',
'list': 'Return a list of all existing robots',
'unveil_secrets': 'Show the secrets given an aggregated signature of all registered robots',
'exit': 'Shutdown the SuperComputer',
}
Para eso, necesitaremos crear un robot, ya que necesitamos una clave secreta para firmar nuestros comandos:
def create(self) -> Dict[str, str]:
r = Robot(next(self.rand))
self.robots.append(r)
return {'msg': 'Do not lose your secret key!', 'sk': hex(r._sk)[2:], **r.json()}
El método anterior devuelve una instancia de Robot:
class Robot:
def __init__(self, robot_id: int, verified: bool = True):
self.robot_id: int = robot_id
self.verified: bool = verified
self.pk: BLSPubkey = BLSPubkey(b'')
self._sk: BLSPrivateKey = BLSPrivateKey(0)
if self.verified:
self._sk = BLSPrivateKey(randbelow(curve_order))
self.pk = bls.SkToPk(self._sk)
def json(self) -> Dict[str, str]:
return {'robot_id': hex(self.robot_id)[2:], 'pk': self.pk.hex()}
Observe que el ID del robot es el resultado de este PRNG:
def rng() -> Generator[int, None, None]:
seed = randbelow(curve_order)
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
G = ECC.EccPoint(Gx, Gy, curve='p256')
B = ECC.generate(curve='p256').pointQ
W0 = G * seed + B
Wn = W0
while True:
Wn += G
yield Wn.x >> 32
yield Wn.y >> 32
Además, observe que el SuperComputer ya tiene un total de 4 robots:
def __init__(self, n: int):
self.rand: Generator[int, None, None] = rng()
self.robots: List[Robot] = []
for _ in range(n):
self.create()
Porque se crea de la siguiente manera:
crew = {
'Architects/Engineers',
'Explosives Experts/Demolition Specialists',
'Hackers',
'Stealth/Infiltration specialists',
'Scavengers',
}
sc = SuperComputer(len(crew - {'Hackers'})) # No hackers here...
Una vez que tenemos un robot, podemos usar la clave secreta para firmar un comando. Por ejemplo, podemos ejecutar list:
def list(self, robot_id: int, sig: BLSSignature) -> Dict[str, str] | List[Dict[str, str]]:
if not sig:
return {'error': 'This command requires a signature'}
r = self._find_robot_by_id(robot_id)
if not r:
return {'error': 'No robot found'}
if not bls.Verify(r.pk, b'list', sig):
return {'error': 'Invalid signature'}
return [r.json() for r in self.robots]
Este método devolverá la identificación de todos los robots registrados en el SuperComputer. Esto podría ser necesario para romper el PRNG.
Además, podemos ejecutar join:
def join(self, pk: BLSPubkey) -> Dict[str, str]:
if not pk:
return {'error': 'This command requires a public key'}
r = Robot(next(self.rand), verified=False)
r.pk = pk
self.robots.append(r)
return {'msg': 'Robot joined but not verified', 'robot_id': hex(r.robot_id)[2:]}
Con este método podemos agregar un robot existente al SuperComputer usando su clave pública. La diferencia con create es que el nuevo robot no se verifica, por lo que necesitamos ejecutar verify:
def verify(self, robot_id: int) -> Dict[str, str]:
r = self._find_robot_by_id(robot_id)
if not r:
return {'error': 'No robot found'}
if r.verified:
return {'error': 'User already verified'}
print(json.dumps({'msg': 'Prove that you have the secret key that corresponds to your public key: pk = sk * G1'}))
Pk = pubkey_to_G1(r.pk)
for _ in range(64):
C_hex = input('Take a random value x and send me C = x * G1 (hex): ')
C = decompress_G1(G1Compressed(int(C_hex, 16)))
if next(self.rand) & 1:
x = int(input('Give me x (hex): '), 16)
if normalize(multiply(G1, x)) != normalize(C):
return {'error': 'Proof failed!'}
else:
sk_x = int(input('Give me (sk + x) (hex): '), 16)
if normalize(add(multiply(G1, sk_x), neg(Pk))) != normalize(C):
return {'error': 'Proof failed!'}
r.verified = True
return {'msg': 'Robot verified'}
Este método ejecuta un proceso de verificación interactivo para garantizar que la clave pública del robot sea válida, pero sin revelar la clave secreta asociada. Esto se conoce como prueba de conocimiento cero (ZKP, zero-knowledge proof).
El comando objetivo que queremos ejecutar para resolver el reto es unveil_secrets:
def unveil_secrets(self, agg_sig: BLSSignature) -> Dict[str, str]:
agg_pk = [r.pk for r in self.robots if r.verified]
if not agg_sig:
return {'error': 'This command requires an aggregated signature'}
elif bls.FastAggregateVerify(agg_pk, b'unveil_secrets', agg_sig):
return {'msg': 'Secrets have been unveiled!', 'flag': FLAG}
else:
return {'error': 'Invalid aggregated signature'}
Para esto, necesitamos una firma agregada de todos los robots verificados, lo que significa que cada robot debe haber firmado este comando. De lo contrario, la verificación fallará y no ejecutaremos el comando con éxito.
Firmas BLS
El servidor usa firmas BLS, que implican criptografía basada en emparejamientos. La librería py-ecc hace una buena abstracción de lo que sucede por detrás.
Básicamente, la firma BLS está utilizando dos curvas elípticas $\mathbb{G}_1$ y $\mathbb{G}_2$ (conocidas como BLS12-381), cuyos puntos generadores son $G_1$ y $G_2$. Estas curvas son pairing-friendly, lo que significa que se puede definir una función de emparejamiento aquí.
La idea es que se pueden asociar dos puntos de las curvas elípticas para devolver otro punto de otra curva elíptica, que es $\mathbb{G}_T$. Particularmente, un emparejamiento es una función bilineal:
$$ e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T $$
La propiedad bilineal significa que las siguientes expresiones se mantienen para $P, R \in \mathbb{G}_1$ y $Q, S \in \mathbb{G}_2$:
$$ \begin{align*} e(P + R, Q) = e(P, Q) \cdot e(R, Q) \\ e(P, Q + S) = e(P, Q) \cdot e(P, S) \end{align*} $$
Como resultado, para cualesquiera escalares $a$ y $b$, las siguientes expresiones también se mantienen:
$$ \begin{align*} e(a \cdot P, b \cdot Q) & = e(P, b \cdot Q)^a \\ & = e(a \cdot P, Q)^b \\ & = e(P, Q)^{ab} \\ & = e(b \cdot P, Q)^a \\ & = e(P, a \cdot Q)^b \\ & = e(b \cdot P, a \cdot Q) \\ & = e(ab \cdot P, Q) \\ & = e(P, ab \cdot Q) \end{align*} $$
Esta propiedad bilineal permite definir el esquema de firma BLS:
- Un usuario toma un entero aleatorio $\mathrm{sk}$ y calcula su clave pública como $\mathrm{Pk} = \mathrm{sk} \cdot G_1$
- Para firmar un mensaje $m$, el mensaje debe ser transformado a un punto de la curva mediante una función de hash (hay varios métodos para hacer esto), por lo que $H(m) \in \mathbb{G}_2$
- La firma es $\sigma = \mathrm{sk} \cdot H(m) \in \mathbb{G}_2$
Es el proceso de verificación el que implica el emparejamiento. El verificador solo necesita calcular $e(\mathrm{Pk}, H(m))$ y compararlo con $e(G_1, \sigma)$. Esto funciona porque:
$$ \begin{align*} e(\mathrm{Pk}, H(m)) & = e(\mathrm{sk} \cdot G_1, H(m)) \\ & = e(G_1, H(m))^{\mathrm{sk}} \\ & = e(G_1, \mathrm{sk} \cdot H(m)) \\ & = e(G_1, \sigma) \end{align*} $$
La relevancia de las firmas BLS viene con el hecho de que las firmas pueden agregarse. Entonces, en lugar de verificar la firma de un mensaje contra varias claves públicas, es suficiente para verificar una sola firma agregada contra una sola clave pública agregada:
$$ \begin{align*} \sigma_{\mathrm{agg}} = \sigma_1 + \sigma_2 + \dots + \sigma_n \\ \mathrm{Pk}_{\mathrm{agg}} = \mathrm{Pk}_1 + \mathrm{Pk}_2 + \dots + \mathrm{Pk}_n \\ \\ e(\mathrm{Pk}_{\text{agg}}, H(m)) \stackrel{?}{=} e(G_1, \sigma_{\text{agg}}) \end{align*} $$
Sin embargo, hay un problema con la agregación si un atacante puede usar una clave pública arbitraria. El atacante puede forjar una firma agregada para un mensaje determinado, esto es, decir que algún usuario víctima ha firmado un mensaje:
- El atacante usa la siguiente clave pública: $\mathrm{Pk}_\text{attacker} = \mathrm{sk}_\text{attacker} \cdot G_1 - \mathrm{Pk}_\text{victim}$
- La firma agregada forjada es: $\sigma_\text{forged} = \mathrm{sk}_\text{attacker} \cdot H(m)$
- El verificador comprobará que $e(\mathrm{Pk}_\text{victim} + \mathrm{Pk}_\text{attacker}, H(m))$ es igual que $e(G_1, \sigma_{\text{forged}})$
Y funciona porque
$$ \begin{align*} e(\mathrm{Pk}_\text{victim} + \mathrm{Pk}_\text{attacker}, H(m)) & = e(\mathrm{Pk}_\text{victim} + \mathrm{sk}_\text{attacker} \cdot G_1 - \mathrm{Pk}_\text{victim}, H(m)) \\ & = e(\mathrm{sk}_\text{attacker} \cdot G_1, H(m)) \\ & = e(G_1, H(m))^{\mathrm{sk}_\text{attacker}} \\ & = e(G_1, \mathrm{sk}_\text{attacker} \cdot H(m)) \\ & = e(G_1, \sigma_{\text{forged}}) \end{align*} $$
Esto se conoce como ataque de rogue key. La forma de evitarlo es usando una “prueba de posesión”, que es verificar que el usuario que tiene una clave pública conoce la clave secreta asociada. Normalmente, el usuario debe proporcionar una firma de la propia clave pública, lo que demuestra que el usuario conoce la clave secreta asociada a la clave pública. Otros métodos pueden involucrar pruebas de conocimiento cero.
Para obtener más información sobre las curvas BLS12-381 y las firmas BLS, consulte BLS12-381 For The Rest Of Us o BLS Signatures & Withdrawals.
Prueba de conocimiento cero
La forma de evitar el ataque de rogue key en este reto es mediante una prueba de conocimiento cero interactiva: se pretende que el usuario demuestre que sabe $\mathrm{sk}$ tal que $\mathrm{Pk} = \mathrm{sk} \cdot G_1$, pero sin revelar $\mathrm{sk}$.
Para lograr esto, el servidor le dice al usuario que elija un entero aleatorio $x$ y que envíe $C = x \cdot G_1$. Luego, el servidor elige al azar una de estas dos preguntas:
- Muéstrame $x$
- Muéstrame el resultado de $(\mathrm{sk} + x)$
Si la pregunta es la 1., entonces el servidor puede verificar fácilmente que el valor $x$ satisface que $C = x \cdot G_1$.
Si la pregunta es la 2., entonces el servidor puede verificar que el valor dado $(\mathrm{sk} + x$) satisface que $\mathrm{Pk} + C = (\mathrm{sk} + x) \cdot G_1$.
Si este experimento se repite varias veces y el usuario no puede predecir la pregunta, entonces es prácticamente imposible mentir en el protocolo de ZKP:
def verify(self, robot_id: int) -> Dict[str, str]:
r = self._find_robot_by_id(robot_id)
if not r:
return {'error': 'No robot found'}
if r.verified:
return {'error': 'User already verified'}
print(json.dumps({'msg': 'Prove that you have the secret key that corresponds to your public key: pk = sk * G1'}))
Pk = pubkey_to_G1(r.pk)
for _ in range(64):
C_hex = input('Take a random value x and send me C = x * G1 (hex): ')
C = decompress_G1(G1Compressed(int(C_hex, 16)))
if next(self.rand) & 1:
x = int(input('Give me x (hex): '), 16)
if normalize(multiply(G1, x)) != normalize(C):
return {'error': 'Proof failed!'}
else:
sk_x = int(input('Give me (sk + x) (hex): '), 16)
if normalize(add(multiply(G1, sk_x), neg(Pk))) != normalize(C):
return {'error': 'Proof failed!'}
r.verified = True
return {'msg': 'Robot verified'}
Si el atacante puede predecir la pregunta, entonces el atacante puede engañar al protocolo de ZKP (es decir, demostrar que sabe $\mathrm{sk}$ tal que $\mathrm{Pk}_\text{attacker} = \mathrm{sk} \cdot G_1$, cuando no es verdad):
- Para la pregunta 1., el atacante simplemente envía el valor de $x$ tal que $C = x \cdot G_1$
- Pero para la pregunta 2., puede calcular un valor especial de $C = \mathrm{sk}_x \cdot G_1 - \mathrm{Pk}_\text{attacker}$, enviarlo, y después usar $\mathrm{sk}_x$ como si fuera $(\mathrm{sk} + x)$. El servidor verificará que $\mathrm{Pk}_\text{attacker} + C = \mathrm{sk}_x \cdot G_1$, que es cierto porque
$$ \mathrm{Pk}_\text{attacker} + C = \mathrm{Pk}_\text{attacker} + \mathrm{sk}_x \cdot G_1 - \mathrm{Pk}_\text{attacker} = \mathrm{sk}_x \cdot G_1 $$
EC-LCG
El servidor utiliza esta instancia PRNG para elegir la pregunta para el protocolo de ZKP. Entonces, tendremos que romper el PRNG para predecir preguntas y, por lo tanto, engañar al protocolo de ZKP:
def rng() -> Generator[int, None, None]:
seed = randbelow(curve_order)
Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
G = ECC.EccPoint(Gx, Gy, curve='p256')
B = ECC.generate(curve='p256').pointQ
W0 = G * seed + B
Wn = W0
while True:
Wn += G
yield Wn.x >> 32
yield Wn.y >> 32
Este algoritmo es un EC-LCG que usa la curva P256, denotada por $E(\mathbb{F}_p)$, de la siguiente manera:
$$ \begin{cases} W_0 & = \mathrm{seed} \cdot G + B \\ W_n & = W_{n - 1} + G \\ r_{2 n - 1} & = (W_n)_\mathrm{x} \gg 32 \\ r_{2 n} & = (W_n)_\mathrm{y} \gg 32 \\ \end{cases} $$
Donde $B, G \in E(\mathbb{F}_p)$, $\mathrm{seed} \in \mathbb{Z}$ y $n > 0$. Las salidas del PRNG son $r_i$:
$$ \begin{cases} r_1 & = (W_1)_\mathrm{x} \gg 32 \\ r_2 & = (W_1)_\mathrm{y} \gg 32 \\ r_3 & = (W_2)_\mathrm{x} \gg 32 \\ r_4 & = (W_2)_\mathrm{y} \gg 32 \\ \dots \end{cases} $$
Lo mismo se puede expresar de la siguiente manera:
$$ \begin{cases} W_n & = (\mathrm{seed} + n) \cdot G + B \\ r_{2 n - 1} & = (W_n)_\mathrm{x} \gg 32 \\ r_{2 n} & = (W_n)_\mathrm{y} \gg 32 \end{cases} $$
La clave para romper esta implementación de EC-LCG es que $W_{n + 1} - W_n = G$. Sin embargo, no se nos dan los valores exactos de $(W_n)_\text{x}$ y $(W_n)_\text{y}$, Entonces no podemos simplemente encontrar un punto $W_n$ para romper el EC-LCG. En cambio, podemos escribir algunas ecuaciones con la información que conocemos.
Usemos la siguiente notación para las salidas conocidas:
$$ u_n = r_{2n - 1} = (W_n)_\mathrm{x} \gg 32 \qquad v_n = r_{2n} = (W_n)_\mathrm{y} \gg 32 $$
Y estos para las incógnitas:
$$ a_n = W_n - \big((W_n)_\mathrm{x} \gg 32\big) \ll 32 \qquad b_n = W_n - \big((W_n)_\mathrm{y} \gg 32\big) \ll 32 $$
Conocemos los parámetros de la curva y el punto del generador $G$ (P256). Sabemos que $(u_n + a_n, v_n + b_n) \in E(\mathbb{F}_p)$, por lo que:
$$ (v_n + b_n)^2 = (u_n + a_n)^3 + a \cdot (u_n + a_n) + b \mod{p} $$
Además, sabemos que
$$ G = W_{n + 1} - W_n = (u_{n + 1} + a_{n + 1}, v_{n + 1} + b_{n + 1}) - (u_n + a_n, v_n + b_n) $$
Esto se puede expresar utilizando fórmulas de suma de puntos:
$$ \begin{cases} (x_1, y_1) + (x_2, y_2) = (x_3, y_3) \\ \\ \lambda = (y_2 - y_1) \cdot (x_2 - x_1)^{-1} \mod{p} \\ x_3 = \lambda^2 - x_1 - x_2 \\ y_3 = \lambda \cdot (x_1 - x_3) - y_1 \end{cases} $$
Nosotras podemos deshacernos de $\lambda$ en la fórmula de $x_3$:
$$ \begin{align*} x_3 & = \lambda^2 - x_1 - x_2 \iff \\ x_3 & = \big((y_2 - y_1) \cdot (x_2 - x_1)^{-1}\big)^2 - x_1 - x_2 \iff \\ x_3 & = (y_2 - y_1)^2 \cdot (x_2 - x_1)^{-2} - x_1 - x_2 \iff \\ 0 & = x_3 - (y_2 - y_1)^2 \cdot (x_2 - x_1)^{-2} + x_1 + x_2 \iff \\ 0 & = x_3 \cdot (x_2 - x_1)^2 - (y_2 - y_1)^2 + (x_1 + x_2) \cdot (x_2 - x_1)^2 \iff \\ 0 & = (x_1 + x_2 + x_3) \cdot (x_2 - x_1)^2 - (y_2 - y_1)^2 \end{align*} $$
Y lo mismo con la fórmula de $y_3$:
$$ \begin{align*} y_3 & = \lambda \cdot (x_1 - x_3) - y_1 \iff \\ y_3 & = \big((y_2 - y_1) \cdot (x_2 - x_1)^{-1}\big) \cdot (x_1 - x_3) - y_1 \iff \\ 0 & = y_3 - \big((y_2 - y_1) \cdot (x_2 - x_1)^{-1}\big) \cdot (x_1 - x_3) + y_1 \iff \\ 0 & = y_3 - (y_2 - y_1) \cdot (x_2 - x_1)^{-1} \cdot (x_1 - x_3) + y_1 \iff \\ 0 & = y_3 \cdot (x_2 - x_1) - (y_2 - y_1) \cdot (x_1 - x_3) + y_1 \cdot (x_2 - x_1) \iff \\ 0 & = (y_3 + y_1) \cdot (x_2 - x_1) - (y_2 - y_1) \cdot (x_1 - x_3) \end{align*} $$
Dado que tenemos más incógnitas que ecuaciones, pero las incógnitas lineales están acotadas a $2^{32}$, podemos usar un retículo (lattice) para resolver el problema del vector más corto usando LLL.
Usaremos un total de 6 salidas del PRNG ($u_1$, $v_1$, $u_2$, $v_2$, $u_3$, y $v_3$), es decir, 3 puntos ($W_1$, $W_2$ y $W_3$), y podemos obtener 7 ecuaciones independientes:
$$ \begin{cases} W_1 \in E(\mathbb{F}_p) \\ W_2 \in E(\mathbb{F}_p) \\ W_3 \in E(\mathbb{F}_p) \\ \\ W_2 - W_1 = G \quad \text{(for x and y)} \\ W_3 - W_2 = G \quad \text{(for x and y)} \end{cases} $$
$$ \begin{cases} (u_1 + a_1)^3 + a \cdot (u_1 + a_1) + b - (v_1 + b_1)^2 = 0 \mod{p} \\ (u_2 + a_2)^3 + a \cdot (u_2 + a_2) + b - (v_2 + b_2)^2 = 0 \mod{p} \\ (u_3 + a_3)^3 + a \cdot (u_3 + a_3) + b - (v_3 + b_3)^2 = 0 \mod{p} \\ \\ ((u_1 + a_1) + (u_2 + a_2) + G_\mathrm{x}) \cdot ((u_2 + a_2) - (u_1 + a_1))^2 - ((v_2 + b_2) \color{red}{+} (v_1 + b_1))^2 = 0 \mod{p} \\ ((u_2 + a_2) + (u_3 + a_3) + G_\mathrm{x}) \cdot ((u_3 + a_3) - (u_2 + a_2))^2 - ((v_3 + b_3) \color{red}{+} (v_2 + b_2))^2 = 0 \mod{p} \\ \\ (G_\mathrm{y} \color{red}{-} (v_1 + b_1)) \cdot ((u_2 + a_2) - (u_1 + a_1)) - ((v_2 + b_2) \color{red}{+} (v_1 + b_1)) \cdot ((u_1 + a_1) - G_\mathrm{x}) = 0 \mod{p} \\ (G_\mathrm{y} \color{red}{-} (v_2 + b_2)) \cdot ((u_3 + a_3) - (u_2 + a_2)) - ((v_3 + b_3) \color{red}{+} (v_2 + b_2)) \cdot ((u_2 + a_2) - G_\mathrm{x}) = 0 \mod{p} \end{cases} $$
Los signos coloreados en rojo son para indicar que estamos expresando $W_{n + 1} - W_n = G$, por lo que $-W_n = (u_n + a_n, -v_n - b_n)$.
Podemos deshacernos de $\mod{p}$ agregando algunos enteros $k_1, \dots, k_7$ multiplicados por $p$:
$$ \begin{cases} (u_1 + a_1)^3 + a \cdot (u_1 + a_1) + b - (v_1 + b_1)^2 + k_1 \cdot p = 0 \\ (u_2 + a_2)^3 + a \cdot (u_2 + a_2) + b - (v_2 + b_2)^2 + k_2 \cdot p = 0 \\ (u_3 + a_3)^3 + a \cdot (u_3 + a_3) + b - (v_3 + b_3)^2 + k_3 \cdot p = 0 \\ \\ ((u_1 + a_1) + (u_2 + a_2) + G_\mathrm{x}) \cdot ((u_2 + a_2) - (u_1 + a_1))^2 - ((v_2 + b_2) \color{red}{+} (v_1 + b_1))^2 + k_4 \cdot p = 0 \\ ((u_2 + a_2) + (u_3 + a_3) + G_\mathrm{x}) \cdot ((u_3 + a_3) - (u_2 + a_2))^2 - ((v_3 + b_3) \color{red}{+} (v_2 + b_2))^2 + k_5 \cdot p = 0 \\ \\ (G_\mathrm{y} \color{red}{-} (v_1 + b_1)) \cdot ((u_2 + a_2) - (u_1 + a_1)) - ((v_2 + b_2) \color{red}{+} (v_1 + b_1)) \cdot ((u_1 + a_1) - G_\mathrm{x}) + k_6 \cdot p = 0 \\ (G_\mathrm{y} \color{red}{-} (v_2 + b_2)) \cdot ((u_3 + a_3) - (u_2 + a_2)) - ((v_3 + b_3) \color{red}{+} (v_2 + b_2)) \cdot ((u_2 + a_2) - G_\mathrm{x}) + k_7 \cdot p = 0 \end{cases} $$
Obviamente, no tenemos solo 6 incógnitas, porque hay interacciones entre las variables (por ejemplo, $a_1 \cdot a_2$ or $a_1^3$). Sin embargo, estas variables también están limitadas y cortas en comparación con $p$. Como resultado, podemos usar una base de retículo como esta para determinar el valor de $a_1$, $b_1$, $a_2$, $b_2$, $a_3$ y $b_3$:
$$ \begin{bmatrix} {\begin{pmatrix} p & & & \\ & p & & \\ & & \ddots & \\ & & & p \end{pmatrix}} & {\begin{pmatrix} \mathrm{eq}_1 \quad \mathrm{coefficients} \\ \mathrm{eq}_2 \quad \mathrm{coefficients} \\ \dots \\ \mathrm{eq}_7 \quad \mathrm{coefficients} \end{pmatrix}} \\ \\ & {\begin{pmatrix} 1 & & & & \\ & 1 & & & \\ & & \ddots & & \\ & & & 1 & \\ & & & & 2^{256} \end{pmatrix}} \end{bmatrix} $$
Y el vector objetivo es $(k_1, \dots, k_7,\dots, a_1, b_1, a_2, b_2, a_3, b_3, 2^{256})$, que se puede obtener aplicando LLL en la matriz de base del retículo.
Una vez que tengamos $a_1$, $b_1$, $a_2$, $b_2$, $a_3$ y $b_3$, podemos encontrar $W_1$, $W_2$ y $W_3$ para romper el PRNG.
Solución
Entonces, este es el esquema para resolver el reto:
- Debemos ejecutar
unveil_secrets, que necesita una firma agregada de todos los robots verificados - Podemos usar un ataque rogue key para forjar la firma
- Para esto, debemos proporcionar una clave pública maliciosa, por lo que estaremos ejecutando
join - Necesitamos verificar el robot, es decir, debemos demostrar que tenemos la clave secreta asociada a la clave pública maliciosa
- No es fácil encontrar una clave secreta que pueda generar la clave pública maliciosa, por lo que debemos hacer trampa para completar la prueba de conocimiento cero
- Para esto, necesitamos saber exactamente qué pregunta va a hacer el servidor, por lo que necesitamos romper el PRNG de EC-LCG
- Necesitamos $6$ salidas, por lo que podemos crear un nuevo robot ($5^\text{a}$ salida), usarlo para listar los robots existentes y luego añadir otro robot con la clave pública maliciosa ($6^\text{a}$ salida)
Implementación
La interacción con el servidor está utilizando JSON (excepto el proceso de verificación), por lo que podemos usar esta función para enviar y recibir datos en JSON:
def sr(data):
io.sendlineafter(b'> ', json.dumps(data).encode())
return json.loads(io.recvline().decode())
Primero, creamos un robot y lo usamos para listar el resto:
res = sr({'cmd': 'create'})
sk = int(res.get('sk'), 16)
robot_id = int(res.get('robot_id'), 16)
cmd = 'list'
sig = bls.Sign(sk, cmd.encode())
res = sr({'cmd': cmd, 'robot_id': hex(robot_id), 'sig': sig.hex()})
ids, Pks = [], []
for r in res:
ids.append(int(r.get('robot_id'), 16))
Pks.append(decompress_G1(G1Compressed(int(r.get('pk'), 16))))
Con las claves públicas, podemos elaborar la clave pública maliciosa para el ataque de rogue key (py-ecc hace que sea muy fácil de implementar):
sk = 1337
cmd = 'ss'
pk = bls.SkToPk(sk)
sig = bls.Sign(sk, cmd.encode())
Pk = pubkey_to_G1(pk)
Pk_prime = add(Pk, neg(reduce(add, Pks, Z1)))
pk_prime = G1_to_pubkey(Pk_prime)
assert normalize(add(reduce(add, Pks), Pk_prime)) == normalize(Pk)
io.success('Forged signature!')
Ahora, añadimos a esta clave pública maliciosa y obtenemos la 6$^\mathrm{a}$ salida del PRNG:
res = sr({'cmd': 'join', 'pk': pk_prime.hex()})
robot_id = int(res.get('robot_id'), 16)
ids.append(robot_id)
assert len(ids) == 6
Luego, rompemos el PRNG de EC-LCG:
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
E = EllipticCurve(K, (a, b))
G = E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)
def crack_ec_lcg(values):
assert len(values) == 6
u1, v1, u2, v2, u3, v3 = values
a1, b1, a2, b2, a3, b3 = PolynomialRing(K, 'a1, b1, a2, b2, a3, b3').gens()
ec1 = (v1 + b1) ** 2 - (u1 + a1) ** 3 - a * (u1 + a1) - b
ec2 = (v2 + b2) ** 2 - (u2 + a2) ** 3 - a * (u2 + a2) - b
ec3 = (v3 + b3) ** 2 - (u3 + a3) ** 3 - a * (u3 + a3) - b
ec4 = ((u1 + a1) + (u2 + a2) + G.x()) * ((u2 + a2) - (u1 + a1)) ** 2 - ((v2 + b2) + (v1 + b1)) ** 2
ec5 = ((u2 + a2) + (u3 + a3) + G.x()) * ((u3 + a3) - (u2 + a2)) ** 2 - ((v3 + b3) + (v2 + b2)) ** 2
ec6 = (G.y() - (v1 + b1)) * ((u2 + a2) - (u1 + a1)) - ((v2 + b2) + (v1 + b1)) * ((u1 + a1) - G.x())
ec7 = (G.y() - (v2 + b2)) * ((u3 + a3) - (u2 + a2)) - ((v3 + b3) + (v2 + b2)) * ((u2 + a2) - G.x())
A, v = Sequence([ec1, ec2, ec3, ec4, ec5, ec6, ec7]).coefficients_monomials(sparse=False)
A = A.change_ring(ZZ)
A = (identity_matrix(7) * p).augment(A)
A = A.stack(zero_matrix(len(v), 7).augment(identity_matrix(len(v))))
A[-1, -1] = 2 ** 256
L = A.T.LLL()
assert L[-1][-1] == 2 ** 256
a1, b1, a2, b2, a3, b3 = L[-1][-7:-1]
W1 = E(u1 + a1, v1 + b1)
W2 = E(u2 + a2, v2 + b2)
W3 = E(u3 + a3, v3 + b3)
return W3
Con esto, podemos engañar al protocolo de ZKP para verificar la clave pública maliciosa:
Wn = crack_ec_lcg([i << 32 for i in ids])
io.success('Cracked EC-LCG!')
prog = io.progress('Cheating ZKP')
sr({'cmd': 'verify', 'robot_id': hex(robot_id)})
for _ in range(64 // 2):
Wn += G
for c in Wn.xy():
if (int(c) >> 32) & 1:
x = int(os.urandom(16).hex(), 16)
C = multiply(G1, x)
assert normalize(multiply(G1, x)) == normalize(C)
io.sendlineafter(b'Take a random value x and send me C = x * G1 (hex): ', bytes(G1_to_pubkey(C)).hex().encode())
io.sendlineafter(b'Give me x (hex): ', hex(x).encode())
else:
sk_x = int(os.urandom(16).hex(), 16)
C = add(multiply(G1, sk_x), neg(Pk_prime))
assert normalize(add(multiply(G1, sk_x), neg(Pk_prime))) == normalize(C)
io.sendlineafter(b'Take a random value x and send me C = x * G1 (hex): ', bytes(G1_to_pubkey(C)).hex().encode())
io.sendlineafter(b'Give me (sk + x) (hex): ', hex(sk_x).encode())
prog.success()
Finalmente, ejecutamos el comando unveil_secrets, con la firma agregada maliciosa:
res = sr({'cmd': cmd, 'sig': sig.hex()})
sr({'cmd': 'exit'})
io.success(res.get('flag'))
Flag
Si ejecutamos el script, resolveremos el reto y obtendremos la flag:
$ python3 solve.py 94.237.59.199:57607
[+] Opening connection to 94.237.59.199 on port 57607: Done
[+] Forged signature!
[+] Cracked EC-LCG!
[+] Cheating ZKP: Done
[+] HTB{EC-LCG_cr4ck3r_z3r0_kn0wl3dg3_ch34t3r_4nd_r0gue_k3y_4tt4ck3r!!}
[*] Closed connection to 94.237.59.199 port 57607
El script completo se puede encontrar aquí: solve.py.