Pitfall

Randomness Has Insufficient Entropy

What can go wrong. MPC protocols rely on high-entropy sources for nonces, masks, and blinding factors, and their output must be fresh for each use. A low-entropy source, one that repeats or is predictable, lets an attacker recover any secret that depends on it.

Security implication. Any part of the system that relies on a low-entropy source lets even an honest-but-curious adversary brute-force it and recover the secrets, if any, after one or a few observations. In Schnorr signatures, reusing the nonce $r$ across two messages exposes the signing key: with $s_1 = r + c_1 x$ and $s_2 = r + c_2 x$, the key is $x = (s_1 - s_2)(c_1 - c_2)^{-1}$.

How to avoid. Draw all protocol randomness from a cryptographically secure RNG with at least a 128-bit security level, and never reuse it across runs. For deterministic nonces, follow the construction in RFC 6979.

Example MP-SPDZ FKOS15 randomize_blocks (99c5efc)

FKOS15 is the MPC-with-preprocessing protocol underlying MASCOT and SPDZ2k. Party inputs are masked with preprocessed correlated randomness; the security argument requires that mask to carry the full claimed statistical-security parameter of entropy.

In MP-SPDZ pre-fix, Tools/BitVector.h::randomize_blocks produced under-randomized masks for single-bit input types: the loop drove tmp.randomize(G) once per T-sized block, but for a 1-bit T that path did not place fresh PRG output across every byte of the underlying buffer (source):

 1// Tools/BitVector.h — data61/MP-SPDZ (vulnerable, pre-99c5efc)
 2template<class T>
 3inline void BitVector::randomize_blocks(PRNG& G)
 4{
 5    T tmp;
 6    for (size_t i = 0; i < (nbytes / T::size()); i++)
 7    {
 8        tmp.randomize(G);                            // biased for 1-bit T
 9        memcpy(bytes + i * T::size(), tmp.get_ptr(), T::size());
10    }
11}

A malicious party who observes the masked input transcript can narrow the search space for the honest party’s bit-input by exploiting the mask’s reduced effective entropy: the soundness of FKOS15’s input authentication assumed the mask hid the input information-theoretically up to $2^{-s}$, but the under-randomized mask collapsed that guarantee to a smaller margin.

The fix special-cases the 1-bit case to fill the buffer directly from the PRG, so the mask gets full per-bit entropy rather than the under-populated bits the original loop produced (source):

 1// Tools/BitVector.h — data61/MP-SPDZ (fixed, 99c5efc)
 2template<class T>
 3inline void BitVector::randomize_blocks(PRNG& G)
 4{
 5    if (T::size_in_bits() == 1)
 6    {
 7        G.get_octets(bytes, nbytes);                 // raw PRG output
 8    }
 9    else
10    {
11        T tmp;
12        for (size_t i = 0; i < (nbytes / T::size()); i++)
13        {
14            tmp.randomize(G);
15            memcpy(bytes + i * T::size(), tmp.get_ptr(), T::size());
16        }
17    }
18}