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 y exponente )
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 :

    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, es un número de 2048 bits), entonces y tienen 1024 bits cada uno. Por lo tanto, con la pista se nos proporcionan los 768 bits más significativos de .

Contexto de RSA

RSA funciona de manera que, dado un mensaje en formato decimal, podemos cifrarlo como sigue:

La clave pública está formada por y . Y , que son dos números primos grandes (guardados como clave privada).

Por otro lado, para descifrar se necesitan dos valores más: y , de manera que:

Por lo tanto, la mejor manera de descifrar RSA es encontrar una factorización de (es decir, encontrar y ).

Método de Coppersmith

Este ataque viene bien cuando podemos definir un polinomio de grado sobre con una raíz . Es decir, .

Esta vez, podemos definir un polinomio . Sea , entonces . Como y , el retículo (lattice) que construiremos será válido para módulo también. Trataremos de encontrar la raíz de forma que , y también sabemos que , 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 con coeficientes pequeños que tenga la raíz sobre los números enteros (lo cual es fácilmente resoluble).

Implementación en SageMath

Podemos acotar nuestro polinomio cambiando por . Esta será la base de nuestro retículo:

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 , 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, también es bueno porque . Entonces, la nueva base es:

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 y y es correcto ya que .

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 , 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 , 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.