Introduction
Recently, I participated in 2021 Synack Red Team Five Open Invitational CTF . I was able to finish all 25 challenges and placed 14th out of 333 teams.
It’s a bummer I didn’t get into the top 10 to get the HTB VIP subscriptions, but better luck next time.
As of now, I’ll only have time to have a writeup of the crypto challenges. For this CTF there are 4 challenges which:
- Weak RSA (Super Easy): Basic attacks when the modulo N has known factors
- Leakeyd (Easy): How to factor module N with private key of RSA (known expondents e and d)
- Spy (Easy): Classic meet-in-the-middle attack similar to Triple DES with some guessing/fuzzing needed to find the plaintext.
- Suspicious Signing (Medium/Hard): The server’s ECDSA’s nonce is based on the message’s MD5 hash. Sending two messages with hash collision will trick the server into reusing a nonce. Which allows us to use the well known ECDSA nonce reuse attack.
For raw files of the challenges, you can find them in pberba/ctf-solutions
Crypto Challenges
Weak RSA (225 points, 157 solves)
Problem
In this you are just given:
pubkey.pem: RSA public key fileflag.enc: an encrypted flag.
Solution
When these are all that is given in CTF competitions, it should be clear that it is really trying to “crack” the RSA public key to recover the private key.
For these types of questions, always to use RsaCtfTool which has a suite of well known attacks on weak RSA keys. If it fails, then we can start analyzing the problem deeper.
/opt/RsaCtfTool/RsaCtfTool.py --publickey "pubkey.pem" --uncipherfile flag.encleaky (440 points, 44 solves)
Problem
You are given the following source code
from Crypto.Util.number import getPrime, bytes_to_longfrom math import gcdflag = open("flag.txt").read().strip().encode()p = getPrime(1024)q = getPrime(1024)n = p * qe1 = 0x10001e2 = 0x13369print(e1, e2)assert gcd(p-1,e1) == 1 and gcd(q-1, e1) == 1 and gcd(p-1,e2) == 1 and gcd(q-1, e2) == 1phi = (p-1) * (q-1)d1 = pow(e1, -1, phi)print(f"""Retrieved agent data:n = {n}e = {e1}d = {d1}""")ct = pow(bytes_to_long(flag), e2, n)print(f"""Spy messages: e = {e2}ct = {ct}""")And the output of this message.
Retrieved agent data:n = 13382530295713917123015356265347321094256226566257623545889573061147938007171086142592829334764528434702825531635566369283255332692678671260069812638573184350572810970644394853227367978599113205187410151008372135364394060295976954722797560959041525038250922497629995447141186387045145641624575553004116393538045115640382007521177506372844356599515221123769808759792921557288910541261662071330605482964244218808384883839567178211155363863011452476524600201011039875767940325127282609196357565459539854467622590648672354346990722180911082058098493886116049202007545709584770864598362673608862923836981014279206273097017e = 65537d = 11569455444932772576648367415079245594982518040054082958680004127416877055866142769229969703359760929755598958930190874633423572023464427060332872186341753191857337442586174582207855332582641194737450361411604871225045984226459287130693565601375936121842940123452710408534497128602222588204605057938374149336484991344046184969452360503325068483025278799356513681880021469192847751113510298088839230617951595758843109007278029595681232283778797485901135862107038739149351060518772094867682593519162349240597142862357240797932956424470777291496596508787661226345849862222655652073745922761860271975329314656555016312713Spy messages:e = 78697ct = 4461852328415864419743101452420387961651156933673863713694420947402421429869721670364426655092362407263142072234174378248471219392117855386367222894744130407609532370830178750575600387702022233241268782964579737764081573978397550577590335855096601816184948403341545535505335757184765869011562485472974997984468216491217981788679749360213892759733091674873206632032015518889157979003123181968736952658371579666643477038906444823824649861271863876401740198790710014620615022343576676868923683803704170440327497263852960257492740456717562069360762813846260931117680928543379201453514283942164106220549947266176556883803Solution
For this, we have two RSA keys, K1 and K2 that have a common modulo N. We are given the private key of K1 through the value of d1
d1 = pow(e1, -1, phi) # private key of K1 It is important to realize that if you have the value of e1, d1, and N, it is enough to help you factorize N into p and q. Of course, with p and q, finding the private key of K2 (which also uses the same N, p and q) should be trivial.
If you do not know how to do this, you would need to google something like “RSA Prime Factorization with Private Key” which leads you to a stackexchange forum post.
Review of RSA
Recall these three fundamental equations from RSA
\[N = pq \tag{1}\]\[(p-1)(q-1) = \phi \tag{2}\]\[d_1 \equiv e_1^{-1} \mod \phi \tag{3}\]
We express (3) as equality with some integer k
\[d_1 \equiv e_1^{-1} \mod \phi\]\[d_1 * e_1 \equiv 1 \mod \phi\]\[d_1 * e_1 = 1 + k * \phi\]\[d_1 * e_1 - 1 = k * \phi\]\[d_1 * e_1 - 1 = k * \phi\]\[\frac{d_1 * e_1 - 1}{\phi} = k \tag{4}\]
How do we find k if phi is unknown? Well we know that since p and q are large, then
\((p-1)(q-1) \approx p * q\)\(\phi \approx N\)
Therefore we can approximate k from (4) using N, which we know,
\[\frac{d_1 * e_1 - 1}{N} \approx k \tag{5}\]
Since phi < N then K, and if N is large enough, then K is most probably ceil(d_1 * e_1 - 1 / N).
In python, we can find this using
k = (e1*d1) // n + 1assert (e1 * d1 - 1) % k == 0 # To check that we are correctNow that we have K, N, e1 and e2, we have a system of two equations with only two unknowns, p and q.
\[N = pq \tag{1}\]\[d_1 * e_1 - 1 = k * (p-1) * (q-1)\]
Two equations and two unknowns? This is high school algebra.
Here are some of my scratch notes from this
# First we find (p+q)e1*d1 = (p-1)*(q-1) * k + 1(e1 * d1 - 1) / k = (p-1)*(q-1)(e1 * d1 - 1) / k = p*q - q - p + 1(e1 * d1 - 1) / k = N - q - p + 1(e1 * d1 - 1) / k - 1 - N = - q - pp + q = N + 1 - (e1 * d1 - 1) / k = X# Then we use isolate `p and substitute it in N = pqp = X - qn = q * (X - q)0 = X*q - q*q - nq*q - X*q + n = 0# Quadratic equationThe python code to compute this is
X = n + 1 - (e1*d1 - 1) // ka = 1b = Xc = np = -(-b + gmpy2.isqrt(b**2 - 4*a*c)) // (2*a)q = n // p# Always sense check values assert n % p == 0assert (p*q) == n assert isPrime(p) assert isPrime(q)With p and q you should be able to find the private key of k2 and decrypt the flag.
Full Solution
import gmpy2from math import gcdfrom Crypto.Util.number import isPrime, long_to_bytes, inversen = 13382530...e1 = 65537d1 = 115694...e2 = 78697ct = 4461852...# Step 0 find kk = (e1*d1) // n + 1assert (e1 * d1 - 1) % k == 0# Step 1 find p and qX = n + 1 - (e1*d1 - 1) // ka = 1b = Xc = np = -(-b + gmpy2.isqrt(b**2 - 4*a*c)) // (2*a)q = n // passert n % p == 0assert (p*q) == n assert isPrime(p) assert isPrime(q)# Step 2 decrypt flagphi = (p-1)*(q-1)pt = pow(ct, d2, n)print(long_to_bytes(pt))# HTB{tw4s_4-b3d_1d34_t0_us3-th4t_m0dulu5_4g41n-w45nt_1t...}spy (475 points, 26 solves)
Problem
Here is the source code given but I have removed some code to make it more readable.
Some things to look at:
keygenfunction, how many bytes are truly random?- In encryption, AES is doubled but is key strength doubled?
from Crypto.Cipher import AESimport randomimport timeimport base64BIT_SIZE = 256BYTE_SIZE = 32... def keygen(): random.seed(BYTE_SIZE) h = random.getrandbits(BIT_SIZE) for i in range(BIT_SIZE): random.seed(time.time()) h = h ^ random.getrandbits(2*BIT_SIZE/BYTE_SIZE) return hex(h)[2:-1]def encrypt(data, key1, key2): cipher = AES.new(key1, mode=AES.MODE_ECB) ct = cipher.encrypt(pad(data)) cipher = AES.new(key2, mode=AES.MODE_ECB) ct = cipher.encrypt(ct) return ct...if __name__ == "__main__": #message = [REDUCTED] #flag = [REDUCTED] key1 = keygen() key2 = keygen() key1 = key1.decode('hex') key2 = key2.decode('hex') ct_message = encrypt(message, key1, key2) ct_flag = encrypt(flag, key1, key2) with open('packet_6.txt.enc', 'w') as f: f.write(base64.b64encode(ct_message)) with open('flag.txt.enc', 'w') as f: f.write(base64.b64encode(ct_flag))You are given the ciphertext as well as sample plaintexts for the packets.
Plantext packet 3:'''Report Day 49: Mainframe: Secure Main Control Unit: Secure Internal Network: Secure Cryptographic Protocols: Secure '''Plantext packet 4:'''Report Day 50: Mainframe: Secure Main Control Unit: Secure Internal Network: Secure Cryptographic Protocols: Secure ''' Plantext packet 5:'''Report Day 51: Mainframe: Secure Main Control Unit: Secure Internal Network: Secure Cryptographic Protocols: Insecure ''' Key Generation
Look at the code for key generation
def keygen(): random.seed(BYTE_SIZE) h = random.getrandbits(BIT_SIZE) for i in range(BIT_SIZE): random.seed(time.time()) h = h ^ random.getrandbits(2*BIT_SIZE/BYTE_SIZE) return hex(h)[2:-1]Notice that the initial value of h is not random since the seed is static.
random.seed(BYTE_SIZE)h = random.getrandbits(BIT_SIZE)Also, notice that the code in the loop only modifies the last 16 bits of h
h = h ^ random.getrandbits(2*BIT_SIZE/BYTE_SIZE) # only touches the last 16 bits of hTherefore, we only have to brute force 16 bits per key.
Double AES / Triple DES
def encrypt(data, key1, key2): cipher = AES.new(key1, mode=AES.MODE_ECB) ct = cipher.encrypt(pad(data)) cipher = AES.new(key2, mode=AES.MODE_ECB) ct = cipher.encrypt(ct) return ctThis way of encrypting the plaintext twice does not double the strenght of the encryption. This is very similar to the classic Triple DES.
This is vulnerable to the “meet in the middle attack” which is possible if we have known plaintext and ciphertext pair.
“Guessing” the plaintext
The example plaintexts is not really clear on the exact formating of the packet plaintext.
'''Report Day 51: Mainframe: Secure Main Control Unit: Secure Internal Network: Secure Cryptographic Protocols: Insecure ''' Do I include the ticks? Do I add a newline at the end? Etc…
In the end, I just created a template of the plaintexts and tried to iterate on the different guesses of the plaintex.
I used the following template and
msg = f"""{prefix}Report Day {day}: Mainframe: {s1} Main Control Unit: {s2} Internal Network: {s3} Cryptographic Protocols: {s4} {suffix}"""So all in all, just brute force using meet-in-the-middle attack on the 16 random bits of key1 and key2, while guessing the proper plaintext
Full Solution
Here is the full solution. The nested for-loops is an eyesore but it gets the job done.
random.seed(BYTE_SIZE)key = random.getrandbits(BIT_SIZE)key_low = key - (key % (1<<16))key_high = key_low + (1<<16)ct = {}for day in [52, 53, 54, 55]: for s1 in ['Insecure', 'Secure']: for s2 in ['Insecure', 'Secure']: for s3 in ['Insecure', 'Secure']: for s4 in ['Insecure', 'Secure']: for prefix in ['', '\n']: for suffix in ['', '\n']: msg = f"""\{prefix}Report Day {day}: Mainframe: {s1} Main Control Unit: {s2} Internal Network: {s3} Cryptographic Protocols: {s4} {suffix}""" msg = pad(msg).encode() for k1 in range(key_low, key_high): cipher = AES.new(long_to_bytes(k1), mode=AES.MODE_ECB) _ct = cipher.encrypt(msg) ct[_ct] = k1with open('packet_6.txt.enc') as f: msg_ct = base64.b64decode(f.read())for k2 in range(key_low, key_high): cipher = AES.new(long_to_bytes(k2), mode=AES.MODE_ECB) _ct = cipher.decrypt(msg_ct) if _ct in ct: print(ct[_ct], k2) k1 = ct[_ct] k2 = k2 break# k1, k2 = 27534775351079738483622454743638381042593424795345717535038924797978770229648, 27534775351079738483622454743638381042593424795345717535038924797978770265131with open('flag.txt.enc') as f: ciphertext = base64.b64decode(f.read())p1 = AES.new(long_to_bytes(k2), mode=AES.MODE_ECB).decrypt(ciphertext)p2 = AES.new(long_to_bytes(k1), mode=AES.MODE_ECB).decrypt(p1)print(p2)Suspicious Signing (650 point, 21 solves)
Problem
You are given the following source code and you would have to interact with a server to get the flag.
from hashlib import md5from Crypto.Util.number import bytes_to_long, long_to_bytesfrom Crypto.Cipher import AESfrom Crypto.Util.Padding import padfrom ecdsa import ellipticcurvefrom ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_keyfrom random import randintfrom os import urandomflag = open("flag.txt").read().strip().encode()G = generator_256order = G.order()def genKey(): d = randint(1,order-1) pubkey = Public_key(G, d*G) privkey = Private_key(pubkey, d) return pubkey, privkey def ecdsa_sign(msg, privkey): hsh = md5(msg).digest() nonce = md5(hsh + long_to_bytes(privkey.secret_multiplier)).digest() * 2 sig = privkey.sign(bytes_to_long(msg), bytes_to_long(nonce)) return msg, sig.r, sig.sdef encryptFlag(privkey, flag): key = md5(long_to_bytes(privkey.secret_multiplier)).digest() iv = urandom(16) cipher = AES.new(key, AES.MODE_CBC, iv) ciphertext = cipher.encrypt(pad(flag, 16)) return ciphertext, iv pubkey, privkey = genKey()ct, iv = encryptFlag(privkey, flag)print(f"""Encrypted flag: {ct.hex()}iv: {iv.hex()}""")while True: msg = input("Enter your message in hex: ") try: msg = bytes.fromhex(msg) m, r, s = ecdsa_sign(msg, privkey) print(f"""Message: {m.hex()}r: {hex(r)}s: {hex(s)}""") except: print("An error occured when trying to sign your message.")Initial Analysis
Notice that in the encryptFlag the AES key is generated from the secret exponent of the ECDSA key privkey.secret_multiplier.
Therefore, the main objective is to try to somehow recover the private key of the ECDSA.
A big clue here is that the nonce used in the encryption is not really a nonce.
def ecdsa_sign(msg, privkey): hsh = md5(msg).digest() nonce = md5(hsh + long_to_bytes(privkey.secret_multiplier)).digest() * 2 ...Problems like this are usually using the famous attack on the playstation 3 crypto implementation.
These attacks are able to recover the private key if the nonce is reused for two different signatures.
This attack is well documented:
- http://koclab.cs.ucsb.edu/teaching/ecc/project/2015Projects/Schmid.pdf
- https://github.com/bytemare/ecdsa-keyrec
Hash Collision
This attack is not as straightforward because the nonce uses the hash of the message when being generated.
You might think that since it is derived from the hash of the message, it should be random right?
No. We can trick server into using the same hash for two messages by using hash collision.
Because the hash used is MD5 which is part of a family of hashing that uses the Merkle–Damgård construction we can easily generate hash collisions by sending two messages with the same MD5 hash.
Wikipedia even an example of hash collision that you can use for this problems.
So get the signature for the message
d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f8955ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5bd8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70and then get the signature for
d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f8955ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5bd8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70and validate the the nonce are the same.
The output of the server should be
Encrypted flag: 248005ebc638b16a0208f6c7949f1c68a147f906aa2e749985cdde5e51d230f87af2d19ec0ce1ddfb8808585dd54257bc86d456d4ca1cc8920667e792ad5c4f1iv: d39a60befaeb2cb45ce8d2181371a387Enter your message in hex: d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70Message: d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70r: 0x557a787642ece2fe307b7de417d7d3c7bfe92313020a58e49771be515c4cadcs: 0x8d1c17fb248fb8b0af29d64365fae1b495c4eb6340ce027f9f3625564a945cdaEnter your message in hex: d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70Message: d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70r: 0x557a787642ece2fe307b7de417d7d3c7bfe92313020a58e49771be515c4cadcs: 0xda91bba782f6e63aadd53f74bd989f194664a8273d431d4e104b55e01d355296Recovering private key
I just used the relevant code from bytemare/ecdsa-keyrec
def decryptFlag(secret_exponent, iv, flag): key = md5(long_to_bytes(secret_exponent)).digest() cipher = AES.new(key, AES.MODE_CBC, iv) return cipher.decrypt(flag)order = generator_256.order()ciphertext = bytes.fromhex('248005ebc638b16a0208f6c7949f1c68a147f906aa2e749985cdde5e51d230f87af2d19ec0ce1ddfb8808585dd54257bc86d456d4ca1cc8920667e792ad5c4f1')iv = bytes.fromhex('d39a60befaeb2cb45ce8d2181371a387')m1 = bytes.fromhex('d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70')r1 = 0x557a787642ece2fe307b7de417d7d3c7bfe92313020a58e49771be515c4cadcs1 = 0x8d1c17fb248fb8b0af29d64365fae1b495c4eb6340ce027f9f3625564a945cdam2 = bytes.fromhex('d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70')r2 = 0x557a787642ece2fe307b7de417d7d3c7bfe92313020a58e49771be515c4cadcs2 = 0xda91bba782f6e63aadd53f74bd989f194664a8273d431d4e104b55e01d355296# Validate the the nonce are the same for two different signaturesassert r1 == r2assert s1 != s2h1 = bytes_to_long(m1)h2 = bytes_to_long(m2)r = r1r_inv = inverse_mod(r, order)h = (h1 - h2) % orderfor k_try in (s1 - s2, s1 + s2, -s1 - s2, -s1 + s2): k = (h * inverse_mod(k_try, order)) % order secexp = (((((s1 * k) % order) - h1) % order) * r_inv) % order print(decryptFlag(secexp, iv, ciphertext))# b'HTB{r3u53d_n0nc35?n4h-w3_g0t_d3t3rm1n15t1c-n0nc3s!}\r\r\r\r\r\r\r\r\r\r\r\r\r'