Introduction
Some Trick was the first cryptography challenge in the 2024 edition of SekaiCTF. The challenge implements a key exchange based on a set of permutations and asks us to retrieve the flag that was used as a key in Bob’s first encryption.
import randomfrom secrets import randbelow, randbitsfrom flag import FLAG
CIPHER_SUITE = randbelow(2**256)print(f"oPUN_SASS_SASS_l version 4.0.{CIPHER_SUITE}")random.seed(CIPHER_SUITE)
GSIZE = 8209GNUM = 79
LIM = GSIZE**GNUM
def gen(n): p, i = [0] * n, 0 for j in random.sample(range(1, n), n - 1): p[i], i = j, j return tuple(p)
def gexp(g, e): res = tuple(g) while e: if e & 1: res = tuple(res[i] for i in g) e >>= 1 g = tuple(g[i] for i in g) return res
def enc(k, m, G): if not G: return m mod = len(G[0]) return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod
def inverse(perm): res = list(perm) for i, v in enumerate(perm): res[v] = i return res
G = [gen(GSIZE) for i in range(GNUM)]
FLAG = int.from_bytes(FLAG, 'big')left_pad = randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))FLAG = (FLAG << left_pad.bit_length()) + left_padFLAG = (randbits(randbelow(LIM.bit_length() - FLAG.bit_length())) << FLAG.bit_length()) + FLAG
bob_key = randbelow(LIM)bob_encr = enc(FLAG, bob_key, G)print("bob says", bob_encr)alice_key = randbelow(LIM)alice_encr = enc(bob_encr, alice_key, G)print("alice says", alice_encr)bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])print("bob says", bob_decr)Solution
The first thing we do is retrieve the CIPHER_SUITE variable to set the random seed and reconstruct the set of permutations G, then we care about retrieving bob_key to ultimately recover the flag.
s = int(r.recvline().strip().decode().split('.')[-1])random.seed(s)
G = [gen(GSIZE) for i in range(GNUM)]def decm(k, G, val): m = 0 for i in range(GNUM): x = val % GSIZE y = gexp(G[i], k % GSIZE).index(x) m += y * GSIZE ** i val = (val - x) // GSIZE k //= GSIZE return m
bob_key = decm(alice_encr, G, bob_encr)Recovering the flag takes a bit more work, I’ve only managed a brute-force solution which I optimized the best I could; it’s not the best but it does the job.
def maketable(g): gg = deepcopy(g) # just to be safe table = {} for i in range(GSIZE): table[i] = gg gg = tuple(gg[i] for i in gg) return table
def perm(table, e): res = tuple(table[0]) rbits = reversed(bits(e)) ones = filter(lambda x: x != -1, [i if v == 1 else -1 for i, v in enumerate(rbits)]) for index in ones: res = tuple(res[j] for j in table[index]) return res
def findk(queue, event, table, start, end, index, want): for k in range(start, min(GSIZE, end)): if event.is_set(): return if perm(table, k)[index] == want: event.set() queue.put(k) return
def deck(m, G, val): key = 0 for i in range(GNUM): x = val % GSIZE table = maketable(G[i]) queue = mp.Queue() event = mp.Event() ps = [mp.Process(target=findk, args=(queue, event, table, start, start + (GSIZE // mp.cpu_count()) + 1, m % GSIZE, x)) for start in range(0, GSIZE, GSIZE // mp.cpu_count())][:mp.cpu_count()] for p in ps: p.start()
k = queue.get() if k == 0: return key
key += k * GSIZE ** i val = (val - x) // GSIZE m //= GSIZE return key + m * GSIZE ** GNUM
key = deck(bob_key, G, bob_encr)The recovered key isn’t the flag yet, as it went through some transformations first, but it’s clear that the flag’s bits are still there in the middle, untouched between the two paddings, so we can just do some shifting until we find it.
for i in range(key.bit_length()): shifted = key >> i for j in range(1, shifted.bit_length()): keepmask = (1 << j) - 1 final = shifted & keepmask dec = final.to_bytes(keepmask.bit_length() // 8 + 1) if b'SEKAI{' in dec: start = dec.index(b'SEKAI') end = start + dec[start:].index(b'}') + 1 print(f'flag: {dec[start:end].decode()}') break else: continue breakflag: