Smooth or Non-Biprime Paillier Modulus

What can go wrong. The Paillier cryptosystem relies on a biprime modulus $N = pq$ where $p$ and $q$ are large primes, often required to be safe primes, $p = 2p' + 1$ with $p'$ prime. When parties in an MPC protocol publish their own modulus, skipping biprimality checks lets a malicious sender pick a structured $N$ that enables key-recovery attacks against the protocols that use it.

Security implication. The BitForge attack refers to a collection of zero-day vulnerabilities discovered by Fireblocks researchers that impact MPC wallets. Part of these vulnerability involves skipping the biprimality and no-small-factor checks on the Paillier modulus in the GG18 & GG20 protocols, which led to a vulnerability on the shared key (CVE-2023-33241, technical report). The attacker chooses $N_A = p_1 \cdots p_{16} \cdot q$ with each $p_i \approx 2^{16}$ (small enough to brute-force the range proof), then crafts an out-of-range plaintext $k = N_A / p_i$ in each MtA call and forges the range proof by brute-forcing a blinding factor in about $p_i \approx 2^{16}$ attempts. The victim’s encrypted share leaks $x \bmod p_i$ per signing session; after 16 sessions, CRT reconstructs the full $x$.

How to avoid. Require every party publishing a Paillier key to accompany it with two ZK proofs from CGGMP21: a Paillier-Blum Modulus proof, which proves $N = pq$ for primes $p \equiv q \equiv 3 \pmod 4$, and a No-Small-Factor proof, which rules out small prime factors (formally $p, q > \sqrt{N}/2^{\ell}$ with $\ell = 256$, i.e. no factor below about $2^{256}$). Some deployments additionally require $p$ and $q$ to be safe primes ($p = 2p' + 1$ with $p'$ prime). Reject the participant if either proof fails to verify, before the modulus is stored anywhere.

1// FILE: src/multi-party-ecdsa/gg18/key_gen/round3.cpp
2// Safeheron/multi-party-ecdsa-cpp @ b75d125f (pre-fix, vulnerable)
3ok = bc_message_arr_[pos].pail_proof_.Verify(
4    sign_key.remote_parties_[pos].pail_pub_,
5    sign_key.remote_parties_[pos].index_,
6    bc_message_arr_[pos].dlog_proof_x_.pk_.x(),
7    bc_message_arr_[pos].dlog_proof_x_.pk_.y());