Attacks on Threshold Schemes: Part 2

In Part 1, we covered implementation bugs - the missing checks, skipped validations, and encoding ambiguities that turn provably secure protocols into exploitable systems. Those were failures at the code level: developers trusting inputs they should validate, using insufficient security parameters, or misunderstanding the cryptographic requirements. This part goes deeper. Here we examine attacks that stem from the protocols themselves, design decisions that look sound in the paper but break under adversarial conditions the original authors didn't fully consider. We'll also look at a recent theoretical result that challenges the adaptive security of widely-deployed threshold Schnorr schemes. These aren't bugs you can fix with a parameter check or an extra validation. They're fundamental issues that require protocol redesign or careful understanding of when a protocol's security guarantees actually hold.

The MtA Oracle Attack

The Multiplicative-to-Additive (MtA) share conversion is everywhere in threshold ECDSA. This protocol uses Paillier encryption. Party Alice holds secret $a$ and a Paillier keypair $(E_A, D_A)$ with modulus $N$. Party Bob holds secret $b$. They proceed:

1. Alice encrypts: Computes $c_A = E_A(a)$ along with a zero-knowledge range proof that $a$ is in the correct range and sends $(c_A, \pi_A)$ to Bob.

2. Bob responds:

   • Verifies Alice's proof $\pi_A$
   • Picks random $\beta' \in \mathbb{Z}_N$
   • Sets $\beta = -\beta' \bmod q$ (his output share)
   • Computes $c_B = b \times_E c_A +_E E_A(\beta')$ using Paillier homomorphism (where $\times_E$ and $+_E$ are scalar multiplication and addition in the ciphertext space)
   • Sends $(c_B, \pi_B)$ where $\pi_B$ is a range proof

3. Alice decrypts: Verifies Bob's proof $\pi_B$ then computes $\alpha = D_A(c_B) \bmod q$ (her output share)

The range proofs ensure that $a$ and $b$ are small enough that the decryption doesn't overflow. Specifically, $\alpha' = D_A(c_B) = ab + \beta'$ (computed over the integers), and then $\alpha = \alpha' \bmod q$. If $a$ and $b$ are in range, $\alpha'$ doesn't wrap around modulo $q$, and we get $\alpha + \beta = ab \bmod q$ as desired.

The "Fast" Version

The GG18 paper proposed a variant (MtAwc) that omits the range proofs. Instead $(B, B')$ are published and the authors conjectured that the public values $B = g^b$ and $B' = g^{\beta'}$ "do not leak any additional data and compensate for the missing range proof." They were wrong.

The Attack

The attacker (say, Alice/Party 1) chooses $a = \lfloor \frac{2N}{q} \rfloor$. This is much larger than the protocol expects, $a$ should be roughly $q$-sized, but this $a$ is about $2N$.

Bob proceeds honestly: computes $c_B = b \cdot c_A +_E E_A(\beta')$ and sends $(c_B, B = g^b, B' = g^{\beta'})$.

Alice decrypts: $\alpha = D_A(c_B) = ab + \beta'$. Let's denote $\alpha'$ the original value over the integers (without modular reduction)

Now, $\beta' \in \mathbb{Z}_N$, so $\beta' \in [0, N)$. The key observation: depending on the size of $\alpha'$, it will fall into one of three disjoint ranges:

1. If $\alpha' \in [0, N)$: Then $\alpha' \mod q = \alpha$, so:

$$g^{ab} \cdot g^{\beta'} = g^{\alpha'} = g^\alpha$$

2. If $\alpha' \in [N, 2N)$: Then $\alpha' \mod q = \alpha + N$, so:

$$g^{ab} \cdot g^{\beta'} = g^{\alpha'} = g^{\alpha} \cdot g^N$$

3. If $\alpha' \in [2N, 3N)$: Then $\alpha' \mod q = \alpha + 2N$, and:

$$g^{ab} \cdot g^{\beta'} = g^{\alpha'} = g^{\alpha} \cdot g^{2N}$$

Alice computes $g^{ab} \cdot g^{\beta'} = g^a \cdot B \cdot B'$ (using the public values $B$ and $B'$) and checks which case holds. This reveals which interval $\alpha'$ belongs to, which in turn reveals information about $b$:

• Since $\alpha' = ab + \beta'$ and $\beta' \in [0, N)$, if $\alpha' \in [sN, (s+1)N)$, then $ab \in [(s-1)N, (s+1)N)$.
• With $a = \lfloor \frac{2N}{q} \rfloor$, we get $b \in \left[\frac{(s-1)q}{2}, \frac{(s+1)q}{2}\right]$.

Alice just learned a constraint on Bob's secret $b$ from a single MtA execution.

Generalizing the Attack

Alice can choose $a = \lfloor \frac{MN}{q} \rfloor$ for some integer $M$. Now $\alpha'$ will fall into one of $M+1$ intervals $[sN, (s+1)N)$ for $s \in {0, 1, \ldots, M}$. Each signature reveals which interval, giving Alice a constraint:

$$b \in \left[\frac{(s-1)q}{M}, \frac{(s+1)q}{M}\right]$$

After just a few signatures (each with a different malicious $a$ value), Alice reconstructs Bob's entire secret key.

Why It Happens

The "additional data" $B = g^b$ and $B' = g^{\beta'}$ was supposed to prevent leakage. But when Alice chooses out-of-range $a$, the decryption creates a side channel: the relationship between $g^{ab} \cdot g^{\beta'}$ and $g^\alpha$ reveals how much modular reduction occurred, which leaks information about $b$.

This is the Attack on absent range proofs from "Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations". The paper reports impact on ZenGo and ING libraries.

The Fix: Use the "slow" version with range proofs. Modern protocols like CGGMP20 include proper range proofs for all MtA inputs. Don't skip them.

Oops, We Deleted Too Early

Key resharing protocols are supposed to refresh shares without changing the underlying secret. This maintains continuous access to funds while limiting the damage from gradual key compromise. But if the protocol lacks proper coordination around when to delete old shares, an attacker can weaponize it into a permanent wallet lockout.

The Reshare Protocol

The vulnerable implementation uses VSS-based resharing in a $(t, n)$ threshold setting. The high-level flow:

1. Convert to additive shares: The $t+1$ old parties convert their Shamir shares into additive shares: $sk = w_1 + \cdots + w_{t+1}$, where each old party $P_i^0$ knows $w_i$.
2. Distribute via VSS: Each old party $P_i^0$ samples a random degree-$t$ polynomial with constant term $w_i$ (their additive share becomes the secret).
3. Broadcast commitments: Each $P_i^0$ broadcasts commitments to their polynomial coefficients (as in Feldman VSS).
4. Send new shares: Each old party $P_i^0$ sends evaluations of their polynomial to each of the $n'$ new parties.
5. Verify and sum: Each new party $P_j$ verifies the shares they received using the VSS commitments, then sums them to get their new share $w_j'$.
6. Check public key: New parties verify that the public key reconstructed from new shares matches the old public key.
7. Delete old shares: If all checks pass, parties delete their old shares $w_i$ and keep only the new shares $w_i'$.

The Attack

The adversary (one of the old parties) exploits step 4 by sending selectively malformed shares:

• Send valid shares to some new parties (say, parties $P_1, \ldots, P_k$)
• Send invalid shares to the rest (parties $P_{k+1}, \ldots, P_{n'}$)

At step 5, the verification outcome splits the new parties into two groups:

• Group A (received valid shares): Verification passes. They proceed to step 7 and delete their old shares, replacing them with new shares.
• Group B (received invalid shares): Verification fails. They abort the protocol and keep their old shares, not updating anything.

Now here's the problem: there's no synchronization before deletion. Parties in Group A don't know that Group B aborted. They delete their old shares and switch to the new ones.

The Consequence: The secret can no longer be reconstructed: mixing old and new shares doesn't work, they're not additive shares of the same secret anymore. Even if all parties cooperate, they can't generate a valid signature. The wallet is permanently locked.

This is the Forget-and-Forgive attack described in "Attacking Threshold Wallets".

The Fix Add a blame phase before deletion. After verification (step 5), parties must coordinate:

1. Each new party broadcasts whether their verification succeeded or failed
2. If any party reports a failure, everyone aborts, no one deletes old shares
3. Only if all $n'$ new parties report success does anyone proceed to delete old shares

Nonce Reuse via Deterministic Derivation

Nonce reuse in digital signatures is a classic footgun. Everyone knows the story: reuse your nonce in ECDSA or Schnorr, and your private key leaks. The standard defenses are either (1) sample a fresh random nonce for every signature, or (2) derive the nonce deterministically as $n = H(m | sk)$ .

Option 2 seems perfect for single-party signing, it's deterministic, so you can't accidentally reuse randomness, and it binds the nonce to both the message and the secret key. But in threshold signatures, determinism becomes a weapon.

Why Nonce Reuse Breaks Schnorr

Quick reminder of why nonce reuse is fatal. Suppose you sign two different messages $m_1, m_2$ with the same nonce $n$:

$$s_1 = n + c_1 \cdot sk, \quad s_2 = n + c_2 \cdot sk$$

where $c_1 = H(nG | pk | m_1)$ and $c_2 = H(nG | pk | m_2)$. Subtract:

$$s_1 - s_2 = (c_1 - c_2) \cdot sk \implies sk = \frac{s_1 - s_2}{c_1 - c_2}$$

Game over. The attacker recovers your secret key from two signatures.

The Threshold Setting

Now consider two-party Schnorr (a toy model, but the idea generalizes). Alice and Bob each hold shares $sk_1, sk_2$ of the secret key, with public key $pk = (sk_1 + sk_2) \cdot G$. To sign message $m$:

1. Nonce generation: Each party deterministically derives their nonce:

$$n_1 = H(m | sk_1), \quad n_2 = H(m | sk_2)$$

They exchange public nonces $N_1 = n_1 \cdot G$ and $N_2 = n_2 \cdot G$. The aggregate public nonce is $N = N_1 + N_2$. 2. Partial signatures: Each computes the challenge $c = H(N | pk | m)$ and produces:

$$s_1 = n_1 + c \cdot sk_1, \quad s_2 = n_2 + c \cdot sk_2$$

3. Aggregate: The final signature is over $(N, s_1 + s_2)$.

So far, so good. Each party's nonce depends on their own secret key and the message, so it looks safe.

The Attack

Here's the problem: Alice (the attacker) controls her own nonce. She can choose to use a different nonce on the second signing request, even if the message is the same.

First signature (on message $m$):

• Alice honestly uses $n_1 = H(m | sk_1)$, sends $N_1 = n_1 \cdot G$
• Bob uses $n_2 = H(m | sk_2)$, sends $N_2 = n_2 \cdot G$
• Public nonce: $N = N_1 + N_2$
• Challenge: $c = H(N | pk | m)$
• Bob's partial signature: $s_2 = n_2 + c \cdot sk_2$

Second signature (on the same message $m$):

• Alice picks a fresh random nonce $n_1'$ (ignoring determinism), sends $N_1' = n_1' \cdot G$
• Bob, being honest, derives the same nonce $n_2 = H(m | sk_2)$ again (determinism!)
• New public nonce: $N' = N_1' + N_2$
• New challenge: $c' = H(N' | pk | m)$ (different because $N' \neq N$)
• Bob's partial signature: $s_2' = n_2 + c' \cdot sk_2$

Alice now has two partial signatures from Bob:

$$s_2 = n_2 + c \cdot sk_2, \quad s_2' = n_2 + c' \cdot sk_2$$

Bob reused $n_2$, but with different challenges. Subtract:

$$s_2 - s_2' = (c - c') \cdot sk_2 \implies sk_2 = \frac{s_2 - s_2'}{c - c'}$$

Alice extracts Bob's secret share. With both $sk_1$ (her own) and $sk_2$ (stolen), she can now sign arbitrary messages unilaterally.

This scenario was also covered in one of Jake Craige's articles.

Theoretic attacks

Most threshold signature schemes are proven secure under static corruption: the adversary chooses which parties to corrupt before the protocol starts. But what about adaptive corruption, where the adversary can corrupt parties at any time, even after seeing public keys, commitments, and partial signatures?

Adaptive security is harder to achieve and harder to prove. A recent paper asks: are widely-deployed threshold Schnorr schemes actually adaptively secure? The answer might be no, if a certain computational problem turns out to be easier than we think.

The Setup

Consider a $(t, n)$ threshold Schnorr scheme where:

1. Public key shares $pk_1, \ldots, pk_n$ are public
2. Keys are derived from a degree-$(t-1)$ polynomial $q(Z) = x_0 + x_1 Z + \cdots + x_{t-1} Z^{t-1}$ over $\mathbb{Z}_p$ (where $p$ is the curve order):

$$pk = g^{q(0)}, \quad pk_i = g^{q(z_i)}$$

where $z_i$ are public evaluation points and $sk_i = q(z_i)$ are the secret shares. 3. Signatures are Schnorr-compatible: verification checks $g^z \stackrel{?}{=} R \cdot pk^c$ where $c = H(R, pk, m)$.

This describes FROST and most modern threshold Schnorr variants.

The Problem

The authors propose a computational problem. If this problem is solvable in polynomial time, adaptive security collapses for the above schemes.

Subset-Span Problem: Given a target vector $\mathbf{v} \in \mathbb{Z}_p^t$ and vectors $\mathbf{k}_1, \ldots, \mathbf{k}_n \in \mathbb{Z}_p^t$, find a subset $F \subset {1, \ldots, n}$ with $|F| = f \leq t-1$ such that $\mathbf{v} \in \text{span}({\mathbf{k}*i}*{i \in F})$ (if one exists).

In other words: can you find a small subset of vectors whose span contains the target?

The Attack

Suppose the adversary wants to forge a signature on a fresh message $m^*$. They need to produce $(R^*, z^*)$ such that $g^{z^*} = R^* \cdot pk^{c^*}$ where $c^* = H(R^*, pk, m^*)$. This requires knowing $\log_g(R^* \cdot pk^{c^*})$, the discrete log of the verification equation's right-hand side.

Here's the plan:

Step 1: Choose $R^*$ carefully

Let $X_i = g^{x_i}$ be the commitments to the polynomial coefficients (note: given $pk_1, \ldots, pk_n$, you can compute $X_0, \ldots, X_{t-1}$ via change of basis). Set:

$$R^* = X_0^{\alpha_0} X_1^{\alpha_1} \cdots X_{t-1}^{\alpha_{t-1}}$$

for random $\alpha_0, \ldots, \alpha_{t-1}$. Since $X_0 = g^{x_0} = g^{q(0)} = pk$, we have:

$$R^* \cdot pk^{c^*} = X_0^{\alpha_0 + c^*} X_1^{\alpha_1} \cdots X_{t-1}^{\alpha_{t-1}}$$

where $c^* = H(R^*, pk, m^*)$ depends on our choice of $R^*$ (and can be computed).

Step 2: Express as a linear combination of public keys

Define vectors:

• $K_0 = (1, 0, 0, \ldots, 0) \in \mathbb{Z}_p^t$
• $K_j = (1, z_j, z_j^2, \ldots, z_j^{t-1}) \in \mathbb{Z}_p^t$ for each party $j$

Note that:

$$X^{K_0} = \prod_{i=0}^{t-1} X_i^{(K_0)*i} = X_0 = pk$$ $$X^{K_j} = \prod*{i=0}^{t-1} X_i^{z_j^i} = g^{\sum_{i=0}^{t-1} x_i z_j^i} = g^{q(z_j)} = pk_j$$

Now, if we can find coefficients $\mu_1, \ldots, \mu_f$ and a subset $F \subset {1, \ldots, n}$ with $|F| = f \leq t-1$ such that:

$$(\alpha_0 + c^*, \alpha_1, \ldots, \alpha_{t-1}) = \sum_{j \in F} \mu_j K_j$$

then:

$$R^* \cdot pk^{c^*} = X^{(\alpha_0 + c^*, \alpha_1, \ldots, \alpha_{t-1})} = X^{\sum_{j \in F} \mu_j K_j} = \prod_{j \in F} (X^{K_j})^{\mu_j} = \prod_{j \in F} pk_j^{\mu_j}$$

Taking discrete logs:

$$\log_g(R^* \cdot pk^{c^*}) = \sum_{j \in F} \mu_j sk_j$$

Step 3: Adaptive corruption

The attacker now adaptively corrupts the parties in $F$, learning their secret shares $sk_j$ for $j \in F$. Since $|F| \leq t-1$ (below the threshold), this is within the corruption budget. They compute:

$$z^* = \sum_{j \in F} \mu_j sk_j$$

and output the forged signature $(R^*, z^*)$. Verification passes by construction.

Why This Might Work

For any fixed subset $F$ of size $f$, the probability that a random target vector $\mathbf{v}$ lies in the span of ${\mathbf{k}*j}*{j \in F}$ is roughly $p^{f-t}$ (very small). But there are $\binom{n}{f}$ possible subsets, exponentially many. If $n$ is large enough , the union bound suggests that some subset $F$ will work with non-negligible probability.

The question is: can we find that subset efficiently? If the problem is solvable in polynomial time, then adaptive security breaks.

The above idea is described in detail in the paper "A Plausible Attack on the Adaptive Security of Threshold Schnorr Signatures".

Closing Thoughts

Implementation bugs are fixable with better testing, stricter validation, and careful reading of security proofs. Protocol issues require understanding what security properties you actually have versus what you think you have. The MtA oracle attack works because the protocol's security argument relied on range proofs that were omitted. The reshare attack works because the protocol lacked synchronization primitives. The adaptive security question for threshold Schnorr shows that even well-analyzed protocols might not hold up under stronger adversarial models.

Threshold schemes remain one of our best tools for distributed trust, but the gap between theory and practice is real and multifaceted. Make sure your implementation and your threat model match what the security proofs actually guarantee.