Square Cipher - BuckeyeCTF 2025

Đề bài

---

Giải

Source code

(lambda x=int(input('> '),16):(all((int(bin(y).translate(str.maketrans('1b','fx')),0)&x).bit_count()==15 for y in[511,261632,1838599,14708792,117670336,133955584,68585259008,35115652612096,246772580483072,1974180643864576,15793445150916608,17979214137393152,9205357638345293824,4713143110832790437888,4731607904558235517441,9463215809116471034882,18926431618232942069764,33121255085135066300416,37852863236465884139528,75705726472931768279056,151411452945863536558112,264970040681080530403328,302822905891727073116224,605645811783454146232448,1211291623566908292464896,2119760325448644243226624,2413129272746388704198656])and x&2135465562637171390290201561322170738230609084732268110734985633502584038857972308065155558608880==1271371190459412480076309932821732439054921890752535035282222258816851982409101952239053178406432 or print('incorrect'))and print(__import__('os').environ.get('FLAG','bctf{fake_flag}')))()

Đây chỉ là mã hóa đơn giản, mình sẽ giải mã như sau

Script

y_list = [511,261632,1838599,14708792,117670336,133955584,68585259008,35115652612096,
          246772580483072,1974180643864576,15793445150916608,17979214137393152,
          9205357638345293824,4713143110832790437888,4731607904558235517441,
          9463215809116471034882,18926431618232942069764,33121255085135066300416,
          37852863236465884139528,75705726472931768279056,151411452945863536558112,
          264970040681080530403328,302822905891727073116224,605645811783454146232448,
          1211291623566908292464896,2119760325448644243226624,2413129272746388704198656]

mask   = 2135465562637171390290201561322170738230609084732268110734985633502584038857972308065155558608880
target = 1271371190459412480076309932821732439054921890752535035282222258816851982409101952239053178406432

def M(y):
    return int(bin(y).translate(str.maketrans('1b','fx')), 0)

L = max(y.bit_length() for y in y_list)
Nbits = 4*L

pos_sets = []
for y in y_list:
    positions = []
    for i in range(L):  
        if (y >> i) & 1:
            positions.extend([4*i + j for j in range(4)]) 
    pos_sets.append(positions)

# bit cố định theo x & mask == target
fixed = {p: (target >> p) & 1 for p in range(Nbits) if (mask >> p) & 1}
free_positions = [p for p in range(Nbits) if p not in fixed]

from collections import defaultdict
bit_to_eqs = defaultdict(list)
for ei, poslist in enumerate(pos_sets):
    for p in poslist:
        bit_to_eqs[p].append(ei)

def eval_sums(bits):
    return [sum(bits[p] for p in poslist) for poslist in pos_sets]

def objective(sums):
    return sum((s-15)**2 for s in sums)

import random
random.seed(0)

def solve(max_iters=100000, restarts=50, sample_size=150):
    best = None
    best_obj = 1e18
    for r in range(restarts):
        bits = [random.randint(0,1) for _ in range(Nbits)]
        for p,v in fixed.items(): bits[p]=v
        sums = eval_sums(bits)
        obj = objective(sums)

        for it in range(max_iters):
            if all(s==15 for s in sums):
                x=0
                for p,b in enumerate(bits):
                    if b: x |= (1<<p)
                return x
            improved=False; best_delta=0; best_p=None
            k=min(sample_size, len(free_positions))
            for p in random.sample(free_positions, k=k):
                old = bits[p]
                change = 1-2*old 
                delta = 0
                for ei in bit_to_eqs[p]:
                    s = sums[ei]
                    delta += ((s+change)-15)**2 - (s-15)**2
                if delta < best_delta:
                    best_delta = delta; best_p=p; improved=True
            if improved:
                p = best_p
                old = bits[p]
                change = 1-2*old
                bits[p] = 1-old
                for ei in bit_to_eqs[p]:
                    sums[ei] += change
                obj += best_delta
            else:
                p = random.choice(free_positions)
                old = bits[p]
                change = 1-2*old
                bits[p] = 1-old
                for ei in bit_to_eqs[p]:
                    sums[ei] += change
                obj = objective(sums)
        if obj < best_obj:
            best_obj = obj; best = bits[:]
    raise RuntimeError("no solution found (tăng restarts/iters nếu cần)")

if __name__ == "__main__":
    x = solve()
    print(hex(x)[2:])
    ok1 = all(((M(y) & x).bit_count()==15) for y in y_list)
    ok2 = (x & mask) == target
    print("checks:", ok1, ok2)

Run

┌──(kali㉿kali)-[/BuckeyeCTF 2025/rev/Square Cipher]
└─$ python3 decode.py
f9869482145095632e52cc2287a0175b503961d034ec84718a5465141a1eb07869426cd2b3cd84620
checks: True True

netcat và lấy flag

┌──(kali㉿kali)-[/BuckeyeCTF 2025/rev/Square Cipher]
└─$ ncat --ssl square-cipher.challs.pwnoh.io 1337
> f9869482145095632e52cc2287a0175b503961d034ec84718a5465141a1eb07869426cd2b3cd84620
bctf{5um_0f_f1r57_n_0dd_numb3r5_c1ph3r_025165aa}

---

Flag

Flag: bctf{5um_0f_f1r57_n_0dd_numb3r5_c1ph3r_025165aa}