Is it possible to decrypt an ECDSA private key if the same nonce is used across different private keys?

Question

If the same nonce is used across different messages under the same private key, the private key can be easily revealed.

However, let's consider another scenario.

Two private keys, x1 and x2, are used with the same pair of nonces, k1 and k2. Thus, for each pair of signature (r,s) and hash message h, we get:

$$ s_1=k_1^{-1}(h_1+r_1x_1) \pmod p $$

$$ s_2=k_1^{-1}(h_2+r_1x_2) \pmod p $$

$$ s_3=k_2^{-1}(h_3+r_2x_1) \pmod p $$

$$ s_4=k_2^{-1}(h_4+r_2x_2) \pmod p $$

Therefore, no nonce is used twice by the same private key, but nonces have been reused across different private keys.

Is it possible to retrieve x1 and x2 in this scenario? From what I can observe, the four equations are linearly independent withe each other and consist of four variables. Therefore, there are unique solutions for x1 and x2, right?

Or did I miss something?

SOURCE: This idea was first suggested in this paper: https://link.springer.com/chapter/10.1007/978-3-030-00470-5_29

Answer 1

Is it possible to retrieve $x_1$ and $x_2$ in this scenario?

Yes. We multiply each equation by it's corresponding $k_i$ and reformat, giving $$\begin{array}{rrrrrrr} s_1\,k_1&&-r_1\,x_1&&\equiv&h_1&\pmod p\\ s_2\,k_1&&&-r_1\,x_2&\equiv&h_2&\pmod p\\ &s_3\,k_2&-r_2\,x_1&&\equiv&h_3&\pmod p\\ &s_4\,k_2&&-r_2\,x_2&\equiv&h_4&\pmod p \end{array}$$ and that's a linear system of 4 equations in field $\Bbb Z_p$ with 4 unknowns $k_1$, $k_2$, $x_1$, $x_2$ for one knowing the 4 signatures and (the hash of) their respective messages. It has unique solutions except if $s_1\,s_4\equiv s_2\,s_3\pmod p$, which has no reason to hold, since the $s_i$ are non-zero and randomized at least by their respective $h_i$.

If I got the details right, $$x_1=\frac{h_1\,r_2\,s_2\,s_3-h_2\,r_2\,s_1\,s_3-h_3\,r_1\,s_1\,s_4+h_4\,r_1\,s_1\,s_3}{r_1\,r_2\,(s_1\,s_4-s_2\,s_3)}\bmod p\\ x_2=\frac{h_1\,r_2\,s_2\,s_4-h_2\,r_2\,s_1\,s_4-h_3\,r_1\,s_2\,s_4+h_4\,r_1\,s_2\,s_3}{r_1\,r_2\,(s_2\,s_3-s_1\,s_4)}\bmod p$$ where operations including division are in the multiplicative group $\Bbb Z_p^*$.

Addition: if it happens that $s_2\,s_3\equiv s_1\,s_4\pmod p$, as is the case with the numbers in this other question, it won't be by chance.

---

Michael Brengel and Christian Rossow's Identifying Key Leakage of Bitcoin Users (in proceedings of RAID 2018) is an interesting attack against bitcoin implementations. It gives a good illustration that nonce must be generated with great care in ECDSA (and other DLog-based signature schemes).

A robust and perfectly interoperable option is to deterministically use $k=\text{HMAC}(x,h)\bmod p$ where HMAC uses a hash and output size much wider than $p$ (e.g. SHA-512 and full size output for up to ≈400-bit $p$), $x$ is the private key, and $h$ is the hash of the message as used in the signature production.

If for some reason we want a randomized signature, we can first generate a tentatively true random $d$ then compute $k=\text{HMAC}(x,(h\mathbin\|d))\bmod p$ or $k=(\text{HMAC}(x,h)\oplus d)\bmod p$. This insure that a failure of the true RNG will not reveal the private key.

These three methods to generate $k$ could theoretically give $k=0$ and that should be tested against, but if we encounter this, $r=0$, or $s=0$ in ECDSA signature, the practical line of action should be to declare attack and burninate every data manipulated that won't be an unbearable loss (including the copy of the private key if there is a backup).