How Do MPC Wallets Work?

The goal of a crypto wallet is to keep the user’s coins safe and secure, and MPC wallets are no different. Sometimes, though, the security of these wallets can be compromised when used incorrectly. Let’s dive into the processes of MPC wallets and some real cases where these wallets were attacked.

Multiparty Computation

In the late 1980s, a computer scientist by the name of Andrew Yao proposed a scheme for the first two-party computation scheme. This was dubbed Yao’s Millionaires’ problem since his scheme in a two-person interaction could find out who was richer without revealing their actual wealth.

In traditional cryptography, an individual holds onto a private key while publishing their public key for the whole world. Given the public key, anyone can encrypt a message and send it back such that the individual can decrypt and read the message. The goal of traditional cryptography is to ensure the security and integrity of encrypted messages from eavesdroppers or man-in-the-middle attacks.

Unlike traditional cryptography, multiparty computation (MPC) is for groups of individuals to share information with each other without revealing the actual value of each individual’s private data. It allows users to collaborate on computations with each other without revealing any sensitive information. In math terms, MPC allows a group of people to evaluate a function collectively without sharing each person’s inputs.

Let’s use an example. There are 20 students who have just finished their final exam and have received their scores back. Feeling sorry for the students’ low grades, the professor is willing to give everyone extra credit if they could figure out what the lowest score on the test was without sharing their scores with each other. Wanting to boost their grades, the students would have to evaluate a function like this

$F(a_1, a_2, ... , a_{20}) = min(a_1, a_2, ... , a_{20})$

where a₁,a₂,…,a₂₀ are each of the students’ corresponding test scores. A simple solution to this problem may just be revealing their scores to an outside third party who would look at each test and figure it out quite quickly. However, with none of the students trusting anyone outside of the classroom, they need another way to figure out this problem without an outside party.

Using an MPC protocol, the students would be able to evaluate and learn what the lowest score on the test was. Also, given the output of the function, the 19 other students who did not have the lowest scores would be unable to gain any additional information on which student’s score matched the output of the function.

MPC Wallets Primer

Now that we’re caught up on the basics of MPC, we can start on understanding how it is incorporated into MPC wallets. Crypto wallets come in many different forms↗. The two categories that most crypto wallets fall into are

1. Cold wallets: Cold storage wallets are crypto wallets that store the user’s private key in an offline setting. These types of wallets include hardware wallets or paper wallets. Hardware wallets usually come in a USB-looking drive that plugs into your computer. By storing everything on a physical device, hacking a physical wallet is extremely difficult without hands-on access. On the other hand, paper wallets are physical printouts of a private and public key. The downside to this method is that paper is paper and is susceptible to wear and tear.
2. Hot wallets: Hot wallets are crypto wallets that store the user’s private key online. These types of wallets operate on the internet and include web wallets, desktop wallets, and mobile wallets. All these wallets allow users with an internet connection to access their coins online either through an app or a website. In comparison with cold storage wallets, hot wallets are much easier to send and receive coins given their online status. But this also exposes more attack surface for potential hacks.

MPC wallets↗ differ from these categories, however, since an MPC protocol depends on numerous users. Each person has a copy of their own share of the private key but never the full private key. The private key is never stored in one place. The signature is created when all the users use their own share of the private key to calculate a partial signature on it. By piecing each signature together, a usable copy of the private key signature can be computed. Even then, each person wouldn’t be able to compute the actual private key since each part is held by different users.

Traditionally, a crypto wallet would generate a set of keys (private and public) for every user. This allows a hacker to be able to compromise a wallet by attacking one individual. For MPC wallets, since each wallet holder only has a small share of the full private key, an attacker must compromise a number of key holders greater than the decided threshold of the key.

By spreading out the private key over a large number of wallets, MPC wallets greatly increase the security of storing coins. This also allows users to leave hardware wallets behind since the security of an MPC wallet is good enough and allows for easier coin transferring and payments.

Components of an MPC Wallet

Although a lot of MPC wallets claim to use MPC, most of them today just utilize threshold signatures with multiple parties instead of the full capabilities of general-purpose MPC. An MPC wallet today consists of three main steps↗: key generation, signing, and verification, usually using the elliptic curve digital signature algorithm (ECDSA). Key generation creates the private and public key pairs for the signature. The signing and verifying processes ensure the validity of each transaction in the wallet.

Key Generation

By far the most important step out of the three, this step of key generation must create a public and private key pair for everyone in the party. The private key must also be split up into shares such that each party receives a singular share and does not gain any information about the other shares given to the other people in the party.

In a single ECDSA setting, key generation occurs as follows:

1. Pick a curve $E$ with order $q$.
2. Pick a random generator point $G$.
3. Pick a random number $x$ where $0 < x < q$.
4. Compute $x*G$.
5. Return $(x, x*G)$ where $x$ is the private key and $x*G$ is the public key.

The problem with the single ECDSA setting in an MPC wallet is that it is a single point of failure. If every user has a copy of the private key, each user becomes a single point of failure for the entire protocol. By generating shares of the private key and splitting it among each party in the MPC, each party is no longer a single point of failure.

In a threshold ECDSA setting, the steps are as follows:

1. Two parties use a public curve $E$ with a generator point $G$.
2. Party 1 picks a random number $x_1$ where $0 < x_1 < q$ and computes $Q_1=x_1*G$.
3. Party 2 picks a random number $x_2$ where $0 < x_2 < q$ and computes $Q_2=x_2*G$.
4. Each party will send over $Q_1$ or $Q_2$ to each other such that Party 2 will compute $Q=Q_1*x_2$ and Party 1 will compute $Q=Q_2*x_1$.
5. Both parties should arrive at the same point $Q$ where $Q=x_1*x_2*G$.
6. Party 1 will also generate a Paillier key pair with a modulus N and send an encrypted version of $x_1$, $c_{key} = Enc(x_1)$, with the Paillier public key to Party 2.
7. In the end, Party 1 has a private, public key pair of $(x_1, Q)$ and Party 2 has a private, public key pair of $(x_2,Q \text{ and } c_{key})$.

Why a Paillier key pair? Paillier encryption is used so that operations can be performed on the private key share of another party without revealing the share of the private key. Paillier features both additive and multiplicative homomorphic properties.

The decryption of multiplying two ciphertexts together results in $m_1 + m_2$ where $m_1$ and $m_2$ are the plaintexts for the ciphertexts.

$Dec(Enc(m_1) * Enc(m_2)) = m_1 + m_2$

The decryption of raising a ciphertext to the power of another plaintext will result in $m_1*m_2$ where $m_1$ and $m_2$ are the plaintexts for the ciphertexts.

$Dec(Enc(m_1)^{m_2}) = m_1 * m_2$

Signing

Whenever a user wants to initiate a transaction or another instruction, a signature is created for all other users in the MPC protocol to verify and approve. If the signature is valid, then the instruction is approved. Otherwise, if the signature is invalid, the instruction is not approved and there is something fishy about the user.

Typically, an MPC wallet uses ECDSA for signatures. From the key-generation and key-sharing processes of SSSS, the private key is kept secret and unable to be recovered by an attacker. The ECDSA signature is published for all parties in the MPC protocol, which everyone can verify.

Normally, ECDSA works as follows:

1. Pick a curve $E$.
2. Pick a random generator point $G$.
3. Choose a random nonce, $k$, where $1 < k < q$ and where $q$ is the order of the curve.
4. Compute $r$ = the x-coordinate of $G*k$.
5. Compute $s = k^{-1} * (H(m) + r*x)$ where x is the private key and $H(m)$ is the hash of the message.
6. Output the signature $(r, s)$.

Anyone with the public key can use the values of $r$ and $s$ to validate the signature of the message.

For ECDSA in a threshold setting↗, the parameters are tweaked a little bit. In a two-party ECDSA signature scheme, both parties have the message to be signed and the joint public point on the elliptic curve. The joint public key is created from an elliptic-curve Diffie-Hellman (ECDH) key exchange where both parties compute their own secrets and to obtain a shared point.

Party 2 will also be given the encrypted $x_1$ under a Paillier cryptosystem as $c_{key}$ so that computation can be done with the encrypted version of $x_1$ by Party 2 and decrypted by Party 1. The private key of the Paillier encryption is generated by Party 1 and kept secret. The hash of the message is denoted as $m’$, and the order of the curve is denoted as $q$.

The signing protocol is as follows:

1. Party 1 chooses a random $k_1$, computes $R_1 = k_1*G$, and publishes a ZK proof on the knowledge of $k_1$ along with $R_1$ to Party 2.
2. Party 2 chooses a random $k_2$, computes $R_2 = k_2*G$, and publishes a ZK proof on the knowledge of $k_2$ along with $R_2$ to Party 1.

A ZK proof is required to ensure the $R$ points are calculated from a multiple of the generator $G$ and not a maliciously crafted point.

3. Assuming each proof is verified by the corresponding party, Party 2 computes $R = k_2*R_1 = k_1*k_2*G$ where $r$ is the x-coordinate of $R$.
4. By the homomorphism property of Paillier encryption, Party 2, given $c_{key}$, computes a series of Paillier additions and multiplications.
   • Party 2 uses the public key to compute $c_1=Enc(p*q + k_2^{-1}*m’)$.
   • Party 2 computes $v=k_2^{-1}*r*x_2$ and multiples on $c_{key}$ (encrypted version of $x_1$) to get $c_2$.
   • Party 2 computes a $c_3=c_1+c_2$.
5. Party 2 sends $c_3$ to Party 1.
6. Party 1 computes $R = k_1*R_2$ and extracts $r$ where $r$ is the x-coordinate of $R$. This should result in the same $R$ as in Step 3.
7. Party 1 decrypts $c_3$ to get $s’$ and computes $s = k_1^{-1} * s’$.
8. The signature is then published in the form ($r, s$).

Verification

All parties in the MPC protocol have access to the public key published by the user for the signature. The verification process varies by signature algorithm, but each user can verify the signature individually using the published public key.

For ECDSA, as long as the signature and the message is published, anyone with the public values can verify the validity of the signature. In both the normal and two-party ECDSA protocol, the verification algorithm is the same. The algorithm is as follows:

1. Calculate $H(m)$ with the same hash function from the signing algorithm.
2. Compute $u_1 = H(m)*s^{-1}$.
3. Compute $u_2 = r*s^{-1}$.
4. If the x-coordinate of $G*u_1 + P*u_2 = r$, then the signature is verified. Otherwise, the signature is invalid. In this case, $P = G*x$ where $x$ is the private key used to sign the message.

Attacks & Security

MPC wallets are not always secure, largely due to implementation flaws. Even with MPC protocols proven to be safe, incorrect implementations can lead to vulnerabilities. Let’s check out some real-world examples of how MPC wallets can be exploited. These vulnerabilities are important to know so that they can be avoided in the future.

BitForge

On April 9th, 2023, FireBlocks released what is now called the BitForge↗ vulnerability (CVE-2023-33241). By exploiting small factors in the Paillier modulus, this attack on the GG18, GG20, and Lindell17 MPC protocols affected over 15 of the most popular crypto wallets.

The BitForge vulnerability found that some wallets that use the threshold ECDSA scheme did not provide a ZK proof where $N$ is checked for small factors or that $N$ is biprime during the Paillier key-generation process. Thus, as a corrupt party in the MPC protocol, the generation of the Paillier key could be changed such that $N$ is composed of many small primes. Without a ZK proof on the security of $N$, the receiving party will not notice the insecurity of the corrupted $N$.

For a 2,048-bit Paillier modulus and a 256-bit secret implemented in the GG18 and GG20, the attacking party can construct a modulus such that $N = p_1*p_2*...p_{16}*q$ where $p_1...p_{16}$ are 16-bit primes and $q$ is a large prime, to make $N$ 2,048 bits.

On a high level, by sending these specifically crafted $N$s to the other party for signing, the secret could be extracted in parts. From the signatures received, if the secret was $x$, then the attacker could figure out $x \text{ mod } p_n$ where $p_n$ is one of the sixteen 16-bit primes in the modulus. Using 16 of these “faulty” signatures, the attacker can solve a system of congruences via CRT to reconstruct the secret.

For the actual attack, the vulnerability lay in the oblivious linear evaluation (OLE) part of the GG18/GG20 scheme which, luckily, uses Paillier for encryption and decryption. In OLE, a value $\gamma$ will be taken from Party 1 and the secret $x$ and $\beta$ will be taken from Party 2. The end result of this exchange gives to Party 1 a value $\alpha$ where $\alpha + \beta = \gamma * x \text{ mod } N$. For the exchange,

1. Party 1 (assumed to be trustworthy for now) will send over to Party 2 an encrypted $\gamma$, $Enc(\gamma)$.
2. Party 2, with the Paillier public key and its homomorphic properties, computes $Enc(\gamma*x-\beta)$.
3. This value gets sent back to Party 1 where Party 1 decrypts it with the private Paillier key.

In the malicious setup, without the ZK proof of $N$ being biprime and having large factors, Party 1 can construct the weak $N$. Instead of sending $\gamma$, Party 1 will send $N/p_i$ where $p_i$ is one of the 16-bit primes that make up $N$. Thus, the resulting decrypted value that Party 1 will receive back becomes this:

$\alpha \equiv x * N/p_i - \beta \text{ mod } N$

Since $\beta$ is about 1,024 bits and $N/p_i$ is about 2,000 bits, $\beta$ is very small and can be ignored, and the resulting equation can solve for $x \text{ mod } p_i$:

$x \approx (\alpha - (\alpha \text{ mod } N/p_i))/(N/p_i) \text{ mod } p_i$

By looping through all of the 16-bit primes in $N$, Party 1 can construct a system of congruences with equations in the form $x \approx (\alpha - (\alpha \text{ mod } N/p_i))/(N/p_i) \text{ mod } p_i$_i for all $i$ from 1–16. This system can be solved with CRT to recover the actual 256-bit secret.

Bitcoin Armory SSS

Other than the BitForge vulnerability, there have not been any publicly known critical attacks affecting MPC wallets. However, non-MPC wallets that utilize SSSS for key exchange have been prone to some attacks. Namely, the Bitcoin Armory↗ attack. Bitcoin Armory used to be a popular crypto wallet for storing, as the name suggests, Bitcoin. However, in the SSSS implementation, they repeatedly hashed the actual secret to generate the coefficients of the Lagrange polynomial.

coeff0 = SECRET
coeff1 = Hash(coeff0)
coeff2 = Hash(coeff1)
...
...
coeffn = Hash(coeffn-1)

Even worse, the given shares of each interpolated point were the coefficients of the polynomial. Each user would receive a coefficient (not the secret) and the interpolated function with the coefficient as the value:

share1 = (coeff1, f(coeff1))

Given the share that corresponds to the first coefficient after the secret, the x-coordinate can be hashed multiple times to reconstruct the rest of the coefficients in the polynomial. Then, the secret can be found by interpolating the given point with the known coefficients and thus recover the private key.

Here is the attack implemented in SageMath (assuming SHA-256 as the hash and known degree of polynomial),

from hashlib import sha256
from Crypto.Util.number import long_to_bytes
p = # prime modulus in the sharing scheme for the lagrange polynomial
point = (coeff1,f(coeff1)) # Whatever these values are
coefficients = [point[0]]
for i in range(2): # Degree of secret polynomial - 1

	coefficients.append(int(sha256(long_to_bytes(coefficients[i])).hexdigest(), 16))
P.<x,y> = PolynomialRing(GF(p))
f = x
for i in range(len(coefficients)):

	f += coefficients[i] * y**(i+1)
f = f - point[1]
priv_key = f(x, point[0]).univariate_polynomial().roots()[0][0]
print(priv_key)

Conclusion

While MPC wallets are by far the most secure crypto wallet today, nothing can be completely secure. It is important to keep in mind that no wallets can fully guarantee the security of one’s funds. Incorrect implementations of provenly secure MPC protocols in existing MPC wallets still lead to faulty schemes for attackers to take advantage of.

For a more in-depth guide on building secure MPC protocols, check out Zellic Co-founder Stephen’s blog on building MPC from scratch↗.

About Us

Zellic specializes in securing emerging technologies. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants.

Developers, founders, and investors trust our security assessments to ship quickly, confidently, and without critical vulnerabilities. With our background in real-world offensive security research, we find what others miss.

Contact us↗ for an audit that’s better than the rest. Real audits, not rubber stamps.