Dangers Of Determinism In Threshold Signatures

Common digital signatures schemes like ECDSA, EdDSA and Schnorr require the use of a “nonce”, a number only used once. It’s well known that using it only once is critical to the security of these schemes. Failure to do so results in full private key recovery from two signatures. We’ll use Schnorr signatures for the purposes of this post, but the same concepts apply to others. Here is how private key recovery works.

We first create two signatures $s_1,s_2$ for the key pair $A=xG$ that use the same nonce $r$ for different messages $m_1,m_2$.

$$\begin{array}{rl}R& =rG\\ c_1& =H(R||A||m_1)\\ s_1& =r+c_{1}x\\ c_2& =H(R||A||m_2)\\ s_2& =r+c_{2}x\end{array}$$

Using these two signatures, we can derive an equation to solve for $x$.

$$\begin{array}{rl}{s}_1-s_2& =(r+c_{1}x)-(r+c_{2}x)\\ & =c_{1}x-c_{2}x\\ & =x(c_1-c_2)\\ \frac{s_1-s_2}{c_1-c_2}& =x\end{array}$$

Once the nonces cancel out, we end up with an equation that can be computed using only public information, the signatures and the data required to verify them. There are two ways to fix this:

1. Use a random nonce for every signature
2. Use a “deterministic nonce” like RFC6979

Using a random nonce needs no explanation, so we’ll only review deterministic ones here.

A deterministic nonce is one that is not based on random inputs per signature, but the randomness of your existing private key. It is generated by using a hash function where your secret key $sk$ and the message $m$ being signed are provided as input to create a nonce $r=H(m||sk)$. By using the collision resistance property of the hash function and secret input $sk$, it produces a deterministic result that is different for every message and no one except the private key holder is able to compute it.

This method makes the signature deterministic for a given message and also avoids a class of problems that can happen from having to sample randomness to generate the nonce for each signature. Assuming the hash function is cryptographically secure, this completely solves the problem of accidentally reusing a nonce.

Now we come to threshold signatures… it would make sense to apply the same reasoning here and prefer deterministic nonces, but unfortunately that leads to catastrophic results.

A simple (insecure) 2-of-2 signature scheme

The scheme I describe below is not secure but will serve as a simple way to show what happens when you attempt to use deterministic nonces in a multi-signature scheme.

Assume we have a secure way to generate a public key $A=(d+e)G$ where only Dan knows $d$ and only Eve knows $e$. We now wish to generate a signature where Dan & Eve use deterministic nonces.

First they generate nonces $r_d=H(d||m)$ and $r_e=H(e||m)$ and exchange public nonces $R_d=r_{d}G$ and $R_e=r_{e}G$ such that they each can compute $R=R_d+R_e$ to use when signing.

Next they each compute partial signatures and send them to each other:

$$\begin{array}{rl}c& =H(R||A||m)\\ s_d& =r_d+cd\\ s_e& =r_e+ce\end{array}$$

Each can then add these signatures together to produce a valid signature under the public key $A$ and public nonce $R$:

$$\begin{array}{rl}c& =H(R||A||m)\\ s_d+s_e& =r_d+cd+r_e+ce\\ & =(r_d+r_e)+c(d+e)\end{array}$$

Checking that the verification equation holds is left as an excercise for the reader.

Let’s see what happens when Eve decides to ask for another signature on the same message, but decides to generate a different nonce? We’ll call it $r_e^{\prime }$ and it can be generated in any suitable way, as long as it is different from $r_e$.

By changing her nonce, the public nonce also changes $R^{\prime }=R_d+R_e^{\prime }$. Generating another signature on the same message is done as follows:

$$\begin{array}{rl}{c}^{\prime }& =H(R^{\prime }||A||m)\\ s_d^{\prime }& =r_d+c^{\prime }d\\ s_e^{\prime }& =r_e^{\prime }+c^{\prime }e\end{array}$$

If we look closely, we can see that we’ve just tricked Dan into reusing a nonce with a different $c$ value, $c^{\prime }$. Plugging $s_d$ and $s_d^{\prime }$ into our nonce reuse equation above, we can recover $d$.

$$\begin{array}{rl}{s}_d-s_d^{\prime }& =(r+cd)-(r+c^{\prime }d)\\ & =cd-c^{\prime }d\\ & =d(c-c^{\prime })\\ \frac{s_d-s_d^{\prime }}{c-c^{\prime }}& =d\end{array}$$

Now that we know $d$ and $e$, we can compute the private key of $A$ with $d+e$ and single handedly sign any message without involving Dan using the standard signing algorithm. We have completely broken the 2-of-2 scheme.

Application to Threshold Schemes

This attack can be trivially adapted to threshold schemes and works in the same way. While threshold schemes are parameterized by $(t,n)$ where they are secure as long as no more than $t-1$ parties are compromised, this attack shows that a single malicious party can recover enough key shares to recover the full private key and break the system.

One might ask, what if we provide a proof that the nonce was computed correctly?, that would surely fix this?

Unfortunately no. That just increases the number of malicious parties required to break the scheme. Notice that the break was caused by changing $R$ to $R^{\prime }$, so if there is any way to do this then the same attack applies. How?

Assume a 4-of-5 scheme where parties 1 and 2 are malicious. Parties $1,3,4,5$ honestly compute a signature of message $m$ together, the public nonce is thus $R=(r_1+r_3+r_4+r_5)G$. Now parties $2,3,4,5$ honestly compute a second signature on the message $m$, so the public nonce is $R^{\prime }=(r_2+r_3+r_4+r_5)G$. Notice how this is the exact scenario we created in the 2-of-2 scheme above, individual parties use the same nonce but the aggregated public nonce has changed.

In fact, we can see that the parties don’t even need to be malicious for this to happen! Everyone can behave honestly and just by the fact that different participants signed, a passive observer will be able to recover everyone’s private key shares. Yikes.

Takeaways

The main takeaway I hope people get from this post is that threshold schemes are hard to get right :D. This seemingly innocuous change that is common & recommended in single-party signatures completely breaks the security of the threshold system. Minor changes have significant risks, so be cautious when adapting a protocol on paper to a real world use.

The second takeaway is that while nonce reuse is typically referred to in the context of “using the same nonce for different messages”, these attacks are broader than that. If you can trick someone into changing any of the inputs into the hash function, you trigger the same effect and can recover private keys. So be on the lookout for interesting non-standard ways this might come up in the real world.

If you find any errors in this post or have any questions, reach out to me on Twitter (@jakecraige).