3 Lessons for applied crypto from HTB 2023 — The Great Escape
Introduction:
I recently participated in HTB 2023 Business CTF — The Great Escape with a few of my colleagues at Microsoft and solved some of the crypto(graphy) challenges. Over 900 teams from across the world took part in this event. CTF’s are a great way to practice cybersecurity skills. It’s been a while since I played a CTF, but I found this contest extremely engaging . I learnt a lot and wanted to share my solutions to some of the interesting challenges and some real-world lessons that I think apply well beyond this CTF. I’d highly recommend giving HackTheBox a shot if you’re interested in learning more about security.
If you’d rather skip the details of the solution and see the conclusion, you can jump to the lessons learnt at the bottom of the page.
Challenge : Interception
This was one of my favorite challenges as the solution requires combining multiple concepts and the challenge throws light on some real-world software security anti-patterns.
In this challenge, we’re provided with a server that supports 3 commands —
- Send Encrypted Message
- Reveal Internal Plans
- Forgot Decryption Key
source code for the server application is shown below:
#!/usr/bin/env python3
import signal
import random, os
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from pool import GREET, ANS
from secret import RESTRICTED
class GRAS:
def __init__(self, m, p, q):
self.m = m
self.a = 0xdeadbeef
self.p = p
self.q = q
def generate_key(self):
ct = 0x1337
# this loop runs in milliseconds in our super computer
for _ in range(self.m):
ct = pow(ct, self.a, self.m)
return long_to_bytes(ct)[:16]
class OumaraSystem:
def __init__(self, bits):
self.BITS = bits
self.LIMIT = 2
self.p = getPrime(self.BITS//2)
self.q = getPrime(self.BITS//2)
self.N = self.p * self.q
self.e = 0x10001
self.d = pow(self.e, -1, (self.p-1)*(self.q-1))
self.prng = GRAS(self.N, self.p, self.q)
def encrypt(self, m):
m = bytes_to_long(m.encode())
assert 0 < m < self.N
enc_msg = long_to_bytes(pow(m, self.e, self.N))
return enc_msg
def encrypt_plans(self):
self.symmetric_key = self.prng.generate_key()
cipher = AES.new(self.symmetric_key, AES.MODE_ECB)
enc_plans = [cipher.encrypt(pad(r.encode(), 16)) for r in RESTRICTED]
return enc_plans
def send_encrypted_message(self, c):
if c > 1:
m = pow(c, self.d, self.N)
try:
msg = long_to_bytes(m).decode()
return True
except:
pass
return False
def reveal_internal_plans(self, encrypted_plans, key):
cipher = AES.new(key, AES.MODE_ECB)
plans = [unpad(cipher.decrypt(ep), 16).decode() for ep in encrypted_plans]
return plans
def hash_verified(self, h):
return h == sha256(str(self.N).encode()).digest()
def generate_token(self):
d = self.q.bit_length() - 643
return ((self.q >> d) << d) | random.getrandbits(d)
def show_banner():
print('''
___ ____ ____ _ _
/ _ \ _ _ _ __ ___ __ _ _ __ __ _ / ___| ___ ___ _ _ _ __ ___ / ___| |__ __ _ _ __ _ __ ___| |
| | | | | | | '_ ` _ \ / _` | '__/ _` | \___ \ / _ \/ __| | | | '__/ _ \ | | | '_ \ / _` | '_ \| '_ \ / _ \ |
| |_| | |_| | | | | | | (_| | | | (_| | ___) | __/ (__| |_| | | | __/ | |___| | | | (_| | | | | | | | __/ |
\___/ \__,_|_| |_| |_|\__,_|_| \__,_| |____/ \___|\___|\__,_|_| \___| \____|_| |_|\__,_|_| |_|_| |_|\___|_|
''')
def menu():
print('=======================================')
print('|| ||')
print('|| [S]end your encrypted message ||')
print('|| [R]eveal internal plans ||')
print('|| [F]orgot decryption key ||')
print('|| ||')
print('=======================================')
return input('> ').upper()[0]
def print_plans(plans):
print('==================== CLASSIFIED CONTENT! DO NOT SHARE! ====================')
for i, p in enumerate(plans):
print(f'Plan {i+1} : {p}')
print('===========================================================================')
def main():
#crypto = PopperSystem(2048)
crypto = OumaraSystem(2048)
encrypted_plans = crypto.encrypt_plans()
show_banner()
print('This channel aims at secure communication via asymmetric encryption.')
print(f'We say : {crypto.encrypt(random.choice(GREET)).hex()}')
while True:
ch = menu()
if ch == 'S':
enc_msg = int(input('You say : '), 16)
verified = crypto.send_encrypted_message(enc_msg)
if verified:
print(f'Nice! We say : {crypto.encrypt(random.choice(ANS)).hex()}')
else:
print(f'Nice! We say : {os.urandom(256).hex()}')
elif ch == 'R':
print('Our plans are encrypted via symmetric encryption and protected with our unique super computer that will take us to the Red Planet!')
key = bytes.fromhex(input('Enter decryption key : '))
plans = crypto.reveal_internal_plans(encrypted_plans, key)
print_plans(plans)
exit(0)
elif ch == 'F':
h = bytes.fromhex(input('Before giving you the token, you must prove me that you know the public key : '))
if crypto.hash_verified(h):
token = crypto.generate_token()
print(f'Here is your token : {token}')
print('Make sure you do not forget it next time!')
else:
print('Get out!')
else:
print('Hey, this is suspicious! Terminating the channel...')
exit(0)
if __name__ == '__main__':
# signal.alarm(900)
main()Looking through the source code for the server that was shared, we know that the plans were encrypted using a symmetric key and the request to ‘Reveal Internal Plans’ would ultimately reveal the internal plans and presumably the flag. But it requires sending the correct decryption key.
To understand how this key is generated in the first place, we look through the function generate_key:
class GRAS:
def __init__(self, m, p, q):
self.m = m
self.a = 0xdeadbeef
self.p = p
self.q = q
def generate_key(self):
ct = 0x1337
# this loop runs in milliseconds in our super computer
for _ in range(self.m):
ct = pow(ct, self.a, self.m)
return long_to_bytes(ct)[:16]
# ......
# invocation of GRAS
# ......
class OumaraSystem:
def __init__(self, bits):
self.BITS = bits
self.LIMIT = 2
self.p = getPrime(self.BITS//2)
self.q = getPrime(self.BITS//2)
self.N = self.p * self.q
self.e = 0x10001
self.d = pow(self.e, -1, (self.p-1)*(self.q-1))
self.prng = GRAS(self.N, self.p, self.q)The symmetric key is clearly generated via exponentiation — the constant 0x1337 is raised to the constant 0xdeadbeef and reduced modulo ’N’ where N is the RSA public modulus of the Oumara system’s internal public-private key pair, and the whole process is repeated ’N’ times in a loop and the last 16 bytes of the output are used as the symmetric key to encrypt the plans.
We could rewrite the key generation effectively as follows:
def generate_key(N: int):
ct = 0x1337
a = 0xdeadbeef
key = pow(ct, a ** N, N)
return long_to_bytes(key)[:16]The first step to generating the key is to recover the RSA modulus (N).
Compute RSA modulus ’N’ from ciphertexts:
We know the exponent e is 65537. However, the RSA modulus is not directly revealed in this challenge. Looking at the Oumara system’s send_encrypted_message function, it’s clear that RSA encryption is applied without any padding scheme (such as OAEP) which leads to deterministic encryptions.
RSA encryption without padding works as follows:
c1 = m1 ** e mod N
c2 = m2 ** e mod N
# t1 => c1 - m1 ** e = 0 mod N
# t2 => c2 - m2 ** e = 0 mod Nfrom the above equations, it should be evident that N divides x and y. We could easily compute the greatest common divisor i.e. GCD(t1, t2) to identify ’N’ the public modulus.
The response ciphertexts from the challenge server are randomized i.e we don’t know which of the 3 ANS messages the respective encryptions correspond to — This is easy, we just need to try all 3 possible message choices as follows
import gmpy2
def find_public_key(m0: int, c0: int, m1: int, c1: int) -> int:
pub_exp = 0x10001
# small messages unlikely to wrap around 2048 bit modulus
t1 = c0 - pow(m0, pub_exp)
t2 = c1 - pow(m1, pub_exp)
return gmpy2.gcd(t1, t2)
ans_msgs = [
bytes_to_long(b'Great news, but use this channel responsibly.'),
bytes_to_long(b'I will inform the governor.'),
bytes_to_long(b'Bye!')
]
if __name__ == "__main__":
ans_cts = [
bytes_to_long(
bytes.fromhex('1b44d6f1e24a7d2f975dc1e2cf0eb1313006fa3a0e21d69e2a0ae539c5f721a36dc941e1d6c47f12e3c4c4210e55ab9eff4d3764be400ee0696888805a91493403ccb8c76e7342e075167b5079de70ebac6e9eebec2fcf24ceba480470001b4089220361187f39b58eef2513980e4e05e2a1a6066da1c5fd5898c533a17d5d31d9df880ab407b1786244a78ab270018d84901f838e3bd84a71ab2f4cc3fcf57cac6267e479e39cd792fa409149a24305a58ba94a4990b78cd23cc7e440af35961f136da7f8087787071453428914b46c40de6a0ab75eaea91f55fe942643c0eef3dbdaffd014a12cd7669bf18832f94726bf7c0d8011ac133eae3d38e838979a')
),
bytes_to_long(
bytes.fromhex('03af6c96db108c4d0e12d588434c656785cbf5220a6a5fed2f1a7e6ac5a96b05036dba2ffdff261dedc93a608812695a796727fd519a2d31e63585e4ff4435b7daf67e6ef698c9988c07d2d3a38e9d48fff4931d5c3f331a8173c5e9820c2a1a711c3f82f26595a9753bfd91e838c9668105f9441f0076819606cb28515bfbf5c23206d0e197921c5feaeb9924c7f099471158a38404613af8f5335ce07f00361ad57c6ae5c0a5e39539151ea3cfed762e9212cc4cb8a7691024ab0601dcb25f392b5acd2e492e7b39a2c5007f7c68c109265c607beba4bf727d18023e8385e62bd7b7ce679be85dda7030995b714985b1e912930934ed2fab177ea90c9cb362')
),
bytes_to_long(
bytes.fromhex('0faf324c33c299bdd76c5e56cd7bb9b1df1aad466b68fb5dd109fd1494901c0cb9bfd63c18f5f96662d2516fc76224fbc178b35f353dc4c35d1eb9074e8e97f829254dbcce6b4f4346ab433fa4c7eeaea1045996bab5e5ab6f931e84ada715ed46dc3ad99c5871d513d421c14494e5ff20301d1687cb3c0cec7323723c287131d421faa24b8fb1111ac528759a07ba12e4a27755d74241c461883f35b15aa7a866a06f1a55a1ab0c6cef6d8fd84e9ea5a97e1bdd114d8a8cf777949dc9b18f51f61ef5e18dd54d04c8959a86e4e970aa361288c30b7b56336481f4582b23348cd5430868feeee07599a5ca5e4f9345cd02a0ae9d10d649ad4083eec3460aa756')
)
]
N = 1
public_keys = []
for i, ans_msg2 in enumerate(ans_msgs):
for j, ans_msg in enumerate(ans_msgs):
for k, ans_ct in enumerate(ans_cts):
print (f'finding factors for i: {i}, j : {j}, k : {k}')
factor = find_public_key(ans_msg2, ans_cts[k], ans_msg, ans_cts[ (k+1) % 3 ])
if factor != 1 and factor > 100:
public_keys.append(factor)
for pub_key in public_keys:
print (f'pub_key : {pub_key}, hash : {get_public_key_hash(pub_key)}')Exponentiation (Slow):
When we run the key generation function from the challenge server with the public key we just obtained, we quickly see that it’s extremely inefficient — Now the comment in the generate_key function (‘ this loop runs in milliseconds in our super computer’) makes sense….
Obtain private key from leaked bits of ‘q’ — Coppersmith’s method:
Looking at the Forgot Decryption Key method, we see that it leaks 643 bits of one of the prime factors (each factor is 1024 bits) of the private key (say ‘p’). This is somewhat reminiscent of the heartbleed bug. Applying coppersmith’s theorem, we can re-cast the problem of finding all bits of ‘p’ from the leaked bits of ‘p’, as an equivalent problem of finding small roots of a polynomial equation, which can be solved efficiently using LLL. (See: Recovering cryptographic keys from partial information for an excellent survey of this class of issues).
We use the following sage code to recover all bits of ‘p’ as follows :
Once we obtain ‘p’, it’s trivial to factor the modulus ’N’ to recover the other prime factor ‘q’ as shown below:
Knowing the prime factorization of N allows us to compute the euler’s totient phi(N) = (p -1) * (q -1)
why is this even relevant here? if you take a closer look at the key generation, we can rewrite it as follows
ct = 0x1337
a = 0xdeadbeef
t = pow(a, M)
key = pow(ct, a, M)Since the key is generated using RSA exponentiation, the exponents operate in modulo phi(N) i.e.
t = a ** N = a ** N mod phi(N)knowing phi(N) allows us to reduce a ** N to a ** N mod phi(N) which can be computed very efficiently,
e = 65537
a = 0xdeadbeef
ct = 0x1337
# p, q are prime factors of 'N' obtained from coppersmith method
phi = (p - 1) * (q - 1)
# compute secret key exponents
t = pow(a, N, phi)
sk = long_to_bytes(pow(ct, t, N))[:16]
print (f'secret key : {sk.hex()}')Now we can send the decryption key to ‘Reveal Internal Plans’ and the server returns the flag: HTB{th3y_d3f1n1t3ly_d0nt_h4v3_a_sUp3r_c0mPut3r!}
Lessons Learnt:
- Public Keys must be assumed to be Public:
A public key (by definition) must be treated as a public value. Algorithms such as RSA are not designed to keep public keys safe from leaking, so systems should never rely on public keys being secret for any form of security.
2. if you didn’t use /dev/urandom for generating keys on Linux, you probably got it wrong:
Poor entropy has been the bane of many crypto systems. This is an area where we should opt for plain, boring, known safe methods— call /dev/urandom (or the crypto random generator supported by your respective OS) instead of fancy or complex custom algorithms that are bound to be broken.
3. Memory Leak vulnerabilities are insidious and hard to defend:
Memory safety bugs are a huge problem for today’s software. The ‘Forgot Decryption Key’ workflow in the challenge mimics (in some sense) a heartbleed style bug where memory is leaked and an attacker obtains access to parts of a private key.
Partial leak of a private key is as bad as a full leak in many cases as we demonstrated. That said, this prompted a deeper thought- How do we protect against such problems at scale? That’s probably a topic for another blog post (stay tuned)…..
References:
- https://hackthebox.com/
- Recovering Cryptographic keys from partial information, by example
- https://en.wikipedia.org/wiki/Coppersmith_method
- Mining your P’s and Q’s: Detection of widespread weak keys in network devices
- https://heartbleed.com/
- https://linux.die.net/man/4/urandom
- https://docs.python.org/3/library/secrets.html
- https://msrc.microsoft.com/blog/2019/07/a-proactive-approach-to-more-secure-code/
- https://security.googleblog.com/2022/12/memory-safe-languages-in-android-13.html
- https://www.memorysafety.org/docs/memory-safety/