blog > WMCTF 2022 Crypto Writeups
2022 Aug 22ctfcrypto

# WMCTF2022 Crypto Writeups

## ecc

easy checkin

wmctf{a+b+c}

Attachment: ecc.zip

28 solves, 257 points

CHALLENGE output.txt
TEXT
flag bits: 606e = 0x10001n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997G = (3364552845709696244757995625685399274809023621531082895612949981433844727622567352338990765970534554565693355095508508160162961299445890209860508127449468 : 4874111773041360858453223185020051270111929505293131058858547656851279111764112235653823943997681930204977283843433850957234770591933663960666437259499093 : 1)3G = (8240596254289477251157504980772167439041663401504657696787046343848644902166655624353107697436635678388969190302189718026343959470011854412337179727187240 : 4413479999185843948404442728411950785256136111461847698098967018173326770728464491960875264034301169184074110521039566669441716138955932362724194843596479 : 1)

n, e and c looks like a RSA encrypted message. G and 3G looks like points on an elliptic curve. Since the size of one x/y coordinate of G/3G seems to be half as many digits long as n, we can guess that the elliptic curve is taken modulo p, one of the factors of n. Some of the flag should then be obtained from RSA decrypting c.

Suppose the curve satisfies the equation $y^2 = x^3 + a \cdot x + b \mod p$ for some unknown $a$, $b$ and $p$. Since G and 3G are on this curve, we can substitute the x and y coordinates of both points into that equation to get two equations with three unknowns. Though we do not know $p$, we know that $n$ is a multiple of $p$. We can solve for this equation modulo $n$ instead; instead of finding $a$ and $b$ we obtain some $a' = a + k_a \cdot p$ and $b' = b + k_b \cdot p$ respectively.

The next information we use is the fact that $G \cdot G \cdot G = 3G$ under curve $\bmod p$. Though we cannot do calculations $\bmod p$, we can do calculations $\bmod n$ (using earlier obtained $a'$). The resultant $3G \bmod n$ when taken $\bmod p$ should be congruent to the given 3G from the challenge attachment - the difference of x/y coordinates will then be multiples of p and thus p can be obtained using GCD.

The rest of the flag is obtained by decrypting the RSA payload, recovering $a$ and $b$, padding each value to a 202-bit binary string and decoding the result as ASCII.

Exploit code
SAGE
e = 0x10001n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997gx, gy, _ = (    3364552845709696244757995625685399274809023621531082895612949981433844727622567352338990765970534554565693355095508508160162961299445890209860508127449468,    4874111773041360858453223185020051270111929505293131058858547656851279111764112235653823943997681930204977283843433850957234770591933663960666437259499093,    1)g3x, g3y, _ = (    8240596254289477251157504980772167439041663401504657696787046343848644902166655624353107697436635678388969190302189718026343959470011854412337179727187240,    4413479999185843948404442728411950785256136111461847698098967018173326770728464491960875264034301169184074110521039566669441716138955932362724194843596479,    1)
F = Zmod(n)gx, gy, g3x, g3y = [F(i) for i in [gx, gy, g3x, g3y]]
a_mod_n = ((g3y ^ 2 - g3x ^ 3) - (gy ^ 2 - gx ^ 3)) / (g3x - gx)b_mod_n = gy ^ 2 - gx ^ 3 - a_mod_n * gx
assert gx ^ 3 + a_mod_n * gx + b_mod_n - gy ^ 2 == 0assert g3x ^ 3 + a_mod_n * g3x + b_mod_n - g3y ^ 2 == 0
def add_point(x1, y1, x2, y2, a):    if x1 == x2 and y1 == y2:        l = (3 * x1 ^ 2 + a) / (2 * y1)    else:        l = (y2 - y1) / (x2 - x1)    x3 = l ^ 2 - x1 - x2    y3 = l * (x1 - x3) - y1    return x3, y3
g2x_mod_n, g2y_mod_n = add_point(gx, gy, gx, gy, a_mod_n)g3x_mod_n, g3y_mod_n = add_point(gx, gy, g2x_mod_n, g2y_mod_n, a_mod_n)
p = ZZ(gcd(g3x_mod_n - g3x, g3y_mod_n - g3y))q = n // passert p * q == nprint(f"{p=}")print(f"{q=}")
a = a_mod_n % pb = b_mod_n % pc = F(c) ^ ZZ(Zmod((p-1) * (q-1))(e) ^ -1)print(f"{a=}")print(f"{b=}")print(f"{c=}")
flag_bin = "".join([    bin(int(i))[2:].zfill(202)    for i in [a, b, c]])flag = b"wmctf{" + bytes.fromhex(hex(int(flag_bin, 2))[2:]) + b"}"print(f"{flag=}")
OUTPUT
p=8308060309959524788634404677678479024666400240233812713350984932475838872076486898595574202532027412806488106365658717017155800093596205985127436125626827q=7373872192463191738033336697886150566044010386580579101665086651212656675570461681793837375772679015765588192207913025640568056955479671819537473774809617a=3629864911627283784723617758993690217446918991113173559686999b=988958437986133278846018591274848194060347135958347118693976c=1910700325063785326106590899271324158468993875758894973739361flag=b'wmctf{$$U_c0u1d_s01v3_e11iptiCurv3_s0_34sily$$0f19d82199a0db0dee31fa12330307ea90aa}'

Also see:

# homo

hum ah ah ah ah ah ah

Attachment: homo.zip

17 solves, 415 points

CHALLENGE gentry.py
PYTHON
from Crypto.Util.number import *from secret import flagfrom random import *assert flag.startswith(b'wmctf{') and flag.endswith(b'}')flaglen = len(flag) - 7flag = bytes_to_long(flag[6:-1])pbit = 114qbit = 514rbit = 191keylen = 981nouse = 0
def keygen():    pk = []    sk = getPrime(qbit)    for i in range(keylen):        print(i)        p = getPrime(pbit)        r = getPrime(rbit)        pk.append(p*sk + 2*r)    return pk , sk
def enc(m , pk):    c = []    m = [int(i) for i in bin(m)[2:]]    print(m)    for i in m:        tempc = i        for j in range(keylen):            if randint(0 , 1):                tempc += pk[j]        c.append(tempc)    return c
pk , sk = keygen()print(sk)c = enc(flag , pk)
f = open('./pubkey.txt' , 'w')f.write(str(pk))f.close()
f = open('./cipher.txt' , 'w')f.write(str(c))f.close()print([(i%sk)%2 for i in c])print(sk)

The challenge implements a knapsack-like cryptosystem. The secret key is a single large 500-bit prime while the public key is 981 integers, where the $i$-th is in the form $pk_i = sk \cdot p_i + 2\cdot* r_i$ for some random 114 bit prime $p_i$ and 191 bit prime $r_i$. One bit of message is encrypted by starting from said plaintext bit 0 or 1, then adding a random subset of the public keys to yield a large integer which is published as ciphertext. The bit is recovered by taking the large integer ciphertext modulo $sk$ to remove all $sk \cdot p_i$ terms and then modulo $2$ to remove all $2 \cdot r_i$ terms, yielding the plaintext bit.

Due to the sizes of the various parameters, in each item of the public key list $pk_i$, the $sk \cdot p_i$ term is much larger in magnitude than the $2 \cdot r_i$ term. We can take the ratio of $sk_0$ and $sk_1$ to recover $p_0$ and $p_1$ using continued fractions.

SAGE
pk = [int(i) for i in open("pubkey.txt").read().strip(" \n[]").split(", ")]ct = [int(i) for i in open("cipher.txt").read().strip(" \n[]").split(", ")]
convergents = (ZZ(pk[0]) / ZZ(pk[1])).continued_fraction().convergents()for frac in convergents:    print(frac)
OUTPUT
15/46/5155/129471/3925807/483312085/1005817892/1489129977/24949107823/89738569092/4736391815099/151065564097557/5334656465912656/54857219261835525/217918221[... 50 lines ...]2951728755016117362045052552604515/24566394463381434564246198107226884748005062846370656538636303374328/395162885782773092336287881843361112447738880708858675122325159353171/1035989716199360530315037744758991017195743943555229331660961462727499/1431152601982133622651325626602352150294551491796838994976191539893590246371850701615512602409776565638886755491251194723604419288046/4185871717401702158587963422191846966251831966891323549088625044246687009785649215002454390408253550294551491796838994976191539893590246371850701615512602409776582834630699046480526384565882015545/41858717174017021585879634221918469662518319668913235490886250456778396117677828376537800170106056201178205967187355979904766159574360985487402806462050409639106314142778852630692773877302065334681/1674348686960680863435185368876738786500732786756529419635450018128020584508899772796379444144007031056185581327733618894500022337765395173808864733925764650605308153548524962199944395771076208688950/8790330606543574533034723186602878629128847130471779453086112595207886883721277147747275222421095714425920531278121831557904855510635941680722861742165109012060338928336878701430470356961606900090481/3683567111313497899557407811528825330301612130864364723197990039895956811939400836378548033382838987[... 160 lines ...]1995812930048656259689750634098332502261295378791730205719262185407281355554729107523343915940690619750857821466849215869675288475892851625941071610787149850415656055218545600091197780141/166105803696805700415131919947365139164193165778933568925911855024275280312720594208696580561520274832895837575278243127180279292338319657742714863594218405552990052716548225192059749074678086230048062163215827557039168524732591982807415828566518545608000790736767714294344434083507317015679154027430740094529625782791578191740474785551280839656543126510706171631964696056437/6498893661076147341439349873592562501069471253826967302976023676368674098579393450103228773384847284133544848909980986027773830324335092520106119686706376542476980448142863632789041960746180082042978110819475517307673266857234853278186207558772237807793408072092322443401867777999448007635430011848897589310399301071267471043366415857162067989506958782565924717232055893836578/66649994647729530418544817935399276402336644196059008719019355313929493788921140443119253539463675589664406864852592291549541096166734121778488345503005949480299705008594118579811017098207238250316004283802166862172385702239202298539179830946110994161194816934921412601098079990082403332286539177725225918715328227925326520278473306499875416818670460691642555606096076483729593/198288925906220534251483134606724177815368000930387690467798947391545728563636215387270794812775824020664262218804994443376820495576819168758037887873075664385369214498616873487512453803875

We can see the sudden jump from a 35 digit numerator and denominator to a 98 digit numerator and denominator; this is likely where the continued fraction of $pk_0 / pk_1$ shifts from approximating $p_0/p_1$ to approximating $(sk \cdot p_0 + 2 \cdot r_0) / (sk \cdot p_1 + 2 \cdot r_1)$. We can confirm that we have the correct values of $p_0$ and $p_1$ as the numerator and denominator are primes.

SAGE
p0 = 17195743943555229331660961462727499p1 = 14311526019821336226513256266023521print(f"{p0.is_prime()=}")print(f"{p1.is_prime()=}")
OUTPUT
p0.is_prime()=Truep1.is_prime()=True

Since we have $p_0$, we can approximate a lower bound of $sk = (pk_0 - 2 * r_0) / p_0 \geq pk_0 / p_0 - 2 * 2^{191} / p_0$. By analysing the bit sizes of each parameter, we know that this lower bound is at most $2^{191 - 114 + 2} = 2^{79}$ away from the true value of $sk$. We can then decompose $sk = sk_{lb} + sk_{err}$.

SAGE
p0 = 17195743943555229331660961462727499sk_lb = pk[0] // p0 - 2 * (2 ^ 191) // p0sk_lb
OUTPUT
41565572874253689464437825525802665878958533473562648432875965578230785556539072257838190060392315994424904212374664222250474284551532742984631880350213219

Now we turn our attention to the encryption function. We can decompose each ciphertext into a series sum.

\begin{align*} ct_i & = pt_i + sk \cdot \Sigma p_j + 2 \cdot \Sigma r_j \\ & = pt_i + (sk_{lb} + sk_{err}) \cdot \Sigma p_j + \cdot \Sigma p_j + 2 \cdot \Sigma r_j & \text{Substitute sk} \\ & = pt_i + sk_{lb} \cdot \Sigma p_j + sk_{err} \cdot \Sigma p_j + 2 \cdot \Sigma r_j & \text{Expand} \\ pt_i & = ct_i - sk_{lb} \cdot \Sigma p_j - sk_{err} \cdot \Sigma p_j - 2 \cdot \Sigma r_j & \text{Rearrange} \\ \end{align*}

Notice that other than the $sk_{lb} \cdot \Sigma p_j$ term, all other terms are small relative to $sk_{lb} < 2^{514}$:

• $sk_{err} < 2^{79}$ and $\Sigma p_j < 981 \cdot 2^{114}$, therefore $sk_{err} \cdot \Sigma p_j < 981 \cdot 2^{193}$
• $2 \Sigma r_j < 2 \cdot 981 \cdot 2^{191}$

We can therefore decide that:

\begin{align*} pt_i & = ct_i - sk_{err} \cdot \Sigma p_j - 2 \cdot \Sigma r_j \mod sk_{lb} \\ & = (ct_i \mod sk_{lb}) \mod 2 & sk_{err} \; \text{is even} \\ \end{align*}

We can then offset the lower bound to the next odd number so that $sk_{err}$ is even. Using it as the secret key is sufficient to decrypt the flag!

SAGE
sk_fix = sk_approxif sk_fix % 2 == 0:    sk_fix += 1flag_bin = "".join([    str((i % sk_fix) % 2)    for i in ct])flag = b"wmctf{" + bytes.fromhex(hex(int(flag_bin, 2))[2:]) + b"}"print(f"{flag=}")
OUTPUT
flag=b'wmctf{sodayo>A<!!$%!$_Easy_G@CDp_ATtaCk}'

## nanoDiamond (-rev)

Terraria is a land of adventure! A land of mystery! Can you get all the treasure without losing your head?

server is given by instancer

Attachment: nanoDiamond.tar, nanoDiamond-rev.zip

nanoDiamond: 46 solves, 200 points
nanoDiamond-rev: 23 solves, 339 points

CHALLENGE app.py
PYTHON
# from Crypto.Util.number import *import stringimport secretsfrom hashlib import sha256from random import randint, shuffle, choice
def proof_of_work():    s = ''.join([secrets.choice(string.digits + string.ascii_letters)                for _ in range(20)])    print(f'sha256(XXXX+{s[4:]}) == {sha256(s.encode()).hexdigest()}')    if input('Give me XXXX: ') != s[:4]:        exit(1)
ROUND_NUM = 50
# nanoDiamondPREROUND_NUM = 14# nanoDiamond-revPREROUND_NUM = 13
CHEST_NUM = 6
with open('flag', 'r') as f:    flag = f.read()
white_list = ['==','(',')','0','1','and','or','B0','B1','B2','B3','B4','B5']
def calc(ans, chests, expr):    B0, B1, B2, B3, B4, B5 = chests    return ans(eval(expr))
def round():    chests = [choice((True, False)) for _ in range(CHEST_NUM)]    print("Six chests lie here, with mimics or treasure hidden inside.")    print("But don't worry. Skeleton Merchant knows what to do.")    print("Be careful, Skeleton Merchant can lie twice!")
truth = lambda r: not not r    lie = lambda r: not r    lie_num = randint(0, 2)    lie_status = [truth] * (PREROUND_NUM - lie_num) + [lie] * lie_num    shuffle(lie_status)
for i in range(PREROUND_NUM):        try:            question = input('Question: ').strip()            for word in question.split(' '):                assert word in white_list, f"({word}) No treasure for dirty hacker!"            result = calc(lie_status[i], chests, question)            print(f'Answer: {result}!')        except Exception as e:            print("Skeleton Merchant fails to understand your words.")            print(e)    print('Now open the chests:')    return chests == list(map(int, input().strip().split(' ')))

if __name__ == '__main__':
proof_of_work()
print('Terraria is a land of adventure! A land of mystery!')    print('Can you get all the treasure without losing your head?')
for i in range(ROUND_NUM):        if not round():            print('A chest suddenly comes alive and BITE YOUR HEAD OFF.')            exit(0)        else:            print('You take all the treasure safe and sound. Head to the next vault!')
print(f"You've found all the treasure! {flag}")

The challenge service involves a guessing game. Each round, the challenge server fills 6 "treasure chest" variables with True or False that players must guess. We are allowed to query an oracle using a boolean expression and limited operator set and are returned a True or False answer. At the end of 14 questions (or 13 for -rev) we must guess the value of the treasure chests for that round. The flag is given after guessing correctly for 50 rounds.

However, the oracle may randomly lie in up to 2 answers per round. This means that we cannot just do repeated queries of B0, B1 and so on because the results may be lies. We need to use a more error-tolerant way to query the chest variables.

By looking at the allowed boolean operator list, we can make some gadgets for writing our questions:

• ( 0 == 0 ) makes True
• ( 0 == 1 ) makes False
• We can check if the state of all chests is equal to a list of 6 booleans s at the same time by asking ( ( B0 == s[0] ) and ( B1 == s[1] ) ... ) and replacing s[i] by True or False gadgets. Call this the match s gadget.
• Instead of just checking one possible state of all chests s, we can check if the chest contents matches one of many states. If we have a list of states ss, we can do this by asking ( ( match s[0] ) or ( match s[1] ) ) ... ). Call this the match_one_of ss gadget.
PYTHON
def expr_true():    return "( 0 == 0 )"
def expr_false():    return "( 0 == 1 )"
def expr_chest_check(x, v):    if v:        return f"( B{x} == {expr_true()} )"    else:        return f"( B{x} == {expr_false()} )"
def expr_chest_check_match(vs):    chest_checks = [        expr_chest_check(idx, v)        for idx, v in enumerate(vs)    ]    return "( " + " and ".join(chest_checks) + " )"
def expr_chest_check_match_one_of(vss):    if len(vss) == 0:        return "0"    chest_check_alls = [        expr_chest_check_match(vs)        for vs in vss    ]    return " or ".join(chest_check_alls)

Instead of thinking of the chests as 6 boolean variables, we can treat it as a single "secret number" from 0 to 63. Using the above gadgets, we are able to make queries that ask "Is the hidden number one of 0, 1, 2 ... ". Similarly, instead of thinking of whatever answers we receive as a list of 14 (or 13) booleans, we can think of it as an "answer number" from 0 to 16383 (or 8191).

Consider the scenario where the oracle does not lie. After mapping each secret number to the same answer number, we can convert the expect answer to a list of questions to ask. For example, when mapping secret number 16 to answer number 16 (001000 in binary), the third questions should include a or ( match 16 ) gadget. When the secret number is actually 16, all questions will return False except for the third which will return True. We can then convert the boolean answers back to a number and then reverse the mapping to find the secret number. As another example, when mapping secret number 17 to answer number 17 (binary 001001) the third and sixth questions will include a or ( match 17 ) gadget.

However, if the oracle lies once during the last question, when the secret number is 16 the last answer will return True and it will be confused as answer number 17 mapping back to secret number 17; we will then guess wrongly. We cannot have two secret numbers map to answer numbers that are too close to each other in bit flips, otherwise known has having a small hamming distance.

The solution is to find 64 answer numbers such that no two of them has 4 or less hamming distance from each other; this way there will be no single answer number that can be bit flipped twice to produce two different secret numbers. We can find the 64 mapped answer numbers using a greedy search of candidate outputs from 0 to 16383 in sequence. This is effectively implementing linear error correction codes and using the nearest neighbor algorithm.

Exploit preamble
PYTHON
import stringfrom hashlib import sha256from itertools import productfrom pwn import *
def int_to_bool_arr(x, l):    return [bool(int(i)) for i in bin(x)[2:].zfill(l)]
def hamming_distance(x, y):    return sum([1 for xi, yi in zip(x, y) if xi != yi])
def new_conn():    # r = process(["python3", "app.py"])    r = remote("1.13.154.182", 30291)
proof_of_work = r.recvline().strip().decode()
stream = proof_of_work    _, _, stream = stream.partition("+")    tail, _, res = stream.partition(") == ")
for head in product(string.digits + string.ascii_letters, repeat=4):        if sha256(("".join(head) + tail).encode()).hexdigest() == res:            break    r.sendlineafter(b"Give me XXXX: ", "".join(head).encode())    return r
def play_round(r):    pass
def attempt():    progress = 0    flag = None    try:        r = new_conn()        for i in range(50):            progress = i            play_round(r)        flag = r.recvline()        print("FLAG!!!!", flag)        progress += 1    except EOFError as e:        pass    return progress, flag
Exploit code
PYTHON
n = 6nn = 2 ** nq = 14
codes = []for i in range(2 ** q):    idx = i    i = int_to_bool_arr(i, q)
near = 0    for other in codes:        dist = hamming_distance(i, other)        if dist <= 4:            near += 1            break    if near:        continue
codes.append(i)    if len(codes) == nn:        print(f"Checked {idx + 1} candidate codes to get {len(codes)} spaced out codes")        break
questions = [[] for _ in range(q)]
for idx, code in enumerate(codes):    idx_bool_arr = int_to_bool_arr(idx, n)    for question, code_res in zip(questions, code):        if code_res:            question.append(idx_bool_arr)
questions_expr = [    expr_chest_check_match_one_of(question)    for question in questions]
def play_round(r):    r.recvuntil(b"Be careful, Skeleton Merchant can lie twice!")
round_res = []
r.sendline(b"\n".join([question_expr.encode() for question_expr in questions_expr]))    for _ in questions_expr:        r.recvuntil(b"Question: ")        res = r.recvuntil(b"!").strip().decode()        round_res.append("True" in res)
selected_code = min(enumerate([        hamming_distance(round_res, i)        for i in codes    ]), key=lambda x: x[1])
solution = " ".join(list(bin(selected_code[0])[2:].zfill(n)))    r.recvuntil(b"Now open the chests:\n")    r.sendline(solution.encode())    r.recvline()
print(*attempt())
OUTPUT
Checked 14079 candidate codes to get 64 spaced out codesFLAG!!!! b"You've found all the treasure! WMCTF{TERR4R1a_IS_4_LAND_0F_@DVENturE}\n"50 b"You've found all the treasure! WMCTF{TERR4R1a_IS_4_LAND_0F_@DVENturE}\n"

For the harder variant -rev, the 8192 output states are no longer enough to uniquely identify the $64$ states which are sufficiently spaced out. During CTF time, I decided to use a heuristic approach and generate an imperfect but good enough mapping.

Firstly, we choose output states heuristically. Instead of the initial hard limit on 4 or less hamming distance, we pick new answer numbers such that it must be further than 2 hamming distance from prior selected numbers and must have at most 3 prior selected outputs with 3 or 4 hamming distance. Next, instead of iterating candidate answer numbers sequentially, we iterate through a 13-dimensional Hilbert curve to preserve some amount of "hamming distance proximity" between sequential candidate answer numbers.

With these heuristics, we are able to get 64 candidate answer numbers which translates to a 93% chance that a single round's answer will be correct, and a 2% chance that 50 guesses will be correct in a row. Running several solve scripts in parallel gets us the flag in a reasonable amount of time.

-rev exploit code
PYTHON
import multiprocessing
n = 6nn = 2 ** nq = 13
cur = 0hilbert = [0]for i in range(1, 2 ** q):    lsb = bin(i)[::-1].index("1")    cur = cur ^ (1 << lsb)    hilbert.append(cur)
codes = []for idx, i in enumerate(hilbert):    i = int_to_bool_arr(i, q)
very_near = 0    near = 0    for other in codes:        dist = hamming_distance(i, other)        if dist <= 2:            very_near += 1            break        if dist <= 4:            near += 1
if very_near:        continue    if near > 3:        continue
codes.append(i)    if len(codes) == nn:        print(f"Checked {idx + 1} candidate codes to get {len(codes)} spaced out codes")        break
questions = [[] for _ in range(q)]
for idx, code in enumerate(codes):    idx_bool_arr = int_to_bool_arr(idx, n)    for question, code_res in zip(questions, code):        if code_res:            question.append(idx_bool_arr)
questions_expr = [    expr_chest_check_match_one_of(question)    for question in questions]
def play_round(r):    r.recvuntil(b"Be careful, Skeleton Merchant can lie twice!")
round_res = []
r.sendline(b"\n".join([question_expr.encode() for question_expr in questions_expr]))    for _ in questions_expr:        r.recvuntil(b"Question: ")        res = r.recvuntil(b"!").strip().decode()        round_res.append("True" in res)
selected_code = min(enumerate([        hamming_distance(round_res, i)        for i in codes    ]), key=lambda x: x[1])
solution = " ".join(list(bin(selected_code[0])[2:].zfill(n)))    r.recvuntil(b"Now open the chests:\n")    r.sendline(solution.encode())    r.recvline()
with multiprocessing.Pool(processes=4) as pool:    for progress, flag in pool.imap(attempt, range(1000)):        print(progress, flag)        if flag:            break
OUTPUT
Checked 6313 candidate codes to get 64 spaced out codes6 None6 None29 None[... many lines ...]4 None1 None9 NoneFLAG!!!! b"You've found all the treasure! WMCTF{7ErrAr14_Is_a_lAND_0F_AdVeNTURe!!!!!}\n"50 b"You've found all the treasure! WMCTF{7ErrAr14_Is_a_lAND_0F_AdVeNTURe!!!!!}\n"

This approach so far only considers offline queries where the same questions were asked regardless of intermediate answers. There exists more robust solutions that use online queries where the questions can change depending on earlier answers.

A viable online solution would involve using using match_one_of ss questions to match a randomly selected half of the possible secret numbers each time. After each question, keep track of a penalty for each secret number that is equal to how many times the oracle would have lied if that number was the true secret number. We can also ignore possible secret numbers once they would have needed more than 3 lies. The solution then guesses the secret number that would have required the least number of lies. This strategy works for one round 97% of the time and has a 20% chance of getting the flag.

A final improvement can be done by sorting the secret numbers in increasing number of lies needed so far; this brings the one round success rate up to 99.7%, getting the flag 86% of the time.

-rev online exploit code
PYTHON
n = 6nn = 2 ** nq = 13
def play_round(r):    r.recvuntil(b"Be careful, Skeleton Merchant can lie twice!")
candidates = [(0, i) for i in range(64)]
for _ in range(q):        candidates.sort()        selected = [            i[1]            for i in candidates[::2]        ]
question_expr = expr_chest_check_match_one_of([            int_to_bool_arr(i, n)            for i in selected        ])        r.sendlineafter(b"Question: ", question_expr.encode())        res = r.recvuntil(b"!").strip().decode()        res = "True" in res
candidates = [            (i if (j not in selected) ^ (res) else i + 1, j)            for i, j in candidates        ]        candidates = [            (i, j)            for i, j in candidates            if i < 3        ]
candidates.sort()    selected_code = candidates[0][1]
solution = " ".join(list(bin(selected_code)[2:].zfill(n)))    r.recvuntil(b"Now open the chests:\n")    r.sendline(solution.encode())    return r.recvline()
print(*attempt())
OUTPUT
FLAG!!!! b"You've found all the treasure! WMCTF{7ErrAr14_Is_a_lAND_0F_AdVeNTURe!!!!!}\n"50 b"You've found all the treasure! WMCTF{7ErrAr14_Is_a_lAND_0F_AdVeNTURe!!!!!}\n"

It turns out that this challenge a variant of the Ulam's game but with two lies instead of one. There is a paper that outlines the optimal and deterministic solution.

Also see: