Going In Circles (Crypto)

Challenge Data

Field	Value
CTF	Nullcon CTF 2026
Challenge	Going In Circles
Category	Crypto
Flag	ENO{CRC_is_just_some_modular_remainder}

---

Challenge Description

On each connection, the service returned the result of reducing the flag modulo a random polynomial in GF(2)[x]. A single sample did not look like enough to recover the secret, but every connection added a new relation, and that was exactly what made the challenge work.

---

Reconnaissance

The challenge script read flag.txt, converted the flag to an integer, and then did something equivalent to taking that integer modulo a 32 bit polynomial in GF(2)[x].

def reduce(a, f):
    while (l := a.bit_length()) > BITS:
        a ^= f << (l - BITS)
    return a

Interpreting each integer as a binary polynomial, each server response could be read like this.

flag ≡ r (mod f)

So each connection did not reveal the flag directly, but it did add one more constraint on it.

---

Analysis

The right way to combine those constraints was to apply the Chinese Remainder Theorem in GF(2)[x]. If we collected enough equations of the form

x ≡ r1 (mod f1)
x ≡ r2 (mod f2)

then we could obtain a unique solution modulo the least common multiple of those polynomials. As that combined modulus kept growing, there came a point where it fully fixed the flag length and the solution stopped having multiple possibilities.

In practice, the attack was about collecting pairs (r, f) until the degree of the combined modulus became large enough to reconstruct the original integer and then convert it back into bytes.

The core idea of the challenge was really nice, because each answer was only a remainder, but enough remainders eventually forced the full value into place.

---

Solution

The implementation needed basic operations over binary polynomials, including carry less multiplication, division with remainder, GCD, extended GCD, and a crt_poly() routine to combine two equations at a time.

The main loop looked like this.

1. Connect to the service and collect (r, f).
2. Ignore degenerate cases such as f = 0 or f = 1.
3. Initialize R and M with the first valid sample.
4. Keep combining each new sample with CRT.
5. After each update, try to decode R as bytes and check whether something shaped like ENO{...} already appears.

After enough connections, the recovered value matched the full flag.

---

Flag

ENO{CRC_is_just_some_modular_remainder}