> For the complete documentation index, see [llms.txt](https://lance-kenji.gitbook.io/me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lance-kenji.gitbook.io/me/nullcon-hackim-ctf-goa-2026-writeups/crypto/going-in-circles.md).

# 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`

```python
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:

```python
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.

```python
# 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}`


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lance-kenji.gitbook.io/me/nullcon-hackim-ctf-goa-2026-writeups/crypto/going-in-circles.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.