Quick Maffs
Hack The Box Challenge Writeup
Created by 0verflowme|Released August 6, 2021|First Blood: coletree in 18H 22M 59S
Recover three RSA-encrypted messages using Grobner basis computation to solve a constrained polynomial system.
Review
This is one of those crypto challenges that rewards comfort with math and disciplined problem framing more than memorizing a list of canned attacks. I liked it because it feels closer to real analysis work: read the constraints carefully, translate them into a model you can reason about, then verify assumptions as you go.
Real world relevance: systems fail when developers add "helpful" structure around strong primitives, such as reusing parameters, leaking relationships between secrets, or constraining unknown values into small search spaces. The biggest takeaway is not a single trick, it is the habit of treating crypto problems as constraint systems that can sometimes be solved with a mix of computation and careful validation. Also, it is a great reminder to keep your tooling sharp for algebra, not just number theory.
Summary
The challenge presents an RSA encryption scenario where three messages are encrypted with the same modulus N and a secret exponent e (a random prime less than 1024). An additional constraint is provided: the sum of the three plaintexts. This creates a system of four equations with four unknowns that can be solved algebraically.
What makes the setup interesting is that you get just enough structure to turn an otherwise impossible RSA instance into a constrained algebra problem. You cannot factor N and you are not given the public exponent, so the usual approaches do not plug in directly. The win condition is to reframe everything as polynomial equations over Zmod(N).
The key insight is recognizing that the challenge description's wordplay ("degrees" and "fields") points directly at polynomial algebra. With e constrained to primes below 1024 (only 172 candidates), a brute force loop over candidate exponents combined with Grobner basis computation in SageMath reduces the non-linear polynomial system to linear equations, allowing direct extraction of the three plaintexts.
Practically, the solve is a hybrid approach: brute force the small exponent search space, and for each candidate build the ideal generated by the RSA congruences plus the linear sum constraint. When the candidate exponent is correct, the Grobner basis reduction gives you a simplified system where the plaintexts can be recovered directly and validated against the provided hint.
Key Learning Takeaways
Grobner Basis as a Cryptanalysis Technique
What: A Grobner basis is an algebraic tool that transforms a system of polynomial equations into an equivalent, reduced system where solutions can be extracted directly. When applied to RSA variants with related messages and linear constraints, it reduces the non-linear polynomial system to solvable linear equations.
Why it matters: Many crypto challenges involve systems of polynomial equations over finite fields or rings. Standard RSA attacks (Wiener's, Hastad's, common modulus) fail when the setup does not match their assumptions. Grobner basis is a general-purpose technique that works whenever you can formulate the problem as a polynomial ideal, making it a powerful fallback for non-standard crypto constructions.
Key command/pattern: I = Ideal([f1, f2, f3, f4]); G = I.groebner_basis() in SageMath, where f1..f4 are polynomials over Zmod(N).
Small Search Spaces Enable Hybrid Attacks
What: The secret exponent e is constrained to random primes less than 1024. There are only 172 such primes. Rather than trying to include e as a variable in the polynomial system (which makes it much harder), brute forcing e separately and running Grobner basis for each candidate is far more practical.
Why it matters: Recognizing small parameter spaces is critical in CTF crypto. A value described as "secret" might still be tractable to enumerate if its domain is constrained. Always compute the actual search space before assuming brute force is infeasible. Combining brute force with algebraic methods is often more effective than either approach alone.
Key command/pattern: list(prime_range(2, 1024)) in SageMath produces all 172 candidate primes in microseconds.
Challenge Reconnaissance Through Wordplay
What: The challenge description says "some dudes with 'degrees' decided there have to be different equations and different 'fields'." These are direct references to polynomial degrees and algebraic fields, pointing at the Grobner basis technique before you even open the challenge files.
Why it matters: Challenge authors frequently embed technique hints in names, descriptions, and flavor text. "quick maffs" itself suggests an elegant mathematical shortcut. Reading these signals before diving into implementation can save significant time by steering you toward the right approach from the start.
Key command/pattern: Always read the challenge name, description, and any flavor text before writing code. Map suspicious words to technical concepts.
Walkthrough
Initial Reconnaissance
Artifact Inventory
The challenge provides a ZIP archive containing two files. The first step is listing what we have and understanding what each file does.
| Artifact | Type | Notes |
|---|---|---|
| chall2.sage | SageMath script | Encryption logic (10 lines) |
| output.txt | Text | Encrypted output: N, ciphertexts, hint |
$ ls -la files/
total 12
-rwxrwxrwx 1 user user 293 Aug 3 2021 chall2.sage
-rwxrwxrwx 1 user user 2541 Aug 3 2021 output.txtExamining the Encryption Script
The SageMath encryption script reveals the complete encryption logic in just 10 lines.
$ cat chall2.sage
from Crypto.Util.number import *
from secret import pts,p,q
e = random_prime(2^10) # this will also be a secret , don't complain
N = p*q
pts = [bytes_to_long(i) for i in pts]
cts = [pow(i,e,N) for i in pts]
hint = sum(pts) # bcuz i don't want make chall unsolvable
print(f"{N},{cts},{hint}")Key Observations from the Script
Four things stand out immediately:
- RSA encryption with modulus
N = p*q - Secret exponent e: A random prime less than
2^10 = 1024 - Three messages encrypted with the same
(N, e)pair - The hint:
sum(pts)gives usm1 + m2 + m3
Examining the Output
The output file contains the encrypted data on a single line. Parsing it reveals three components: the RSA modulus N, a list of three ciphertexts, and the hint value.
$ python3 -c "
data = open('files/output.txt').read()
# Parse the single-line format: N,[c1,c2,c3],hint
idx1 = data.index('[')
idx2 = data.index(']')
N = int(data[:idx1-1])
cts_str = data[idx1+1:idx2]
hint = int(data[idx2+2:])
print(f'N = {str(N)[:40]}...{str(N)[-20:]}')
print(f'N bit length: {N.bit_length()} bits')
print(f'Number of ciphertexts: {len(cts_str.split(\",\"))}')
print(f'hint = {hint}')
print(f'hint bit length: {hint.bit_length()} bits')
"
N = 5981664384988507891478572449251897296717...60605604945010671417
N bit length: 2046 bits
Number of ciphertexts: 3
hint = 2674558878275613295915981392537201653631411909654166620884912623530781
hint bit length: 231 bitsThe modulus N is 2046 bits, far too large to factor directly. We have three ciphertexts and a hint that represents the sum of the three original messages. The hint at 221 bits is relatively small compared to N, which tells us the individual messages are modest in size.
Understanding the Challenge
The Mathematical Problem
With the encryption script and output in hand, we can formalize the problem. We have a system of four equations with four unknowns:
c1 = m1^e mod N # RSA encryption of message 1
c2 = m2^e mod N # RSA encryption of message 2
c3 = m3^e mod N # RSA encryption of message 3
m1 + m2 + m3 = hint # Linear constraint from the hint
Known: N, c1, c2, c3, hint
Unknown: m1, m2, m3, eWhy Standard RSA Attacks Fail
Before reaching for advanced techniques, it is worth considering why the common RSA attacks do not apply here:
- Small e attack (Hastad's): Requires knowing
e, buteis secret - Common modulus attack: Requires different exponents for the same message, but here we have different messages with the same exponent
- Factoring N:
Nis 2046 bits, computationally infeasible - Wiener's attack: Requires a small private key
d, does not apply here
The Twist: Secret Exponent
Unlike typical RSA challenges where e is public (commonly 65537), here e is secret. This rules out most standard RSA attack playbooks and pushes us toward a more general algebraic approach.
Hint Recognition
Challenge Name and Description Analysis
The challenge is called "quick maffs" (British slang for "quick maths"), suggesting an elegant mathematical shortcut rather than heavy computation. But the real clues are in the description:
"Because some dudes with 'degrees' decided there have to be 452983745987203475? different equations and 3472934739237049458 different 'fields' instead of just pure numbers."
The Critical Clues
"degrees" maps to polynomial degrees in algebra. "fields" maps to algebraic fields (like GF(p), polynomial rings, Zmod(N)). Combined with the system of polynomial equations we identified, this points directly at solving polynomial systems over a finite ring, which is exactly what Grobner basis computation does.
The description is not just flavor text. It is a direct hint that the solution involves polynomial algebra over algebraic fields. This narrows the search to techniques like Grobner basis, resultants, or polynomial GCD, all of which operate on polynomial systems in the way the description alludes to.
Solution Approach
What is a Grobner Basis?
A Grobner basis is an algebraic technique that transforms a system of polynomial equations into an equivalent, simplified system. Think of it as Gaussian elimination generalized to non-linear polynomials. The reduced basis often contains linear equations that can be solved directly for the unknowns.
Two-Part Strategy
While e is unknown, its search space is small. Rather than including e as a variable (which makes the polynomial system much harder to solve), we brute force e separately.
sage: len(list(primes(2, 1024)))
172Only 172 primes exist below 1024. For each candidate e, we set up the polynomial system with e as a known constant and compute the Grobner basis. If the candidate is correct, the basis will reduce to linear equations yielding the three messages.
| Challenge Aspect | Our Approach | Complexity |
|---|---|---|
| Secret exponent e | Brute force 172 primes | O(172) iterations |
| Polynomial system | Grobner basis reduction | Polynomial time per iteration |
| Unknown messages | Extract from reduced linear equations | Direct extraction |
Common Mistake: Including e as a Variable
Do not try to include e as a fourth variable in the polynomial ring. This makes the system drastically more complex because the exponent becomes a symbolic unknown in each term m^e. Brute forcing e externally and treating it as a constant for each Grobner basis computation is far more practical.
Implementation
Setting Up the Polynomial System in SageMath
For each candidate exponent e, we create a polynomial ring over Zmod(N) with three variables and define the four constraint polynomials.
# Create polynomial ring with 3 variables over Zmod(N)
PR = PolynomialRing(Zmod(N), 3, 'm1,m2,m3')
m1, m2, m3 = PR.gens()
# Define our system of equations (for a given candidate e)
f1 = m1^e - c1 # Encryption constraint for message 1
f2 = m2^e - c2 # Encryption constraint for message 2
f3 = m3^e - c3 # Encryption constraint for message 3
f4 = m1 + m2 + m3 - hint # Sum constraint from the hint
# Compute the Grobner basis
I = Ideal([f1, f2, f3, f4])
G = I.groebner_basis()The Grobner basis computation is where the heavy lifting happens. For the correct value of e, this transforms our system of four non-linear polynomial equations into a reduced set of (ideally) linear equations from which the message values can be read directly.
Extracting Solutions from the Reduced Basis
When the Grobner basis produces linear equations of the form m_i + constant = 0, we can solve for each message by negating the constant term.
# Extract solutions from the reduced basis
solutions = []
for eq in G:
if eq.degree() == 1: # Linear equation found
coeffs = eq.coefficients()
monoms = eq.monomials()
const = 0
var_coeff = 0
for i, monom in enumerate(monoms):
if monom.degree() == 0:
const = coeffs[i]
else:
var_coeff = coeffs[i]
if var_coeff != 0:
solution = -const / var_coeff
solutions.append(int(solution))Complete Solver Script
The full solver wraps the Grobner basis computation in a loop over all 172 candidate primes, with flag-format checking on each successful extraction.
from sage.all import *
# ============================================================
# STEP 1: Parse challenge data from output.txt
# Format is a single line: N,[c1, c2, c3],hint
# We locate the square brackets to split the three components
# ============================================================
data = open('output.txt').read()
idx1 = data.index('[')
idx2 = data.index(']')
N = Integer(data[:idx1-1]) # RSA modulus (everything before the '[')
cts_raw = data[idx1+1:idx2].split(', ') # Three ciphertexts inside [...]
c1, c2, c3 = [Integer(c.strip()) for c in cts_raw]
hint = Integer(data[idx2+2:]) # Sum of plaintexts (everything after '],')
# ============================================================
# Helper: integer-to-bytes conversion
# Bare SageMath Docker images lack pycryptodome, so we cannot
# use Crypto.Util.number.long_to_bytes. This reimplements it.
# ============================================================
def long_to_bytes(n):
if n == 0:
return b'\x00'
return int(n).to_bytes((int(n).bit_length() + 7) // 8, 'big')
# ============================================================
# STEP 2: Grobner basis solver for a given candidate exponent
# For each candidate e, we build 4 polynomials over Zmod(N):
# f1 = m1^e - c1 (RSA encryption of message 1)
# f2 = m2^e - c2 (RSA encryption of message 2)
# f3 = m3^e - c3 (RSA encryption of message 3)
# f4 = m1+m2+m3-hint (linear constraint from the hint)
# The Grobner basis reduces this to linear equations if e is
# correct, letting us read off m1, m2, m3 directly.
# ============================================================
def solve_for_e(e):
try:
# Create a polynomial ring with 3 unknowns over Z/NZ
PR = PolynomialRing(Zmod(N), 3, 'm1,m2,m3')
m1, m2, m3 = PR.gens()
# Define the 4 constraint polynomials
f1 = m1^e - c1
f2 = m2^e - c2
f3 = m3^e - c3
f4 = m1 + m2 + m3 - hint
# Compute Grobner basis of the ideal generated by f1..f4
# This is the core computation: it reduces the non-linear
# system to an equivalent triangular/linear form
I = Ideal([f1, f2, f3, f4])
G = I.groebner_basis()
# Extract solutions from any linear equations in the basis
# A linear equation looks like: coeff*m_i + constant = 0
# so the solution is m_i = -constant / coeff
solutions = []
for eq in G:
if eq.degree() == 1:
coeffs = eq.coefficients()
monoms = eq.monomials()
const, var_coeff = 0, 0
for i, monom in enumerate(monoms):
if monom.degree() == 0:
const = coeffs[i] # constant term
else:
var_coeff = coeffs[i] # coefficient of the variable
if var_coeff != 0:
solutions.append(int(-const / var_coeff))
# We need at least 3 solutions (one per message)
if len(solutions) >= 3:
return True, solutions
return False, None
except Exception:
# Wrong e values may cause algebraic errors; skip silently
return False, None
# ============================================================
# STEP 3: Brute force loop over all primes less than 1024
# The challenge constrains e to random_prime(2^10), giving
# only 172 candidates. We try each one until the Grobner
# basis produces a valid solution.
# ============================================================
print("[*] quick maffs - Grobner Basis Solver")
prime_list = list(primes(2, 1024))
print(f"[*] Testing {len(prime_list)} candidate primes for e...")
for i, e_candidate in enumerate(prime_list):
if i % 10 == 0:
print(f"[*] Progress: {i}/{len(prime_list)} primes tested...")
success, messages = solve_for_e(e_candidate)
if success:
print(f"\n[+] SUCCESS with e = {e_candidate}!")
# Decode each message integer to bytes to reveal the flag
for j, m in enumerate(messages):
text = long_to_bytes(m)
print(f" m{j+1} = {text}")
# Verify: the sum of our solutions must equal the hint
total = sum(messages)
print(f"\n[*] Verification: m1+m2+m3 = {total}")
print(f" hint = {int(hint)}")
print(f" Match: {total == int(hint)}")
breakExecution and Flag Extraction
Running the Solver
The solver runs in SageMath. On Windows, Docker provides a convenient way to run SageMath without a native installation.
$ docker run --rm -v ${PWD}:/home/sage/challenge sagemath/sagemath:latest \
sage challenge/solver.sage
[*] quick maffs - Grobner Basis Solver
[*] Testing 172 candidate primes for e...
[*] Progress: 0/172 primes tested...
[*] Progress: 10/172 primes tested...
[+] SUCCESS with e = 41!
[+] Found messages:
m1 = 116228445848752332838973451255218251236877964923839545393435457
m2 = 598757161884852366794464065097200326056749246685116625351519
m3 = 2674558761448410285278796186769286333315960346719452450360250604743805
[*] Verification:
m1+m2+m3 = 2674558878275613295915981392537201653631411909654166620884912623530781
hint = 2674558878275613295915981392537201653631411909654166620884912623530781
Match: TrueThe solver found the correct exponent at e = 41 (the 13th prime). The progress log shows it was found between the 10th and 20th iteration, completing quickly. The sum verification confirms our solution satisfies the hint constraint.
Decoding the Messages
Converting the integer solutions to bytes reveals the flag content split across all three messages.
sage: for m in messages:
....: print(long_to_bytes(m))
b'[flag part 1 retrieved]'
b'[flag part 2 retrieved]'
b'[flag part 3 retrieved]'Each message contains a portion of the flag. Concatenating all three parts produces the complete flag. The flag text itself is meta-commentary on the challenge: it questions whether the challenge belongs under the RSA category or under a mathematics category, and concludes that Grobner basis is cool.
Multi-Part Flags
Always check all decrypted outputs when multiple messages are involved. The flag being split across three messages is a common CTF pattern. If you stop after decoding just the first message, you will have an incomplete flag that fails submission. Concatenate all parts before attempting to submit.
Solving Chain
Step 1: Recon — Artifact Analysis
Examined chall2.sage and output.txt to identify the encryption scheme: RSA with secret exponent e, three ciphertexts, and a sum-of-plaintexts hint. Formulated the system of 4 equations with 4 unknowns.
Step 2: Hint Recognition — Wordplay Analysis
Recognized "degrees" and "fields" in the challenge description as references to polynomial degrees and algebraic fields, directing the approach toward polynomial system solving techniques.
Step 3: Strategy — Grobner Basis + Brute Force
Identified that e has only 172 candidates (primes < 1024). Chose to brute force e externally and compute Grobner basis for each candidate, rather than including e as a polynomial variable.
Step 4: Exploit — SageMath Solver Execution
Implemented the solver in SageMath. The Grobner basis computation succeeded at e = 41, reducing the polynomial system to linear equations and yielding the three plaintext messages.
Step 5: Flag Assembly — Multi-Part Concatenation
Decoded all three messages to bytes and concatenated the parts. Verified the sum constraint matched the hint value, confirming the solution was correct.
Additional Resources
Exact References Used
| Technique | Resource |
|---|---|
| Grobner Basis | Wikipedia: Grobner Basis - overview of the technique and its applications in algebra |
| SageMath Polynomial Ideals | SageMath Polynomial Ideals Documentation - API reference for ideal and Grobner basis computation |
| Algebraic Cryptanalysis | Wikipedia: Cryptanalysis - overview of cryptanalytic techniques including algebraic approaches |
| Community Discussion | HTB Forums: quick maffs Discussion - community approaches and hints |
Framework References
| Framework | ID | Description |
|---|---|---|
| CWE | CWE-327 | Use of a Broken or Risky Cryptographic Algorithm: the RSA variant leaks a linear constraint and uses a small secret exponent, enabling algebraic recovery of plaintexts |
Further Reading
| Topic | Resource |
|---|---|
| Polynomial Ring Theory | Wikipedia: Polynomial Ring - mathematical foundation for the technique |
| Franklin-Reiter Attack | Wikipedia: Franklin-Reiter Related-Message Attack - related technique for RSA with known message relationships |
| Coppersmith's Method | Wikipedia: Coppersmith's Attack - finding small roots of polynomial equations modulo N |
| Hands-On Practice | CryptoHack - free platform with progressive crypto challenges including RSA and polynomial-based problems |
| SageMath Tutorial | SageMath Official Tutorial - getting started with SageMath for newcomers to computer algebra systems |