malicious-crs-soundness.ipynb

Kernel: SageMath 10.0

Break: Soundness Failure with Malicious CRS

Module 10 | Breaking Weak Parameters

A malicious CRS generator can embed a backdoor that gives universal forgery capability.

Why This Matters

In the previous notebook we showed that leaking the toxic waste breaks soundness. Here we show something worse: a malicious setup authority can deliberately construct a CRS with a hidden backdoor.

The CRS looks valid to anyone inspecting it (it has the right structure, the right number of elements), but the authority has secretly embedded a trapdoor that lets them forge proofs for any statement, forever.

Attack	Who can forge	How
Toxic waste leak	Anyone who obtains the waste	Solve for $c$ using $\delta^{-1}$
Malicious CRS	Only the malicious authority	Backdoor baked into CRS structure

This is more insidious because the CRS cannot be audited for correctness without knowing the toxic waste.

The Scenario

A malicious authority runs the setup ceremony. Instead of choosing independent random values for the toxic waste, they use related randomness that gives them a trapdoor.

We demonstrate two attacks:

1. Trivial delta: setting $\delta = 1$ so that $c$ can be computed without the inverse

2. Related randomness: choosing $\delta = \alpha \cdot \beta$ so that a simple relationship holds

We work in $\mathbb{F}_{101}$ and simulate the Groth16 verification equation algebraically.

# === Setup: field and constraint ===
p = 101
F = GF(p)

# Same R1CS: prove x^2 = v for public value v
# Verification equation: a*b = alpha*beta + pub + c*delta

# First, let's see what a NORMAL (honest) CRS looks like
set_random_seed(100)
alpha_honest = F.random_element()
while alpha_honest == 0:
    alpha_honest = F.random_element()
beta_honest = F.random_element()
while beta_honest == 0:
    beta_honest = F.random_element()
delta_honest = F.random_element()
while delta_honest == 0:
    delta_honest = F.random_element()

print("=== Honest CRS ===")
print(f"  alpha = {alpha_honest}")
print(f"  beta  = {beta_honest}")
print(f"  delta = {delta_honest}")
print(f"  alpha*beta = {alpha_honest * beta_honest}")
print()
print("Properties of honest CRS:")
print(f"  delta is random: {delta_honest} (no special relationship)")
print(f"  Verifier sees curve points [alpha]_1, [beta]_2, [delta]_2")
print(f"  Cannot check independence of the underlying scalars!")

# === Attack 1: Trivial Delta ===
# Malicious authority sets delta = 1

alpha_mal1 = F(37)  # looks random
beta_mal1 = F(73)   # looks random
delta_mal1 = F(1)   # THE BACKDOOR: delta = 1

ab_mal1 = alpha_mal1 * beta_mal1

print("=== Malicious CRS #1: delta = 1 ===")
print(f"  alpha = {alpha_mal1}")
print(f"  beta  = {beta_mal1}")
print(f"  delta = {delta_mal1}  <-- BACKDOOR")
print(f"  alpha*beta = {ab_mal1}")
print()
print("Why is this bad?")
print("  Verification equation: a*b = alpha*beta + pub + c*delta")
print("  With delta = 1:        a*b = alpha*beta + pub + c")
print("  So: c = a*b - alpha*beta - pub")
print("  The authority can solve for c WITHOUT needing delta^(-1)!")
print("  In fact, ANYONE can, because [delta]_2 = [1]_2 = G_2.")
print("  But in the curve point world, [1]_2 = G_2 is the generator,")
print("  which looks like a valid point, hard to detect without")
print("  knowing delta should be random.")

# Forge with malicious CRS #1
print("=== Forging with delta = 1 ===")

# Claim: x^2 = 50 (may or may not be solvable, doesn't matter)
pub_claim = F(50)

# Pick any a, b
a_forge = F(22)
b_forge = F(33)

# c = a*b - alpha*beta - pub  (no division by delta needed!)
c_forge = a_forge * b_forge - ab_mal1 - pub_claim

# Verify
lhs = a_forge * b_forge
rhs = ab_mal1 + pub_claim + c_forge * delta_mal1

print(f"  False claim: x^2 = {pub_claim}")
print(f"  Proof: a={a_forge}, b={b_forge}, c={c_forge}")
print(f"  Check: a*b = {lhs}, alpha*beta + pub + c*delta = {rhs}")
print(f"  Valid? {lhs == rhs}")
print(f"\n  Forgery succeeded with NO need for delta^(-1).")
print(f"  The malicious CRS made forgery trivial.")

Attack 2: Related Randomness

Setting $\delta = 1$ is detectable in some scenarios (e.g., if $[\delta]_2 = G_2$ is checked). A subtler attack: set $\delta = \alpha \cdot \beta$.

Now the verification equation becomes: $$a \cdot b = \alpha\beta + \text{pub} + c \cdot \alpha\beta$$ $$a \cdot b = \alpha\beta \cdot (1 + c) + \text{pub}$$

The authority knows $\alpha\beta$ (which is public anyway in the CRS as $e([\alpha]_1, [\beta]_2)$), so they can solve for $c$.

# === Attack 2: Related Randomness (delta = alpha * beta) ===

alpha_mal2 = F(53)
beta_mal2 = F(67)
delta_mal2 = alpha_mal2 * beta_mal2  # THE BACKDOOR

ab_mal2 = alpha_mal2 * beta_mal2

print("=== Malicious CRS #2: delta = alpha * beta ===")
print(f"  alpha = {alpha_mal2}")
print(f"  beta  = {beta_mal2}")
print(f"  delta = {delta_mal2} = alpha*beta  <-- BACKDOOR")
print(f"  alpha*beta = {ab_mal2}")
print()
print("From outside: [delta]_2 = delta * G_2 looks like a random point.")
print("You cannot tell delta = alpha*beta without solving DLP.")
print()

# Forge: claim x^2 = 77
pub_claim2 = F(77)
a_forge2 = F(15)
b_forge2 = F(88)

# c = (a*b - alpha*beta - pub) / delta
# But delta = alpha*beta, so c = (a*b - alpha*beta - pub) / (alpha*beta)
# The authority knows alpha*beta, so this is trivial
c_forge2 = (a_forge2 * b_forge2 - ab_mal2 - pub_claim2) * delta_mal2^(-1)

lhs2 = a_forge2 * b_forge2
rhs2 = ab_mal2 + pub_claim2 + c_forge2 * delta_mal2

print(f"Forging proof for x^2 = {pub_claim2}:")
print(f"  Proof: a={a_forge2}, b={b_forge2}, c={c_forge2}")
print(f"  Check: {lhs2} == {rhs2}? {lhs2 == rhs2}")
print(f"\nKey insight: the authority knows delta as a scalar because")
print(f"they CHOSE it to equal alpha*beta. An honest CRS would have")
print(f"delta independent of alpha and beta.")

# === Can we DETECT a malicious CRS? ===

print("=== Detection Attempt ===")
print()
print("What the verifier sees (as curve points):")
print("  Honest CRS:    [alpha]_1, [beta]_2, [delta]_2")
print("  Malicious CRS: [alpha]_1, [beta]_2, [delta]_2")
print()
print("Both look identical in structure!")
print()
print("Can the verifier check independence?")
print("  Test: e([delta]_1, G_2) == e([alpha]_1, [beta]_2)?")
print("  This would reveal delta = alpha*beta...")
print("  But this requires [delta]_1, which may not be in the CRS!")
print()

# In Groth16, the CRS structure is fixed. Checking relationships between
# CRS elements is possible only for certain pairs.

# The fundamental problem: you can't verify that secret values are
# independently random by looking at their curve-point encodings.

print("Fundamental problem:")
print("  Proving that scalars are independently random from")
print("  their curve-point encodings is computationally impossible")
print("  (it would require solving the discrete logarithm).")
print()
print("This is WHY multi-party computation ceremonies exist:")
print("  each participant contributes randomness, ensuring independence.")

STARKs: No Setup, No Problem

STARKs (Scalable Transparent Arguments of Knowledge) eliminate the trusted setup entirely. The CRS is replaced by public randomness derived from hash functions.

Property	Groth16 (SNARK)	STARK
Setup	Trusted ceremony (toxic waste)	None (transparent)
CRS	Contains hidden trapdoor potential	Public coins only
Malicious setup risk	Complete soundness break	Impossible
Cryptographic assumption	Pairings + DLP	Hash functions only
Quantum resistance	No	Yes
Proof size	192 bytes	~50-200 KB

The trade-off is clear: STARKs have larger proofs, but no trust assumption.

# === Comparison: transparent vs trusted ===

import hashlib

# STARK-style: all randomness is public (Fiat-Shamir)
# No secrets, no toxic waste, no backdoor possible

def stark_random_challenge(transcript_data):
    """Derive a verifier challenge from public transcript (Fiat-Shamir)."""
    h = hashlib.sha256(str(transcript_data).encode()).hexdigest()
    return F(int(h, 16) % p)

# The STARK verifier challenge is deterministic from public data
challenge_1 = stark_random_challenge("prover_commitment_round_1")
challenge_2 = stark_random_challenge("prover_commitment_round_2")

print("=== STARK: Transparent Randomness ===")
print(f"  Challenge 1 = Hash('round_1') mod {p} = {challenge_1}")
print(f"  Challenge 2 = Hash('round_2') mod {p} = {challenge_2}")
print()
print("Anyone can recompute these challenges.")
print("No secrets involved. No backdoor possible.")
print()
print("=== Groth16: Hidden Randomness ===")
print(f"  alpha = {alpha_mal2} (hidden as [{alpha_mal2}]_1 on the curve)")
print(f"  delta = {delta_mal2} (hidden as [{delta_mal2}]_2 on the curve)")
print(f"  These could be related, you can't tell from the outside.")

Exercises

1. Another backdoor: Set $\delta = \alpha + \beta$. Can the malicious authority still forge proofs? Write the forgery.

2. Detection game: Given two CRS instances (one honest, one malicious with $\delta = 1$), can you distinguish them if you have access to a pairing oracle? What pairing equation would you check?

3. MPC fix: Suppose two participants each contribute $\delta_1, \delta_2$, and the final $\delta = \delta_1 \cdot \delta_2$. If participant 1 is malicious but participant 2 is honest, show that participant 1 cannot determine $\delta$.

# Exercise 3 (Worked): MPC ceremony with one honest participant

print("=== MPC Ceremony: 2 Participants ===")
print()

# Participant 1 (malicious): chooses delta_1 = 1 (trying to make delta trivial)
delta_1 = F(1)  # malicious choice
print(f"Participant 1 (malicious): delta_1 = {delta_1}")

# Participant 2 (honest): chooses truly random delta_2
set_random_seed(999)
delta_2 = F.random_element()
while delta_2 == 0:
    delta_2 = F.random_element()
print(f"Participant 2 (honest):    delta_2 = {delta_2}")

# Combined delta
delta_combined = delta_1 * delta_2
print(f"\nCombined: delta = delta_1 * delta_2 = {delta_1} * {delta_2} = {delta_combined}")
print()
print("What participant 1 knows:")
print(f"  delta_1 = {delta_1}")
print(f"  [delta_2 * G_2] (curve point, cannot extract delta_2)")
print(f"  [delta * G_2] = [(delta_1 * delta_2) * G_2] (curve point)")
print(f"  Even with delta_1 = 1, delta = delta_2 which is UNKNOWN to P1.")
print()
print("Result: participant 1 cannot forge because they don't know delta.")
print("As long as ONE participant is honest, the ceremony is secure.")
print()

# Even if P1 tries harder: delta_1 = alpha (also toxic waste)
# The combined delta = alpha * delta_2 is still random to P1
# because P1 doesn't know delta_2.
print("Key insight: the MPC protocol ensures that the COMBINED toxic waste")
print("is unknown to any single participant, making forgery impossible.")

Summary

Attack	Mechanism	Detectability	Fix
Toxic waste leak	Attacker obtains $\delta$ after honest setup	Not applicable	Destroy waste
Malicious CRS ($\delta = 1$)	Authority embeds trivial $\delta$	Hard (requires DLP)	MPC ceremony
Malicious CRS (related $\delta$)	Authority uses $\delta = f(\alpha, \beta)$	Impossible from curve points	MPC ceremony
Transparent setup (STARKs)	N/A	N/A	No setup needed

Key takeaways:

• A malicious CRS generator can embed undetectable backdoors.

• The verifier cannot check that CRS elements are independently random.

• MPC ceremonies fix this: as long as one participant is honest, the CRS is secure.

• Transparent systems (STARKs) eliminate the problem entirely by using only public randomness.

---

Back to Module 10: SNARKs and STARKs