4
$\begingroup$

I know that when I have a ECDSA keypair and use it twice with the same $k$ to sign different messages then the private key can be recovered.

If I now have multiple ECDSA keypairs and sign a message with each, and use the same $k$ in each signature, is this still secure?

Note: The signed messages may be identical.

I personally see no problem with it and the math seems to support that in my opinion, but better safe then sorry. This is why I'm asking the question.

$\endgroup$
3
$\begingroup$

For ECDSA the per-message secret $k$ should be generated randomly. In particular you have to ensure that the per-message secrets never repeat, or else the private key $d$ can be recovered. First, let's have a look at an example where the same per-message secret $k$ and the same private key $d$ was used to generate ECDSA signatures $(r, s_1)$ and $(r, s_2)$ on two messages $m_1$ and $m_2$. Then $s_1 \equiv k^{-1}(e_1+dr)$ (mod n) and $s_2 \equiv k^{-1}(e_2+dr)$ (mod n), where $e_1 = H(m_1)$ and $e_2 = H(m_2)$. Then $ks_1 \equiv e_1 + dr$ (mod n) and $ks_2 \equiv e_2 +dr$ (mod n). Subtraction gives $k(s_1-s_2) \equiv e_1 - e_2$ (mod n). If $s_1 \not\equiv s_2$ (mod n), which occurs with overwhelming probability, then

\begin{equation} k \equiv (s_1 - s_2)^{-1}(e_1 - e_2)\mod{n}. \end{equation}

From this an adversary can determine $k$, and then use $d=r^{-1}(ks-e)\mod n$ to recover the private key $d$. This implementation failure was used, for example, to extract the signing key used for the PlayStation 3 gaming console or in 2013 to rip users of Android Bitcoin Wallet off their funds.

Now let's have a look at a second example, where the same per-message secret $k$, but different private keys $d_1$ and $d_2$ $(d_1 \neq d_2)$ are used to generate different signatures. In this case the subtraction step from before would lead to $k(s_1-s_2) \equiv e_1-e_2+r(d_1-d_2) \mod n$. From this you are not able to recover the private keys $d_1$ and $d_2$ used to generate the signatures $s_1$ and $s_2$ unless you can efficiently solve the $ECDLP$ (assuming an adequate elliptic curve group was chosen). If you signed the same message, i.e. $m_1=m_2$, then $e_1-e_2$ would cancel out, but this doesn't give the attacker any more advantage as $e_1$ and $e_2$ are supposed to be known anyway.

But be aware that as soon as you’d use the same private-key / message-secret pair to sign another message, this would lead us back to the scenario depicted in the first example. This means that you’d have to be 100 % sure that you only need to sign one single message using the same $k$/$d$-pair. In practice however, you normally don't create a new ECDSA key-pair for every new data you need to sign, as

  • for every new key-pair you create the verifying party will need to learn the new corresponding public key
  • you need to keep track of which key to use for every piece of data you signed if you are both the verifying and signing party
  • using some crypto APIs you sometimes cannot control the per-message secret but only the private key and the signing function will create its own per-message secret making use of the underlying CSRNG
$\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.