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:

1. Mutual exclusion on the MAC check. A mutex or semaphore prevents two threads from executing overlapping MAC-check instances, including the possible abort path.
2. 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.
3. 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.

 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}

 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}