Mirror Image (NEXSEC 2026) | Ammar Hakimi Adnan

Summary

The challenge hid a 1024-bit integer $s$ behind 112 prime moduli, each between $2^{15}$ and $2^{16}$ . For every modulus it gave two candidate residues, and only one of them matched $s$ . Trying every combination would mean $2^{112}$ guesses. I used the Chinese Remainder Theorem to turn the choices into a binary subset-sum problem, built a 114-dimensional lattice, recovered the correct choices with LLL, and used $s$ to decrypt the AES-GCM value called ward.

What I was given

One file, output.txt, containing 112 prime moduli, two candidate residues for each, and ward, an AES-GCM encrypted value holding a nonce and ciphertext. For each modulus $m_{i}$ the secret satisfied one of two congruences, and nothing said which.

s \equiv x_{i} (\mod m_{i}) or s \equiv y_{i} (\mod m_{i})

(1)

That made it more than a normal system of modular equations, because the right combination of residues also had to be found. With $2^{112}$ possibilities, brute force was out, so I looked at how all the constraints fit together instead of guessing pair by pair.

Method

1. Combine the constraints with CRT. The moduli are distinct primes, so they are pairwise coprime and the conditions merge into one congruence modulo their product. For each modulus I built a CRT basis element that is 1 for its own modulus and 0 for all the others.

M = \prod_{i = 1}^{112} m_{i}

(2)

E_{i} \equiv 1 (\mod m_{i}), E_{i} \equiv 0 (\mod m_{j}), for j \neq i

(3)

s \equiv \sum_{i = 1}^{112} r_{i} E_{i} (\mod M)

(4)

2. Turn the choice into a binary variable. Each selection became $b_{i} \in {0, 1}$ , which exposed the problem as subset-sum: find the bits that produce the right secret.

r_{i} = x_{i} + b_{i} (y_{i} - x_{i}), b_{i} \in {0, 1}

(5)

s \equiv base + \sum_{i = 1}^{112} b_{i} c_{i} (\mod M)

(6)

base = \sum_{i = 1}^{112} x_{i} E_{i}, c_{i} = (y_{i} - x_{i}) E_{i}

(7)

3. Encode it as a lattice. Lattice reduction does not solve an arbitrary subset-sum problem, so the basis has to be built so the right vector stands out. I used 114 dimensions: 112 for the binary variables, one for the modular relationship, and one to enforce the target size, with a scaling parameter $P = 720$ .

4. Reduce with LLL. I ran LLL with fpylll and looked through the reduced basis for a vector with the binary-selection structure, instead of enumerating anything.

5. Verify before trusting it. A short vector from LLL is not proof. I rebuilt $s$ from the recovered bits and checked that $s \mod m_{i}$ was one of the two candidates for all 112 moduli, and that it had the expected 1024-bit size.

6. Decrypt ward. I derived the AES key from $s$ using the challenge’s key-derivation logic and decrypted with Python’s cryptography library. AES-GCM is authenticated, so a successful decryption is itself confirmation that the secret was right.

What went wrong

My first lattice was built straight from the CRT coefficients. LLL ran, but nothing in the output looked like a binary-selection vector. A mathematically valid lattice does not guarantee that LLL reveals the answer you want. I went back to how the binary variables, the CRT coefficients and the target-size constraint were represented, reworked the basis to encode them properly, and settled on $P = 720$ . The second attempt produced a vector I could verify.

Result

The recovered secret passed all 112 modular checks, its decryption of ward authenticated, and that gave the flag shown at the top of this page.

What I learned

Identify the mathematical structure behind a problem before choosing an implementation. Here that meant seeing 112 residue pairs as a binary subset-sum. Also, lattice reduction depends heavily on the model: the basis and the scaling must reflect the problem’s constraints, and every candidate should be checked against the original conditions before it is used.