7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Semantic note on the title: "Decrypt" is not used in its usual sense, which is recovering data that was explicitly encrypted. Decipher may be is less specific about intentional encryption, but still does not fit. I propose: ECDSA private key leak if nonce is reused with different private keys. $\endgroup$ – fgrieu Apr 26 at 7:28
  • $\begingroup$ For one nonce shared across two keys, no: crypto.stackexchange.com/questions/46621/… crypto.stackexchange.com/questions/71764/… But sharing two nonces makes the difference $\endgroup$ – dave_thompson_085 Apr 27 at 2:04
5
$\begingroup$

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^*$.


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).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.