0
$\begingroup$

I recently began to look into some information about obtaining the private key $k$ when two signatures have been produced using the same $m$ and $k$.

I've been using the well-publicised information about how the Sony PS3 private key was leaked, where:

$$m = \frac{e_1 - e_2}{s_1 - s_2}$$ $$k = \frac{e_1s_2 - e_2s_1}{R(s_1 - s_2)}$$

This has worked well and I've managed to use it to calculate $k$ (private key) in a few situations successfully.

However, I'm confused by what I should do with two different signatures ($e_1 \neq e_2$) with the same $s_1$ and $s_2$, because when I calculate $m$ or $k$ I get:

$$m = \frac{e_1 - e_2}{0}$$ $$k = \frac{e_1s_2 - e_2s_1}{R(0)}$$

Is there a way to calculate $m$ or $k$ in the situation where $s_1 - s_2 = 0$?

Improve this question
$\endgroup$
7
  • $\begingroup$ We assume the $m$ is known, why do you assume unknown? $\endgroup$ – kelalaka Jan 13 at 14:06
  • 2
    $\begingroup$ @kelalaka: he's using nonstandard notation (not that ECDSA has strongly standardized notation); he's using $m$ to designate the secret nonce (more typically labeled $k$) $\endgroup$ – poncho Jan 13 at 14:14
  • 1
    $\begingroup$ Signing produce signatures, not messages. Signing the same message twice is not a security issue. The Sony PS3 private key ($k$ in the question, $d_U$ in the standard description of ECDSA, $d_A$ in wikipedia) was leaked because the ephemeral key (noted $m$ in the question, $k$ in other references) was the same from one signature to another, and different messages have been signed. $\endgroup$ – fgrieu♦ Jan 13 at 14:20
  • $\begingroup$ As pointed by poncho, when we assume $r$ ($R$ in the question) is the same in the two signatures, and $s_1-s_2=0$, no attack is possible. Is it assumed $s_1=s_2$ with $r_1\ne r_2$? $\endgroup$ – fgrieu♦ Jan 13 at 14:47
  • $\begingroup$ @fgrieu In this case, $s_1 = s_2$ and $r_1 = r_2$, which presumably means that I am unable to calculate $m$ or $k$ in this case $\endgroup$ – Martin Jan 13 at 14:58
2
$\begingroup$

However, I'm confused by what I should do with two different messages ($e_1 \ne e_2$) with the same $s_1$ and $s_2$

Well, if we consider how $s$ is computed:

$$s_i = m^{-1} ( \text{hash}(e_i) + r \cdot k )$$

If $s_1 = s_2$, then (because the private key $k$ is the same in both cases, and $m$ (the secret nonce) and $r$ are assumed to be the same, we have $\text{hash}(e_1) = \text{hash}(e_2)$

If $e_1 \ne e_2$, that means that we have a hash collision on our hands; because the signature depends on the hash of the message (and nothing else about the message), that means that (as far as ECDSA is concerned) we're signing the same message twice, and so the attack isn't possible.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for this response. In some cases, I have multiple $e$ signatues. Is there anything further that can be done if I have enough of them given the same $s$, $r$, $k$ and $m$ in each case? $\endgroup$ – Martin Jan 13 at 15:04
  • 1
    $\begingroup$ @Martin: if every signature you have has the same $(r, s)$ pair, then there is nothing you can do; as far as ECDSA is concerned, it's as if each signature were effectively identical, that is, signing the same hashed message $\text{hash}(e_i)$ $\endgroup$ – poncho Jan 13 at 15:36
  • $\begingroup$ @ponco: Thanks again for the reply. I'm confused in this case, because each $e$ is different (i.e. $e_1 \neq e_2 \neq e_3 ...$), but $s$ and $r$ are identical in each case. I know $k$ is the same (but don't know how to calculate it) and I'm presuming that $m$ is identical too $\endgroup$ – Martin Jan 13 at 15:49
  • $\begingroup$ If I know the source for each message signature (so I know both $e$ and the hash of $e$), can this be used to discern $k$ or $m$ where $s_1 - s_2 = 0$? $\endgroup$ – Martin Jan 13 at 19:25
  • 1
    $\begingroup$ @Martin: again, no - if $s_1 - s_2 = 0$, that can only be caused (assuming that $k$ and $m$ are the same) by $\text{hash}(e_1) = \text{hash}(e_2)$, and in that case, you can't learn anything new by the second signature $\endgroup$ – poncho Jan 13 at 20:42

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.