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 leak the global SPDZ MAC key $\alpha$ in one stalled MAC-check thread before the failure is detected. 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 of synchronizing output and MAC-check instructions through a global MAC-check thread is a useful reference point.

Example MP-SPDZ MAC-check leakage under multithreading (Rushing at SPDZ, ePrint 2025/789)

In MP-SPDZ, the concrete synchronization point is Commit_And_Open_, the helper used by the MAC check to commit to local check values and then open them. Before the fix, each thread ran this helper independently. There was no coordinator shared across concurrent MAC checks, so one stalled check did not block another thread using the same global MAC key (source):

 1// FILE: Tools/Subroutines.cpp — MP-SPDZ (vulnerable, before 6a42453)
 2void Commit_And_Open_(vector<octetStream>& datas, const Player& P)
 3{
 4  vector<octetStream> Comm_data(P.num_players());
 5  vector<octetStream> Open_data(P.num_players());
 6
 7  Commit(Comm_data[P.my_num()], Open_data[P.my_num()], datas[P.my_num()],
 8      P.my_num());
 9  P.Broadcast_Receive(Comm_data);
10
11  P.Broadcast_Receive(Open_data);
12
13  for (int i = 0; i < P.num_players(); i++)
14    { if (i != P.my_num())
15        { if (!Open(datas[i], Comm_data[i], Open_data[i], i))
16             { throw invalid_commitment(); }
17        }
18    }
19}

The Rushing at SPDZ paper cites commits 6a42453 and b86f29b as the MP-SPDZ fix. The final version passes a shared Coordinator into Commit_And_Open_, waits before the opening phase, validates every opening, and only then calls coordinator.finished() (source):

 1// FILE: Tools/Subroutines.cpp — MP-SPDZ (fixed, commit b86f29b)
 2void Commit_And_Open_(vector<octetStream>& datas, const Player& P,
 3        Coordinator& coordinator)
 4{
 5  vector<octetStream> Comm_data(P.num_players());
 6  vector<octetStream> Open_data(P.num_players());
 7
 8  Commit(Comm_data[P.my_num()], Open_data[P.my_num()], datas[P.my_num()],
 9      P.my_num());
10  P.Broadcast_Receive(Comm_data);
11
12  coordinator.wait(P.get_id());
13  P.Broadcast_Receive(Open_data);
14
15  for (int i = 0; i < P.num_players(); i++)
16    { if (i != P.my_num())
17        { if (!Open(datas[i], Comm_data[i], Open_data[i], i))
18             { throw invalid_commitment(); }
19        }
20    }
21
22  coordinator.finished();
23}

Holding the coordinator until validation completes serializes the MAC-check opening path: a stalled or invalid MAC check prevents other threads from continuing under the same key.

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 GG20 and CGGMP21 (and, via an offline preprocessing phase, GG18) 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.

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, 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.

List of Pitfalls