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: 194898fd609b747c07b0df862b5f8fc61d87d30b91a6246fa29bd5ae45f353858511fafeb91ecf1a06e10ae5ab07c91c98736b349765af99cdd4f695ef8c814e584ac3532a658c120a85e0a5dba64aad44d6e891be641cb211d59c55d9e7269d48b28363a639742fd61535e4e84de430c0619ccf4bed3cfbbce0700743b187f5dd9d505bcfb8f97a61840934486f442d334aaee721baf3870a60d1b7137fcbd46a71b140c46a67f4062288e070676998945f33ed3d8ee3e4801871f1d77299bc42816947f6640d6ba9ebf756b9b29bbf9296f1dd2cc72a694b7f57f8cc2470673aedbe6bf1938380f68c6986e36811d40741151e595599aa7b6c0f067025d63c
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: 0x78c3befdd0808bd7a5c5ef27b57942ee93b5c26e5648767ad4a315ffc4a4f51525f3b52d821a3cfecd5492eb41cc641836034a7a9f5c1e66dc5a59af2b7fe9ca0d0131d237e0dd9dce371d868e440cc6f9b7a5ed00ba081a93595a741f2383973dd56590c78e223b80f68168cb19a97b06996f052c86eb73d323368007ab65763566da32dc54f9fb1d7047896f0332bc63eecc038381d50cec44d7921b4073e0a37d468c70600b1bbb614027bf3925ef63f40cb02de917c00287c2c18a4ddcd9d2513d32c044b5f6abb19df282a637547cbe7efc862e3d8aa08bf03c02077c1aa6056112f34b28ef7c87f6dd6c50612f0ec3f889a57c48c96aa2c476ef66f055
[*] n = 16342523985659798453585315405858755196045597037411811583943549229160966505177123482225687334207825904075504302452144813180041593980127673037781237712646376447276239438367346327341562929597349029806390301853276811829059721019470061841762216620852848761224170958070114201287374520148481854323985892179833450165355728759966101384579900309612316614838381108170543834647543991291108580693298177666282529040199105907513598645518072018003814857256193756752027897026591034770548641573671078676480387271973721854707549399174257465702830638041333666811838070115317082769271173135011417687584296619466506693731238583711935626173
[*] p_hint = 137726791065496950470318193030667973409629720750887907239138874007325238628430190124644545799750974619466485559752534008664792711791342893313990076940138744260463081999177846577289076112399561549395008225778574526580575004510914556711889633473036983333031744734848179239068387585105045927699478941810846334976
[*] hex(p_hint) = '0xc4212456e6ff758bbf64b26f3a2641146324a69990d855467960012f2d4a6ddf16a6358a40bacf3ad6fce4ec15f95edee42d99227fe382954b5e00e75a2c2eab25c11ee46aac5aab65db7d0a2b0de0d17b539c03b422b0df32123aed79e135cb0000000000000000000000000000000000000000000000000000000000000000'
[+] Passphrase: horcrux_horcrux_Helga_Hufflepuff's_cup
[+] Flag: HTB{c00p325m17h_15_57111_m491c!}
[*] Closed connection to 178.62.21.211 port 31474
El script completo se puede encontrar aquí: solve.py.