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: 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.
>
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: 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
The full script can be found in here: solve.py.