Qualifiers#
I participated in Hacktheon Sejong CTF 2023 under the c'est la vie team. The CTF this year is very guessy and do not involve high level techniques. Hence, I pretty much got carried (helped the team a bit though). The solution to the only Crypto challenge I attempted is solution with a lot of guesswork.
There is another Crypto challenge, but it is in Hangul - the writing system of the Korean language, which obviously I have no idea of. The admins gave out clues on using OCR, but I don’t even recognize the text to begin with to check whether the text after OCR is legible or not.
Our team managed to clinch Top 46, which is enough to be qualified for the next round. I solved 1 crypto challenge.
Encrypted JPG File#
We are given a encrypted image, with the knowledge that it is encrypted under AES-128 CBC mode with PKCS-7 padding, and the IV is b'\x00' * 16. The key is hidden in the hiddenkey.txt file, in which the content is the following:
1
2
|
SEjoNg cITy, EveR-aDVaNciNG aDMinIstRAtIvE CApitaL oF KoRea
sEjoNG, ThE dE faCTo aDMiniStRAtivE CaPitAl, bEInG hOmE tO 43 CenTRaL AdMinIStrAtIVe aGeNCieS
|
For the technical side of things, we cannot decrypt or obtain any information about the image itself, even though we should know the starting bytes of the image (magic numbers and other specifications) and the padding (from the image size). There are no attacks from research to leak the content of the encrypted image.
Hence, from this, we basically have to find some 16 byte value in the hiddenkey.txt file. I tried brute forcing all the substrings in the two lines, substrings of capital letters (as the capital letters are very weirdly placed), substrings of non-capitalized letters, substrings of capitalized letters including spaces (and numbers), substrings of non-capitalized letters including spaces (and numbers).
After 5 hours of trying to guess out the key, I gave up. Thanks to my teammate Jin Kai for his quick hands, and some kind soul on Discord, I managed to obtain the solution, which is this
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad , pad
f = open("./hiddenkey.txt" , "r").read()
f = "".join([i for i in f if i.isalpha()])
def test(key , filename):
secret = open("./cipher.jpg" , "rb").read()
aes = AES.new(key , AES.MODE_CBC , iv=b"\x00" * 16)
with open(f"output_file_{filename}" , "wb") as f:
f.write(aes.decrypt(secret))
key = int.to_bytes(int("".join(["1" if i.islower() else "0" for i in f]) , 2) , byteorder="little" , length=16)
key1 = int.to_bytes(int("".join(["0" if i.islower() else "1" for i in f]) , 2) , byteorder="little" , length=16)
key2 = int.to_bytes(int("".join(["1" if i.islower() else "0" for i in f]) , 2) , byteorder="big" , length=16)
key3 = int.to_bytes(int("".join(["0" if i.islower() else "1" for i in f]) , 2) , byteorder="big" , length=16)
print(key3)
test(key , "1")
test(key1 , "2")
test(key2 , "3")
test(key3 , "4") # Correct key
|
And I cannot express the depression after getting this solution. I don’t think there is even a chance I would think of taking the alphanumeric characters, then convert it to a binary string in Big Endian would be the way to go. Definitely not the greatest of design for a CTF challenge.
Finals#
There is only one crypto challenge at the finals, which most teams solve.
Invalid RSA#
The challenge involves a faulty implementation of RSA using CRT, and our task is to provide the secret $d$. Initially the math was too complicated so I decided to guess out the relation to solve the challenge. It eventually turns out (after I figured out the relation) that this is similar to the Fault attacks on RSA signing.
Challenge:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
from Crypto.Util.number import getPrime, bytes_to_long, inverse
from math import gcd
class RSA:
def __init__(self):
self.p = getPrime(512)
self.q = getPrime(512)
self.n = self.p * self.q
self.phin = (self.p - 1) * (self.q - 1)
self.e = 65537
assert gcd(self.e, self.phin) == 1
self.d = inverse(self.e, self.phin)
self.dp = self.d % (self.p-1)
self.dq = self.d % (self.q-1)
self.qinvp = inverse(self.q, self.p)
def print_public_key(self):
with open("modulus.txt", "w") as f:
f.write(f"{self.n}")
with open("exponent.txt", "w") as f:
f.write(f"{self.e}")
def decrypt(self, c):
mp = pow(c, self.dp, self.p)
mq = pow(c, self.dq, self.p) # mq must be pow(c, self.dq, self.q)
s = (mp-mq)%self.p
return mq+s*self.qinvp*self.q
rsa = RSA()
c = 401578470156104860340584014730570245702458205483572045
m = rsa.decrypt(c)
rsa.print_public_key()
with open("message.txt", "w") as f:
f.write(f"{m}")
|
and we are given the parameters:
1
2
3
4
|
m = 55209008618435811591187358367111772933823750280182293069139342735140807096981089997996928870297524704236966278817610274660204497402079403972832606337326167427115308079573732811600268249351995319136084632253810436000552330018793710219197840616933961641383344358390079104154710289285636886380011125199851364416230104315964641423821412336132982913912278474853322648296354892297413104136161116147125220640385213496204386481871510965547860898129269166674024840861684
n = 63903657904398455430072399897584814146786832603770411090087949649506462804265566406681855558062140079017190799848579141343805303858536540446145931600960992999004368307642297461468601833292437621267615821663823678384519510772112132283155603331111879342048858279040500003011127360850459735523987050535346952537
e = 65537
c = 401578470156104860340584014730570245702458205483572045
|
My fuzzing code, in which I print out all the variables needed to solve the challenge. This is a test run so I have full information on all the involved variables
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
d = 89762147208169603141263508485495473204766076038339050807101820361618088831754886938012727505587421268897407288953888239806296495741126611452973495382061909502164095258302228930133504371950203370484573487054495179723987278741105560124811688017188965887545866505292590581475036017893860884493943174594043325673
dp = 5581007723062595331632179830883881401513859507300612345720974275366595291959989641841555655782530459620570363138989886268752208525156338442162612890910753
dq = 7716497276954636577610267002416300867594125875420242951581858709810725849044259852391048831580395974245152354337257946530832985112600742966018766320892733
mp = 12237326286919461734975121389047007154246729613049128046013331446694649505170511560005184945700084495733230100040431840890569053312573023040219331686107632
mq = 2099441436026740896797016067726106703889814179360443969764921326347295161504330652826765803222408532142731672942735357033128291545508808686914852868506267
s = 10137884850892720838178105321320900450356915433688684076248410120347354343666180907178419142477675963590498427097696483857440761767064214353304478817601365
n = 140018609072733167065001822145330528571922557369558394172062455396757382962029800191758464381722350352257090053224424562578789295029899908001940400029851772233158290272069950266832318456177190670311907319848853555937311811044041268440415830131235587820433646860123529068861135114858590670866495234539337688901
p = 12444287668289102825570841371006972489487405094241978473785910828956877914030411035566481798211067594316593627144800632022156147595031673669162056376960331
q = 11251637120984648631398657690058227872547417512068180979793981094310184220371415875631917573872745315803509763854422507938219226300994858091130954664983471
m = 689271520195684148955620065788631997965517461886478079378107538641424550315097201524887261096599228270985834819795056660778978994385359440002890715852814695850794905026635285958774801546367314065542353510318494177202093823396071072236896125005494166300563551156280796439317129045901238142143878985205628943248584836921597344075837793731306124466131245412842355722571975206421754710249680708480787680142055161273441838704836172993040360055135931145901639983783247
c = 401578470156104860340584014730570245702458205483572045
e = 65537
print(m % p == mp)
print(m % q == mq)
a = pow(m, e, n)
print(a % p == c) # key finding
|
Nonetheless, there are excellent articles on how to work with this sort of challenge, namely from Trail Of Bits, cryptologie, and a CTFTime Writeup
The $m$ derived from the decryption part only satisfies $m ^ e = c (mod p)$ and not $m ^ e = c (mod q)$. We thus have $m ^ e - c = 0 (mod p)$, and combined with the fact that $n = pq$, we have $gcd(m ^ e - c, n) = p$. This explains the key finding I derive from fuzzing. With $p$ figured out, then deriving the private exponent is simple.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
from math import gcd
m = 55209008618435811591187358367111772933823750280182293069139342735140807096981089997996928870297524704236966278817610274660204497402079403972832606337326167427115308079573732811600268249351995319136084632253810436000552330018793710219197840616933961641383344358390079104154710289285636886380011125199851364416230104315964641423821412336132982913912278474853322648296354892297413104136161116147125220640385213496204386481871510965547860898129269166674024840861684
n = 63903657904398455430072399897584814146786832603770411090087949649506462804265566406681855558062140079017190799848579141343805303858536540446145931600960992999004368307642297461468601833292437621267615821663823678384519510772112132283155603331111879342048858279040500003011127360850459735523987050535346952537
e = 65537
c = 401578470156104860340584014730570245702458205483572045
c_prime = pow(m, e, n)
p = gcd(c_prime - c, n)
q = n // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
# Printing out the hex value of d for the flag
print(hex(d))
|