Foreword#
My first non-NUS CTF! I was mostly carried by the insane people @ NUS Greyhats.
Quals#
I did manage to contribute something though, the Welcome challenge (which is to find the flag hidden in the emotes on the ISITDTU CTF Discord server), a OSINT and Misc challenge.
Find#
A tough OSINT challenge. Initially we are only given the following image.
There was initially no clues given by the challenge organizer. We did locate something in the right corner of the challenge image that is useful somewhat for finding the location of the place - the motel, or in Vietnamese nha khach. Unfortunately I am not so sure what follows afterwards, giao thong is a guess I made, but in the end it turned out to be wrong. The location associated with the name of nha khach giao thong is not in the countryside area, and mostly in the urban regions.
We do know from our sixth sense that the place is in Viet Nam - the fauna and the river bank strongly suggests a Vietnamese location.
Afterwards, a hint of a famous place in Tuyen Quang is given out. It is sensible just to brute-force the solution at this point - this clue was basically giving out the solution to the challenge itself. In the end, the place that the picture was taken is at “Den Ha, Tuyen Quang” - which indeed is a famous place. We did manage to find the exact spot on Google Maps where the image was taken. The Google Maps link for “Den Ha” is at this link
dceased-xxiv#
A Misc category, but Crypto related challenge. We are given three pictures out.png and part.png, where it seems like part.png is leaking a bit of out.png.
We are also given what seems like the Python script for the encryption of the original file
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
36
37
38
|
from PIL import Image
import random, time
def xor(a):
return a[0] ^ a[1]
def xor_tuple(a, b):
return tuple(i for i in map(xor, zip(*[a, b])))
def rgba2int(rgba: tuple):
ret = 0
for i in range(3, -1, -1):
ret += rgba[i] << 8*(3 - i)
return ret
def int2rgba(n):
r, g, b, a = tuple([(n >> 8*i) & 0xff for i in range(3, -1, -1)])
return (r, g, b, a)
img = Image.open('flag.png')
random.seed(time.time())
px = img.load()
x_len, y_len = img.size
new = Image.new('RGBA', (x_len, y_len), 'white')
px1 = new.load()
for y in range(y_len):
for x in range(x_len):
rand = random.getrandbits(32)
rr, rg, rb, ra = int2rgba(rand)
r, g, b, a = px[x, y]
new_pix = xor_tuple((rr, rg, rb, ra), (r, g, b, a))
px1[x, y] = new_pix
new.save('out.png')
|
What the script basically does is to xor the RGB values of each pixel in the original file flag.png with the random number (actually the converted representation of the number into a tuple of (a, b, c)) and write the RGB values of the encrypted pixel to out.png.
We can take advantage of the fact that the random module of Python uses Mersenne Twister, in particular, MT19937, which is reversible. The random module in Python does not provide a cryptographically secure pseudorandom number generator (PRNG), as the output generation of MT19937 is a reversible operation. Hence, an attacker, with enough bits observed from the PRNG, can clone the PRNG itself, or in other words, obtain the exact value of the seed in use. More on this can be found by The Book of Gehn and the Cryptopals writeup from cedricvanrompay.
There are implementations to break the random module used in Python. One such tool is randcrack. Two crucial things to note: first, randcrack only needs 624 bits to obtain the value of the seed; second, after inputting 624 bits of the PRNG to randcrack, we generate the pseudorandom values generated from the guessed out seed of random by doing rc.predict_getrandbits(32) - it will start generating the next 32 bits after the initial 624.
The idea of the script is to use the few pixels that is leaked in part.png, xor-ing with the encrypted pixels in out.png, we should get the random values used. Supplying about 624 bits to randcrack, we should be able to clone the PRNG and output the future values generated by the PRNG.
Solution Implementation:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
from PIL import Image
from randcrack import RandCrack
import random
from tqdm import tqdm
rc = RandCrack()
def xor(a):
return a[0] ^ a[1]
def xor_tuple(a, b):
return tuple(i for i in map(xor, zip(*[a, b])))
def rgba2int(rgba: tuple):
ret = 0
for i in range(3, -1, -1):
ret += rgba[i] << 8 * (3 - i)
return ret
def int2rgba(n):
r, g, b, a = tuple([(n >> 8*i) & 0xff for i in range(3, -1, -1)])
return (r, g, b, a)
part = Image.open('part.png')
out = Image.open('out.png')
px_part = part.load()
px_out = out.load()
x_len, y_len = part.size
for y in range(1):
for x in range(x_len - 96):
part_r, part_g, part_b, part_a = px_part[x, y]
out_r, out_g, out_b, out_a = px_out[x, y]
key = xor_tuple((part_r, part_g, part_b, part_a), (out_r, out_g, out_b, out_a))
key = rgba2int(key)
rc.submit(key)
new = Image.new('RGBA', (x_len, y_len), 'white')
px_flag = new.load()
for y in tqdm(range(y_len)):
for x in range(x_len):
if (y == 0 and x in range(x_len - 96)):
continue
rand = rc.predict_getrandbits(32)
rr, rg, rb, ra = int2rgba(rand)
r, g, b, a = px_part[x, y]
new_pix = xor_tuple((rr, rg, rb, ra), (r, g, b, a))
px_flag[x, y] = new_pix
new.save('flag.png')
|
The image after running the Python script should hold the flag.
Finals#
For the finals, I managed to solve one crypto challenge using the techniques from my writeups in the Cryptohack journey.
(update) In 2023, in the ISITDTU finals, I met the author of this challenge! She said there is some weakness in the way that the challenge is created, hence my solution. To be fair though, it was the only technique I knew of at that time, hence I was pretty proud anyways of solving the challenge in the only method I knew.
Sussy RSA#
Straightforward challenge, we were given the modulus N, and this RSA variant is trying to sum the ciphertexts of different public exponent together.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
m = bytes_to_long(FLAG)
p = getPrime(512)
q = getPrime(512)
N = p * q
E = []
C = []
for _ in range(10):
es = random.choices(sieve_base, k=5)
c = 0
for e in es:
c += pow(m, e, N)
C.append(c % N)
E.append(es)
|
In other words, the ciphertext $c$ from the message (flag) $m$ is given by:
$$
c = m ^ {e_1} + m ^ {e_2} + m ^ {e_3} + m ^ {e_4} + m ^ {e_5} \mod N
$$
There are multiple ways to solve this, but I choose the technique in solving RSA with linear padding. Two polynomials of the form $x ^ {e_1} + x ^ {e_2} + x ^ {e_3} + x ^ {e_4} + x ^ {e_5} - c = 0$ should have a common greatest common divisor of $x - m$, as both polynomials yield a solution $x = m$ and the remaining factors of the polynomials are relatively prime.
We can take two polynomials with the smallest degree, then calculate the greatest common divisor of the two polynomials. The constant term should be the value of $m$
Sage Implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from Crypto.Util.number import long_to_bytes
N = 145573074243624094259045505018214707732072790008595748299844560882718370444055770811438657485599030295828973765024640921541271135500659041224853393363904981532379033396031425301817004202181747896482364760707617834523266817304195617481820684006104556478947710504949606952363376993696540521711571034878673727911
E = [[97579, 55967, 35617, 37159, 103813], [9431, 81023, 58991, 28559, 41], [61813, 21701, 33851, 68531, 6761], [97711, 38867, 23327, 74707, 71327], [36599, 45289, 56383, 25169, 45823], [62827, 28393, 20947, 53, 89897], [45569, 11503, 92489, 39359, 3389], [38273, 75209, 28729, 40111, 59351], [90149, 71503, 92831, 4289, 46933], [29581, 16427, 41887, 17333, 9221]]
C = [49227922004810245776534838666187305514871514271158134722818690382462402813274009253475980673664326958512654960813575356207133549452901533372553451059659403016824868444011917411142435898672967191499509099385728840013223089455282099231419967052476755035184058831209851104547399033046817280933970657256885472718, 37601028253749715479471245240707069320548448113707738835427453620437091470466377827215207449044039876173054883194907492685818787137498696805686512732305330831917877757692899639504977066285462702368110064571535922211702702315805386974675784660042196711000718940314618080916092626790268169229986748217401361443, 114677719296814341321663450033591595939761579957812812711642883466753488461514263990784495432652420711263971620309231650405687885227004294751361216153323453557860906950568662280977864029289024877321596897068290283795443306712922016720377290371787178007118012361128379990618868717023298141485838214038296819268, 138398918072470809451495032330045160937041099512072945799396832138913694732078234061928879456670654964039471270135418508041749617042356818745844206301547227921416829733672594209268895057901016612390552863857347769375035092010845395232920904938770167629044933805979703596347946684015545751938983448650104406570, 70932586164818345520197763803939338611699058272404597978700717458086818903547412376780707289387501691325450996592925929646777587363795934500090311998343040912331187223915758658350481612742205629450152681144655315599889681601639082626671503906289922070151928098979409238723108896761682093318924625241287161025, 127255996207056883221066465957627839241024650733433772130118526826022790807872078225518117611582771215312403630005348446375587494804230674474441919875075377102257476405662883380330809573379113581250378177019690611150365386138108405309865794422647189270710716224247808165019347816971502408912258976210646144202, 3905583022512680603686447906864238844117809935710143198196057437043913439568485526929764626653893260973954349544600700008462421548097045072250392789331332000111881557437427084017379068964943371052416886956150270690949728653176478165950727387200176653798488359779042885431461956082693406174363435089374769160, 105581648076102583711930436674850333224020816764542554186251849683750658013225471011232808443565886816979658678048929394909153915022061529648035592425435534461430355328998559148757059944444237232875915967867604201750357902452322994839726015774717811266188559890096541602548243826008791727792534712956090173693, 20644256655706904364872639666653322389927562854667009190419687330757962390340911496941592959760278342925883125556278136856681565530002466543260522167462810958401388619793906330540926043910805540548302592587209276886479551857135696977204944312818272947239878647359296187936103217434799716328566513962618716212, 82894837416684692905279833348202128571692323715666936645488078910063976455599098075837599038268833844129045799925385085518604877459811693435060981611982880854303676401897749347719164577447981729236569621331656933662039902820499453735118592749515166705119617781994134938620250285200988500505257212184814903052]
def gcd(a,b):
# custom GCD implementation because Sage's one apparently doesn't work here
while b:
a, b = b, a % b
return a.monic()
idx_1 = 1
idx_2 = 4
f_c = E[idx_1]
g_c = E[idx_2]
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x ^ 29581 + x ^ 16427 + x ^ 41887 + x ^ 17333 + x ^ 9221 - C[9]
g = x ^ 36599 + x ^ 45289 + x ^ 56383 + x ^ 25169 + x ^ 45823 - C[4]
print(long_to_bytes(int(-gcd(f, g).coefficients()[0])))
|