Linchan — asisctf2026

Description

Provided archive: linchan.txz

The archive extracts to linchan/linchan.py and linchan/output.txt. The goal is to recover the hidden matrices well enough to reproduce the challenge key derivation and decrypt the final ChaCha20Poly1305 ciphertext.

Analysis

Reading linchan.py shows the real structure of the problem:

• matrices are 32x32 over GF(2)
• five secret invertible matrices S are generated
• for each secret, the challenge builds a random subspace C and its conjugate D = S C S^{-1}
• both sides are obfuscated again by random basis mixing and optional transpose
• all of that is shuffled together with many decoy boxes into 112 public boxes
• the final key is shake_256(b"linchan-v2/key\0" + sorted(_f(S_i))), where _f canonicalizes a matrix up to inverse and transpose

The important consequence is that I did not need to reconstruct full hidden subspaces. The useful signal was much smaller: among the 112 boxes, exactly 10 are special, and each of those contains exactly two nonzero combinations of rank 25.

Those special boxes pair as:

• (1, 92)
• (32, 44)
• (47, 106)
• (49, 60)
• (82, 86)

For a special box with the two rank-25 elements A and B, the tuple of invariants based on

• charpoly(A)
• charpoly(B)
• charpoly(A + B)
• charpoly(AB)

matches exactly with its true partner box. That gives the correct five pairings without recovering the whole subspace structure.

Once a true pair is known, recover the secret conjugator by solving the simultaneous intertwiner system over GF(2):

X A_i = B_i X

trying both orderings of the two low-rank elements and also the optional transpose on one side. For each real pair, this produces a unique one-dimensional solution space whose representative is invertible. Because the challenge key derivation already canonicalizes by inverse and transpose, that recovered matrix is sufficient even if it is only determined up to the same equivalence class as _f(S).

Solution

1. Extract linchan.txz.
2. Read linchan/linchan.py to identify the custom matrix operations, the _f(S) canonicalization, and the ChaCha20Poly1305 key schedule.
3. Enumerate linear combinations inside each box and keep the boxes that contain exactly two nonzero rank-25 combinations.
4. For each such box, compute the joint signature from charpoly(A), charpoly(B), charpoly(A+B), and charpoly(AB) for its two low-rank elements.
5. Pair the boxes by matching that signature, yielding the five real conjugate pairs.
6. For each paired boxes, solve X A_i = B_i X over GF(2), trying both low-rank orderings and optional transpose on the right-hand side.
7. Keep the unique invertible solution X; this recovers each hidden matrix up to the same canonical equivalence used by _f(S).
8. Recompute the key with the sorted canonical forms.
9. Decrypt the output.txt ciphertext with ChaCha20Poly1305 and AAD b"linchan/v2".

Reproducible local evidence:

• notes: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/linchan/notes.md
• solver: /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/linchan/solve.py
• run: python3 /Users/sergeyskorobogatov/Projects/Agents/CTF/tasks/asisctf2026/linchan/solve.py

#!/usr/bin/env python3

import base64
import hashlib
import json
import zlib
from cryptography.hazmat.primitives.ciphers.aead import ChaCha20Poly1305

N = 32
PAIRS = [(1, 92), (32, 44), (47, 106), (49, 60), (82, 86)]
AAD = b"linchan/v2"


def rank(A):
    piv = {}
    for x in A:
        while x:
            i = x.bit_length() - 1
            y = piv.get(i)
            if y is None:
                piv[i] = x
                break
            x ^= y
    return len(piv)


def transpose(A):
    R = [0] * N
    for i, x in enumerate(A):
        while x:
            b = x & -x
            R[b.bit_length() - 1] |= 1 << i
            x ^= b
    return R


def inv(A):
    R = [x | (1 << (N + i)) for i, x in enumerate(A)]
    for i in range(N):
        j = next(j for j in range(i, N) if (R[j] >> i) & 1)
        R[i], R[j] = R[j], R[i]
        for j in range(N):
            if j != i and ((R[j] >> i) & 1):
                R[j] ^= R[i]
    return [x >> N for x in R]


def pack(A):
    return b"".join(x.to_bytes(4, "little") for x in A)


def canon(A):
    T = inv(A)
    return min(pack(A), pack(T), pack(transpose(A)), pack(transpose(T)))


def load_boxes(path):
    raw = open(path, "rb").read().strip()
    X = json.loads(zlib.decompress(base64.b85decode(raw)))
    boxes = []
    for b in X["boxes"]:
        data = base64.b85decode(b["x"])
        m = b["m"]
        mats = []
        for i in range(m):
            off = i * N * 4
            mats.append([int.from_bytes(data[off + 4 * r:off + 4 * (r + 1)], "little") for r in range(N)])
        boxes.append((m, mats))
    return X, boxes


def lowrank_two(box):
    m, mats = box
    lows = []
    cur = [0] * N
    prevg = 0
    for i in range(1, 1 << m):
        g = i ^ (i >> 1)
        diff = g ^ prevg
        bit = (diff & -diff).bit_length() - 1
        cur = [x ^ y for x, y in zip(cur, mats[bit])]
        prevg = g
        if rank(cur) == 25:
            lows.append(cur[:])
    assert len(lows) == 2
    return lows


def build_eq(Aset, Bset):
    eq = []
    for A, B in zip(Aset, Bset):
        for r in range(N):
            Brow = B[r]
            for k in range(N):
                row = 0
                for j in range(N):
                    if (A[j] >> k) & 1:
                        row ^= 1 << (r * N + j)
                bb = Brow
                while bb:
                    bit = bb & -bb
                    i = bit.bit_length() - 1
                    row ^= 1 << (i * N + k)
                    bb ^= bit
                eq.append(row)
    return eq


def solve_1d(eq):
    piv = {}
    order = []
    for row in eq:
        x = row
        while x:
            i = x.bit_length() - 1
            y = piv.get(i)
            if y is None:
                piv[i] = x
                order.append(i)
                break
            x ^= y
    if 1024 - len(piv) != 1:
        return None
    free = next(i for i in range(1024) if i not in piv)
    v = 1 << free
    for i in sorted(order):
        row = piv[i]
        if ((row ^ (1 << i)) & v).bit_count() & 1:
            v |= 1 << i
    return [sum(((v >> (r * N + c)) & 1) << c for c in range(N)) for r in range(N)]


def recover_secret(box_a, box_b):
    A = lowrank_two(box_a)
    B = lowrank_two(box_b)
    found = []
    for perm in [(0, 1), (1, 0)]:
        B0 = [B[perm[0]], B[perm[1]]]
        for t in [False, True]:
            BB = [transpose(M) for M in B0] if t else B0
            S = solve_1d(build_eq(A, BB))
            if S is not None and rank(S) == N:
                found.append(S)
    assert len(found) == 1
    return found[0]


def main():
    X, boxes = load_boxes("linchan/output.txt")
    K = [recover_secret(boxes[a], boxes[b]) for a, b in PAIRS]
    key = hashlib.shake_256(b"linchan-v2/key\0" + b"".join(sorted(canon(S) for S in K))).digest(32)
    ct = base64.b85decode(X["ct"])
    nonce, cipher = ct[:12], ct[12:]
    pt = ChaCha20Poly1305(key).decrypt(nonce, cipher, AAD)
    print(pt.decode())


if __name__ == "__main__":
    main()