blog > WMCTF 2022 Crypto Writeups
2022 Aug 22 ctfcrypto

WMCTF2022 Crypto Writeups

ecc

easy checkin

wmctf{a+b+c}

Attachment: ecc.zip

28 solves, 257 points

CHALLENGE output.txt
TEXT COPY TEXT?
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 y2=x3+ax+bmodpy^2 = x^3 + a \cdot x + b \mod p for some unknown aa, bb and pp. 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 pp, we know that nn is a multiple of pp. We can solve for this equation modulo nn instead; instead of finding aa and bb we obtain some a=a+kapa' = a + k_a \cdot p and b=b+kbpb' = b + k_b \cdot p respectively.

The next information we use is the fact that GGG=3GG \cdot G \cdot G = 3G under curve mod  p\bmod\;p. Though we cannot do calculations mod  p\bmod\;p, we can do calculations mod  n\bmod\;n (using earlier obtained aa'). The resultant 3Gmodn3G \bmod n when taken mod  p\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 aa and bb, padding each value to a 202-bit binary string and decoding the result as ASCII.

Exploit code
SAGE COPY SAGE?
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 COPY OUTPUT?
p=8308060309959524788634404677678479024666400240233812713350984932475838872076486898595574202532027412806488106365658717017155800093596205985127436125626827
q=7373872192463191738033336697886150566044010386580579101665086651212656675570461681793837375772679015765588192207913025640568056955479671819537473774809617
a=3629864911627283784723617758993690217446918991113173559686999
b=988958437986133278846018591274848194060347135958347118693976
c=1910700325063785326106590899271324158468993875758894973739361
flag=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 COPY PYTHON?
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 ii-th is in the form pki=skpi+2ripk_i = sk \cdot p_i + 2\cdot* r_i for some random 114 bit prime pip_i and 191 bit prime rir_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 sksk to remove all skpisk \cdot p_i terms and then modulo 22 to remove all 2ri2 \cdot r_i terms, yielding the plaintext bit.

Due to the sizes of the various parameters, in each item of the public key list pkipk_i, the skpisk \cdot p_i term is much larger in magnitude than the 2ri2 \cdot r_i term. We can take the ratio of sk0sk_0 and sk1sk_1 to recover p0p_0 and p1p_1 using continued fractions.

SAGE COPY 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 COPY 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 pk0/pk1pk_0 / pk_1 shifts from approximating p0/p1p_0/p_1 to approximating (skp0+2r0)/(skp1+2r1)(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 p0p_0 and p1p_1 as the numerator and denominator are primes.

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

Since we have p0p_0, we can approximate a lower bound of sk=(pk02r0)/p0pk0/p022191/p0sk = (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 2191114+2=2792^{191 - 114 + 2} = 2^{79} away from the true value of sksk. We can then decompose sk=sklb+skerrsk = sk_{lb} + sk_{err}.

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

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

cti=pti+skΣpj+2Σrj=pti+(sklb+skerr)Σpj+Σpj+2ΣrjSubstitute sk=pti+sklbΣpj+skerrΣpj+2ΣrjExpandpti=ctisklbΣpjskerrΣpj2ΣrjRearrange\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 sklbΣpjsk_{lb} \cdot \Sigma p_j term, all other terms are small relative to sklb<2514sk_{lb} < 2^{514}:

  • skerr<279sk_{err} < 2^{79} and Σpj<9812114\Sigma p_j < 981 \cdot 2^{114}, therefore skerrΣpj<9812193sk_{err} \cdot \Sigma p_j < 981 \cdot 2^{193}
  • 2Σrj<298121912 \Sigma r_j < 2 \cdot 981 \cdot 2^{191}

We can therefore decide that:

pti=ctiskerrΣpj2Σrjmodsklb=(ctimodsklb)mod2skerr  is even\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 skerrsk_{err} is even. Using it as the secret key is sufficient to decrypt the flag!

SAGE COPY 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 COPY 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 COPY PYTHON?
# 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 generators
PYTHON COPY 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 COPY PYTHON?
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 code
PYTHON COPY PYTHON?
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 COPY 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 6464 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 COPY PYTHON?
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 COPY 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 code
PYTHON COPY PYTHON?
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 COPY 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:


Newer: SECCON CTF 2022 Crypto Writeups

Older: UIUCTF 2022 Crypto + Misc Writeups