<- HTB UNICTF

Bank-er-smith

7 minutes to read

We got the Python source code of the server:

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)

Source code analysis

Basically, the server uses RSA, creates a vault with an identifier "vault_68" to store a secret key (passphrase). Then the key is encrypted (encrypted_passphrase) and the flag is stored in the vault:

    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)

We are given three options:

  1. Get the public key for the RSA cryptosystem (modulus $n$ and exponent $e$)
  2. Calculate a hint
  3. Open a vault
            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)

We are interested in obtaining the secret key in order to open the vault and get the 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)

The hint are the most significant bits of the private prime number $p$:

    def calculateHint(self):
        return (self.rsa.p >> self.shift) << self.shift

Since self.shift = 256 and the RSA cryptosystem was initialized to have a 2048 bit key (that is $n$ is 2048 bits long), then $p$ and $q$ are 1024 bits long. Therefore, with the hint we are provided with the 768 most significant bits of $p$.

RSA background

RSA works so that, given a message $m$ in decimal format, we can encrypt it as follows:

$$ c = m^e \mod{n} $$

The public key is formed by $n$ and $e$. And $n = p \cdot q$, which are two big primes (kept as private key).

On the other hand, the decryption needs two more values: $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$, so that:

$$ m = c^d \mod{n} $$

Therefore, the best way to decrypt RSA is to somewhat find the factorization of $n$ (that is, finding $p$ and $q$).

Coppersmith method

This attack comes into place when we can define an $r$-degree polynomial $f$ under $\mathbb{Z}/m\mathbb{Z}$ with a root $x_0 < m ^ r$. That is to say that $f(x_0) \equiv 0 \pmod{m}$.

This time, we can create a polynomial $f(x) = x + p_\text{hint} \pmod{p}$. Let $x_0 = p - p_\text{hint}$, then $f(x_0) = 0$. Since $n = p \cdot q \equiv 0 \pmod{p}$ and $f(x_0) \equiv 0 \pmod{p}$, the lattice we will construct is valid for modulo $n$ as well. We aim to find the root $x_0$ so that $p = p_\text{hint} + x_0$, and we also know that $x_0 < 2^{256} = R$, so the attack is feasible.

For more information on the implementation, you can see Wikipedia or find a more rigorous paper regarding this topic. Basically, Coppersmith method uses LLL lattice reduction to find another polynomial $h$ with short coefficients that has root $x_0$ over the integers (which is easily solvable).

SageMath implementation

We can bound our polynomial $f(x) = x + p_\text{hint} \pmod{p}$ changing $x$ by $R$. This will be the lattice basis:

$$ \begin{pmatrix} R & 0 \\ p_\text{hint} & n \end{pmatrix} $$

Let’s take the needed parameters:

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

>

To perform the attack, we will use the LLL algorithm to reduce the lattice and find the shortest vector. Let’s use SageMath to do the computations:

$ 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

We see that SageMath does find a solution to the polynomial but it is useless (it results in $p = 0$, which satisfies the conditions but it is not what we are looking for).

Thus, we can define another polynomial and add it to the lattice. For instance $g(x) = (x + p_\text{hint})^2 = x^2 + 2p_\text{hint} x + p_\text{hint}^2 \pmod{p}$ is also good because $g(x_0) \equiv 0 \pmod{p}$. Then, the new basis of the lattice is:

$$ \begin{pmatrix} R^2 & 0 & 0 \\ 2 p_\text{hint} R & R & 0 \\ p_\text{hint}^2 & p_\text{hint} & n \end{pmatrix} $$

Let’s try again:

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

And there it is, we have $x_0$ and $p$ and it is correct since $n \equiv 0 \pmod{p}$.

SageMath has a method called small_roots that implements the same procedure we did above, so this is another way of finding the value of $x_0$, just defining one polynomial:

sage: F.<x> = PolynomialRing(Zmod(n))
sage: f = x + p_hint
sage: f.small_roots(R, beta=0.5)
[29530888989514148513404894909866751479005495143273888935316777747772562098475]

Python implementation

We can do the same in Python, importing SageMath’s functions:

    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

Once we have $p$, it is trivial to decrypt RSA.

Flag

This is the output of the solution 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

The full script can be found in here: solve.py.