🎯 My Team's Stuck On A CTF Puzzle — Anyone Up To Help?

[odirachukwu_onyejefu]

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 (222.6 KB)
Live challenge: ecowasctf.com.gh/events/2
Flag format: EcowasCTF{...}

---

💡 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, 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.

[Hakam_Abu_Roumi]

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.

• 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)?

[Jenna]

Three concerns I’m seeing in your post —

Standard MQ arsenal (Sage, CMS, Magma, linearization) → silent. Hours in.
“Kente” feels like a hint, but the system isn’t surfacing the structure.
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)

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.

---

⚡ The 30-second test (run this now)

Open system.txt in Sage. Check how dense your equations actually are:

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.

---

🎯 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	Equations come back as a list of polynomials over GF(2)
2	Run linearization probe — pcw109550’s PlaidCTF MPKC writeup, ~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 (CPU) or kcning/mqsolver (GPU, Crossbred)	Solver returns the regular vector
5	CryptoMiniSat raw? Use 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)	Find your (n, m) row → recommended algorithm
7	While solver runs, ping CryptoHack Discord #challenge-hints	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 0s and 1s. 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 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.