Less is more — asisctf2026

Description

Please redownload the attachment!

English summary: the first local attachment was obsolete, and the real task was a different binary PKP-vault format stored in new_less_is_more.txz. The updated archive contains challenge.py and flag.enc; the goal is to recover the hidden real keys from leaked transcript records and use them to unseal the encrypted flag.

Analysis

The decisive step was ignoring the old output.txt instance and re-downloading the attachment. The obsolete files under less_is_more/ describe a different challenge path; the solvable instance is the updated archive with:

• MAGIC = b'ASIS117\x04'
• zlib-compressed, pickled body
• fields pub, records, sealed
• parameters P=827, N=548, K=274, T=345, W=75, REAL=7, SLOTS=17

The public helpers are all reproducible from the code:

• chal(cmt, salt, msg)
• token(cmt, node)
• label(cmt, seed)
• take(seed, tag, n, k)

Only REAL = 7 secret keys are genuine, but SLOTS = 17 public slots are published because 10 junk keys are mixed in.

The break comes from two bugs inside Box.one():

1. State carry-over bug

   target = (37 * serial + 11) % T
   if sha256(b'v' + root) % 100 < 72:
       f[target] = self.state[target]

   Instead of using int(b[target] != 0), one position often inherits the previous round state. A genuinely challenged round can therefore be treated as if it were revealable.

2. Decoy reveal bug

   Fake path entries are chosen from indices with f[i] == 1, i.e. positions that correspond to real challenged rounds, and appended to path.

Together these bugs sometimes reveal both:

• the challenged leaf seed, and
• the corresponding response bitset.

That is enough to turn one buggy record into a constraint on a real secret key. From a revealed challenged seed we recompute:

v = take(leaf_seed, b'n', N, K)

For the matching response, the bitset gives the unordered image set S = invs[x - 1](v) for the real key class x = chal(...)[i].

Collecting many (v, S) pairs for the same class lets us recover the inverse permutation position-by-position by intersecting possibilities. Two filters are needed to avoid poisoned samples:

• discard leaf-level decoys from path (node >= base0)
• discard wholesale-corrupted responses from the extra 14% corruption bug when contradiction count bad > 3

The updated instance provided enough leakage:

• records = 5963
• leaked round-openings: 574
• per key: {1: 92, 2: 70, 3: 85, 4: 71, 5: 87, 6: 86, 7: 83}
• unresolved positions: 0/548 for every real key

Recovered real-key to public-slot matching:

• 1 -> 0
• 2 -> 4
• 3 -> 14
• 4 -> 2
• 5 -> 6
• 6 -> 16
• 7 -> 12

After recovering the permutation part, the diagonal part d is solved by testing candidate public slots against the RREF relation:

public(g, item) = red(G[:, p] * diag(1 / d))

This determines d up to the same global scalar normalization already removed by pack_key().

Finally, recompute pack_key(real_keys), derive the pad with SHAKE256(b'o' + pack_key(real_keys)), XOR it with sealed, and recover the flag.

Solution

1. Use the updated attachment, not the obsolete less_is_more/output.txt challenge.
2. Parse flag.enc after checking the ASIS117\x04 magic, then decompress and unpickle the body.
3. Recompute chal(cmt, salt, msg) for every record.
4. Walk every path entry, invert token(cmt, e), expand internal tree nodes, and keep only anomalous blocks that cover exactly one challenged round.
5. For each leaked challenged seed, compute v = take(leaf_seed, b'n', N, K) and pair it with the matching response set S.
6. Group constraints by real class x in {1..7} and intersect possible inverse-permutation images until all 548 positions are fixed.
7. For each recovered permutation, test public slots and solve the diagonal entries d from the public RREF relation.
8. Rebuild the 7 real keys, compute pack_key(real_keys), derive the SHAKE256 pad, and XOR it with sealed.

Working solver used for reproduction:

#!/usr/bin/env python3
import sys, struct, zlib, pickle, hashlib

MAGIC = b'ASIS117\x04'

def inv(x, P):
    return pow(x, P - 2, P)

def stream(seed, tag, n):
    return hashlib.shake_256(tag + seed).digest(8 * n)

def take(seed, tag, n, k):
    b, a = stream(seed, tag, k), list(range(n))
    for i in range(k):
        j = i + int.from_bytes(b[8 * i:8 * i + 8], 'big') % (n - i)
        a[i], a[j] = a[j], a[i]
    return a[:k]

def chal(cmt, salt, msg, T, W, REAL):
    b = hashlib.shake_256(b'c' + cmt + salt + msg).digest(8 * (2 * T + 2))
    a = list(range(T))
    for i in range(T - 1, 0, -1):
        j = int.from_bytes(b[8 * (T - 1 - i):8 * (T - i)], 'big') % (i + 1)
        a[i], a[j] = a[j], a[i]
    out = [0] * T
    for i in a[:W]:
        out[i] = int.from_bytes(b[8 * (T + i):8 * (T + i + 1)], 'big') % REAL + 1
    return out

def token(cmt, node):
    mask = int.from_bytes(hashlib.sha256(b'm' + cmt).digest()[:2], 'big') & 1023
    return node ^ mask

def label(cmt, seed):
    return hashlib.sha256(b't' + cmt + seed).digest()[:8]

def tree_depth(T):
    z, depth = 1, 0
    while z < T:
        z <<= 1
        depth += 1
    return depth

def expand_leaves(node, seed, depth, T, out):
    base0 = 1 << depth
    stack = [(node, seed)]
    while stack:
        u, s = stack.pop()
        if u >= base0:
            i = u - base0
            if i < T:
                out[i] = s
            continue
        stack.append((2 * u, hashlib.sha256(b'l' + s).digest()))
        stack.append((2 * u + 1, hashlib.sha256(b'r' + s).digest()))

def bits_to_set(buf, n):
    v = int.from_bytes(buf, 'little')
    return set(i for i in range(n) if (v >> i) & 1)

def red(mat, P):
    a = [row[:] for row in mat]
    h, w, r = len(a), len(a[0]), 0
    piv = []
    for c in range(w):
        z = next((i for i in range(r, h) if a[i][c]), None)
        if z is None:
            continue
        a[r], a[z] = a[z], a[r]
        u = inv(a[r][c], P)
        a[r] = [(x * u) % P for x in a[r]]
        for i in range(h):
            if i != r and a[i][c]:
                u = a[i][c]
                a[i] = [(x - u * y) % P for x, y in zip(a[i], a[r])]
        piv.append(c)
        r += 1
        if r == h:
            break
    return a, piv

def mat_inv(mat, P):
    n = len(mat)
    aug = [row[:] + [1 if i == j else 0 for j in range(n)] for i, row in enumerate(mat)]
    r_, piv = red(aug, P)
    assert len(piv) == n
    return [row[n:] for row in r_]

def matvec(mat, vec, P):
    return [sum(m * v for m, v in zip(row, vec)) % P for row in mat]

def pack_key(key, P):
    out = bytearray()
    for p, d in key:
        u = inv(d[0], P)
        for x in p:
            out.extend(x.to_bytes(2, 'little'))
        for x in d:
            out.extend((x * u % P).to_bytes(2, 'little'))
    return bytes(out)

def recover_invs(N, cons):
    possible = [set(range(N)) for _ in range(N)]
    for v_set, S_set in cons:
        bad = 0
        for j in v_set:
            if not (possible[j] & S_set):
                bad += 1
                if bad > 3:
                    break
        if bad > 3:
            continue
        comp = set(range(N)) - S_set
        for j in range(N):
            target = S_set if j in v_set else comp
            new = possible[j] & target
            if new:
                possible[j] = new
    invs = [None] * N
    for j in range(N):
        if len(possible[j]) == 1:
            invs[j] = next(iter(possible[j]))
    used = set(v for v in invs if v is not None)
    free_vals = [v for v in range(N) if v not in used]
    free_js = [j for j in range(N) if invs[j] is None]
    changed = True
    while changed and free_js:
        changed = False
        for j in list(free_js):
            cand = [v for v in possible[j] if v in free_vals]
            if len(cand) == 1:
                invs[j] = cand[0]
                free_vals.remove(cand[0])
                free_js.remove(j)
                changed = True
    return invs, free_js

def recover_p_d(g, invs, pubs, P, N, K):
    p_arr = [None] * N
    for j in range(N):
        p_arr[invs[j]] = j
    A = [[g[i][p_arr[j]] for j in range(N)] for i in range(K)]
    _, piv = red([row[:] for row in A], P)
    A_piv = [[A[i][c] for c in piv] for i in range(K)]
    A_piv_inv = mat_inv(A_piv, P)
    U = [matvec(A_piv_inv, [A[i][c] for i in range(K)], P) for c in range(N)]
    for cand_idx, R in enumerate(pubs):
        d_pivot = [None] * K
        d_pivot[0] = 1
        ok = True
        for m in range(1, K):
            val = None
            for c in range(N):
                u0, um = U[c][0], U[c][m]
                if u0 and um:
                    val = (R[m][c] * u0 * inv((R[0][c] * um) % P, P)) % P
                    break
            if val is None:
                ok = False
                break
            d_pivot[m] = val
        if not ok:
            continue
        d = [None] * N
        good = True
        for c in range(N):
            m = next((m for m in range(K) if U[c][m]), None)
            if m is None:
                good = False
                break
            d[c] = (d_pivot[m] * U[c][m] % P) * inv(R[m][c], P) % P
        if not good:
            continue
        test, _ = red([[(A[i][j] * inv(d[j], P)) % P for j in range(N)] for i in range(K)], P)
        if test == R:
            u0 = inv(d[0], P)
            d_norm = [(v * u0) % P for v in d]
            return cand_idx, p_arr, d_norm
    return None, p_arr, None

def main():
    path = sys.argv[1] if len(sys.argv) > 1 else 'flag.enc'
    with open(path, 'rb') as f:
        blob = f.read()
    assert blob[:8] == MAGIC
    (ln,) = struct.unpack('>I', blob[8:12])
    data = pickle.loads(zlib.decompress(blob[12:12 + ln]))
    pub = data['pub']
    P, N, K, T, W, REAL, SLOTS = (pub['p'], pub['n'], pub['k'], pub['t'], pub['w'], pub['real'], pub['slots'])
    g = pub['g']
    pubs = pub['pub']
    records = data['records']
    sealed = data['sealed']
    depth = tree_depth(T)
    constraints = {x: [] for x in range(1, REAL + 1)}
    base0 = 1 << depth
    for rec in records:
        cmt, salt, msg = rec['cmt'], rec['salt'], rec['msg']
        b = chal(cmt, salt, msg, T, W, REAL)
        rsp_by_label = {lbl: bts for lbl, bts in rec['rsp']}
        for e, seed in rec['path']:
            node = token(cmt, e)
            if node >= base0:
                continue
            covered = {}
            expand_leaves(node, seed, depth, T, covered)
            nonzero = [i for i in covered if b[i] != 0]
            if len(nonzero) != 1:
                continue
            i = nonzero[0]
            leaf_seed = covered[i]
            x = b[i]
            lbl = label(cmt, leaf_seed)
            bts = rsp_by_label.get(lbl)
            if bts is None:
                continue
            v = take(leaf_seed, b'n', N, K)
            S = bits_to_set(bts, N)
            if len(S) == K:
                constraints[x].append((set(v), S))
    real_keys = []
    for x in range(1, REAL + 1):
        invs, unresolved = recover_invs(N, constraints[x])
        assert not unresolved
        idx, p_arr, d = recover_p_d(g, invs, pubs, P, N, K)
        assert d is not None
        real_keys.append((p_arr, d))
    pad = hashlib.shake_256(b'o' + pack_key(real_keys, P)).digest(len(sealed))
    flag = bytes(a ^ b for a, b in zip(sealed, pad))
    print(flag.decode())

if __name__ == '__main__':
    main()