WMCTF2022 Crypto Writeups

ecc
homo
nanoDiamond (-rev)

ecc

easy checkin

wmctf{a+b+c}

Attachment: ecc.zip

28 solves, 257 points

CHALLENGE output.txttext
flag bits: 606
e = 0x10001
n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259
c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997
G = (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 codesage
e = 0x10001
n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259
c = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997
gx, 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 == 0
assert 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 // p
assert p * q == n
print(f"{p=}")
print(f"{q=}")

a = a_mod_n % p
b = b_mod_n % p
c = 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=8308060309959524788634404677678479024666400240233812713350984932475838872076486898595574202532027412806488106365658717017155800093596205985127436125626827
q=7373872192463191738033336697886150566044010386580579101665086651212656675570461681793837375772679015765588192207913025640568056955479671819537473774809617
a=3629864911627283784723617758993690217446918991113173559686999
b=988958437986133278846018591274848194060347135958347118693976
c=1910700325063785326106590899271324158468993875758894973739361
flag=b'wmctf{$$U_c0u1d_s01v3_e11iptiCurv3_s0_34sily$$0f19d82199a0db0dee31fa12330307ea90aa}'

Also see:

corCTF 2022 threetreasures: Archived challenge, writeup by jsurin

homo

hum ah ah ah ah ah ah

Attachment: homo.zip

17 solves, 415 points

CHALLENGE gentry.pypython
from Crypto.Util.number import *
from secret import flag
from random import *
assert flag.startswith(b'wmctf{') and flag.endswith(b'}')
flaglen = len(flag) - 7
flag = bytes_to_long(flag[6:-1])
pbit = 114
qbit = 514
rbit = 191
keylen = 981
nouse = 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

1
5/4
6/5
155/129
471/392
5807/4833
12085/10058
17892/14891
29977/24949
107823/89738
569092/473639
1815099/1510655
64097557/53346564
65912656/54857219
261835525/217918221
[... 50 lines ...]
2951728755016117362045052552604515/2456639446338143456424619810722688
4748005062846370656538636303374328/3951628857827730923362878818433611
12447738880708858675122325159353171/10359897161993605303150377447589910
17195743943555229331660961462727499/14311526019821336226513256266023521
50294551491796838994976191539893590246371850701615512602409776565638886755491251194723604419288046/41858717174017021585879634221918469662518319668913235490886250442466870097856492150024543904082535
50294551491796838994976191539893590246371850701615512602409776582834630699046480526384565882015545/41858717174017021585879634221918469662518319668913235490886250456778396117677828376537800170106056
201178205967187355979904766159574360985487402806462050409639106314142778852630692773877302065334681/167434868696068086343518536887673878650073278675652941963545001812802058450889977279637944414400703
1056185581327733618894500022337765395173808864733925764650605308153548524962199944395771076208688950/879033060654357453303472318660287862912884713047177945308611259520788688372127714774727522242109571
4425920531278121831557904855510635941680722861742165109012060338928336878701430470356961606900090481/3683567111313497899557407811528825330301612130864364723197990039895956811939400836378548033382838987
[... 160 lines ...]
1995812930048656259689750634098332502261295378791730205719262185407281355554729107523343915940690619750857821466849215869675288475892851625941071610787149850415656055218545600091197780141/1661058036968057004151319199473651391641931657789335689259118550242752803127205942086965805615202748328958375752782431271802792923383196577427148635942184055529900527165482251920597490746
78086230048062163215827557039168524732591982807415828566518545608000790736767714294344434083507317015679154027430740094529625782791578191740474785551280839656543126510706171631964696056437/64988936610761473414393498735925625010694712538269673029760236763686740985793934501032287733848472841335448489099809860277738303243350925201061196867063765424769804481428636327890419607461
80082042978110819475517307673266857234853278186207558772237807793408072092322443401867777999448007635430011848897589310399301071267471043366415857162067989506958782565924717232055893836578/66649994647729530418544817935399276402336644196059008719019355313929493788921140443119253539463675589664406864852592291549541096166734121778488345503005949480299705008594118579811017098207
238250316004283802166862172385702239202298539179830946110994161194816934921412601098079990082403332286539177725225918715328227925326520278473306499875416818670460691642555606096076483729593/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 = 17195743943555229331660961462727499
p1 = 14311526019821336226513256266023521
print(f"{p0.is_prime()=}")
print(f"{p1.is_prime()=}")

output

p0.is_prime()=True
p1.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 = 17195743943555229331660961462727499
sk_lb = pk[0] // p0 - 2 * (2 ^ 191) // p0
sk_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_approx
if sk_fix % 2 == 0:
    sk_fix += 1
flag_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.pypython
# from Crypto.Util.number import *
import string
import secrets
from hashlib import sha256
from 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

# nanoDiamond
PREROUND_NUM = 14
# nanoDiamond-rev
PREROUND_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.

Question gadget generatorspython
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 preamblepython
import string
from hashlib import sha256
from itertools import product
from 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 codepython
n = 6
nn = 2 ** n
q = 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 codes
FLAG!!!! 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 codepython
import multiprocessing

n = 6
nn = 2 ** n
q = 13

cur = 0
hilbert = [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 codes
6 None
6 None
29 None
[... many lines ...]
4 None
1 None
9 None
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"

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 codepython
n = 6
nn = 2 ** n
q = 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:

HackASat 2021 Bit Flipper : Archived challenge, writeup by widow