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