Nullcon HackIM CTF Goa 2026 – Going in Circles

Category: Crypto / Reverse

Difficulty: Easy/Medium

1. Challenge Overview

Upon connecting to the server, I was greeted with two integers. Looking at the provided source code, chall.py, I saw that the program takes a secret flag, converts it into a large integer, and then passes it through a function called reduce(a, f) using a random 32-bit integer f. The server then prints the result of this reduction along with the value of f. My goal was to recover the flag from these outputs.

chall.py

from Crypto.Util import number
BITS = 32

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

flag = int.from_bytes(open('flag.txt','r').read().strip().encode(), byteorder = 'big')
f = number.getRandomNBitInteger(BITS)
print(reduce(flag,f),f)

2. Vulnerability Analysis

The core of the challenge lies in the reduce function:

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

This logic is a textbook implementation of Polynomial Division over the Finite Field $GF(2)$. In this field:

Addition and subtraction are both performed using the XOR (^) operation.
The function mimics long division by aligning the most significant bit of the divisor f with the current bit of a and XORing them to eliminate that bit.

This is exactly how a Cyclic Redundancy Check (CRC) is calculated. The output is essentially flag % f in the ring of polynomials $GF(2)[x]$. Since f is only 32 bits, a single output only gives me 32 bits of information about the flag, which is much larger. However, because the server allows multiple connections with the same flag but different random f values, the system is vulnerable to a Chinese Remainder Theorem (CRT) attack applied to polynomials.

3. Developing the Exploit

Since I have multiple pairs of $(remainder_i, f_i)$, and I know that:

$$Flag(x) \equiv remainder_i(x) \pmod{f_i(x)}$$

I can collect enough pairs until the product of the degrees of $f_i(x)$ exceeds the likely bit-length of the flag.

Each connection gives me 32 bits. A typical flag is around 30-50 characters (240-400 bits). Therefore, collecting about 15-20 samples is sufficient to uniquely reconstruct the flag polynomial.

4. The Solution Script

Using SageMath is the most efficient way to handle polynomial rings over $GF(2)$. The script defines the ring, converts the integers to polynomials, applies the CRT, and converts the result back to bytes.

# The data collected from multiple nc connections: (remainder, f)
data = [
    (1064458413, 3883728261),
    (390831997, 3804908672),
    (666626513, 2282960927),
    (3332578781, 3116072065),
    (2378265221, 3629947460),
    (1090448765, 3492336848),
    (1682687389, 2602396929),
    (2580884285, 3972155314),
    (3938901393, 3960129650),
    (2223283587, 2612332575),
    (3536033261, 3286717684),
    (4175443085, 4291037560),
    (1781683571, 3283899545),
    (2766320843, 2679580103),
    (2548209617, 4163369055),
    (1292078669, 2897010373),
    (2943932165, 3954051178),
    (3931768257, 3400367311),
    (3219359661, 2841246968),
    (1106802541, 3379979372)
]

# 1. Define the Polynomial Ring over GF(2)
R.<x> = GF(2)[]

def int_to_poly(n):
    """Converts an integer to a polynomial in GF(2)[x]"""
    return R(Integer(n).bits())

def poly_to_int(p):
    """Converts a polynomial in GF(2)[x] back to an integer"""
    return sum(int(c) << i for i, c in enumerate(p.list()))

# 2. Convert all gathered data into polynomials
polys_r = [int_to_poly(r) for r, f in data]
polys_f = [int_to_poly(f) for r, f in data]

# 3. Apply the Chinese Remainder Theorem for Polynomials
# Finds flag_poly such that flag_poly % f_i == r_i
flag_poly = crt(polys_r, polys_f)

# 4. Convert result back to an integer and then to bytes
flag_int = poly_to_int(flag_poly)

# Way to convert long to bytes (big-endian as per chall.py source code)
flag_hex = hex(flag_int)[2:]
if len(flag_hex) % 2 != 0:
    flag_hex = '0' + flag_hex
print(bytes.fromhex(flag_hex).decode())

I pasted it in https://sagecell.sagemath.org and let it evaluate my script.

5. Result

After processing the gathered data through the SageMath CRT solver, the flag was reconstructed from the bits of the resulting polynomial:

Flag: ENO{CRC_is_just_some_modular_remainder}

mis4nthr0pia