1
$\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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 at 14:58

1 Answer 1

Reset to default
3
$\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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 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$ Commented Jan 13, 2021 at 20:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.