Devious Transfer: Breaking Oblivious Transfer-Based Threshold ECDSA

The research this blog post covers has been conducted by Aviv Frenkel, Dima Kogan, and Ben Riva (Mysten Labs).

Our cryptography team has recently uncovered three critical vulnerabilities in open-source cryptographic libraries. Two of these vulnerabilities result in key extraction attacks on Threshold ECDSA implementations within these libraries. The vulnerabilities were found in implementations of Oblivious Transfer, a simple yet fundamental cryptographic building block for Multi-Party Computation (MPC) protocols.

Threshold signature schemes (TSS) are a key component of MPC wallets, enabling multiple parties to collaboratively generate digital signatures without revealing their key shares. There are two main approaches to constructing threshold signatures for the ECDSA signature scheme:

1. Linearly Homomorphic Encryption (LHE)
2. Oblivious Transfer (OT)

While LHE-based TSS schemes have faced significant attacks recently with BitForge and TSSHOCK, OT-based protocols have gained popularity due to their simplicity and perceived robustness.

Our research suggests that although OT-based TSS implementations show promise, security can still be improved in certain areas.

We found vulnerabilities in the implementation of Oblivious Transfer in each of the following libraries:

• mpecdsa: The reference implementation of DKLs19 by the authors of the protocol. Its implementation of Oblivious Transfer contains a bug that makes the TSS protocol vulnerable to a key-extraction attack by an active adversary.

• sl-crypto: A commercial, professionally-audited implementation of the DKLs23 protocol. Its implementation of Oblivious Transfer contained a bug that made the TSS protocol vulnerable to a key-extraction attack by a passive adversary.

• docknetwork/crypto: A library offering various cryptographic primitives, including an OT implementation that contained a bug where one of the parties inadvertently revealed its secret state.

In this post, we will explain the concept of Oblivious Transfer, discuss two different OT protocols, and highlight the respective vulnerabilities in the implementations of these protocols.

Responsible Disclosure

Upon discovering these vulnerabilities, we promptly informed the maintainers of each library to ensure that they were aware of the issues and could take appropriate action. We provided enough time for the maintainers to release the patches and for users of these libraries to update their systems.

The maintainers of sl-crypto were responsible enough to acknowledge and come back with a patch within two days. They confirmed that none of the users in production were affected.

The maintainers of mpecdsa have acknowledged the issue, and docknetwork/crypto have addressed the vulnerabilities and patched their code accordingly.

Setting the Stage: Oblivious Transfer

Oblivious transfer (OT) was first introduced in 1981 by Rabin, who described it as a two-party protocol allowing one party, the sender, to transfer one of several pieces of information to the other party, the receiver, without the sender knowing which piece the receiver has chosen.

As shown in the figure, the sender has two messages,

$m_0$ and

$m_1$, and the receiver has a choice bit

$c$. At the end of this protocol, the receiver learns the message of his choice,

$m_c$.

The security requirement from this protocol is that the parties learn nothing else - specifically, the receiver doesn’t learn the other message

$m_{1-c}$, and the sender doesn’t learn which message the receiver received.

In its simplest application, OT can be used to evaluate an AND gate securely between two parties. More generally, OT was shown to be sufficient for generic MPC, and among other applications it can be used to construct Threshold ECDSA protocols. In this post we don’t cover the details on how to construct Threshold ECDSA, for further reading, we recommend this linked paper.

In 2015, Chou and Orlandi showed the following Oblivious Transfer protocol, named: The Simplest Protocol for Oblivious Transfer. In this protocol, which builds on the Computational Diffie-Hellman assumption (CDH). The protocol begins similarly to DH, with a cyclic group

$G$ generated by a generator element

$g$. Alice samples some secret,

$a$, and sends her public key,

$A=g^a$. If Bob's choice is 0, he sends

$g^b$ to Alice. Otherwise, he multiplies this value by Alice's public key,

$A$. Alice then encrypts her messages under two different keys; precisely one of those keys computes to

$g^{ab}$, which is computable by Bob, while the other key is

$g^{ab\pm a^2}$ which, assuming CDH is hard, is not computable by Bob. The result is that Bob can decrypt exactly one of Alice’s messages.

A key observation is that Bob's wire messages must be indistinguishable, as otherwise Alice could extract information about his secret choice bit.
As long as

$G$ is a cyclic group,

$b$ is chosen randomly from

${\mathbb{Z}}_q$, and

$A\in G$, both

$g^b$ and

$A\cdot g^b$ distribute uniformly in

$G$ and thus indistinguishable. Notice that for this claim to hold, Bob must verify that Alice’s

$A$ is indeed in

$G$. Depending on the group

$G$, and especially with Elliptic Curve groups, ensuring these elements are indistinguishable can be a subtle task. Which brings us to discuss Elliptic Curve groups and their pitfalls.

As demonstrated in the graph, Elliptic Curve elements are points with

$(x,y)$ coordinates over a finite field, satisfying a specific curve equation of the form

$y^2=x^3+ax+b$. The group operation is defined only for points lying on the curve. Other points are not considered part of the group, so libraries must check the validity of the points before operating on them. Failing to perform such checks is a common pitfall among Elliptic Curve use cases, which have historically led to significant security issues.

The Vulnerability in the mpecdsa Library

Consider the scenario where Bob does not verify the validity of the point

$A$ he receives from Alice. If Alice is malicious and sends an invalid point,

$A$, this would cause Bob’s response to reveal his choice. Specifically, if Bob chooses

$c=0$, his response will be a valid group element. However, if he chooses

$c=1$, his response will involve a group operation on an invalid point, resulting in an invalid point. The result is that Alice can extract Bob's secret choice bit by simply checking whether or not Bob’s response is a valid curve point.

That was the basis of the vulnerability we found in the OT implementation in the mpecdsa library. This library uses OT as the basis for its TSS implementation. The result is that a malicious party, exploiting the vulnerable OT to extract the other party's choice bits, can consequently achieve a complete extraction of their ECDSA key share.

What we presented so far was a simplified version of the actual exploit. The mpecdsa library implements a modified version of the Simplest-OT protocol, which they named Verified Simplest OT (VSOT). The details of the attack on this modified version are more complex and can be found at the end of this post.

Random Oblivious Transfer

We will now discuss a different flavor of OT, known as Random Oblivious Transfer. In this form of OT, the messages are not provided by the sender as inputs but are instead generated as random outputs. This functionality fits protocols that only require the OT messages to be random. Such a relaxed functionality is useful because it can be implemented in just one communication round instead of the three messages needed for the regular OT.

This functionality fits protocols that only require the OT messages to be random. Such a relaxed functionality is useful because it can be implemented in just one communication round instead of the three messages needed for the regular OT.

Here, we show a simplified description of the Masny-Rindal protocol, which implements the Random-OT functionality.Compared to the previous protocol, rather than using the established key to encrypt Alice's message, the established key itself is used as the transferred message. The protocol begins with Bob generating two group elements:

$r,\overline{r}$. They are generated such that

$r$ will produce the transferred message, and

$\overline{r}$ will produce the other message. Bob permutes these elements, so Alice couldn’t tell which one was used for the transferred message. Alice’s computations on

$r$, will result in the transferred message,

$g^{ab}$, and her computations on

$\overline{r}$, will result in the message that Bob cannot compute.

The Vulnerability in the sl-crypto Library

The following vulnerability was found in an implementation of the Masny-Rindal protocol in the sl-crypto library. This library is used in the Silence Laboratories implementation of the DKLs23 protocol.
As we just demonstrated with the previous vulnerability, for Alice not to learn Bob's secret choice bit, Bob must generate the random group element such that it's indistinguishable from an actual public key. For this property to hold, the protocol requires that Bob samples

$\overline{r}$ as a random group element and that the hash function

$H$ outputs are in the group.
For group operations, the sl-crypto implementation utilized the X25519 library, a high-level interface for key exchange over Curve25519, a standard choice when doing DH. Being aware of the potential pitfalls we discussed earlier, one might even gain some assurance from the Wikipedia page of Curve25519:

Nevertheless, there is one pitfall one should be aware of when designing protocols that utilize Curve25519. A known property of Curve25519 is that it has a cofactor of 8, meaning that the group size is

$|E|=8\cdot q$, where

$q$ is a large prime number.

We can think of

$E$ as comprised of a subgroup of size

$q$ (denoted as

$\mathcal{G}$) and another seven cosets of the same size. It's important to note that honestly generated elements are computed as some

$g^x$ and always reside in the prime subgroup. While the 'other' points are valid in that we can operate on them, they remain distinguishable from honestly generated points. This distinguishability is a pitfall that must be considered when designing protocols using Curve25519.

Side note: In some applications, like the X25519 key exchange, all elements are treated as valid public keys, regardless of whether they are in the prime subgroup or not. It uses an operation known as 'cofactor clearing,' which projects elements to the prime subgroup, and all subsequent operations remain confined within this prime subgroup

Back at the protocol. For simplicity, let's assume that the hash function

$H$ returns elements in

$\mathcal{G}$. Consequently,

$r\in \mathcal{G}$. Now let's look at

$\overline{r}$; while the protocol requires that

$\overline{r}$ is sampled from

$\mathcal{G}$, in the sl-crypto implementation

$\overline{r}$ was sampled as random 32-bytes, which makes

$\overline{r}\notin \mathcal{G}$ with a probability of

$7/8$, and thus distinguishable from

$r\in \mathcal{G}$. Checking this property is simple, as

$x\in \mathcal{G}$ if and only if

$x^q=1$ (the identity element). The result is that anyone who sees Bob's message could extract his secret choice bit with a probability of

$7/8$.

This attack is stronger than the previous one as it doesn't require an active malicious party; any passive party seeing Bob's messages could learn his secret bit. In the vulnerable implementation, this protocol is used as a primitive in a DKLs23 implementation, where the parties engage in 256 instances of this OT. This vulnerability is expected to leak

$7/8$ of the 256 receiver’s choice bits, leaving only 32 bits secret, feasible enough for a brute-force attack.

The Vulnerability in the docknetwork/crypto Library

The docknetwork/crypto library is a comprehensive library offering various cryptographic primitives. Among its many features, the library includes an implementation of the Masny-Rindal protocol.

Our research identified that their implementation deviated from the original specification of the protocol. Specifically, the essence of the deviation was that sender’s output messages were a direct function of the messages sent to the receiver, without involving a secret value, as required by the protocol. This introduced a critical vulnerability, where the OT sender inadvertently revealed all their output messages to the receiver.

Takeaways

In light of our findings, two important points need to be emphasized.

Need for Reliable OT Implementations: Given how fundamental oblivious transfer (OT) is as a cryptographic primitive, it is surprising that there is a shortage of reliable and well-audited implementations. To address this, the cryptographic community must come together and foster the development of robust and thoroughly vetted OT protocols.

Risk of Invalid Point Attacks: The risk of invalid curve point attacks is well-known in cryptography. However, this risk has typically been limited to specific use cases with carefully tailored solutions to counter common pitfalls, as seen with X25519. With the rapid development of complex cryptographic protocols, these pitfalls will likely reappear in new contexts. Therefore, renewing awareness of these issues is crucial to ensure robust security across all implementations.

Appendix: The mpecdsa Vulnerability - Full Details

In the “The vulnerability in the mpecdsa library” section, we provided a simplified overview of the attack on the mpecdsa implementation. In reality, the mpecdsa implementation is based on a more sophisticated protocol named VSOT (Verified Simplest OT), and the actual exploit involves additional complexities that were not covered in our initial explanation. In this section, we will give the full details of the VSOT protocol as implemented in mpecdsa, and the actual exploit.

While Simplest-OT is not proven secure in the UC framework, VSOT augments it to achieve UC-security by including the following verifications:

1. Alice sends a Schnorr proof of knowledge of the discrete logarithm of her first message,
   $A$.
2. A verification phase where both parties prove the correctness of their outputs.

The VSOT protocol is summarized in the figure below; notice that this protocol implements a Random-OT functionality.

We previously described an attack where Alice sent an invalid curve point, causing Bob to leak his choice bit. The two additional verifications by Bob pose the following challenges to this exploit:

1. Alice must present a valid Schnorr proof of knowledge of discrete logarithm of
   $A$. Attempting to send invalid curve points is expected to fail this check because non-group elements aren’t generated by the group generator, so by definition, they don’t have a discrete logarithm.
2. Alice must prove to Bob that she knows his output message,
   $m_c$. In the simplified attack, we showed that Alice managed to leak his choice bit,
   $c$, but that doesn’t imply that she is able to compute
   $m_c$.

To pass these two verifications, Alice couldn’t just use any invalid point,

$A$, as it would immediately fail the Schnorr proof. Interestingly, the secp256k1 library used by the mpecdsa implementation admits a special point,

$\mathcal{A}=(1,0)$, with some interesting properties:

1. $\mathcal{A}$ is an invalid curve point
2. The secp256k1 library allows to operate on
   $\mathcal{A}$
3. For every integer
   $t$,
   ${\mathcal{A}}^t\in \{\mathcal{O},Z\}$ where
   $Z=(0,0)$ is some other invalid point and
   $\mathcal{O}$ is the point-at-infinity, the identity element in the group. Both values appear equally often.

While the first two properties are required by the simplified attack, this weird third property will be useful to complete the exploit.

Step 1 - overcoming the Schnorr proof

In a Schnorr proof, Alice proves knowledge of

$a$, the discrete log of

$A$ as follows:

1. Chooses random
   $k\leftarrow {\mathbb{Z}}_q$ and computes
   $R=g^k$
2. Computes a challenge
   $e=f(A,R)$ via the Fiat-Shamir heuristic.
3. Computes
   $z=e\cdot a+k$ and sends
   $R,z$

The verifier who gets

$A,R,z$ verifies the prover’s claim as follows:

1. Computes the challenge
   $e=f(A,R)$
2. Verifies that
   $g^z=A^e\cdot R$

Let’s see that Alice can forge a Schnorr proof for the gadget point,

$\mathcal{A}$. With the special property of

$\mathcal{A}$, for a challenge

$e=f(\mathcal{A},R=g^k)$, there is a probability of

$1/2$ that

${\mathcal{A}}^e=\mathcal{O}$. So Alice is expected to find such a challenge with two attempts on

$k$. Now

$A=\mathcal{A},R=g^k,z=k$ is a valid Schnorr proof, and you can see that indeed

$g^k={\mathcal{A}}^e\cdot R=\mathcal{O}\cdot R=R$.

Step 2 - proving the knowledge of Bob’s message

With Alice passing the Schnorr proof, the attack proceeds like before - with Bob not checking the validity of

$A=\mathcal{A}$, he either sends a valid or an invalid point according to his choice bit

$c$, thus revealing it to Alice.

Alice remains to prove her knowledge of Bob’s output message

$m_c$. But notice that once Alice sends an invalid point as

$A$, the relation

$A^b=g^{ab}$ no longer holds, so Alice can no longer use this relation to compute

$m_c$.

However, recall that weird property of the gadget point, so

$m_c={\mathcal{A}}^b\in \{\mathcal{O},Z\}$. That’s only two options. Even so, she can’t tell which of the two is the actual one computed by Bob.

Luckily for Alice, she can learn the remaining bit from Bob's message as part of the verification phase. Specifically, Alice sends her challenge

$\xi =H(H(\mathcal{O}))\oplus H(H(Z))$, and Bob sends his response as

$H(H(m_c))\oplus c\cdot \xi$. Since Alice already knows

$c$ she can check which value out of

$\{\mathcal{O},Z\}$ matches this expression and sets her

$m_c,m_{1-c}$ accordingly. Now that she has learned

$m_c$, she is now able to pass the last verification step by sending

$H(m_0),H(m_1)$.

This completes the exploit, allowing Alice to leak Bob's choice bit and learn his output message without the protocol aborting.