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

...