Bank-er-smith
7 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes, inverse, GCD
from secret import FLAG, KEY
WELCOME = """
************** Welcome to the Gringatts Bank. **************
* *
* Fortius Quo Fidelius *
* *
************************************************************
"""
class RSA():
def __init__(self, key_length):
self.e = 0x10001
phi = 0
prime_length = key_length // 2
while GCD(self.e, phi) != 1:
self.p, self.q = getPrime(prime_length), getPrime(prime_length)
phi = (self.p - 1) * (self.q - 1)
self.n = self.p * self.q
self.d = inverse(self.e, phi)
def encrypt(self, message):
message = bytes_to_long(message)
return pow(message, self.e, self.n)
def decrypt(self, encrypted_message):
message = pow(encrypted_message, self.d, self.n)
return long_to_bytes(message)
class Bank:
def __init__(self, rsa):
self.options = "[1] Get public certificate.\n[2] Calculate Hint.\n[3] Unlock Vault.\n"
self.shift = 256
self.vaults = {
f"vault_{i}": [b"passphrase", b"empty"]
for i in range(100)
}
self.rsa = rsa
def initializeVault(self, name, passphrase, data):
self.vaults[name][0] = passphrase
self.vaults[name][1] = data
def calculateHint(self):
return (self.rsa.p >> self.shift) << self.shift
def enterVault(self, vault, passphrase):
vault = self.vaults[vault]
if passphrase.encode() == vault[0]:
return vault[1].decode()
else:
print("\nFailed to open the vault!\n")
exit(1)
if __name__ == "__main__":
rsa = RSA(2048)
bank = Bank(rsa)
vault = "vault_68"
passphrase = KEY
bank.initializeVault(vault, passphrase, FLAG)
encrypted_passphrase = rsa.encrypt(bank.vaults[vault][0])
print(f"You managed to retrieve: {hex(encrypted_passphrase)[2:]}")
print("\nNow you are ready to enter the bank.")
print(WELCOME)
while True:
try:
print("Hello, what would you like to do?\n")
print(bank.options)
option = int(input("> "))
if option == 1:
print(f"\n{bank.rsa.n}\n{bank.rsa.e}\n")
elif option == 2:
print(f"\n{bank.calculateHint()}\n")
elif option == 3:
vault = input("\nWhich vault would you like to open: ")
passphrase = input("Enter the passphrase: ")
print(f"\n{bank.enterVault(vault, passphrase)}\n")
else:
"Abort mission!"
exit(1)
except KeyboardInterrupt:
print("Exiting")
exit(1)
except Exception as e:
print(f"An error occurred while processing data: {e}")
exit(1)
Análisis del código fuente
Básicamente, el servidor usa RSA, crea un almacén con un identificador "vault_68" para almacenar una clave secreta (passphrase). Entonces la clave está cifrada (encrypted_passphrase) y la flag se guarda en el almacén:
rsa = RSA(2048)
bank = Bank(rsa)
vault = "vault_68"
passphrase = KEY
bank.initializeVault(vault, passphrase, FLAG)
encrypted_passphrase = rsa.encrypt(bank.vaults[vault][0])
print(f"You managed to retrieve: {hex(encrypted_passphrase)[2:]}")
print("\nNow you are ready to enter the bank.")
print(WELCOME)
Tenemos tres opciones:
- Obtener la clave pública del criptosistema RSA (módulo $n$ y exponente $e$)
- Calcular una pista
- Abrir un almacén
if option == 1:
print(f"\n{bank.rsa.n}\n{bank.rsa.e}\n")
elif option == 2:
print(f"\n{bank.calculateHint()}\n")
elif option == 3:
vault = input("\nWhich vault would you like to open: ")
passphrase = input("Enter the passphrase: ")
print(f"\n{bank.enterVault(vault, passphrase)}\n")
else:
"Abort mission!"
exit(1)
Nos interesa obtener la clave secreta para abrir el almacén y obtener la flag:
def enterVault(self, vault, passphrase):
vault = self.vaults[vault]
if passphrase.encode() == vault[0]:
return vault[1].decode()
else:
print("\nFailed to open the vault!\n")
exit(1)
La pista son los bits más significativos del número primo privado $p$:
def calculateHint(self):
return (self.rsa.p >> self.shift) << self.shift
Como self.shift = 256 y el criptosistema RSA se inicializó para tener una clave de 2048 bits (es decir, $n$ es un número de 2048 bits), entonces $p$ y $q$ tienen 1024 bits cada uno. Por lo tanto, con la pista se nos proporcionan los 768 bits más significativos de $p$.
Contexto de RSA
RSA funciona de manera que, dado un mensaje $m$ en formato decimal, podemos cifrarlo como sigue:
$$ c = m^e \mod{n} $$
La clave pública está formada por $n$ y $e$. Y $n = p \cdot q$, que son dos números primos grandes (guardados como clave privada).
Por otro lado, para descifrar se necesitan dos valores más: $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$, de manera que:
$$ m = c^d \mod{n} $$
Por lo tanto, la mejor manera de descifrar RSA es encontrar una factorización de $n$ (es decir, encontrar $p$ y $q$).
Método de Coppersmith
Este ataque viene bien cuando podemos definir un polinomio $f$ de grado $r$ sobre $\mathbb{Z}/m\mathbb{Z}$ con una raíz $x_0 < m ^ r$. Es decir, $f(x_0) \equiv 0 \pmod{m}$.
Esta vez, podemos definir un polinomio $f(x) = x + p_\text{hint} \pmod{p}$. Sea $x_0 = p - p_\text{hint}$, entonces $f(x_0) = 0$. Como $n = p \cdot q \equiv 0 \pmod{p}$ y $f(x_0) \equiv 0 \pmod{p}$, el retículo (lattice) que construiremos será válido para módulo $n$ también. Trataremos de encontrar la raíz $x_0$ de forma que $p = p_\text{hint} + x_0$, y también sabemos que $x_0 < 2^{256} = R$, por lo que el ataque es posible.
Para más información sobre la implementación, se puede mirar Wikipedia o encontrar algún artículo riguroso sobre el tema. Básicamente, el método de Coppersmith usa la reducción de retículo mediante el algoritmo LLL para encontrar otro polinomio $h$ con coeficientes pequeños que tenga la raíz $x_0$ sobre los números enteros (lo cual es fácilmente resoluble).
Implementación en SageMath
Podemos acotar nuestro polinomio $f(x) = x + p_\text{hint} \pmod{p}$ cambiando $x$ por $R$. Esta será la base de nuestro retículo:
$$ \begin{pmatrix} R & 0 \\ p_\text{hint} & n \end{pmatrix} $$
Tomemos los parámetros necesarios:
$ nc 178.62.21.211 31474
You managed to retrieve: 6e03e9795ba67e61b92fd8dd7732bc48866d3dc1bbf4f5fa6a01d0445cb2b0f6c099a2ab186e884be5fae0086bd8246c138729fe0bdaa010777dbafc45b960e624fcac162a2cafdd63b03be210d5cb3fe63beb7099be1d52a5fb9f688f0a77256fe09bf765450a9e79a36d58519e120104cb9f9409514c80bf8d6ac5097c16bd7a6c43f8afa4bde2c2cb6de421a7d5dc4d71d564af934d4dddedb6adf39ba5ac0e8ed1d9fd2beff76f69ba1c9d1875e07566ff588f0fbeaede0b628683d6dfbd9037fd15b3c84128dd5b659eac9c2939ebd0f5b7d0c826aec270be131d384bdf18dd9154e92d357cad2da0d422efbbfcd28173824a511ebed608e3e2d19cf495
Now you are ready to enter the bank.
************** Welcome to the Gringatts Bank. **************
* *
* Fortius Quo Fidelius *
* *
************************************************************
Hello, what would you like to do?
[1] Get public certificate.
[2] Calculate Hint.
[3] Unlock Vault.
> 1
26272664590454787317352428900080135303036824329225668215899235395498371297220608915287247882099527866486908073714840896632505356593849938005661416313626842832910157870436577746226539583105246910746160039315084401138202814320559979029681260701154933068691946494411441272586267469555487746306431018592741482920298785785255459140818521237201072165071775175131477347714978523756346220471825385097972523551714989714821491387719163336371620584125033335582245505841966988256943130882728184301092573790447077431924690832924860672052042187861402010412129161498191219460963008705942492258678022361012754018835298970470223897723
65537
Hello, what would you like to do?
[1] Get public certificate.
[2] Calculate Hint.
[3] Unlock Vault.
> 2
165827368659014322049070097492184363669461448162202433107877051902713529917252355235212811191092876543125397226502677845569204467693133285626314402419242502597722363061603851825594894065632491081621172917189807107692715075418759526342409775702830301217139670416277399241044094329521480527431296677621650161664
Hello, what would you like to do?
[1] Get public certificate.
[2] Calculate Hint.
[3] Unlock Vault.
>
Para realizar el ataque, usaremos el algoritmo LLL para reducir el retículo y encontrar el vector más corto. Usemos SageMath para hacer los cálculos:
$ sage -q
sage: n = 2627266459045478731735242890008013530303682432922566821589923539549837129722060891528724788209952786648690807371484089663250535659384993800566141631
....: 36268428329101578704365777462265395831052469107461600393150844011382028143205599790296812607011549330686919464944114412725862674695554877463064310185927
....: 41482920298785785255459140818521237201072165071775175131477347714978523756346220471825385097972523551714989714821491387719163336371620584125033335582245
....: 50584196698825694313088272818430109257379044707743192469083292486067205204218786140201041212916149819121946096300870594249225867802236101275401883529897
....: 0470223897723
sage: p_hint = 16582736865901432204907009749218436366946144816220243310787705190271352991725235523521281119109287654312539722650267784556920446769313328562631
....: 44024192425025977223630616038518255948940656324910816211729171898071076927150754187595263424097757028303012171396704162773992410440943295214805274312966
....: 77621650161664
sage: R = 2 ** 256
sage: M = matrix([[R, p_hint], [0, n]])
sage: B = M.LLL()
sage: b = B[0]
sage: h = b[0] / R * x + b[1]
sage: h.roots(ring=ZZ)
[(-165827368659014322049070097492184363669461448162202433107877051902713529917252355235212811191092876543125397226502677845569204467693133285626314402419242502597722363061603851825594894065632491081621172917189807107692715075418759526342409775702830301217139670416277399241044094329521480527431296677621650161664,
1)]
sage: p = p_hint + h.roots(ring=ZZ)[0][0]
sage: p
0
Vemos que SageMath encuentra una solución al polinomio, pero es inútil (da como resultado $p = 0$, que satisface las condiciones, pero no es lo que estamos buscando).
Por lo tanto, podemos definir otro polinomio y agregarlo a la base del retículo. Por ejemplo, $g(x) = (x + p_\text{hint})^2 = x^2 + 2p_\text{hint} x + p_\text{hint}^2 \pmod{p}$ también es bueno porque $g(x_0) \equiv 0 \pmod{p}$. Entonces, la nueva base es:
$$ \begin{pmatrix} R^2 & 0 & 0 \\ 2 p_\text{hint} R & R & 0 \\ p_\text{hint}^2 & p_\text{hint} & n \end{pmatrix} $$
Intentémoslo de nuevo:
sage: M = matrix([[R^2, 2 * p_hint * R, p_hint^2], [0, R, p_hint], [0, 0, n]])
sage: B = M.LLL()
sage: b = B[0]
sage: h = b[0] / R^2 * x^2 + b[1] / R * x + b[2]
sage: h.roots(ring=ZZ)
[(29530888989514148513404894909866751479005495143273888935316777747772562098475,
1)]
sage: x0 = h.roots(ring=ZZ)[0][0]
sage: p = x0 + p_hint
sage: p
165827368659014322049070097492184363669461448162202433107877051902713529917252355235212811191092876543125397226502677845569204467693133285626314402419242502597722363061603851825594894065632491081621172917189807107692715075418759526371940664692344449730544565326144150720049589472795369462748074425394212260139
sage: n % p
0
Y ahí está, tenemos $x_0$ y $p$ y es correcto ya que $n \equiv 0 \pmod{p}$.
SageMath tiene un método llamado small_roots que implementa el mismo procedimiento que hicimos anteriormente, por lo que esta es otra forma de encontrar el valor de $x_0$, solo definiendo un polinomio:
sage: F.<x> = PolynomialRing(Zmod(n))
sage: f = x + p_hint
sage: f.small_roots(R, beta=0.5)
[29530888989514148513404894909866751479005495143273888935316777747772562098475]
Implementación en Python
Podemos hacer lo mismo en Python, importando las funciones de SageMath:
F = PolynomialRing(Zmod(n), names=('x', ))
x = F._first_ngens(1)[0]
f = x + p_hint
x0 = f.small_roots(2 ** 256, beta=0.5)[0]
p = int(x0) + p_hint
assert n % p == 0
Una vez que tenemos $p$, es trivial descifrar RSA.
Flag
Esta es la salida del script:
$ python3 solve.py 178.62.21.211:31474
[+] Opening connection to 178.62.21.211 on port 31474: Done
[*] Encrypted passphrase: 0x6be52642ecb714e40ba08d2b63fc3d79ce382fb53e8eeb996c29af74a984054bc2a76b5d9d0fc666a686e23bf505aef8fa3655d55a605b60eb2f8ac6b71f9f6e2351bfa8907c11f51182da19b2a4225815b7b0e83021e1c7ba0ebe5bd3efd5633656be8a3d6c8a1dfa6c77f1a649d1abb8a0dad9143777063aae97b9ab64440864952a3a03935dbe8e85c2ccf105e88a7f3eef411ab33a1e4cc72a9f9aca0f9952e9e5b4179f65bc373e6f2f7e34d6c360d6bcaadeb2558f2dd79ce369c983f01a01735bad9c76cce488df07a169a3cedab6a584dbd19938f81f4da56cea5c0fcde18f4dff9ef276a686d4db02acbe3d7a628bc49f7be2a3938fb18987fafd2e
[*] n = 14400878729469982456179516687494452333286500328565876899179902248177684629937217718437574488172224931589421772336496454875545580667410777013666908730512676506326371495417352769134980724598935201491425737935374107783194641383396958683973738543114005736271181318832017547519297547749907181376583321445821386086980602987727703970520409980173518180921488588114200254585911928855969631189715050927936842330791032328862242564444667382945377589585072306486446858044652847926709046477233902145148112514558989572835813900935299985542592154182848246093046169114707468712610559700162203477043446118147130087640096909850873541857
[*] p_hint = 159784397383368745375939311753965839025297029017923725686964240287435529885977686929574499753302250206773543871932926191676848988485805867725579997623234684483812283898612216002420484475547343709133508708282274891595350584724954547651974161765498586034599022448579332825909579187656013169640947078699220467712
[*] hex(p_hint) = '0xe38a607cfd071bec8f6a6b928ad21d9a7722e21cdfb811a7fca50bae18c58a60ca92d81a1b4a8d2f9f124756e83e404b1b664e590720fa361f7d8f38cb309fb40e3e5ddf9ff7340295083aae613271b6250944e7092f834d56d97909d24171620000000000000000000000000000000000000000000000000000000000000000'
[+] Passphrase: The_horcrux_is_Helga_Hufflepuff's_cup
[+] Flag: HTB{LLL_4nd_c00p325m17h_15_57111_m491c_70_my_3y35}
[*] Closed connection to 178.62.21.211 port 31474
El script completo se puede encontrar aquí: solve.py.