0x2 - Learn CTF: Cryptography

2026-02-23 23:40 +0700

error-code — Merkle-Hellman implementation bug
nito — truncated-state recovery with Coppersmith

error-code — Merkle-Hellman implementation bug

Summary

Category: Cryptography
Challenge: error-code
Core scheme: Merkle-Hellman knapsack (subset-sum)
Given files: chall.py, output
Recovered flag:

CBC{4_cl4ss1c_subs3t_sum_pr0blem_r1ght_9c209955}

Problem statement (practical)

The challenge author says they implemented Merkle-Hellman, but decryption does not work. The job is to identify the implementation error and recover the plaintext.

Root cause

In Merkle-Hellman, the private sequence W must be superincreasing:

$$ W_i > \sum_{j=0}^{i-1} W_j $$

But in chall.py, sequence generation only enforces monotonic growth from the previous term:

def getSequence(size):
    W = []
    w0 = 99999
    for _ in range(size):
        wi = random.randint(w0 + 1, 2 * w0)
        W.append(wi)
        w0 = wi
    return W

This condition is too weak. It creates an increasing sequence, but not necessarily superincreasing. So the classic private-key greedy decryption path is invalid/unreliable.

Why encryption still leaks

Even with that bug, encryption is still linear subset sum over public key coefficients:

$$ c = \sum b_i \cdot pub_i $$

For this instance, each ciphertext block uses 48 coefficients (because len(flag) = 48), and there are 8 blocks in ct_lst. That is directly solvable as subset-sum with meet-in-the-middle.

Solver approach (meet-in-the-middle)

Split public key into two halves of 24 + 24:

Enumerate all subset sums of first half, map sum -> mask.
Enumerate all subset sums of second half, map sum -> mask.
For each ciphertext ct, find s1 + s2 = ct.
Recover 48 bits for that block from masks.
Reconstruct original integer/bytes according to the challenge bit-order.

Repro solver

# solve.py
pub = [399556779992238, 34298225407642, 20642131245786, 65490996326207, 122628372242215, 9829827117171,
       396026745275353, 167294584165304, 296444912760811, 80351792351840, 409914932982222, 85802434589354,
       401591010427922, 187008763237642, 152108391468386, 31583306493979, 25525613569306, 162082080588558,
       126634456980331, 164430139182734, 83701623822886, 402679681495011, 192369423507295, 160258497915791,
       258919777739363, 64531362352673, 306761417690632, 341920025542429, 26318306417850, 4818756642968,
       207127269238936, 200786177672536, 179782888357779, 58758524994661, 278516593354891, 158487072996052,
       291093591620507, 64579822017072, 210651490815487, 217428030502253, 258408901203031, 360703727369716,
       29799816650929, 279304424652560, 34106935830323, 424511985165056, 296198681936242, 429117013029379]

cts = [4732215009804500, 4609442091199342, 5692746616356737, 3525483039088576,
       6333124120174760, 5291548626672528, 4905835028190278, 4783246254953126]

HALF = 24
A, B = pub[:HALF], pub[HALF:]

sa = {0: 0}
for i, w in enumerate(A):
    bit = 1 << i
    for s, m in list(sa.items()):
        ns = s + w
        if ns not in sa:
            sa[ns] = m | bit

sb = {0: 0}
for i, w in enumerate(B):
    bit = 1 << i
    for s, m in list(sb.items()):
        ns = s + w
        if ns not in sb:
            sb[ns] = m | bit

chunks = []
for ct in cts:
    found = None
    for s1, m1 in sa.items():
        need = ct - s1
        m2 = sb.get(need)
        if m2 is not None:
            found = (m1, m2)
            break
    if found is None:
        raise RuntimeError(f"No subset solution for ct={ct}")

    m1, m2 = found
    bits = [((m1 >> i) & 1) for i in range(24)] + [((m2 >> i) & 1) for i in range(24)]
    chunks.append(bits)

msg = 0
for j, bits in enumerate(chunks):
    val = sum((b << i) for i, b in enumerate(bits))
    msg |= val << (48 * j)

raw = msg.to_bytes(48, 'big')
print(raw.decode())

Expected output:

CBC{4_cl4ss1c_subs3t_sum_pr0blem_r1ght_9c209955}

Correct key-generation fix

To make decryption valid in Merkle-Hellman, generate W as superincreasing:

def getSequence(size):
    W = []
    s = 1
    for _ in range(size):
        wi = random.randint(s + 1, 2 * s)
        W.append(wi)
        s += wi
    return W

Keep:

q > sum(W)
gcd(r, q) = 1

Then private-key decryption works as intended.

nito — truncated-state recovery with Coppersmith

Summary

Category: Cryptography
Challenge: nito
Given files: challenge.sage, output.txt
Core idea: recover unknown 64-bit tails from leaked high bits of modularly-related values
Recovered flag:

CBC{cryp70_i5_ju57_AI_5p33drun?}

Given construction

Challenge generates:

prime p (256-bit)
random a0
a1 = a0^2 mod p
leaked values:
- b0 = a0 >> 64
- b1 = a1 >> 64
ciphertext:

c = bytes_to_long(flag) ^^ pow(a1, 42, p)

Let unknown low 64-bit parts be x, y:

$$ a0 = (b0 « 64) + x, \quad a1 = (b1 « 64) + y, \quad 0 \le x,y < 2^{64} $$

From a1 = a0^2 mod p:

$$ ((b0 « 64) + x)^2 - ((b1 « 64) + y) \equiv 0 \pmod p $$

This is a bivariate small-root problem over bounds (2^64, 2^64).

Solve strategy

Use Coppersmith small-roots on the polynomial above to recover (x, y).

I used:

Sage (via Docker image sagemath/sagemath)
coppersmith.sage from defund/coppersmith

Found root:

x = 8804081745998249949
y = 10378144287870099762

Then reconstruct a1, compute pow(a1,42,p), XOR with c, and decode bytes.

Repro script (Sage)

load('coppersmith.sage')

p = 12721492641695199020302023719104846741933769337250722901191654350831830951811
c = 41191888024213095867034353749467947785476609376959645738506308145695929457707
b0 = 505745372664810403157022893345560792860796814985411337944
b1 = 55363083749705718410582971847380097690792442149083200327

kbits = 64
B0 = b0 << kbits
B1 = b1 << kbits

PR.<x,y> = PolynomialRing(Zmod(p))
f = (B0 + x)^2 - (B1 + y)

roots = small_roots(f, bounds=(2^64,2^64), m=3, d=3)
for xv, yv in roots:
    a1 = B1 + int(yv)
    m = c ^^ power_mod(a1, 42, p)
    print(Integer(m).to_bytes((Integer(m).nbits()+7)//8, 'big'))

Expected output:

CBC{cryp70_i5_ju57_AI_5p33drun?}

Zero's Blog