A CTF themed on greek literature and history. I was time-constrained and wanted to focus on Crypto challenges. Here are my writeups.
Challenges
Anarkhia
A term which refers to the year 404 BCE in which the city of Athens had no Archon, i.e. without a democratically elected leader of the government. Anarkhia literally means Without Archon; instead of an Archon, the city was ruled by Thirty Tyrants who were elected at the end of the Peloponnesian War (431-404 BCE); the reign of the Thirty Tyrants lasted only one year.
import random
from secret import flag
'''
The seed for random() is either:
a. 3-digit numeric string (from 000 - 999)
b. 4-digit numeric string (from 0000 - 9999)
c. 5-digit numeric string (from 00000 - 99999)
'''
random.seed(''.join([str(random.randint(0x0, 0x9)) for i in range(random.randint(3, 6))]));
# with the above key ... one random byte value is generated for each character of the flag
theKey = [random.randint(0, 255) for i in range(len(flag))];
# some XOR magic
theEnc = "".join([hex(((random.choice(theKey)) ^ ord(flag[i]))<<1) for i in range(len(flag))]);
open('out.txt', 'w').write(theEnc)
Upon analysis, we can see that the random seed can be at most \(10^6\) values. So, it is a good candidate for brute-forcing.
Note that a string value is passed in as a seed. So the seeds 0123 is distinct from 123 and will produce a different sequence of pseudo-random values.
import random
out = [0x5e, ... 0x1b0] # from out.txt
for i in range(3,6):
for d in range(0, 10**i): # the upper bounds set to 10^i
fmtstring = f"0{i}d"
seed = f"{d:{fmtstring}}"
if (d%1000 == 0):
print(seed)
random.seed(seed) # pass the string as the seed. Not the numeric value
theKey = [random.randint(0, 255) for i in range(len(out))]
# reverse the XOR magic.
flag = "".join([chr(random.choice(theKey) ^ (out[i] >> 1)) for i in range(len(out))] )
if ("flag{" in flag):
print(seed, " : ", flag)
# 6527 : flag{in_the_depths_of_chaos_seeds_of_creation_lie}
Thermopolium
In the ancient Greco-Roman world, a thermopolium (plural thermopolia), from Greek θερμοπώλιον (thermopōlion), i.e. cook-shop,[1] literally "a place where (something) hot is sold", was a commercial establishment where it was possible to purchase ready-to-eat food. In Latin literature they are also called popinae, cauponae, hospitia or stabula, but archaeologists call them all thermopolia.[2] Thermopolia are forerunners of today's restaurants and the items served in them are sometimes compared to modern fast food.
====================================
You are connected to : Αρχαία Γεύση
Please make yourself at home
====================================
Food of the day:
1. Cook flagga : ingredients = flavor(condiment(grb(64)), condiment(grb(64)))
2. Cook your own menu : ingradients = flavor(gp(64), gp(64))
3. Exit
>> 1 : I did this about 4 times to collect 4 different samples
gp(n) : generate prime of bit length = n
grb(n): generate random bits of size = n
By looking at the flavor class, we can see that it is an implementation of Linear Congruent Generator, with the multiplier and increment randomized.
The initiatl state and modulus are also randomly created primes for each operation. So, there is no sharing of state that we can see.
The cook function is the encoding function. Looking into it, we can see that the byte value of the flag’s characters are taken to the power of 4 with a modulus of a 64-bit prime. The flag’s character value is 7 bits. So, the pow(c, 4) can be at most 7*4 = 28 bits. So, the modulus part of the pow() function has no effect on the operation.
class flavor:
def __init__(self, state, mod):
self.state = state
self.mod = mod
self.mult = grb(32)
self.inc = grb(32)
def gen(self):
self.state = ((self.state * self.mult + self.inc) % self.mod)
return self.state
def cook(m, x):
n = gp(64)
res = ""
for i in m:
res += hex(pow(i, 4, n) ^ x.gen())[2:] + "xx"
return res
We know that the FLAG is encoded with a series of states generated by the LCG, implemented by the flavor() class. We also know that the FLAG starts with the values of flag{. So, we can use this information to determine the first 5 values of the LCG’s state. With the five values, we can determine the parameters of the LCG and reproduce the series. This can be accomplished by the technique shown in https://tailcall.net/posts/cracking-rngs-lcgs/
# 4 different encoding of the flag, via option #1 from the challenge server
flag_encs = [
"3022179b4aaebbbexx...",
"2a9919508bfcfb8dxx...",
"1973146195274216xx...",
"bdd75e220573aa9axx...",
]
# Implementation of LCG cracking from https://tailcall.net/posts/cracking-rngs-lcgs/
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
print(f"[=] {modulus= } {multiplier= } {increment= }")
return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
multiplier = ( (states[2] - states[1]) * pow(states[1] - states[0], -1, modulus) ) % modulus
print(f"[=] {modulus= } {multiplier= }")
return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
print(f"[=] {modulus= }")
#return modulus
return crack_unknown_multiplier(states, modulus)
# Implement gen_lcg() method to generate PRNG without using random()
class flavor:
def __init__(self, state, mult, incr, mod):
self._state = state
self._mult = mult
self._incr = incr
self._mod = mod
def gen_lcg(self):
self._state = ((self._state * self._mult + self._incr) % self._mod)
return self._state
# for each flag encoding,
for enc in flag_encs:
enc_chars = enc.strip().split('xx')
# knowing that flag starts with the header: 'flag{'
header = b'flag{'
n = gp(64) # value of n is immaterial
gens = []
state = 0
for i in range(len(header)):
print(f"{header[i]= } {enc_chars[i]= } {pow(header[i],4,n):08x} ^ {int(enc_chars[i],16):08x}")
gen = pow(header[i],4,n) ^ int(enc_chars[i],16)
gens.append(gen)
mod, mult, incr = crack_unknown_modulus(gens)
print(f"Cracked LCG: {mod= } {mult= } {incr= }")
# use the first to set the initial state
flag = "f"
LCG = flavor(gens[0], mult, incr, mod)
for i in range(1, len(enc_chars)-1):
gen = LCG.gen_lcg()
fc = int(enc_chars[i], 16) ^ gen
flag += chr(gmpy2.iroot(fc, 4)[0])
print(flag)
print(f"FLAG: {flag}")
# flag{mUltipl3_PRNGs_i5_st1ll_PRNG}
Notes:
- Note that we did not have to use the
Cook your own menuoption from the challenge server. This seems to indicate that the intended solve could be different than cracking the LCG like I have done.
Astynomoi (Todo)
Astynomoi, a board of magistrates whose responsibilities included care for both city and suburban streets, city blocks and their party walls, water channels, fountains, and cisterns. In Athens there were five for the city and five for the Piraeus, appointed by lot for one year. Their principal duties were to keep the streets and sanctuaries clean and free from obstructions, and they enforced certain sumptuary laws.
Dreams of Sacred Amulets (Todo)
You are connected to:
================================
Land of the Divine Mortals
================================
Pantheion: 178781627668918722110949704949143521748613601045667566564761566803807584045793589011943098438418882572803925943970610799705984289798692765358405531976521186572559129766265008038058819932867962823371841117387121313504853351532625919197958294179979992367545489481276669477528644772479117490145800312436033261421
Quiescent: 956663177302110972558982807810203289351368268609
Hemerologiographos: 60025144088948900944674083848650681140063362507326686505088340190835986418185932515059561558459915142994955687631606610819205948998506180239908326185116904888521098066597348242365411560836155907420684525330922835968647928020552211236666058767747750269078258804627452721703648860218262179853539215248068818336
Gnosi: 170996679399653032386543963470424380628532404018224053846453862590793553812459926893191426144366482993143386454459875120252958116565268930066228538182240399609230540561703197977325381869374665213158238347041815691945683623024788220367518643744381489281036776493300079344438851077709242559007286234255938630429
1. Amulets
2. Produce
3. Mark
4. Depart
>> 1
['Areti', 'Basileiokratia', 'Chaos', 'Doxa']
Picasso (Todo)
Charles GPTcheater IV
The Greek Period immersion was broken with the last two challenges. In any case, this challenge provided us a binary file, oddly named as hidden.txt, and a text file called snip.txt, which seems to unreadable.
EULAV_NRUTER 04
)pmet( 2 TSAF_DAOL 83 >> 6
21 ETULOSBA_PMUJ 63
)pmet( 2 TSAF_EROTS 43
DDA_ECALPNI 23
1 NOITCNUF_LLAC 03
ROX_YRANIB 82
)56( 1 TSNOC_DAOL 62
1 NOITCNUF_LLAC 42
)x( 3 TSAF_DAOL 22
)dro( 1 LABOLG_DAOL 02
)rhc( 0 LABOLG_DAOL 81
)pmet( 2 TSAF_DAOL 61 5
)x( 3 TSAF_EROTS 41
)83 ot( 42 RETI_ROF 21 >>
RETI_TEG 01
)v( 0 TSAF_DAOL 8 4
)pmet( 2 TSAF_EROTS 6
)''( 2 TSNOC_DAOL 4 3
)a( 1 TSAF_EROTS 2
)56( 1 TSNOC_DAOL 0 2
Reversing each line and reading the file backwards from the end of the file, gives us the following, which can be recognized as python bytecodes.
$ rev snip.txt | tail -r
2 0 LOAD_CONST 1 (65)
2 STORE_FAST 1 (a)
3 4 LOAD_CONST 2 ('')
6 STORE_FAST 2 (temp)
4 8 LOAD_FAST 0 (v)
10 GET_ITER
>> 12 FOR_ITER 24 (to 38)
14 STORE_FAST 3 (x)
5 16 LOAD_FAST 2 (temp)
18 LOAD_GLOBAL 0 (chr)
20 LOAD_GLOBAL 1 (ord)
22 LOAD_FAST 3 (x)
24 CALL_FUNCTION 1
26 LOAD_CONST 1 (65)
28 BINARY_XOR
30 CALL_FUNCTION 1
32 INPLACE_ADD
34 STORE_FAST 2 (temp)
36 JUMP_ABSOLUTE 12
6 >> 38 LOAD_FAST 2 (temp)
40 RETURN_VALUE
Taking a hint from the challenge title, I used ChatGPT to convert this bytecode to python language snippet.
def decode_sequence(v):
a = 65
temp = ''
for x in v:
temp += chr(ord(x) ^ a)
return temp
Reversing this logic for hidden.txt,
% python3 -c "print(''.join(chr(x ^ 65) for x in open('hidden.txt', 'rb').read()))"
I'm a secret you must unveil,
A puzzle wrapped in a cryptic tale.
Within my grasp, the answer lies,
Decrypt me to claim your prize.
Hidden within the code's embrace,
A flag to find in this riddle's space.
Look for clues, read between the lines,
The solution awaits, the treasure shines.
In letters and numbers, a pattern to see,
Unlock the mystery, set it free.
I have 91 p1 bugs at T1.
I have Benzene(CH).
Crack the code, reveal the key,
And i also have code to my vault name "34T".
And the secret, yours it will be if you combined what i have.
But my darling was not able to do so.
All she must do is to read and figure out.
Now i ask you this, am i complicated?
Or she's just loss the mind of my riddle?
I could piece together the odd references like CH and 34T, which would spell CHEAT in leetspeak. However, I could not decipher the riddle (?) to get the flag.
After the CTF, I was told on Discord that the flag was just the odd characters just assembled together to sound like GPTCheat.
91 p1 T1 CH 34T –> flag{91p1T1CH34T} –> gi pi ti cheat !!