H4ckIT CTF 2016: Interceptor - Crypto Challenge

Reading time ~1 minute

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:

# 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 

Interviewing in Tech: Security Engineer & Security Analyst

Landing a job as a security engineer or analyst at a tech company is a significant feat. It requires not only technical acumen but also s...… Continue reading

BSides Sydney 2023 Writeups

Published on November 24, 2023

DUCTF 2023 Writeups

Published on August 31, 2023