Algebraic Mirage

Flag: isfcr{3v3ry_m1r4g3_c4575_4_l1n34r_5h4d0w_e39672b62c}

What the capture contains

public_exchange.sage gives the epoch 0 parameters, Alice's and Bob's public states, and a shuffled pool of 48 braid anchors. ciphertext.json contains seven frames. Frame e is encrypted with the shared secret from epoch e-1; frames 1–6 reveal the next registry and handshake, while frame 7 contains the vault note. Thus each epoch has to be solved before the next one can even be inspected.

The crucial weakness is that the eraser action maps braids into a finite-dimensional matrix space. A linear expression for the evaluated private action can be applied to the other public state. The ChaCha20-Poly1305 tag tells us when an expression gives the exact shared secret.

The matrix attack

Write $E_\sigma(w)$ for the matrix returned by erase((I, sigma), w), and write $\pi(w)$ for the braid's permutation. The basic identity is

$$ E_\sigma(uv)=E_\sigma(u)E_{\sigma\pi(u)}(v). $$

An anchor $a$ with permutation of order $r$ gives a pure braid $a^r$: its permutation is the identity. Products of such pure braids therefore act as ordinary matrix products at a fixed starting permutation. If the public permutation is $P$, a short breadth-first search in the group generated by the anchor permutations finds a word $w_0$ with $\pi(w_0)=P$. We build a basis from pure words $u_j$ and the coset $u_jw_0$. Where powers of individual anchors leave a relation out, the pure word

$$ (ab)^{\operatorname{ord}(\pi(a)\pi(b))} $$

adds it to the basis. This was needed for the later mirror epochs.

For epochs 0–1 the private matrix lies in $\mathbb F_p[\kappa]$. With published public matrix $A$, a basis expression has the form

$$ A=\sum_{i,j}c_{ij},\kappa^i E_{\mathrm{id}}(u_jw_0). $$

For an eraser epoch, if the other input state is $(B,Q)$, apply the same coefficients to obtain

$$ K=\sum_{i,j}c_{ij},\kappa^i B E_Q(u_jw_0), \qquad \operatorname{perm}(K)=P Q. $$

The published party's braids commute with the other members' braids, and their private matrices commute. Those properties make this linear substitution valid even when the chosen basis expression is different from the relay's actual private word.

The widened private algebra

From epoch 2 onward, the provisioned commutative algebra is unpublished and can be larger than $\mathbb F_p[\kappa]$. Its elements still commute with the public $\kappa$. We calculate the 45-dimensional centralizer

$$ \operatorname{Cent}(\kappa)={D:D\kappa=\kappa D} $$

by solving linear equations over $\mathbb F_p$. The actual inverse private matrix $D=C^{-1}$ lies there. For an eraser epoch, let $W=E_{\mathrm{id}}(w_0)$ and let $U_j=E_{\mathrm{id}}(u_j)$. The additional condition

$$ DAW^{-1}=\sum_j c_jU_j $$

is linear in the entries of $D$ and the coefficients $c_j$. For a candidate solution, compute

$$ K=D^{-1}B\left(\sum_jc_jE_Q(u_j)\right)E_Q(w_0). $$

An arbitrary element of the centralizer need not commute with the peer's private matrix. We therefore enumerate the resulting candidates and accept one only when the next frame's authentication tag verifies.

Mirror action

The order of multiplication changes at epoch 4. The mirror public matrix is $A=E_{\mathrm{id}}(w)^{-1}C$, and combining with $(B,Q)$ gives $E_Q(w)^{-1}BC$. Set $D=C^{-1}$, $W=E_{\mathrm{id}}(w_0)$, and $G_j=E_{\mathrm{id}}(u_j)^{-1}$. We solve the linear condition

$$ WAD=\sum_jc_jG_j. $$

The corresponding secret candidate is

$$ K=E_Q(w_0)^{-1} \left(\sum_jc_jE_Q(u_j)^{-1}\right)BD^{-1}. $$

Using the eraser multiplication order here produces plausible matrices but invalid authentication tags.

Finding the live layers

Trying every published anchor as if it were live is insufficient: the registry includes look-alike layers, and later epochs split one member's presentation across two of them. For each anchor pair, we measured the dimension of the matrix algebra generated by their pure powers. Pairs from the same layer form small spans; this identifies the eight-anchor groups. In epoch 5, several groups have the same dimension, so common prefixes of the supplied braid normal forms break the tie. We then test combinations of partial layers with the linear condition above and the frame tag.

All indices below are zero-based positions in that epoch's anchors list. The listed pair is enough for the linear attack in epochs 0–3. In epochs 4–6, the two listed eight-anchor layers form the successful presentation.

For the three-member ring in epoch 5, Alice's final input is rounds["2"]["CAROL-9"]. For the four-member ring in epoch 6, Carol's final input is rounds["3"]["BOB-3"]. Using a round-1 public key as the input would derive a different matrix and fail authentication.

Opening the frames

For each recovered matrix and permutation, we used the exact encode_secret format in protocol.sage: magic bytes, four-byte big-endian $p$, one-byte $n$, row-major matrix entries, then permutation images. The frame key is HKDF-SHA256 with that encoding as input key material, the frame's salt, and algebraic-mirage/v2.3/frame|<session>|<epoch> as info. ChaCha20-Poly1305 uses <session>|<epoch> as associated data. The plaintext is zlib-compressed JSON.

All seven frames passed authentication in order. Frame 7 says:

quartet is up. vault note follows: isfcr{3v3ry_m1r4g3_c4575_4_l1n34r_5h4d0w_e39672b62c}

Flag: isfcr{3v3ry_m1r4g3_c4575_4_l1n34r_5h4d0w_e39672b62c}