3
$\begingroup$

I've seen many answers here and many articles that says we can recover the private key from reused R signatures. But, what if the r,s signatures are different in transaction of bitcoin then is there a way we could find the ephemeral Key k used in both the cases and find the private key?

$\endgroup$
  • $\begingroup$ The r values of two signatures are equal iff the same k is used. If the same k is used, it's easy to recover the private key, otherwise not so much. $\endgroup$ – SEJPM Mar 26 '18 at 14:38
  • $\begingroup$ @SEJPM I think if we could get 2 different k values then probably we should be able to get the private key from it... $\endgroup$ – Harvy Sam Mar 26 '18 at 15:06
  • $\begingroup$ @HarvySam If you get even one k value, then you can recover the private key... But the point is that the value of k is concealed in the signature and can be deduced only if there is a misuse, like reusing twice the same k value. $\endgroup$ – Lery Mar 26 '18 at 15:17
4
$\begingroup$

In ECDSA, each signature has its own ephemeral key $k$. If $k$ is generated properly, then no amount of signatures will help you recover the private key. "Proper" generation here means either random uniform selection in the proper range, or an appropriate derandomization process such as the one described in RFC 6979.

If the very same $k$ value is used in two signatures, on two distinct messages, but with the same private key $x$, then the private key is revealed. This is the deadly mistake of Sony back in early 2011 (and the initial motivation for RFC 6979, btw). Indeed, if the two messages are $m_1$ and $m_2$, and both values use the same $k$ values, then the two signatures are $(r,s_1)$ and $(r,s_2)$: \begin{eqnarray} s_1 &=& (h(m_1) + xr) / k \\ s_2 &=& (h(m_2) + xr) / k \\ \end{eqnarray} The ephemeral key $k$, and the private key $x$, can then be computed as: \begin{eqnarray} k &=& \frac{h(m_1) - h(m_2)}{s_1 - s_2} \\ x &=& \frac{ks_1 - h(m_1)}{r} \\ \end{eqnarray}

If the values of $k$ are not reused, but are generated with some bias (i.e. not all values in the $[1,q-1]$ range are selected with the same probability), then the private key $x$ can still be recovered from a set of signatures. If for instance $q$ has size 256 bits, but values of $k$ are always lower than $2^{253}$ (i.e. the top three bits are always zero), then a few hundreds of signatures suffice.

If the values of $k$ are generated with a strong, cryptographically secure source, and with no bias, then there is no known attack against ECDSA that would recover the private key $x$, even if many signatures are known. The first reuse of $k$ out of pure back luck is expected to happen after an average of $2^{n/2}$ signatures for an $n$-bit curve, i.e. never in practice if you use a decent curve.

Also, in Bitcoin, people tend not to sign a lot with any given key. For privacy reason, address reuse is discouraged.

$\endgroup$
  • $\begingroup$ You're too fast for a bear! Welp, I still posted my answer since I've worked on it for too long now ;) $\endgroup$ – Lery Mar 26 '18 at 15:42
  • 3
    $\begingroup$ Bears actually run faster than humans. This is true on all terrain conditions, save maybe partially cooled lava, if the human wears protective boots but the bear does not. $\endgroup$ – Thomas Pornin Mar 26 '18 at 15:53
1
$\begingroup$

So, let me recall a few details about ECDSA:

An ECDSA signature is a pair of integers $(r,s)$.

In order to generate a signature for a given message $m$, a given hash function $H$, curve parameters $(\mathcal{C}, G, n)$ for $\mathcal{C}$ a curve, $G$ a base point of prime order $n$ of $\mathcal{C}$, a private key integer $d$ and a public key point $Q = d\times G$, one can:

  1. Compute $e = H(m)$, where $H$ is a cryptographic hash function and let $z$ be the integer representing the leftmost bits of $e$, when $e$ is truncated to the bit length of the group order.
  2. Pick uniformly at random a value $k$ where $0 < k < n-1$ ;
  3. Compute the point $(x, y) = k G$ ;
  4. Compute $r = x\,\bmod\,n$. If $r = 0$, go back to 2 ;
  5. Compute $s = k^{-1}(z + r d_A)\,\bmod\,n$. If $s = 0$, go back to step 2.

Then, when one has signed the message $m$, one can transmit the tuple $(m, r,s)$ and anybody can verify the signature $(r, s)$ by performing the following steps:

  1. Compute $e = H(m)$ and let $z$ be like in the signature process ;
  2. Compute $w = s^{-1}\,\bmod\,n$ ;
  3. Compute $u_1 = zw\,\bmod\,n$ and $u_2 = rw\,\bmod\,n$ ;
  4. Compute the point $(x, y) = u_1 G + u_2 Q$.

If $r \equiv x \mod n$, then the signature is valid, otherwise it is invalid.

Note that ECDSA crucially relies on the uniqueness (just like in the PS3 fail), but also on the entropy used in the choice of $k$, since a bias there can also lead to private key recovery by an attacker having only public signatures at her disposal, see for example this paper [1].

Now, what happens actually when you have re-used twice the same $k$ value?

Let's assume you obtained two signatures for two distinct messages $m_1$ and $m_2$, then you have the two signatures $(r_1,s_1)$ and $(r_2,s_2)$ and the $s$-values are computed as in step 5 above. This means that you can easily recover the value of $k$ by computing:

$$ k = (z_1 - z_2)(s_1-s_2)^{-1} \bmod{n} $$ where we are working with the inverse modulo the order of our curve. From $k$, it is easy also to compute the value of the secret integer $d$, with the help of any of the two signatures: $$ d= (ks-z)r^{-1} \bmod{n} $$ Once this has been done, you can easily check you have recovered the private key by comparing the public key with the value of $d\times G$, since if you have the correct $d$, both will be the same.

Finally, notice that this is true for any instance of ECDSA, not only using Seco256k1.

References

[1] De Mulder, Elke, et al. "Using bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA." International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, 2013.

$\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.