Quick writeup for this one so I remember it for later. Although this CTF ran all week, we sorta need that, since it took about a day for the challenge GUI to load every time you clicked something. Ugh. Anyways, this was an interesting challenge because it appeared very simple but I wasn’t immediately solving it using quick tricks. Anyway lets look at the clue:
Looks like in this time Alice and Bob have decided to pay a minimal attention to malicious Eve, who has been “sniffing”(as always) all the traffic during their private chat. Is their private life`s secret in danger for now?.. h4ck1t{key}
There’s a link with a file containing three sets of public keys and ciphertexts.
Usual attempts at factoring the moduli are not successful, and common factor attacks amongst the moduli are also unsuccessful. I am then reminded of Cryptopals challenge about the RSA broadcast attack with an public exponent of 3 (e=3). In our case the profile of the challenge fits this exactly: https://cryptopals.com/sets/5/challenges/40
The overview is, when you have a plaintext, encrypted three times with different public keys, we can use the chinese remainder theorem to solve for the plaintext cubed.
Using python, and libnum, we quickly code up a solution:
#!/usr/bin/python
# RSA broadcast attack for Interceptor challenge @ H4ckIT 2016
# @ctfkris - Capture the Swag
import libnum
rsashit = [int(x.strip().split('=')[1]) for x in open('EvelSniff_c637ac54760f179a5aa3e164847405fa.log').readlines() if '=' in x]
n_0 = rsashit[1]
n_1 = rsashit[4]
n_2 = rsashit[7]
ct_0 = rsashit[2]
ct_1 = rsashit[5]
ct_2 = rsashit[8]
# product of all moduli
N_012 = n_0 * n_1 * n_2
# n1 * n2
m_s_0 = n_1 * n_2
# n0 * n2
m_s_1 = n_0 * n_2
# n0 * n1
m_s_2 = n_0 * n_1
crt = libnum.solve_crt([ct_0,ct_1,ct_2], [n_0,n_1,n_2])
c_0 = crt % n_0
c_1 = crt % n_1
c_2 = crt % n_2
result = ((c_0 * m_s_0 * libnum.invmod(m_s_0, n_0)) + (c_1 * m_s_1 * libnum.invmod(m_s_1, n_1)) + (c_2 * m_s_2 * libnum.invmod(m_s_2, n_2))) % N_012
pt = libnum.nroot(result, 3)
print libnum.n2s(pt)
Which gives us the flag! Nice!
root@kali:~/ctf-solutions/crypto/h4ck1t16-interceptor# ./portugal.py
key=bff149a0b87f5b0e00d9dd364e9ddaa0