Ring, Rainbow, and Rust: Crafting a Post-Quantum Cryptography CTF Challenge That Actually Matters

There's nothing quite like the rush of a CTF competition. The clock counting down, your terminal filled with half-working exploit code, energy drink number three sitting beside stacks of scribbled notes on lattice basis vectors. That moment when your script finally spits out the flag and you hear the scoreboard update notification—pure digital adrenaline. As CTO and Head of Cyber Range & Education at Exploit3rs Cybersecurity Academy, I've watched thousands of competitors experience these moments, and honestly? It never gets old.

But here's what drives me crazy: challenges that waste competitors' time. The "guess the author's mind" crypto challenge. The unrealistic scenarios with no connection to real-world security. The copy-paste-from-StackOverflow web challenges that teach nothing. At Exploit3rs Cybersecurity Academy, we have a philosophy: every challenge should make you better at your craft. When you solve one of our challenges, you should walk away with skills that matter—techniques you can research, implement, and yes, eventually use to secure (or responsibly break) real systems.

So when I sat down to design "Ring, Rainbow, and Rust," I had one goal: create a challenge that would force competitors into the deep end of post-quantum cryptography—the most significant cryptographic revolution since the 1970s. Post-quantum cryptography is no longer theoretical—it's standardized, deployed, and ready to break. In August 2024, NIST finalized its first three post-quantum cryptographic standards after an eight-year evaluation, marking a fundamental shift in how we protect digital communications.

This challenge isn't for beginners, and I won't pretend it is. It's a hard challenge spanning lattice cryptography, multivariate systems, and code-based schemes—requiring competitors to implement attacks drawn from cutting-edge academic cryptanalysis. But here's the beautiful thing: if you can understand why these systems are hard to break at full strength, you'll understand why the world is spending billions of dollars migrating to them. And more importantly, you'll have skills that maybe 0.1% of security professionals currently possess.

Let me walk you through how this challenge came together, why I made the design decisions I did, and what I hope every competitor learns from attempting it.

Why post-quantum cryptography demands your attention now

The threat model is elegantly simple and deeply unsettling. Shor's algorithm, published in 1994, can factor integers and solve discrete logarithms in polynomial time on a quantum computer. This means RSA, elliptic curve cryptography, and Diffie-Hellman—the mathematical foundations securing virtually all internet communications—will be completely compromised once cryptographically relevant quantum computers (CRQCs) exist.

Current quantum computers aren't there yet. Google's 105-qubit Willow chip and IBM's 1,121-qubit Condor processor remain firmly in the NISQ era (Noisy Intermediate-Scale Quantum), too error-prone for cryptographic attacks. Breaking RSA-2048 requires approximately 4,099 stable logical qubits or millions of physical qubits with error correction. Expert timelines for CRQCs range from 2030 to 2040, with the Global Risk Institute assessing a 17-34% probability of a code-breaking quantum computer by 2034.

But here's the catch: the "harvest now, decrypt later" threat means adversaries are already intercepting encrypted traffic today, storing it indefinitely, waiting for quantum capabilities to mature. Data that must remain confidential for decades—government secrets, medical records, intellectual property—is already at risk. NIST's deprecation timeline reflects this urgency: quantum-vulnerable algorithms deprecated by 2030, disallowed entirely by 2035.

When I conceived this challenge, I wanted competitors to understand these aren't abstract concerns. The mathematics they're attacking represents humanity's collective bet on what problems quantum computers cannot efficiently solve.

The three pillars and NIST's choices (or: why I structured the challenge this way)

Here's where the real fun began in my design process. I didn't want just another "break this crypto" challenge. I wanted to tell a story through three fundamentally different mathematical paradigms.

NIST's standardization process, spanning 2016 to 2024, evaluated 82 submissions across three primary mathematical families:

Lattice-based cryptography emerged dominant. CRYSTALS-Kyber (now ML-KEM, FIPS 203) and CRYSTALS-Dilithium (now ML-DSA, FIPS 204) provide key encapsulation and digital signatures respectively. Their security reduces to the hardness of the Module Learning with Errors problem—finding a secret polynomial given noisy polynomial products in high-dimensional lattices.

Hash-based signatures provided the backup. SPHINCS+ (now SLH-DSA, FIPS 205) derives security solely from hash function properties, making it the most conservative choice with the longest security track record.

Code-based cryptography earned recognition through HQC's selection in March 2025 as an alternative KEM. Classic McEliece, with 46 years of unbroken cryptanalysis, was passed over for NIST standardization due to its massive public keys (261KB to 1.3MB) but continues toward ISO standardization.

One family notably absent from final standards: multivariate cryptography. Rainbow, a Round 3 finalist for digital signatures, was catastrophically broken in February 2022. More on that delicious cryptographic disaster shortly—it's my favorite part of the challenge.

"Ring, Rainbow, and Rust" forces competitors through all three paradigms—lattice, multivariate, and code-based—in sequence, each phase unlocking the next. The title itself encodes the structure: Ring-LWE (lattice), Rainbow-style MQ systems (multivariate), and the iron-oxidized reliability of syndrome decoding (code-based). The "Rust" is also a nod to the challenge's implementation language, because at Exploit3rs Cybersecurity Academy, we believe modern cryptographic challenges should use memory-safe code. No segfaults should stand between competitors and the crypto they're meant to break.

Phase 1: Ring-LWE in the quotient ring (or: welcome to lattice hell)

I'll be honest: designing this phase took me three weeks of tweaking parameters. Too easy, and it becomes a scripting exercise. Too hard, and nobody finishes. Finding that sweet spot where competitors need to actually understand lattice reduction theory but can still succeed with determination? That's the art of CTF design.

The first phase attacks a deliberately weakened version of the Ring Learning with Errors problem, the mathematical foundation underlying CRYSTALS-Kyber.

The setup operates in the quotient ring R = Z₂₅₇[x]/(x¹⁶ + 1). Elements are polynomials of degree at most 15 with coefficients modulo 257. The cyclotomic polynomial x¹⁶ + 1 creates the ring structure: multiplying polynomials and reducing modulo x¹⁶ + 1 means x¹⁶ ≡ -1, causing coefficients to "wrap around" with sign changes.

Participants receive a public key (a, b) where b = a·s + e mod q. The polynomial a is uniformly random, s is the secret key they must recover, and e is a small error polynomial drawn from a discrete Gaussian distribution. The search problem: extract s given only (a, b).

At production scale (n = 256, q = 3329, secret dimension k = 2-4), this problem requires approximately 2¹⁴³ operations to solve—far beyond practical computation. I intentionally chose parameters (n = 16, q = 257, single ring element) where the underlying lattice has low enough dimension for lattice reduction attacks to succeed.

The attack: LLL and BKZ lattice reduction

The key insight is reformulating Ring-LWE as a lattice problem. Given b = as + e, we can construct a lattice where the secret (s, e) corresponds to an unusually short vector. Finding short vectors in lattices is the Shortest Vector Problem (SVP), and while NP-hard in general, practical algorithms exist for low dimensions.

The LLL algorithm (Lenstra-Lenstra-Lovász, 1982) is the starting point. It runs in polynomial time and produces a "reduced" basis with shorter, more orthogonal vectors. However, LLL's approximation factor grows exponentially with dimension—for cryptographic parameters, it produces vectors far longer than the shortest.

BKZ (Block Korkine-Zolotarev) strengthens LLL by solving SVP exactly within sliding windows of size β (the "blocksize"). BKZ with blocksize 20-30 typically suffices for the challenge parameters. The algorithm iterates "tours" over the basis, each tour improving reduction quality, until the target vector emerges.

The elegance of this attack is watching abstract lattice geometry yield a concrete secret polynomial. Competitors construct the embedding lattice, run BKZ, and extract s from the shortest vector. At challenge scale, this takes seconds. At production scale, it would take longer than the universe's remaining lifetime.

When I watched the first competitor solve this phase during beta testing, they spent six hours implementing the lattice construction before realizing they'd mixed up their coefficient ordering. The moment they fixed it and saw the secret polynomial pop out? That's the CTF magic we live for at Exploit3rs Cybersecurity Academy.

Phase 2: The Rainbow that fell (my personal favorite)

Okay, this is where I got a bit theatrical with the challenge design. Phase 2 presents a system of multivariate quadratic equations over F₃₁—two equations in eight variables, structured similarly to the Rainbow signature scheme. This phase tells one of my favorite stories in modern cryptography: the hubris of assuming your construction is secure just because the underlying problem is hard.

Rainbow was a Round 3 NIST finalist, one of three signature schemes expected to be standardized. It offered extraordinarily small signatures (66 bytes) and fast operations. Then Ward Beullens published "Breaking Rainbow Takes a Weekend on a Laptop" in February 2022, demonstrating practical key recovery against the scheme's lowest security level in 53 hours on a standard laptop.

Let that sink in. A NIST finalist—meaning it survived years of public scrutiny, multiple rounds of cryptanalysis by the world's best researchers, and was weeks away from becoming a federal standard—fell to a grad student with a clever algebraic observation and a weekend.

The attack exploited Rainbow's multi-layer structure. Rainbow extended the Unbalanced Oil and Vinegar (UOV) scheme by dividing variables into layers with specific algebraic relationships. These relationships, designed to enable efficient signing, created differential structures Beullens exploited to peel away the outer layer, reducing the problem to a UOV instance with parameters far too small for security. The attack won "Best Early Career Researcher Paper" at CRYPTO 2022 and eliminated Rainbow from standardization.

My challenge phase captures this lesson. The MQ system has hidden structure—not Rainbow's exact construction, but analogous algebraic relationships that make an apparently random system tractable. I wanted competitors to experience that "wait, this shouldn't work" moment when their solver succeeds faster than the theoretical complexity suggests it should.

The attack: Gröbner bases and the F4/F5 algorithms

Solving systems of polynomial equations is the domain of Gröbner bases—a multivariate generalization of Gaussian elimination. A Gröbner basis is a special generating set for a polynomial ideal that enables systematic solution extraction.

The F4 algorithm (Faugère, 1999) computes Gröbner bases using matrix-based reduction, processing multiple polynomials simultaneously through linear algebra. Its successor F5 (2002) adds signatures to eliminate redundant computations. These algorithms powered the 2002 solution of the HFE challenge (80 equations, 80 variables over GF(2)) in 52 hours.

For my challenge parameters (2 equations, 8 variables, F₃₁), competitors can use SageMath's Gröbner basis implementation or specialized tools like Magma. The system's degree of regularity—the maximum polynomial degree encountered during computation—determines complexity. For underdetermined systems like this one, structural hints reduce the effective degree, making the computation tractable.

The pedagogical goal: competitors should understand that the MQ problem's NP-completeness provides theoretical security, but specific constructions can introduce exploitable structure. Rainbow's fall proves this isn't academic—a billion-dollar NIST finalist was broken by one researcher on commodity hardware.

This is the kind of lesson we obsess over at Exploit3rs Cybersecurity Academy. Real-world security failures, translated into CTF challenges that teach the underlying principles. No contrived scenarios—just actual cryptographic history you can hold in your hands and break.

Phase 3: Syndrome decoding and the McEliece legacy (respect your elders)

The final phase presents syndrome decoding: given a 16×31 parity-check matrix H over a binary field and a syndrome vector s, find an error vector e with Hamming weight ≤ 3 such that He^T = s.

This is the computational problem underlying Classic McEliece, the scheme with the longest unbroken track record in post-quantum cryptography—**46 years since Robert McEliece's 1978 proposal**. While NIST passed over Classic McEliece due to key size concerns (selecting HQC instead in March 2025), the syndrome decoding problem remains the gold standard for conservative security assumptions.

The problem's NP-completeness was proven by Berlekamp, McEliece, and Van Tilborg in 1978. For random linear codes, no algorithm substantially better than brute force exists. Unlike lattice problems, where algebraic structure enables increasingly sophisticated attacks, syndrome decoding for random codes has resisted meaningful improvement for decades.

I included this phase partially because it's a beautiful mathematical problem, and partially because I wanted to end the challenge with a system that hasn't been broken. After showing competitors how Ring-LWE can fall to lattice reduction and how Rainbow collapsed under algebraic pressure, Phase 3 demonstrates what actual long-term security looks like. Sometimes the oldest solutions really are the best.

The attack: Information Set Decoding

Information Set Decoding (ISD) is the canonical attack family against code-based cryptography, originating with Prange's algorithm in 1962.

The core insight: if you can identify a set of k positions (an "information set") containing no errors, Gaussian elimination immediately recovers the error vector. Prange's algorithm randomly samples position sets until finding an error-free one—the probability of success is C(n-t, k)/C(n, k), where t is the error weight.

Successive refinements improved this baseline:

- Stern's algorithm (1989) uses the birthday paradox, splitting the information set and using collision-finding to match partial solutions

- BJMM (Becker-Joux-May-Meurer, 2012) introduces the "representation technique," exploiting that single solutions can be represented exponentially many ways

For challenge parameters (n=31, k=15, t≤3), even basic ISD succeeds quickly. The probability of a random 15-position set being error-free when 3 positions contain errors is approximately C(28,15)/C(31,15) ≈ 39%—just a few random trials suffice.

I chose these parameters to make the attack accessible while preserving the algorithmic structure. Competitors implement ISD, understand the probability calculations, and appreciate why scaling to production parameters (n=6688, t=128 for Classic McEliece Category 5) pushes complexity to 2²⁴⁸ operations.

The gamification layer (because story matters)

A CTF challenge isn't just mathematics—it's narrative. This is something we emphasize constantly at Exploit3rs Cybersecurity Academy when developing our cyber range scenarios. The technical content might be what teaches skills, but the narrative is what keeps competitors engaged at 3 AM when they're debugging their third lattice reduction implementation.

"Ring, Rainbow, and Rust" wraps each phase in a storyline about a fictional secure messaging system that deployed all three post-quantum primitives in a misguided "defense in depth" approach. The twist: by using weak parameters for backwards compatibility (a sin I've seen in real-world systems more times than I care to admit), they created a system where each layer falls sequentially.

Phase 1's Ring-LWE key exchange reveals a session key. That session key decrypts a multivariate signature verification challenge in Phase 2. Successfully forging a signature unlocks Phase 3's code-based authentication token. The final flag combines components extracted from all three phases.

This structure serves a pedagogical purpose beyond just making the challenge flow nicely: it demonstrates that cryptographic security isn't about piling on algorithms. Weak instances of strong primitives provide false confidence. The fictional system's administrators thought three post-quantum schemes meant three times the security—instead, they created three sequential points of failure.

I've seen this mistake in production systems. Defense in depth is meaningless if each layer is individually compromised. Better to have one properly implemented primitive than three poorly chosen ones.

What I hope every competitor learns (the Exploit3rs Cybersecurity Academy philosophy)

Post-quantum cryptography isn't magic. It's mathematics with concrete security assumptions, subject to the same adversarial analysis as any cryptographic construction. CRYSTALS-Kyber's security rests on the hardness of Module-LWE; if lattice reduction algorithms improve substantially, security margins shrink. Classic McEliece's confidence comes from 46 years of failed attacks, not mathematical proof of impossibility. Rainbow's collapse proves that even NIST finalists can fall to dedicated cryptanalysis.

The attacks in this challenge—lattice reduction, Gröbner basis computation, information set decoding—represent the frontier of classical cryptanalysis against post-quantum systems. Competitors who successfully complete all three phases will have hands-on experience with the mathematical problems protecting global communications for the next several decades.

More importantly, they'll understand why cryptographic transitions require years of preparation. NIST estimates federal migration will cost $7.1 billion through 2035. Every TLS library, every HSM, every certificate authority, every embedded device with cryptographic capabilities must be updated. The mathematics is settled; the engineering challenge has just begun.

At Exploit3rs Cybersecurity Academy, we believe CTF competitions are more than just games. They're the training ground for the next generation of security researchers, the place where theoretical knowledge becomes practical skill, where academic papers transform into working exploits. Every challenge we develop—whether it's reverse engineering, web exploitation, or cutting-edge cryptography—is designed with one question in mind: Will solving this make you genuinely better at securing or breaking real systems?

"Ring, Rainbow, and Rust" is my answer to that question for post-quantum cryptography. The techniques you learn attacking these weakened systems are the same techniques researchers use to analyze the full-strength versions. The parameter choices that make this challenge solvable are the same parameters that would make a production deployment vulnerable. The mathematics is real, the attacks are real, and the lessons transfer directly to understanding the cryptographic landscape of 2025 and beyond.

Technical notes for implementers (for the challenge designers reading this)

For those building similar challenges—and please do, we need more quality crypto CTFs—some practical guidance from my development process:

Ring-LWE: Use SageMath's polynomial ring functionality. The quotient ring Z_q[x]/(x^n + 1) is straightforward to construct, and fpylll provides production-quality LLL/BKZ implementations. Ensure your error distribution has sufficiently small standard deviation that the lattice attack succeeds—I used σ = 1.5 for the discrete Gaussian. Test extensively with different random seeds; I found that about 10% of key generations accidentally created slightly easier instances, which is actually fine for a CTF but worth noting.

MQ systems: SageMath's solve_mod and Gröbner basis functions handle small systems efficiently. The challenge is designing a system that's solvable but not trivially so. I constructed mine by choosing a solution first, generating random quadratic terms, then verifying the degree of regularity permits computation in reasonable time (under 5 minutes on a standard laptop). If your solving time varies wildly with different equation sets, your parameters are probably in an unstable regime.

Syndrome decoding: Binary matrices are cleanest, but F₂ makes the Hamming weight constraint more meaningful. Implement Stern's algorithm rather than pure Prange—it's more educational and handles slightly larger parameters. I initially used t=5 for error weight, but beta testers found it tedious rather than challenging. Sometimes less is more.

The meta-lesson: Test your challenges with actual competitors before deploying them. I ran three rounds of beta testing with our Exploit3rs Cybersecurity Academy community, and each round revealed assumptions I'd made that weren't obvious to solvers. The best challenge designers are also good listeners.

Closing thoughts

When I started designing "Ring, Rainbow, and Rust," I wanted to create something that would still be relevant in five years. Most CTF challenges have a shelf life measured in months—once the solutions are public, the educational value diminishes. But this challenge teaches principles that transcend the specific parameters I chose.

Lattice reduction will remain relevant as long as lattice-based cryptography dominates post-quantum standards. Understanding how multivariate systems can fail prepares competitors for whatever replaces the failed candidates. Syndrome decoding isn't going anywhere—it's been the bedrock of code-based crypto since the 1970s and will remain so.

At Exploit3rs Cybersecurity Academy, our mission is to develop security professionals who don't just follow tutorials but understand the deep theory underlying modern systems. CTF competitions are our vehicle for that mission. They're intense, they're challenging, they're sometimes frustrating—but when you finally see that flag pop up after hours of work, you've earned something real. You've proved to yourself that you can tackle research-level problems and win.

If you attempt "Ring, Rainbow, and Rust," I hope you emerge with a deeper understanding of post-quantum cryptography, a healthier respect for the mathematics underlying security, and maybe a few new tools in your cryptanalysis toolkit. And if you get stuck? That's fine too. The challenge will be there when you're ready.

After all, the quantum threat isn't going anywhere. We might as well learn to think like the attackers—because in a few years, they'll be thinking like quantum computers.

Stay curious, stay persistent, and happy hacking.