Jorge Wants a Token
10 minutos de lectura
Se nos el código fuente en Python del servidor. Por un lado tenemos administation.py (el archivo principal), y por otro tenemos library.py (funciones auxiliares). El servidor nos da estas opciones:
$ nc 0.cloud.chals.io 15980
__ __ __ ____
/ / / /___ ______/ /__/ __ \____
/ /_/ / __ `/ ___/ //_/ / / / __ \
/ __ / /_/ / /__/ ,< / /_/ / / / /
/_/ /_/\__,_/\___/_/|_|\____/_/ /_/
Welcome to the HackOn administration.
1. Log In - With token.
2. Register.
3. Make a complain.
4. Exit
[*]Option:
Análisis del código fuente
Las únicas opciones útiles son la 1 y la 2:
def menu():
banner()
show_options()
for i in range(32):
try:
option = int(input("[*]Option: ").strip())
except:
print("Wait, what?")
exit()
if option == 1:
token = input("Token, please: ").strip()
login(token)
elif option == 2:
new_user = input("Username: ").strip()
algorithm = input("Alg: ").strip()
register(new_user, algorithm)
elif option == 3:
print("Fuck no, send bizum to this number +34 631223245 to get the flag")
else:
print("Goodbye!!")
exit()
Aunque solo podemos usar la 2 de momento. Por otro lado, tenemos un total de 32 consultas al servidor.
Proceso de registro
A la hora de registrarnos, nos piden un nombre de usuario y un algoritmo para crear un token JWT (JSON Web Token):
def register(username: str, algorithm: str):
payload = dict()
payload['username'] = username
payload['iat'] = os.urandom(32).hex()
payload['status'] = "Student"
payload['dfh'] = "3+3=2, right?"
token = jws.encode(json.dumps(payload), algorithm)
print(token)
En la clase JWS de library.py podemos ver cómo funciona el método encode:
def encode(self, payload, algorithm="HSMAC256"):
if algorithm not in self.ALGORITHMS:
raise ValueError(f"ALgorithm {algorithm} not supported.")
try:
self.payload = json.loads(payload)
except:
raise Exception("Invalid payload format.")
if algorithm == "HSMAC256":
self.header = '{"alg":"HSMAC256","typ":"JWT"}'
elif algorithm == "ES512":
self.header = '{"alg":"ES512","typ":"JWS"}'
elif algorithm == "ESBLK":
self.header = '{"alg":"ESBLK","typ":"JWS"}'
signature = self.sign(payload,self.header, self.key, algorithm)
token = ".".join([JWS.base64url_encode(data).decode() for data in [self.header.encode(),payload.encode(),signature]])
return token
Este método, llama a sign:
def sign(self, payload, header, key:bytes, algorithm="HSMAC256"):
sign_input = ".".join([header, payload])
if algorithm not in self.ALGORITHMS:
raise ValueError(f"ALgorithm not supported.")
if algorithm == "HSMAC256":
signature = hmac.new(key, sign_input.encode(), digestmod=sha256).digest()
else:
signature = self.ecdsa_sign(sign_input, key, algorithm)
return signature
Y aquí se distingue entre el algoritmo HSMAC256 (basado en SHA256 y HMAC) y los algoritmos ES512 y ESBLK. En este segundo caso, se utiliza ECDSA como manera de firmar el token JWT, con el siguiente método:
def ecdsa_sign(self, input:str, key:bytes, algorithm:str):
if algorithm == "ES512":
hash = sha512()
else:
hash = blake2b(digest_size=46)
hash.update(key + urandom(16))
nonce = bytes_to_long(hash.digest())
sign = self.privKey.sign(bytes_to_long(sha256(input.encode()).digest()), nonce)
return long_to_bytes(sign.r)+ b'&&' +long_to_bytes(sign.s)
Y la diferencia entre ES512 y ESBLK es la función de hash utilizada. Por un lado, la función SHA512, y por otro, blake2b. Por lo demás, el uso de ECDSA es idéntico.
Implementación del ECDSA
El uso de ECDSA es casi correcto (más información aquí). Para firmar mensajes, utiliza un punto generador $G$ de la curva P-384 y SHA256 como función hash. Entonces, el programa calcula:
$$ h = \mathrm{SHA256}{(m)} $$
$$ r = (k \cdot G)_x $$
$$ s = k^{-1} \cdot \left(h + x \cdot r\right) \mod{n} $$
Donde $n$ es el orden de la curva y $k$ es un nonce aleatorio. La salida es la tupla $(r, s)$.
El problema está en la generación de los nonces; y en concreto, cuando se usa ESBLK como algoritmo, puesto que se usa blake2b con una longitud de hash digest de 46 bytes. Como la curva es la P-384 (384 bits, 48 bytes), estos nonces tienen 2 bytes que son siempre nulos (los 2 bytes más significativos).
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, y 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 46 bytes y el retículo involucra vectores con entradas de 48 bytes.
Una vez resuelto el HNP, obtendremos la clave privada $x$ para firmar cualquier token JWT.
Proceso de inicio de sesión
La otra opción que da el servidor es login:
def login(token: str):
if jws.verify(token):
try:
_,payload,_ = JWS.load_token(token)
payload = json.loads(payload)
status = payload['status']
username = payload['username']
iat = payload['iat']
dfh = payload['dfh']
except:
print("Problem in your payload detected.")
exit()
if status == "Rector" and type(dfh) == int == type(iat):
flag = bytes_to_long(FLAG.encode())
assert flag.bit_length() > 600
if iat > dfh and dfh.bit_length() == 200 and isPrime(dfh):
print(f"Rector, this belongs to you: {pow(iat,flag,dfh**2)}")
else:
print("Bad Parameters.")
else:
print(f"Welcome {username},your iat is {iat} and your status is {status}")
print(f"This is your public key: ")
print(jws.pubKey.point.x(),jws.pubKey.point.y())
else:
print("Fail in Log In. Invalid Token.")
Para conseguir la flag (bueno, un resultado dependiente de la flag), tenemos que pasar algunos atributos al contenido del token JWT. Por un lado status tiene que ser "Rector"; y luego $\mathrm{iat}$ y $\mathrm{dfh}$ tienen que ser números enteros con $\mathrm{iat} > \mathrm{dfh}$, y $\mathrm{dfh}$ número primo de 200 bits. Si todo esto se cumple, el servidor nos muestra el resultado de:
$$ \mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2} $$
Y además sabemos que la flag tiene más de 600 bits.
Problema del Logaritmo Discreto
En este caso, lo que tenemos que resolver es un Problema del Logaritmo Discreto (DLP). Esto es, hallar $\mathrm{flag}$ tal que $\mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2}$, sabiendo $\mathrm{iat}$ y $\mathrm{dfh}$.
En este caso, hay varias formas, ya que controlamos tanto $\mathrm{iat}$ como $\mathrm{dfh}$, y $\mathrm{dfh}$ es un número primo.
Por ejemplo, si decimos que $\mathrm{iat} = \mathrm{dfh} + 1$, la expansión del binomio de Newton en $\mod{\mathrm{dfh}^2}$ es:
$$ \begin{align*} \mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2} & = (\mathrm{dfh} + 1)^\mathrm{flag} \mod{\mathrm{dfh}^2} \\ & = \sum_{i = 0}^{\mathrm{flag}} {\mathrm{flag} \choose i} \cdot \mathrm{dfh}^i \mod{\mathrm{dfh}^2} \\ & = 1 + \mathrm{flag} \cdot \mathrm{dfh} + \sum_{i = 2}^{\mathrm{flag}} {\mathrm{flag} \choose i} \cdot \mathrm{dfh}^i \mod{\mathrm{dfh}^2} \\ & = 1 + \mathrm{flag} \cdot \mathrm{dfh} \end{align*} $$
Entonces, podemos hallar el valor de flag fácilmente (aunque $\mod{\mathrm{dfh}^2}$):
$$ \mathrm{flag} \mod{\mathrm{dfh}^2} = \frac{(\mathrm{iat}^\mathrm{flag} \mod{\mathrm{dfh}^2}) - 1}{\mathrm{dfh}} $$
Por otro lado, existen algoritmos para resolver un DLP módulo una potencia de un número primo (más información en este paper o en math.stackexchange.com). Este fue el método que utilicé durante el CTF.
Entonces, lo que conseguimos es $\mathrm{flag} \mod{\mathrm{dfh}^2}$, es decir, obtenemos un resultado incompleto. Por este motivo, debemos pedir otro resultado al servidor con otro valor $\mathrm{dfh}$, resolver el DLP y utilizar el Teorema Chino del Resto (CRT), juntando las soluciones hasta obtener la flag entera (más de 600 bits).
Solución
Para la primera parte del reto (recuperar la clave privada de JWT mediante ECDSA biased nonces) podemos definir esta función que resuelve el HNP usando LLL:
def get_private_key():
h, r, s = [], [], []
for _ in range(31):
token = register('a', 'ESBLK')
header, payload, signature = token.encode().split(b'.')
r_i, s_i = map(bytes_to_long, base64_url_decode(signature).split(b'&&'))
h.append(bytes_to_long(sha256(base64_url_decode(header) + b'.' + base64_url_decode(payload)).digest()))
r.append(r_i)
s.append(s_i)
p = int(generator_384.order())
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 = 256 ** 46
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()
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}')
return x
Luego, tenemos que generar un nuevo token JWT para pedir el resultado dependiente de la flag y resolver un DLP. Como necesitamos resolver varios logaritmos discretos y luego usar el CRT, podemos usar un bucle. Decidí reiniciar la conexión en cada iteración para usar un total de 31 consultas de register, para que el HNP sea más fácil de resolver:
def dlog_mod_power_prime(g, g_x, p, e):
"""
Discrete Logarithm modulo prime power
- Calculate x, such that g_x = g^x mod p^e
Implementation source: Discrete Logarithms and Factoring, Eric Bach
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf
"""
def theta(x, p, e):
p_2e_1 = pow(p, 2 * e - 1)
ret = pow(x, (p - 1) * pow(p, e - 1), p_2e_1) - 1 # we can use ^ 2*(p-1)p^(e-1)
assert ret % (p ** e) == 0
return ret // (p ** e)
p_e_1 = p ** (e-1)
theta_a = theta(g, p, 2)
theta_b = theta(g_x, p, 2)
x = (theta_b * inverse(theta_a, p_e_1)) % p_e_1
return x
crt_r, crt_m = [], []
for _ in range(4):
io = get_process()
x = get_private_key()
key = long_to_bytes(x)
jws = JWS(key)
dfh = getPrime(200)
token = jws.encode(json.dumps({
'iat': dfh + 1,
'status': 'Rector',
'dfh': dfh,
'username': '7Rocky',
}))
io.sendlineafter(b'[*]Option: ', b'1')
io.sendlineafter(b'Token, please: ', token.encode())
io.recvuntil(b'Rector, this belongs to you: ')
enc = int(io.recvline().decode())
io.close()
f = dlog_mod_power_prime(dfh + 1, enc, dfh, 2)
assert pow(dfh + 1, f, dfh ** 2) == enc
crt_r.append(f)
crt_m.append(dfh)
io.success(long_to_bytes(crt(crt_r, crt_m)).decode())
Flag
Con este script podemos obtener la flag:
$ python3 solve.py 0.cloud.chals.io 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 21527056898547024587609061810343314636054103071083534282832602787779906208125346961093976190169270897359572999836562
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 18814722945154313480948727673868769998572454698779537940745768538072367594925761035156672852090498617182007108488964
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 33961003751330092278804628895767649698903687994164285766669837669581590400494603649396321858221791508300235658238462
[*] Closed connection to 0.cloud.chals.io port 15980
[+] Opening connection to 0.cloud.chals.io on port 15980: Done
[*] Private key: 2260618360756416815541341091789168739127662042173042144222183197102177554812745377485235625697522113617557847117469
[*] Closed connection to 0.cloud.chals.io port 15980
[+] HackOn{I_c4n_s33_b14s3d_N0nc3s_3verywh3r3_I_g0.0nc3_m0r3_s4g3_1s_4lways_4_g00d_fr13nd}
El script completo se puede encontrar aquí: solve.py.