rogue-key-attack-bls.ipynb

Kernel: SageMath 10.0

Break: Rogue Key Attack on Naive BLS Aggregation

Module 07 | Breaking Weak Parameters

Craft a malicious public key that lets you forge an aggregate BLS signature.

Why This Matters

BLS signature aggregation is one of the most powerful features of pairing-based cryptography. In the same-message setting, $n$ signatures compress into a single curve point, verified with just 2 pairings:

$$e(\sigma_{\text{agg}}, g_2) = e(H(m), pk_1 + pk_2 + \cdots + pk_n)$$

But there is a critical vulnerability: if public keys are not validated, an attacker can construct a rogue key that cancels out all other signers' public keys. This lets the attacker forge an aggregate signature without any honest signer's participation.

This attack was identified by Micali, Ohta, and Reyzin (2001) and is the reason Ethereum 2.0 requires proof of possession during validator registration.

The Scenario

Alice is an honest validator with key pair $(a, pk_A = a \cdot g_2)$.

Mallory wants to forge an aggregate signature that appears to come from both Alice and Mallory, even though Alice never signed the message. Mallory's strategy:

1. Observe Alice's public key $pk_A$.

2. Choose a secret $m$ and set her "public key" to $pk_M = m \cdot g_2 - pk_A$.

3. The aggregate public key becomes $pk_A + pk_M = m \cdot g_2$.

4. Mallory can now sign alone using $m$ and produce a valid aggregate signature.

Your job: carry out this attack step by step on a toy curve and verify it works.

# === Step 1: Set up BLS on a supersingular curve ===

# Supersingular curve y^2 = x^3 + x over GF(p), p ≡ 3 mod 4
p = 467
E = EllipticCurve(GF(p), [1, 0])
card = E.cardinality()
print(f"Curve: y^2 = x^3 + x over GF({p})")
print(f"|E(GF({p}))| = {card} = {factor(card)}")

# Subgroup of prime order n, embedding degree k = 2
n = 13
k = 2
cofactor = card // n

# Extension field for the pairing target
F2.<a> = GF(p^k)
E_ext = E.change_ring(F2)

# Find G1 generator
while True:
    g1 = cofactor * E.random_point()
    if g1 != E(0) and n * g1 == E(0):
        break

g1_ext = E_ext(g1)

# Find G2 generator (linearly independent from g1 in the n-torsion over F_{p^2})
cofactor_ext = E_ext.cardinality() // n
while True:
    g2 = cofactor_ext * E_ext.random_point()
    if g2 != E_ext(0) and n * g2 == E_ext(0):
        if g1_ext.weil_pairing(g2, n) != 1:
            break

print(f"\nSubgroup order: n = {n}")
print(f"G1 generator: g1 = {g1}")
print(f"G2 generator: g2 = {g2}")
print(f"Pairing check: e(g1, g2) = {g1_ext.weil_pairing(g2, n)}  (non-trivial => good)")

# === Hash-to-curve helper (simplified for teaching) ===

def hash_to_curve(message, E, n, cofactor):
    """Map a message string to a point in the n-torsion subgroup of E."""
    h = hash(message) % (10^6)
    for x_try in range(h, h + 1000):
        x = GF(p)(x_try)
        y_sq = x^3 + x
        if y_sq.is_square():
            y = y_sq.sqrt()
            P = E(x, y)
            Q = cofactor * P
            if Q != E(0):
                return Q
    return cofactor * E.random_point()

def bls_sign(message, sk, E, n, cofactor):
    """BLS sign: sigma = sk * H(m)."""
    h = hash_to_curve(message, E, n, cofactor)
    return sk * h

def bls_verify(message, sigma, pk, g2, E, n, cofactor):
    """BLS verify: e(sigma, g2) == e(H(m), pk)."""
    h = hash_to_curve(message, E, n, cofactor)
    h_ext = E_ext(h)
    sigma_ext = E_ext(sigma)
    lhs = sigma_ext.weil_pairing(g2, n)
    rhs = h_ext.weil_pairing(pk, n)
    return lhs == rhs

# Quick sanity check
test_sk = 5
test_pk = test_sk * g2
test_sig = bls_sign("test", test_sk, E, n, cofactor)
print(f"Sanity check: BLS sign/verify = {bls_verify('test', test_sig, test_pk, g2, E, n, cofactor)}")

Step 2: Alice Signs Honestly, Mallory Constructs the Rogue Key

Alice generates a legitimate key pair and signs a message. Meanwhile, Mallory observes Alice's public key and constructs a rogue public key designed to cancel it out.

# === Step 2: Alice's honest setup and Mallory's rogue key ===

# Alice: honest key pair
sk_alice = randint(1, n - 1)
pk_alice = sk_alice * g2
print(f"Alice's secret key: sk_A = {sk_alice}")
print(f"Alice's public key: pk_A = {pk_alice}")

# Mallory: picks her own secret, but constructs a ROGUE public key
sk_mallory = randint(1, n - 1)
pk_mallory_honest = sk_mallory * g2  # what Mallory's pk SHOULD be
pk_mallory_rogue = sk_mallory * g2 - pk_alice  # the rogue key!

print(f"\nMallory's secret key:     sk_M = {sk_mallory}")
print(f"Mallory's honest pk:      sk_M * g2 = {pk_mallory_honest}")
print(f"Mallory's ROGUE pk:       sk_M * g2 - pk_A = {pk_mallory_rogue}")

# The critical observation: aggregate pk = pk_A + pk_M_rogue = sk_M * g2
pk_agg = pk_alice + pk_mallory_rogue
print(f"\nAggregate public key:     pk_A + pk_M = {pk_agg}")
print(f"Mallory's sk_M * g2:      {sk_mallory * g2}")
print(f"Equal? {pk_agg == sk_mallory * g2}")
print(f"\nMallory now controls the aggregate public key entirely!")

Step 3: Mallory Forges the Aggregate Signature

In same-message BLS aggregation, verification checks:

$$e(\sigma_{\text{agg}}, g_2) = e(H(m), pk_{\text{agg}})$$

Since $pk_{\text{agg}} = sk_M \cdot g_2$, Mallory computes $\sigma_{\text{forge}} = sk_M \cdot H(m)$. This satisfies the equation because:

$$e(sk_M \cdot H(m), g_2) = e(H(m), g_2)^{sk_M} = e(H(m), sk_M \cdot g_2) = e(H(m), pk_{\text{agg}})$$

Alice never signed this message!

# === Step 3: Mallory forges the aggregate signature ===

forged_msg = "Transfer 1000 ETH to Mallory"

# Mallory signs alone using her secret key
h_forged = hash_to_curve(forged_msg, E, n, cofactor)
sigma_forged = sk_mallory * h_forged

print(f"Forged message: '{forged_msg}'")
print(f"H(m) = {h_forged}")
print(f"Forged sigma = sk_M * H(m) = {sigma_forged}")

# Verify as a same-message aggregate of Alice + Mallory
sigma_f_ext = E_ext(sigma_forged)
h_f_ext = E_ext(h_forged)

lhs = sigma_f_ext.weil_pairing(g2, n)
rhs = h_f_ext.weil_pairing(pk_agg, n)

print(f"\n=== Aggregate Verification ===")
print(f"e(sigma_forged, g2)  = {lhs}")
print(f"e(H(m), pk_agg)      = {rhs}")
print(f"Verification passes? {lhs == rhs}")

# === Step 4: Alice never signed! ===

# Let's prove Alice didn't sign this message.
# If Alice had honestly signed, her individual signature would be:
sigma_alice_honest = bls_sign(forged_msg, sk_alice, E, n, cofactor)

# The real aggregate would be sigma_alice + sigma_mallory for some sigma_mallory
# But Mallory's forged sigma is just sk_M * H(m), NOT the sum of two individual sigs.

# Check: does Mallory's forged sigma equal Alice's sig + some Mallory sig?
sigma_mallory_would_need = sigma_forged - sigma_alice_honest

# If Mallory had honestly signed with her rogue key's "secret"...
# But she doesn't KNOW the discrete log of pk_mallory_rogue w.r.t. g2!
# Her rogue key was constructed algebraically, not from a known scalar.

print("=== Proof that Alice never participated ===")
print(f"Alice's honest signature on the forged message: {sigma_alice_honest}")
print(f"Mallory's forged aggregate:                     {sigma_forged}")
print(f"Are they related? sigma_forged - sigma_alice =  {sigma_mallory_would_need}")
print()
print("Alice NEVER computed bls_sign on this message.")
print("The aggregate verification passed because Mallory's rogue key")
print("made the aggregate pk collapse to something Mallory fully controls.")
print()
print("This is the rogue key attack: the aggregate 'looks like' a joint")
print("signature from Alice and Mallory, but Alice was never involved.")

The Fix: Proof of Possession (PoP)

The defense is simple: before accepting any public key into the aggregation set, require the owner to prove they know the corresponding secret key.

Proof of Possession: each signer produces $\text{PoP} = sk \cdot H_{\text{pop}}(pk)$, where $H_{\text{pop}}$ is a hash function distinct from the message hash $H$.

Verification of PoP: check $e(\text{PoP}, g_2) = e(H_{\text{pop}}(pk), pk)$.

Mallory cannot produce a valid PoP for her rogue key because she does not know the discrete log of $pk_M = sk_M \cdot g_2 - pk_A$ with respect to $g_2$.

# === The Fix: Proof of Possession ===

def hash_to_curve_pop(pk, E, n, cofactor):
    """Separate hash for PoP (domain-separated from message hash)."""
    # Use a different seed to simulate domain separation
    pk_str = f"PoP-domain:{pk}"
    h = hash(pk_str) % (10^6)
    for x_try in range(h, h + 1000):
        x = GF(p)(x_try)
        y_sq = x^3 + x
        if y_sq.is_square():
            y = y_sq.sqrt()
            P = E(x, y)
            Q = cofactor * P
            if Q != E(0):
                return Q
    return cofactor * E.random_point()

def make_pop(sk, pk, E, n, cofactor):
    """Produce proof of possession: sk * H_pop(pk)."""
    h_pop = hash_to_curve_pop(pk, E, n, cofactor)
    return sk * h_pop

def verify_pop(pk, pop, g2, E, n, cofactor):
    """Verify PoP: e(pop, g2) == e(H_pop(pk), pk)."""
    h_pop = hash_to_curve_pop(pk, E, n, cofactor)
    h_pop_ext = E_ext(h_pop)
    pop_ext = E_ext(pop)
    lhs = pop_ext.weil_pairing(g2, n)
    rhs = h_pop_ext.weil_pairing(pk, n)
    return lhs == rhs

# Alice can produce a valid PoP
pop_alice = make_pop(sk_alice, pk_alice, E, n, cofactor)
print(f"Alice's PoP valid? {verify_pop(pk_alice, pop_alice, g2, E, n, cofactor)}")

# Mallory CANNOT produce a valid PoP for her rogue key
# She would need to compute sk_rogue * H_pop(pk_rogue), but she doesn't
# know sk_rogue (the discrete log of pk_mallory_rogue w.r.t. g2).
# She only knows sk_mallory, which is NOT the discrete log of pk_mallory_rogue.

# Mallory tries her best: use sk_mallory with the rogue pk
pop_mallory_attempt = make_pop(sk_mallory, pk_mallory_rogue, E, n, cofactor)
print(f"Mallory's PoP for rogue key valid? {verify_pop(pk_mallory_rogue, pop_mallory_attempt, g2, E, n, cofactor)}")

print()
print("Mallory cannot produce a valid PoP because she does not know")
print("the discrete log of her rogue key. The attack is blocked!")

Exercise: Rogue Key with 3 Signers

Extend the attack to 3 signers. Alice and Bob have honest keys. Mallory constructs:

$$pk_M = sk_M \cdot g_2 - pk_A - pk_B$$

1. Set up honest keys for Alice and Bob.

2. Construct Mallory's rogue key that cancels both.

3. Forge an aggregate signature that "verifies" for all three.

4. Confirm that PoP blocks the attack.

# === Exercise: 3-signer rogue key attack ===

# Alice and Bob: honest key pairs
sk_bob = randint(1, n - 1)
pk_bob = sk_bob * g2

# Mallory constructs rogue key to cancel both Alice and Bob
pk_mallory_rogue_3 = sk_mallory * g2 - pk_alice - pk_bob

# Aggregate public key
pk_agg_3 = pk_alice + pk_bob + pk_mallory_rogue_3
print(f"Alice pk:   {pk_alice}")
print(f"Bob pk:     {pk_bob}")
print(f"Mallory pk: {pk_mallory_rogue_3}")
print(f"Aggregate:  {pk_agg_3}")
print(f"sk_M * g2:  {sk_mallory * g2}")
print(f"Controlled by Mallory? {pk_agg_3 == sk_mallory * g2}")

# Forge aggregate signature
msg_3 = "All three approve this transaction"
h_3 = hash_to_curve(msg_3, E, n, cofactor)
sigma_forge_3 = sk_mallory * h_3

# Verify
s3_ext = E_ext(sigma_forge_3)
h3_ext = E_ext(h_3)
lhs_3 = s3_ext.weil_pairing(g2, n)
rhs_3 = h3_ext.weil_pairing(pk_agg_3, n)

print(f"\nForged 3-signer aggregate verifies? {lhs_3 == rhs_3}")
print("Neither Alice nor Bob signed this message!")

# PoP check blocks Mallory
pop_bob = make_pop(sk_bob, pk_bob, E, n, cofactor)
pop_mal_3 = make_pop(sk_mallory, pk_mallory_rogue_3, E, n, cofactor)
print(f"\nBob's PoP valid?     {verify_pop(pk_bob, pop_bob, g2, E, n, cofactor)}")
print(f"Mallory's PoP valid? {verify_pop(pk_mallory_rogue_3, pop_mal_3, g2, E, n, cofactor)}")
print("\nWith PoP required, Mallory's rogue key is rejected at registration.")

Summary

Aspect	Detail
Attack	Rogue key: $pk_M = sk_M \cdot g_2 - \sum pk_i$ makes aggregate pk controlled by Mallory
Impact	Mallory forges aggregate signatures without other signers' participation
Root cause	Naive aggregation does not verify that signers know their secret keys
Fix	Proof of Possession (PoP): sign your own public key to prove key knowledge
Real world	Ethereum 2.0 requires PoP at validator registration (EIP-2333/2334)

Key takeaway: aggregation is not free, it requires careful key validation. The pairing equation is mathematically correct, but cryptographic security requires protocol-level defenses beyond the raw math.

---

Back to Module 07: Bilinear Pairings