GCD but it's ACD: Noisy Common Divisors and LLL

Overview

The challenge gave one exact sample x₀ = p·q₀ and ten noisy samples xᵢ = p·qᵢ + eᵢ with |eᵢ| < 2⁵². The flag was XORed with a SHAKE-256 keystream derived from p.

Challenge brief

Recover the hidden common divisor p from noisy samples.

Analysis

A normal GCD fails immediately: the noise destroys exact divisibility. This is the Approximate Common Divisor (ACD) problem — the title says as much.

With the exact anchor x₀, the quantities q₀·xᵢ − qᵢ·x₀ = q₀·eᵢ are small. That makes (q₀, q₀e₁, …, q₀e₁₀) a short vector in a lattice built from the samples, which LLL can find.

Solution

Building the lattice from the ten noisy samples and the anchor (scaling factor S = 1 was enough) and running LLL revealed q₀ as a 320-bit integer, and therefore p = x₀ / q₀. All recovered errors were below 2⁵², confirming the result, and the provided SHA-256 of the plaintext matched.

1# key derivation exactly as specified by the challenge2pb  = int(p).to_bytes((int(p).bit_length() + 7) // 8, "big")3key = shake_256(b"acd-revenge/key|" + pb).digest(len(ciphertext))4flag = bytes(c ^ k for c, k in zip(ciphertext, key))

Flag

Redacted. Format: BSides_Mumbai{…}.

Lessons learned

When a problem is "almost" a classical one, look for the lattice. Small errors relative to the modulus are exactly the structure LLL exploits.