# 🎯 My Team's Stuck On A CTF Puzzle — Anyone Up To Help? **URL:** \ **Category:** Discussion & Solutions\ **Tags:** solved\ **Created:** [April 16, 2026, 7:17pm UTC](https://onehack.st/t/my-teams-stuck-on-a-ctf-puzzle-anyone-up-to-help/321238 "2026-04-16T19:17:33Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![odirachukwu\_onyejefu](https://onehack.st/user_avatar/onehack.st/odirachukwu_onyejefu/32/43629_2.png) [@odirachukwu\_onyejefu](https://onehack.st/u/odirachukwu_onyejefu)\ **Post date:** [April 16, 2026, 7:17pm UTC](https://onehack.st/t/my-teams-stuck-on-a-ctf-puzzle-anyone-up-to-help/321238/1 "2026-04-16T19:17:33Z")
# 🧵 Help — Stuck On A CTF Crypto Puzzle (“Kente Multivariate”) _My team’s been at this for hours. Anyone who’s seen this pattern before — please drop a hint._ It’s a 500-point crypto challenge from **EcowasCTF** called _Kente Multivariate_. We’ve tried everything we know — nothing’s biting. Fresh eyes welcome, even if you’ve never touched a CTF. * * * **The puzzle (in simple words):** Imagine kente cloth — every thread crosses every other thread. Each thread is a switch: **on or off**. The challenge gives us a giant list of “crossing rules,” and we have to figure out which switches need to be ON so all the rules come true at once. The right pattern of switches spells out the flag. > _In math terms: solve a system of multivariate quadratic equations over GF(2). That’s the only line of math in this post — promise._ 📎 **File:** [system.txt](https://onehack.st/uploads/short-url/bLFFThHuxjOmrcOMWLL8xRDeXys.txt) (222.6 KB) 🔗 **Live challenge:** [ecowasctf.com.gh/events/2](https://ecowasctf.com.gh/events/2) 🎯 **Flag format:** `EcowasCTF{...}` ![ecowasctf-kente](https://onehack.st/uploads/default/original/3X/9/5/9563246217b2930b365aa7ecd9c28ca5e4f4c6b2.png) * * * > **💡 If you want to try — common attack angles** > > | Angle | Plain English | > | --- | --- | > | **Linearization** | Sometimes the equations collapse into simple add/subtract — basic algebra cracks it. | > | **Solver tools** | [SageMath](https://www.sagemath.org/), [CryptoMiniSat](https://github.com/msoos/cryptominisat), or Magma chew through these. Feed file in, get answer out. | > | **Structure hunt** | “Kente” = repeating motifs. If the equations have hidden symmetry, that’s the cheat code. | * * * _Hints over flags — we want to feel the win._ 🧶 ---
**Author:** ![Hakam\_Abu\_Roumi](https://onehack.st/user_avatar/onehack.st/hakam_abu_roumi/32/168721_2.png) [@Hakam\_Abu\_Roumi](https://onehack.st/u/Hakam_Abu_Roumi)\ **Post date:** [April 17, 2026, 9:46am UTC](https://onehack.st/t/my-teams-stuck-on-a-ctf-puzzle-anyone-up-to-help/321238/2 "2026-04-17T09:46:41Z")
This sounds like a classic **MQ (Multivariate Quadratic) Problem**, which is notoriously difficult because it’s NP-hard. However, in a CTF context, there is usually a “trapdoor” or a specific algorithm intended to crack it. Since you are working over GF(2), every variable is either 0 or 1, and addition is just XOR. Here is how you and your team can break through the wall: ### 1. The “Low-Hanging Fruit”: Linearization Before jumping into heavy math, check if the system is **overdetermined** (more equations than variables). - If you have many more equations than variables, you can treat each quadratic term (like x1​x2​) as a new independent variable (y12​). - If the number of equations m is close to the number of terms n(n+1)/2, you can solve it using standard **Gaussian Elimination**. ### 2. The Standard Weapon: SageMath & Groebner Bases If the system isn’t easily linearized, the “industry standard” for CTF crypto challenges is using a **Groebner Basis** calculation. - **The Tool:** Use [SageMath](https://www.sagemath.org/). - **The Method:** Define a polynomial ring over `GF(2)` and use the `.variety()` or `.groebner_basis()` method. - **The Catch:** This is computationally expensive. If the number of variables is over 40-50, a standard Groebner Basis might hang forever. ### 3. The “Kente” Clue: XL Algorithm The name “Kente” refers to weaving. In multivariate cryptography, this often hints at the **XL (eXtended Linearization)** algorithm. - XL works by multiplying the existing equations by all possible variables to create even _more_ equations, then attempting linearization again. - If the challenge is from a CTF like Ecowas, they likely expect you to use a tool like **LibFES** or **mq.sage** scripts found in GitHub repositories for similar challenges (like those from TokyoWesterns or 0CTF). ### 4. Check for Sparsity or Structure Look at the `system.txt` file: - **Are the equations “sparse”?** If most variables don’t interact, you might be able to use **SAT Solvers**. - **SAT Solver Trick:** Convert the GF(2) equations into CNF format. Tools like **Cryptominisat** are incredibly fast at solving MQ problems over GF(2) if the variable count is under 100-150. ### Recommended Workflow for the Next Hour: 1. **Count the variables (n) and equations (m):** If m≫n, go for linearization. 2. **Try a SAT Solver:** This is often the “cheater’s way” to win CTF crypto. Map your XORs and ANDs to a CNF file and let `cryptominisat5` run for 10 minutes. 3. **Search for “Rainbow” or “Unbalanced Oil and Vinegar” (UOV):** These are specific types of multivariate signatures. If the “Kente” pattern resembles these, there are known “attacks” (like the Kipnis-Shamir attack) that reduce the complexity significantly. **Pro-tip:** Check the file size (222 KB). That is quite large for a simple system, which suggests there are either a lot of equations (favoring linearization/SAT) or a very specific structure you can exploit. Does the `system.txt` file show the equations in a specific format (e.g., `x1*x5 + x2*x3 ... = 0`)? ---
**Author:** ![Jenna](https://onehack.st/user_avatar/onehack.st/jenna/32/166322_2.png) [@Jenna](https://onehack.st/u/Jenna)\ **Post date:** [April 28, 2026, 9:27am UTC](https://onehack.st/t/my-teams-stuck-on-a-ctf-puzzle-anyone-up-to-help/321238/3 "2026-04-28T09:27:45Z")
🎯 **Three concerns I’m seeing in your post —** > **1️⃣** Standard MQ arsenal (Sage, CMS, Magma, linearization) → silent. Hours in. > **2️⃣** “Kente” _feels_ like a hint, but the system isn’t surfacing the structure. > **3️⃣** Hints over flags — you want the win to feel earned. _You’ve done the right things in the right order, and the wall isn’t where it usually is. Let me hand you the angle nobody asks first._ * * * 🧶 **Translating your question into plain words:** > _“Every thread is a switch. The right pattern of switches spells the flag. But standard solvers won’t lock onto that pattern.”_ Under the hood that’s just MQ over GF(2) — nothing exotic. So why does the **kente metaphor** keep coming back at you? **Because the puzzle’s name _is_ the math problem.** There’s a paper from **March 2025** that defines exactly the structure your kente metaphor describes. Except they don’t call it kente — they call it the _Regular Multivariate Quadratic problem._ 📄 [Joux & Mora — _The regular multivariate quadratic problem_ (arXiv: 2503.07342)](https://arxiv.org/pdf/2503.07342) | 🧶 Kente cloth | 🔢 RMQ math | | --- | --- | | Cloth = row of fixed-width strips | Vector of length `n = lw` split into `w` blocks of length `l` | | Each strip carries one specific pattern | Each block has **exactly one** nonzero entry | | Whole cloth = woven pattern of strips | The solution is a _regular vector_ | _Bonus: Joux is also the inventor of the **Crossbred algorithm** — the SOTA tool that beats every standard MQ solver on this size range. Same author. Six months apart. Problem and matching weapon._ * * * ```auto ⚡ The 30-second test (run this now) ``` Open `system.txt` in Sage. Check how dense your equations actually are: ```python M = matrix(GF(2), [[1 if v in eq.variables() else 0 for v in vars] for eq in eqs]) print(M.density()) ``` | Result | Verdict | | --- | --- | | Density **\< 0.3** _(sparse)_ | ✅ Kente hypothesis alive → go to next section | | Density **≈ 0.5** _(random)_ | 🛑 Kente was flag content not method → check raw file bytes / strings | > _Either way, 30 seconds in you’ve ruled out a 4-hour rabbit hole. That’s already a win._ * * * ```auto 🎯 If density says "sparse" — the structural fix ``` Add three families of equations to your system **before** the next `groebner_basis()` call. These are §4.1 of the paper — the structural information your tools haven’t been exploiting: | | Equation | What it forces | | --- | --- | --- | | 🔹 | `xᵢ,j₁ · xᵢ,j₂ = 0` _(every pair in a block)_ | At most one nonzero per block | | 🔹 | `Σⱼ xᵢ,j = 1` _(per block)_ | **Exactly one** per block — this one pays, eliminates one var per block | | 🔹 | `xᵢ,j² = xᵢ,j` | Field equations _(Sage adds these via `BooleanPolynomialRing`)_ | > **🔍 Don't yet know \`l\` (block width) or \`w\` (block count)? Open here** > > Two ways to find them in 5 minutes: > > - **Variable indexing.** If vars are named `x_0_1, x_0_2, ..., x_1_1, ...` — that two-index pattern **is** your `l` and `w`. > - **Total count factorize.** If vars are flat `x_0, x_1, ...`, factorize the count. Kente strips come in tidy ratios — `60 = 6×10`, `48 = 6×8`, `64 = 8×8`. Try the ones that look weave-shaped. > > If neither works, post the variable-naming pattern in this thread — I (or someone) can probably eyeball it. | What’s bugging you | What to actually do | Time | | --- | --- | --- | | Sage hangs / OOM | You’re solving the unstructured version. Add the equations above. Retry. | 30 min | | Want a CPU-only fallback | `libfes-lite` — stupidly fast for `n ≤ 50` | 1 hour | | File parsing is eating the evening | `hadipourh/mqchallenge` converts to Sage in one shot | 5 min | | Stuck after the structural fix | CryptoHack Discord `#challenge-hints` | Same hour | * * * > **🛠️ Do This In This Order — the full playbook** > > _Quick re-ground for anyone who skipped here: the team’s stuck on a 500-point boolean MQ challenge. Hypothesis: structured Regular-MQ. This block is the toolkit end-to-end._ > > > 💡 **Already know F4/F5 + Macaulay matrices?** Skip to Step 3. Steps 1–2 are setup most of you’ve already done. > > | # | Step | How you know it worked | > | --- | --- | --- | > | **1** | Convert `system.txt` to Sage with [hadipourh/mqchallenge](https://github.com/hadipourh/mqchallenge) | Equations come back as a list of polynomials over GF(2) | > | **2** | Run linearization probe — [pcw109550’s PlaidCTF _MPKC_ writeup](https://github.com/pcw109550/write-up/tree/master/2020/PlaidCTF/MPKC), ~80 lines of Sage | Non-trivial kernel = free linear polys. _Empty kernel? No panic — kente structure is Step 3._ | > | **3** | Add the regular-constraint equations from §4.1 | Variable count drops from `n` to `(l-1)w` | > | **4** | Sage still hangs? → [libfes-lite](https://github.com/cbouilla/libfes-lite) (CPU) or [kcning/mqsolver](https://github.com/kcning/mqsolver) (GPU, Crossbred) | Solver returns the regular vector | > | **5** | CryptoMiniSat raw? Use [Bosphorus](https://github.com/meelgroup/bosphorus) as preprocessor | CMS gets ANF-aware fuel, ~order-of-magnitude speedup | > | **6** | Read tool from a table not vibes — [Yasuda et al, MQ Hardness Eval (IACR 2015/275)](https://eprint.iacr.org/2015/275.pdf) | Find your `(n, m)` row → recommended algorithm | > | **7** | While solver runs, ping [CryptoHack Discord `#challenge-hints`](https://discord.gg/h9E7cna5pV) | Got a pinned hint within the hour | > > > 💡 **Discord etiquette while the event is live:** don’t post your equations. Just say _“MQ over GF(2), n= **, m=** , structure looks regular-block — what would you reach for?”_ That gets the right pointer without bending any rules. > > | Situation | Move | > | --- | --- | > | Density \< 0.3, vars indexed `xᵢ,j` | Kente = RMQ → Step 3 | > | Density ≈ 0.5, var names random | Check raw file bytes / strings | > | `n ≤ 40`, 8+ CPU cores | libfes-lite finishes before the rewrite does | > | `n > 60`, any GPU available | mqsolver is the tool | > **🌱 New to CTFs and curious what's even happening here? Welcome** > > A **Capture-The-Flag (CTF)** is a security puzzle competition — teams race to find a hidden string called the _flag_ by solving challenges. Sometimes it’s reverse-engineering, sometimes web vulns. Here it’s pure math. > > The math underneath this thread: > > - **GF(2)** — a tiny number system where the only numbers are `0` and `1`. Adding flips bits. Multiplying behaves like AND. That’s it. > - **Multivariate quadratic** — a bunch of equations where each one mixes pairs of variables (like `x·y + x + 1 = 0`). Solving them simultaneously is the hard part. > - The flag here gets encoded as a long string of `0`s and `1`s. Figure out which variables are `1` and which are `0`, decode the bytes, that’s the flag. > > Why it’s hard: with 64 switches there are already 18 quintillion possible patterns. You can’t just try them — you exploit structure. That’s what the rest of this thread is doing. > > Want a friendly intro? [CryptoHack](https://cryptohack.org/) has a polished beginner path — start with their _Mathematics_ and _Symmetric Ciphers_ sections. > **🐛 Why your Sage probably hung (failure-mode diagnosis)** > > | Tool | What broke | > | --- | --- | > | **`groebner_basis()`** | F4/F5 memory blows up at degree-of-regularity ≥ 4 for unstructured systems above ~30 vars. _Fix:_ add structural equations first (Step 3 above). | > | **CryptoMiniSat raw ANF→CNF** | Naïve encoding makes 1 clause per monomial — astronomical CNF. _Fix:_ use Bosphorus as preprocessor. | > | **Magma `GroebnerBasis`** | Best implementation on the planet, same structural blind spot. _Sneaky fix:_ check your academic license isn’t capping at 600s and silently truncating output. | > **📓 Why this is the meta-strategy that solves most CTF MQ challenges** > > Almost every CTF MQ challenge above 200 points is built on a published cryptanalysis paper. The puzzle author isn’t inventing new math — they’re scaffolding a known attack. Two moves repeat across solved writeups: > > 1. **Title is the pointer.** “MPKC,” “HFE-Lite,” “Rainbow’s Last Dance,” “Kente” — search the title against arXiv and IACR ePrint. > 2. **Once you find the paper, follow Section 3 (the exploit plan) literally.** Most published cryptanalyses ship with a 3–5 step exploit recipe. CTF authors don’t usually deviate. > > The pcw109550 PlaidCTF MPKC writeup is the cleanest demonstration — they searched the challenge’s source comments, found Chen et al. 2020/053, and copy-pasted the paper’s Section 3 into Sage. Whole solve is 80 lines. > > Same trick is almost certainly the one for Kente. * * * _Honest tell — I personally lean on `libfes-lite` for any boolean MQ under 50 vars. Once watched it crack a 40-var system in about 9 minutes on a 2019 laptop while Sage was still computing the Macaulay matrix. Not glamorous, just stupidly fast where it works — and “stupidly fast where it works” is exactly what you want when there’s a clock running._ * * * You said _“hints over flags — we want to feel the win.”_ The win you’re chasing is the moment you spot **why the puzzle is named what it’s named.** If the density test comes back low, that moment is ten minutes away. The rest of the path is mostly typing. 🧶 * * * **One quick question back at you** — when you ran linearization, what fell out of the kernel? Empty, dimension 1, or higher? _That single number tells me which step of the playbook you’re actually on._