Interception
12 minutos de lectura
Se nos proporciona el código fuente en Python del servidor. Esto es server.py:
#!/usr/bin/env python3
import signal
import random, os
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from pool import GREET, ANS
from secret import RESTRICTED
class GRAS:
def __init__(self, m, p, q):
self.m = m
self.a = 0xdeadbeef
self.p = p
self.q = q
def generate_key(self):
ct = 0x1337
# this loop runs in milliseconds in our super computer
for _ in range(self.m):
ct = pow(ct, self.a, self.m)
return long_to_bytes(ct)[:16]
class OumaraSystem:
def __init__(self, bits):
self.BITS = bits
self.LIMIT = 2
self.p = getPrime(self.BITS//2)
self.q = getPrime(self.BITS//2)
self.N = self.p * self.q
self.e = 0x10001
self.d = pow(self.e, -1, (self.p-1)*(self.q-1))
self.prng = GRAS(self.N, self.p, self.q)
def encrypt(self, m):
m = bytes_to_long(m.encode())
assert 0 < m < self.N
enc_msg = long_to_bytes(pow(m, self.e, self.N))
return enc_msg
def encrypt_plans(self):
self.symmetric_key = self.prng.generate_key()
cipher = AES.new(self.symmetric_key, AES.MODE_ECB)
enc_plans = [cipher.encrypt(pad(r.encode(), 16)) for r in RESTRICTED]
return enc_plans
def send_encrypted_message(self, c):
if c > 1:
m = pow(c, self.d, self.N)
try:
msg = long_to_bytes(m).decode()
return True
except:
pass
return False
def reveal_internal_plans(self, encrypted_plans, key):
cipher = AES.new(key, AES.MODE_ECB)
plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]
return plans
def hash_verified(self, h):
return h == sha256(str(self.N).encode()).digest()
def generate_token(self):
d = self.q.bit_length() - 643
return ((self.q >> d) << d) | random.getrandbits(d)
def show_banner():
print('''
___ ____ ____ _ _
/ _ \ _ _ _ __ ___ __ _ _ __ __ _ / ___| ___ ___ _ _ _ __ ___ / ___| |__ __ _ _ __ _ __ ___| |
| | | | | | | '_ ` _ \ / _` | '__/ _` | \___ \ / _ \/ __| | | | '__/ _ \ | | | '_ \ / _` | '_ \| '_ \ / _ \ |
| |_| | |_| | | | | | | (_| | | | (_| | ___) | __/ (__| |_| | | | __/ | |___| | | | (_| | | | | | | | __/ |
\___/ \__,_|_| |_| |_|\__,_|_| \__,_| |____/ \___|\___|\__,_|_| \___| \____|_| |_|\__,_|_| |_|_| |_|\___|_|
''')
def menu():
print('=======================================')
print('|| ||')
print('|| [S]end your encrypted message ||')
print('|| [R]eveal internal plans ||')
print('|| [F]orgot decryption key ||')
print('|| ||')
print('=======================================')
return input('> ').upper()[0]
def print_plans(plans):
print('==================== CLASSIFIED CONTENT! DO NOT SHARE! ====================')
for i, p in enumerate(plans):
print(f'Plan {i+1} : {p}')
print('===========================================================================')
def main():
crypto = PopperSystem(2048)
encrypted_plans = crypto.encrypt_plans()
show_banner()
print('This channel aims at secure communication via asymmetric encryption.')
print(f'We say : {crypto.encrypt(random.choice(GREET)).hex()}')
while True:
ch = menu()
if ch == 'S':
enc_msg = int(input('You say : '), 16)
verified = crypto.send_encrypted_message(enc_msg)
if verified:
print(f'Nice! We say : {crypto.encrypt(random.choice(ANS)).hex()}')
else:
print(f'Nice! We say : {os.urandom(256).hex()}')
elif ch == 'R':
print('Our plans are encrypted via symmetric encryption and protected with our unique super computer that will take us to the Red Planet!')
key = bytes.fromhex(input('Enter decryption key : '))
plans = crypto.reveal_internal_plans(encrypted_plans, key)
print_plans(plans)
exit(0)
elif ch == 'F':
h = bytes.fromhex(input('Before giving you the token, you must prove me that you know the public key : '))
if crypto.hash_verified(h):
token = crypto.generate_token()
print(f'Here is your token : {token}')
print('Make sure you do not forget it next time!')
else:
print('Get out!')
else:
print('Hey, this is suspicious! Terminating the channel...')
exit(0)
if __name__ == '__main__':
signal.alarm(900)
main()
Y esto es pool.py:
GREET = [
'Is there an emergency?',
'How you doing?',
'Hey!'
]
ANS = [
'Great news, but use this channel responsibly.',
'I will inform the governor.',
'Bye!'
]
Se nos dan tres opciones:
$ nc 94.237.62.195 47360
___ ____ ____ _ _
/ _ \ _ _ _ __ ___ __ _ _ __ __ _ / ___| ___ ___ _ _ _ __ ___ / ___| |__ __ _ _ __ _ __ ___| |
| | | | | | | '_ ` _ \ / _` | '__/ _` | \___ \ / _ \/ __| | | | '__/ _ \ | | | '_ \ / _` | '_ \| '_ \ / _ \ |
| |_| | |_| | | | | | | (_| | | | (_| | ___) | __/ (__| |_| | | | __/ | |___| | | | (_| | | | | | | | __/ |
\___/ \__,_|_| |_| |_|\__,_|_| \__,_| |____/ \___|\___|\__,_|_| \___| \____|_| |_|\__,_|_| |_|_| |_|\___|_|
This channel aims at secure communication via asymmetric encryption.
We say : 5753adf1fb98f6dadd29631df780b6af712f99681b234da1598251a155d7549ecd8661355a2449fe341258b391225a1dc10f85e775311b5b56f07e678eea89ebce581e1badc7472c09e8639d0b406f314aaf603bc7674a17725546d1dfaeec93ace74b69c876e0d524709bd7d751939a1f6caaebd0ac5b410e4c4f409d71ffb9cf5a9ccd78eefed3174bdf5a5f715c1beb5a4ab578e20ca25e389514db9905905b298a8f84f1b5157b94241c0c22c196effe6563f3b20af1be6afde29eedceddea550d552a2fbb7fe105a0bc3d2254049d7ba204fe9db5f595b38bc73236c8ae832888f7ded43d05e179715839326c6ded91e2d62dacb2304bf544a2b364d4b0
=======================================
|| ||
|| [S]end your encrypted message ||
|| [R]eveal internal plans ||
|| [F]orgot decryption key ||
|| ||
=======================================
>
Para usar la opción F necesitamos tener la clave pública, y para usar la opción R necesitamos tener una clave de descifrado, por lo tanto, primero debemos usar la opción S.
Opción S
En esta opción, se nos dará un mensaje cifrado ANS aleatorio o simeplemente 256 bytes aleatorios dependiendo del mensaje que enviemos:
if ch == 'S':
enc_msg = int(input('You say : '), 16)
verified = crypto.send_encrypted_message(enc_msg)
if verified:
print(f'Nice! We say : {crypto.encrypt(random.choice(ANS)).hex()}')
else:
print(f'Nice! We say : {os.urandom(256).hex()}')
EL objeto crypto es una instancia de la clase OumaraSystem (aunque el código muestra PopperSystem). Vemos que el método encrypt Utiliza RSA para cifrar un mensaje m dado. Todos los parámetros de RSA son correctos:
class OumaraSystem:
def __init__(self, bits):
self.BITS = bits
self.LIMIT = 2
self.p = getPrime(self.BITS//2)
self.q = getPrime(self.BITS//2)
self.N = self.p * self.q
self.e = 0x10001
self.d = pow(self.e, -1, (self.p-1)*(self.q-1))
self.prng = GRAS(self.N, self.p, self.q)
def encrypt(self, m):
m = bytes_to_long(m.encode())
assert 0 < m < self.N
enc_msg = long_to_bytes(pow(m, self.e, self.N))
return enc_msg
Obsérvese que no se nos da ningún parámetro de RSA. Solo tenemos un texto cifrado de un mensaje aleatorio GREET.
print('This channel aims at secure communication via asymmetric encryption.')
print(f'We say : {crypto.encrypt(random.choice(GREET)).hex()}')
Para que la opción S funcione, necesitamos enviar un mensaje cifrado con su clave pública de RSA. Entonces, simplemente podemos enviar el texto cifrado que ya tenemos. Con esto, el servidor nos enviará un mensaje aleatorio ANS cifrado y no 256 bytes aleatorios.
Como resultado, para algunos índices $0 \leqslant i, j \leqslant 2$ tenemos esto:
$$ \begin{cases} c_1 = (\mathrm{GREET}[i]) ^ e \mod{n} \\ c_2 = (\mathrm{ANS}[j]) ^ e \mod{n} \end{cases} $$
GCD
La idea es precalcular $(\mathrm{GREET}[2]) ^ e$ y $(\mathrm{ANS}[2]) ^ e$, que son los mensajes más pequeños, y conectarnos al servidor hasta que el servidor cifre $\mathrm{GREET}[2]$.
El objetivo es encontrar $n$, que se puede hallar utilizando el mayor común divisor (GCD), porque:
$$ \begin{cases} (\mathrm{GREET}[2]) ^ e - c_1 \equiv 0 \pmod{n} \\ (\mathrm{ANS}[2]) ^ e - c_2 \equiv 0 \pmod{n} \end{cases} $$
Por lo que,
$$ n = \gcd{\Big((\mathrm{GREET}[2]) ^ e - c_1, \quad (\mathrm{ANS}[2]) ^ e - c_2\Big)} $$
En realidad, es posible que no obtengamos exactamente $n$, sino algún múltiplo de $n$. Podemos superar esto tratando de dividir el resultado del GCD con algunos pocos números primos pequeños.
Como resultado, podemos pensar que el servidor nos está enviando el mensaje $\mathrm{GREET}[2]$ cifrado y solo necesitamos usar la opción S varias veces hasta que tengamos los tres posibles mensajes $\mathrm{ANS}[j]$ cifrados. Luego, calculamos el GCD con todas las combinaciones utilizando el valor de $\mathrm{ANS}[2]) ^ e$ precalculado hasta encontrar $n$, que es un número impar de 2048 bits. Si no encontramos $n$, entonces repetimos el proceso porque el servidor no ha enviado el mensaje $\mathrm{GREET}[2]$ cifrado:
e = 65537
guessed_greet = bytes_to_long(b'Hey!')
guessed_greet_e = guessed_greet ** e
guessed_ans = bytes_to_long(b'Bye!')
guessed_ans_e = guessed_ans ** e
while True:
io = get_process()
io.recvuntil(b'We say : ')
enc_greet = int(io.recvline().decode(), 16)
enc_anss = set()
while len(enc_anss) < 3:
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'You say : ', hex(enc_greet).encode())
io.recvuntil(b'Nice! We say : ')
enc_anss.add(int(io.recvline().decode(), 16))
n = max(gcd(guessed_greet_e - enc_greet, guessed_ans_e - enc_ans) for enc_ans in enc_anss)
for p in primes(100):
if n % p == 0:
n //= p
if n.bit_length() == 2048 and n & 1:
io.success(f'Found {n = }')
break
io.close()
Opción F
Una vez que tenemos la clave pública de RSA $(n, e)$, podemos usar la opción F, porque solicita el hash SHA256 de $n$ como texto decimal:
if crypto.hash_verified(h):
token = crypto.generate_token()
print(f'Here is your token : {token}')
print('Make sure you do not forget it next time!')
else:
print('Get out!')
El método hash_verified solo verifica el hash:
def hash_verified(self, h):
return h == sha256(str(self.N).encode()).digest()
Ya tenemos $n$, por lo que no hay problemas con el proceso de verificación. Después de eso, se nos da un token, que es la salida de generate_token:
def generate_token(self):
d = self.q.bit_length() - 643
return ((self.q >> d) << d) | random.getrandbits(d)
Este token contiene información sobre el número primo $q$ (que es parte de la clave privada de RSA). En realidad, nos dan $643$ bits de información (ocultan $381$ bits).
Método de Coppersmith
Para recuperar $q$ podemos usar el método de Coppersmith. Para esto, creamos un polinomio $f(x) = x + q_H \pmod{p}$. Sea $q_L = q - q_H$, entonces $f(q_L) = 0$, por lo que $q_L$ es una raíz. Además, la raíz es pequeña porque debe ser un número de 381 bits. Para obtener más información sobre la implementación, se recomienda echar un vistazo a Bank-er-smith.
Para implementar el ataque, SageMath tiene un método llamado small_roots:
io.sendlineafter(b'> ', b'F')
io.sendlineafter(
b'Before giving you the token, you must prove me that you know the public key : ',
sha256(str(n).encode()).hexdigest().encode(),
)
io.recvuntil(b'Here is your token : ')
d = 1024 - 643
token = int(io.recvline().decode())
q_H = (token >> d) << d
x = PolynomialRing(Zmod(n), names='x').gens()[0]
q_L = int((x + q_H).small_roots(X=2 ** d, beta=0.5)[0])
q = q_H + q_L
assert n % q == 0 and 1 < q < n
p = n // q
io.success(f'Found {p = }')
io.success(f'Found {q = }')
Necesitamos especificar el límite superior para la raíz pequeña ($2^{381}$) y $\beta = porque.5$ because $q \approx n^{0.5}$.
Una vez que tenemos $q$, es trivial encontrar $p$, por lo que tenemos la clave privada de RSA.
Opción R
Para esta opción, necesitamos proporcionar una clave de descifrado:
elif ch == 'R':
print('Our plans are encrypted via symmetric encryption and protected with our unique super computer that will take us to the Red Planet!')
key = bytes.fromhex(input('Enter decryption key : '))
plans = crypto.reveal_internal_plans(encrypted_plans, key)
print_plans(plans)
exit(0)
Esta clave se usa para descifrar algunos planes usando AES:
def reveal_internal_plans(self, encrypted_plans, key):
cipher = AES.new(key, AES.MODE_ECB)
plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]
return plans
Sabemos cómo se cifraron estos planes:
def encrypt_plans(self):
self.symmetric_key = self.prng.generate_key()
cipher = AES.new(self.symmetric_key, AES.MODE_ECB)
enc_plans = [cipher.encrypt(pad(r.encode(), 16)) for r in RESTRICTED]
return enc_plans
Y self.symmetric_key viene de self.prng.generate_key:
def generate_key(self):
ct = 0x1337
# this loop runs in milliseconds in our super computer
for _ in range(self.m):
ct = pow(ct, self.a, self.m)
return long_to_bytes(ct)[:16]
Recordemos que prng es una instancia de GRAS, inicializada como GRAS(self.N, self.p, self.q) desde OumaraSystem:
class GRAS:
def __init__(self, m, p, q):
self.m = m
self.a = 0xdeadbeef
self.p = p
self.q = q
Entonces, la clave de AES es el resultado de realizar esta recurrencia:
$$ \begin{cases} \mathrm{ct}_0 = \mathtt{0x1337} \\ \mathrm{ct}_{i + 1} = (\mathrm{ct}_i) ^ \mathtt{0xdeadbeef} \mod{n}, \quad 0 \leqslant i < n \end{cases} $$
Esta recurrencia no es asequible para hacerla como tal, porque $N$ iteraciones son demasiados. Pero podemos intentar transformar la recursión en una expresión cerrada. Comencemos con las primeras rondas:
$$ \begin{cases} \mathrm{ct}_0 & = \mathtt{0x1337} \\ \mathrm{ct}_1 & = (\mathrm{ct}_0) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ \mathtt{0xdeadbeef} \mod{n} \\ \mathrm{ct}_2 & = (\mathrm{ct}_1) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = (\mathtt{0x1337} ^ \mathtt{0xdeadbeef}) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 2} \mod{n} \\ \mathrm{ct}_3 & = (\mathrm{ct}_2) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = (\mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 2}) ^ \mathtt{0xdeadbeef} \mod{n} \\ & \quad = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ 3} \mod{n} \\ \dots \end{cases} $$
Entonces, por inducción, vemos que
$$ \mathrm{ct}_i = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ i} \mod{n} $$
Por lo tanto, la clave simétrica es el valor de $\mathrm{ct}_n$, que es
$$ \mathrm{ct}_n = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ n} \mod{n} $$
Teorema de Euler
De nuevo, calcular $\mathtt{0xdeadbeef} ^ n$ no es asequible. Sin embargo, sabemos por el Teorema de Euler que:
$$ a^{\phi(n)} \equiv 1 \pmod{n} $$
Para todo $a$ que es coprimo con $n$. Obsérvese que en nuestro caso, $\phi(n) = (p - 1) \cdot (q - 1)$, sabemos su valor.
Como resultado, podemos expresar $\mathtt{0xdeadbeef} ^ n = k \cdot \phi(n) + r$ para unos ciertos $r, k \in \mathbb{Z}$ con $0 \leqslant r < \phi(n)$. Esto significa que
$$ \begin{align} \mathrm{ct}_n & = \mathtt{0x1337} ^ {\mathtt{0xdeadbeef} ^ n} \mod{n} \\ & = \mathtt{0x1337} ^ {k \cdot \phi(n) + r} \mod{n} \\ & = \mathtt{0x1337} ^ {k \cdot \phi(n)} \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = (\mathtt{0x1337} ^ {\phi(n)})^k \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = 1^k \cdot \mathtt{0x1337} ^ r \mod{n} \\ & = \mathtt{0x1337} ^ r \mod{n} \\ \end{align} $$
Entonces, podemos encontrar fácilmente $\mathrm{ct}_n$ calculando $\mathtt{0x1337} ^ r \mod{n}$, donde $r = \mathtt{0xdeadbeef} ^ n \mod{\phi(n)}$.
Finalmente, calculamos el valor para obtener la clave de AES y la enviamos al servidor para obtener los planes descifrados, donde encontraremos la flag:
phi_n = (p - 1) * (q - 1)
r = pow(0xdeadbeef, n, phi_n)
key = long_to_bytes(pow(0x1337, r, n))[:16]
io.sendlineafter(b'> ', b'R')
io.sendlineafter(b'Enter decryption key : ', key.hex().encode())
io.success(io.recvall())
Flag
Si ejecutamos el guión, eventualmente obtendremos la flag:
$ python3 solve.py 94.237.62.195:47360
[+] Opening connection to 94.237.62.195 on port 47360: Done
[*] Closed connection to 94.237.62.195 port 47360
[+] Opening connection to 94.237.62.195 on port 47360: Done
[+] Found n = 21828146529253275647528009268961483917051427953072577306400212670783019877630592727742182289463031611647097861086320726593126769979528665193048139486760894654690438277251180052193057515070370801418498585589171513684267978232583787004127360151128840623431139630252021535654195838570606968632681095031823079824965797727053272091392851725752523879162831055146384238685312134668411531994622000792062370758867536394634102913088089786880545130192783530519953571718954658995201918458155388045089276232631781288844941398393317786447871785850810213239753970564827735726630395643445385451025512627762738759777002612894573124779
[+] Found p = 138914161634423579755973890643073661570844937467514466292807268924640588600508463767512520820631207681003342696298915409507816838560655431962752418410182732334881168218381565403199082791198460278491813223075820718287282969472364968722297813493964939725554441884621069455843858556284476182996052034694182305499
[+] Found q = 157134062304589100449250495092477382712810341772835720236404481783671949518284747291908024847223653945202337368600411462252602380456101761563657012208023722487110626000059267031658199648905100702047735660944313210898947637050045958141628827881758216447663733390406115171560673050045606192734569616598139140721
[+] Receiving all data: Done (590B)
[*] Closed connection to 94.237.62.195 port 47360
[+] ==================== CLASSIFIED CONTENT! DO NOT SHARE! ====================
Plan 1 : Their governor goes to sleep at 23:30 PM. We can then break in their warehouses tomorrow night and steal some fuels and water.
Plan 2 : Listen to the plan carefully! When you are done with the aforementioned invasion, make sure you come back silently and whisper the passphrase HTB{0ur_c0mput3r_1s_t00_f4st___w3_d0nt_3v3n_n33d_3u13r!} to the guards so you can enter.
Plan 3 : WE will conquer the red planet and get the Vitalium!
===========================================================================
El script completo se puede encontrar aquí: solve.py.