Concurrency and State

SPDZ Multi-Threaded MAC Check

What can go wrong. SPDZ (Damgård–Pastro–Smart–Zakarias, 2012) is a maliciously-secure MPC protocol with a dishonest majority, where up to $n-1$ out of $n$ parties can be actively corrupted by an adversary. Shared values are authenticated by an information-theoretic MAC under a global key $\alpha$ that no party knows individually, and openings are verified by a MAC check that aborts if the opened value was tampered with. SPDZ is proven secure in the UC framework, which guarantees security under “concurrent execution” with arbitrary independent protocols. However, this guarantee does not extend to a multithreaded SPDZ implementation, where all threads share the same $\alpha$. In particular, when an implementation runs two MAC check instances concurrently in different threads, a malicious party can cheat in one of them to leak the entire MAC key $\alpha$ and use it in the other to forge MACs on arbitrary values.

Security implication. The paper Rushing at SPDZ: On the Practical Security of Malicious MPC Implementations (IEEE S&P 2025) shows that a malicious party can exploit the multi-thread interleaving to cause one MAC-check thread to abort, leaking the global SPDZ MAC key $\alpha$. The adversary then uses the leaked key to manipulate a concurrent thread of the honest parties, e.g. forging MACs on tampered values at will. The paper analyzed three SPDZ implementations and found two, MP-SPDZ and SCALE-MAMBA, vulnerable to this multi-thread MAC interleaving attack. The example below walks through the patches in MP-SPDZ, one of the two.

How to avoid. Treat the MAC check sub-protocol as an atomic critical section across all threads. Three concrete rules:

Mutual exclusion on the MAC check. A mutex or semaphore prevents two threads from executing overlapping MAC-check instances, including the possible abort path.
Unconditional verification on every open. The MAC check() call must fire whenever secret values are opened, regardless of whether the opened values reach an output gate.
Design-level isolation. Where possible, avoid sharing secret state across threads entirely. Fresco’s design-by-construction single-thread-per-session model is a useful reference point.

Example MP-SPDZ `POpen` and `Commit_And_Open_` race conditions

Two bugs were found and patched in MP-SPDZ.

Bug 1 — Missing MAC check in multi-threaded POpen (commit 5e714b2). The SubProcessor<T>::POpen() function opens secret values. The MAC verification call check() was only triggered by an explicit output-gate condition (inst.get_n()), so in multi-threaded programs, some opened values could be used without the MAC checks needed around the open:

 1// FILE: Processor/Processor.hpp — MP-SPDZ (vulnerable, prior to fix)
 2template <class T>
 3void SubProcessor<T>::POpen(const Instruction& inst)
 4{
 5    if (inst.get_n())
 6        check();    // ← MAC check only before the loop, only if inst.get_n() is truthy
 7    // ... batched open setup ...
 8    for (auto it = reg.begin(); it < reg.end(); it += 2)
 9        for (int i = 0; i < size; i++)
10            C[*it + i] = MC.finalize_open();
11    // ← no MAC check after the loop, even when nthreads > 0
12}

The fix widens the pre-loop gate and adds a new post-loop MAC check with the same gate, so multi-threaded opens trigger both checks:

 1// FILE: Processor/Processor.hpp — MP-SPDZ (fixed, commit 5e714b2)
 2template <class T>
 3void SubProcessor<T>::POpen(const Instruction& inst)
 4{
 5    if (inst.get_n() or BaseMachine::s().nthreads > 0)
 6        check();    // ← gate widened to also fire under multi-threading
 7    // ... batched open setup ...
 8    for (auto it = reg.begin(); it < reg.end(); it += 2)
 9        for (int i = 0; i < size; i++)
10            C[*it + i] = MC.finalize_open();
11    if (inst.get_n() or BaseMachine::s().nthreads > 0)
12        check();    // ← NEW: post-loop MAC check, same gate
13}

Bug 2 — Race condition in Commit_And_Open_ (commit b86f29b). Inside Tools/Subroutines.cpp, a shared coordinator object lets one thread signal to the others that its commitment phase is complete. That signal was raised before the commitment-opening validation loop ran, so a second thread waiting on the coordinator could observe the “finished” state and proceed with values that had not yet been verified:

1// FILE: Tools/Subroutines.cpp — MP-SPDZ (vulnerable)
2
3P.Broadcast_Receive(Open_data);
4coordinator.finished();                    // ← signals completion before verifying
5
6for (int i = 0; i < P.num_players(); i++)
7    if (!Open(datas[i], Comm_data[i], Open_data[i], i))
8        throw invalid_commitment();

The fix moves the signal to after the validation loop:

1// FILE: Tools/Subroutines.cpp — MP-SPDZ (fixed)
2
3P.Broadcast_Receive(Open_data);
4for (int i = 0; i < P.num_players(); i++)
5    if (!Open(datas[i], Comm_data[i], Open_data[i], i))
6        throw invalid_commitment();
7
8coordinator.finished();                    // ← now after verifying

The attack exploits the race by having a malicious party controlling Thread B observe that Thread A’s coordinator has finished and immediately proceed to use the opened values in its own MAC check instance, before A has confirmed those values are authenticated. By carefully timing two concurrent MAC check instances the adversary extracts information about $\alpha$ through the unauthenticated intermediate state, then uses this to forge MACs on arbitrary output values.

Threshold Presignature Reuse (Nonce Reuse)

What can go wrong. ECDSA produces signatures $(r, s)$ where

$s = k^{-1}(H(m) + r \cdot x) \bmod n$

with $k$ a fresh random nonce, $r = (k \cdot G)_x$, and $x$ the long-term signing key. This equation is linear in $x$ once $k$ and $r$ are fixed, so reusing the same $k$ across two different messages $m_1 \ne m_2$ produces a pair $(r, s_1), (r, s_2)$ from which any observer recovers $x$ in closed form: solve $k = (H(m_1) - H(m_2)) \cdot (s_1 - s_2)^{-1} \bmod n$, then $x = (s_1 \cdot k - H(m_1)) \cdot r^{-1} \bmod n$. The canonical real-world incident is the 2010 fail0verflow PlayStation 3 ECDSA break, where Sony reused a fixed nonce across game-code signatures and the master key fell out of two signed binaries.

Some threshold ECDSA protocols such as GG18, GG20, and CGGMP21 generate this nonce distributively as a presignature $(k, R = k \cdot G)$ before the message is known, consuming it once a message arrives. The set of unused presignatures is a stateful object, and implementations must ensure that no two executions consume the same presignature. If they do, two or more signatures share a nonce.

Security implication. When two signatures over different messages share a presignature, anyone who observes them can recover the long-term signing key $x$. In threshold deployments the reuse is both easy to trigger and hard to detect: a malicious party can abort a ceremony after the presignature is fixed and force a retry on a different message, or route two non-interactive signing requests to different honest subsets using the same presignature. Honest parties signing non-interactively have no way to notice that the same nonce is being consumed twice. The Aumasson–Shlomovits Attacking Threshold Wallets paper catalogs presignature reuse as a first-class threshold-wallet threat.

How to avoid. Atomically (across parallel sessions) consume the presignature before starting the signing, and consume it whether or not the signing protocol completed successfully. Upon failure, never retry signing with the same presignature; generate a fresh one. Beware lifecycle events that can resurrect a consumed presignature: backup-and-restore, process restarts, snapshots, and replication must not reintroduce a presignature that has already been used.

Example Blockdaemon Builder Vault warns against 2-of-3 presignature reuse (Builder Vault TSM docs)

Builder Vault is Blockdaemon’s production MPC threshold-signing platform (powered by the Sepior TSM). Its developer documentation explains that each presignature contains shares of a random signing nonce, and that an MPC node enforces single-use by deleting the presignature in the same transaction in which it consumes its share. The docs additionally warn that backup-and-restore can reintroduce a previously-consumed presignature, turning a routine ops procedure into a key-extraction vector if mishandled. Operators are therefore instructed to delete all presignatures either before taking a database backup or upon restoring.

Concurrent Signing Sessions (ROS Attack)

What can go wrong. Many signature schemes rely on linear structures, and when run sequentially they are proven secure: blind Schnorr, for instance, is one-more unforgeable in the sequential setting (Pointcheval–Stern, 2000), and the GJKR threshold Schnorr scheme is proven secure in a stand-alone sequential setting (GJKR07). The reason is that each session finishes before the next one starts, so partial signatures from different sessions can never be combined. Under concurrent execution, though, their security comes to rest on the hardness of the ROS problem (Random inhomogeneities in an Overdetermined Solvable system of linear equations): Schnorr (2001) could establish blind Schnorr’s concurrent security only by reducing it to ROS hardness. And ROS, it turns out, is not hard. Benhamouda et al. gave an efficient algorithm that solves it, letting an attacker forge signatures in exactly these settings.

The shared structure is this. Across $\ell$ concurrent sessions a forger collects nonce commitments $R_i$ and responses $s_i = k_i + c_i x$, then combines them with coefficients $\rho_i$:

$$ R^* = \sum_{i=1}^{\ell} \rho_i R_i, \qquad s^* = \sum_{i=1}^{\ell} \rho_i s_i = \Big(\sum_i \rho_i k_i\Big) + \Big(\sum_i \rho_i c_i\Big) x. $$

The pair $(R^*, s^*)$ is a valid signature on a fresh message $m^*$ exactly when the challenges satisfy the ROS relation

$$\sum_{i=1}^{\ell} \rho_i c_i = c^* = H(R^*, m^*).$$

Sequentially the forger never holds all the $R_i$ at once, so it cannot pick challenges to satisfy this; concurrency is what exposes every $R_i$ before the challenges are fixed and hands it the free variables. The three schemes differ only in who steers the $c_i$:

Blind Schnorr. The signer returns $s_i = k_i + c_i x$ to whatever challenge it is handed, and the requester sends the $c_i$, so it sets them directly to solve the ROS relation.
GJKR threshold Schnorr. The challenge is $c_i = H(R_i, m_i)$ over a jointly generated nonce $R_i = \sum_j R_{i,j}$, and each honest party returns a partial $s_{i,j} = k_{i,j} + c_i \lambda_j x_j$ (with Lagrange coefficient $\lambda_j$ and share $x_j$). A rushing corrupt party chooses its own share $R_{i,n}$ after seeing the honest ones, so it controls every $R_i$, hence every $c_i$, across the concurrent sessions. GJKR’s security proof reached only the non-concurrent setting, or up to a logarithmic number of concurrent sessions, so this high-concurrency path lies outside what it ever guaranteed.
Original FROST. Structurally the same, with a single un-bound nonce $D_{i,j}$ per party and partial $z_{i,j} = d_{i,j} + c_i \lambda_j x_j$. The July 2020 revision closes it by adding a second nonce $E_{i,j}$ and a per-participant binding factor $b_j = H(j, m, B)$ over the whole commitment list $B$, so the group nonce becomes $R_i = \sum_j (D_{i,j} + b_j E_{i,j})$. Every challenge now depends on $B$ through the $b_j$, the $c_i$ can no longer be lined up across sessions, and the ROS relation cannot be set up.

Security implication. Concretely, that algorithm solves ROS over a 256-bit elliptic-curve group with about $\ell = 256$ concurrent sessions in seconds (Benhamouda et al.): the adversary combines the responses it has collected and outputs one signature more than it was granted, breaking one-more unforgeability. The significance varies by primitive. For multi-signatures that claimed concurrent security (the 2018 MuSig, CoSi) it breaks those claims outright; for threshold signatures like GJKR, whose proofs covered only the non-concurrent or bounded-concurrency setting, it contradicts no theorem but rules the scheme out wherever signing happens under load. In a threshold deployment that gap is concrete: unauthorized signatures on attacker-chosen messages, once enough sessions have run concurrently. No public exploit against a deployed implementation has surfaced, but it is worth keeping in mind whenever signing protocols are chosen or composed.

How to avoid. Two complementary approaches.

Structural. Bind each challenge to the session’s specific nonce commitment and message so the adversary cannot freely choose challenges after observing the nonces. FROST achieves this with a per-participant binding factor, standardized in RFC 9591. MuSig2 (Nick et al., CRYPTO 2021) uses two aggregated nonces per session whose specific linear combination is provably secure under concurrent execution.

Application-layer serialization. These schemes are proven secure sequentially, so if the protocol itself cannot be changed, simply run it that way: have the signer complete or abort one session before starting the next. Full serialization is the safe rule, since the polynomial attack needs about $\ell = 256$ open sessions while the sub-exponential variant succeeds with fewer, so capping concurrency at a small bound is not enough.

Mapped Pitfalls