13
$\begingroup$

We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as: $s=\frac{H(m)+xr}{k}$

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r}$

$x_1 = x_2 \rightarrow x_1r - x_2r = 0$

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 \ne x_2$:

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} = \frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 - x_2)r}$

If you know either $x_1 - x2$ or $\frac{x_1}{x_2}$ you should be able to compute $k$ as long as $s_1 \ne s_2$.

You can calculate $x_1 - x_2 = \frac{H(m_2) - H(m_1)}{r}$ in case where $s_1 - s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 \ne s_2$ you can compute $\frac{x_1 - x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.

$\endgroup$
  • 1
    $\begingroup$ What happens when you add another signature $s_3$ with the same nonce again? $\endgroup$ – user679128 Jul 5 at 19:50
  • $\begingroup$ I believe this is the same security as the case with just two signatures accept you have a third signature. Do you see something I'm missing? $\endgroup$ – Ethan Heilman Jul 8 at 15:21
  • 1
    $\begingroup$ Your derivation of $k$ when $x_1 = x_2$ is wrong. $s1 - s2 = k^{-1}(H(m_1) - H(m_2))$ which implies $k = \frac{H(m_1) - H(m_2)}{s_1 - s_2}$. See section 2.3 of this paper for clarification. $\endgroup$ – puzzlepalace Jul 19 at 19:42
  • $\begingroup$ Thanks, I got the numerator and denominator reversed. I fixed it above. $\endgroup$ – Ethan Heilman Jul 19 at 20:10
  • $\begingroup$ If this happens, then the second signer (owner of $x_2$) can recalculate $k$ and therefore they can calculate $x_1$ from $s_1$. But it appears that outsiders can't; see Ilmari's post below. $\endgroup$ – Myria Jul 31 at 19:07
3
+500
$\begingroup$

Suppose you have two message signature pairs and following values are then public i.e. known to you -

  • The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$
  • The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$
  • The signatures: $(r_1, s_1)$, ($r_2, s_2$)

The following are unknown -

  • The private keys: $x_1$, $x_2$
  • The nonce: $k$

The following relations are known as well -

  • $s_1 = k^{-1}(H(m_1) + r_1x_1)$
  • $s_2 = k^{-1}(H(m_2) + r_2x_2)$

Note that we have two equations in three unknowns. In order to solve these we'll need to eliminate at least one unknown so that we can write one equation in terms of only one unknown and substitute that into the other equation (resulting in an equation with one unknown which can be solved via basic algebra).

The trick employed when $k$ is used with the same $x$ (i.e. $x_1 = x_2$) is that it eliminate two unknowns ($x_1$ and $x_2$) which yields an equation that is easily solved.

So how do we approach this when $x_1 \ne x_2$? The only way I see is to try to divide $s_1$ by $s_2$ to eliminate $k^{-1}$. Eliminating $x_1$ or $x_2$ seems like it would require index calculus, and that would mean solving ECDLP, which would violate the security assumptions ECDSA is predicated on.

So let's see what $\frac{s_1}{s_2}$ yields -

$$\frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)}$$ $$\frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2}$$ $$\frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1$$ $$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2} = r_1x_1$$ $$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1$$

Note that we can now remove $x_1$ from the equation defining $s_1$ and we are left with a system of two equations in two variables, which can be solved via linear algebra as long as they are not linearly dependent.

(From here on I'll be using $h_n = H(m_n)$ for the sake of brevity)

$$s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2})$$ $$k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2})$$

Then doing some more substitution -

$$s_2 = k^{-1}(h_2 + r_2x_2)$$ $$k = s_2^{-1}(h_2 + r_2x_2)$$ $$s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2)$$ $$s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$ $$s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$ $$(h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2)$$ $$s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2)$$

So we're left with a tautology... why? Because substituting for $x_1$ into the first equation essentially left us with two instances of the same equation, just with some extra terms and terms on different sides of the equation. This means we can't solve the system. Or more precisely, that the system we have has infinitely many solutions. A simple way to see this is to consider a simpler system -

$$x = 2y$$ $$2x = 4y$$

You could substitute for $x$ in the second equation but it won't do you any good.


In conclusion, it would appear that nonce reuse with different key pairs does not allow recovery of any secret material. While far from a full or rigorous proof the above should convince you that it at least does not fall victim to an attack that uses the same approach as the nonce reused with the same key setting. In any case, if you have the choice I would advise to avoid this scenario, there are plenty of good ways to generate nonces out there. RFC 6979 is a good place to start.

$\endgroup$
  • 2
    $\begingroup$ "Eliminating 𝑥1 or 𝑥2 seems like it would require index calculus, and that would mean solving ECDLP". It should be possible to show this via a reduction. $\endgroup$ – Occams_Trimmer Jul 24 at 14:20
  • $\begingroup$ I am awarding the bounty. While this is not a complete answer in that it does not provide a proof of security or insecurity it gets to the heart of the issue and seems plausible. $\endgroup$ – Ethan Heilman Jul 26 at 16:57
0
$\begingroup$

NO! because if you use the same K(random number), then R will be the same for any signature on the same curve: R depends only on KG (G generation point on curve)

Example: we have two signatures (r1,s1), (r2,s2) If K is the same, then the key can be calculated as follows:

  1. r1=r2 (because r=xP modn and P=kG (G generation point on curve) is the same for both signatures).

  2. From the equaition for s: (s1-s2)mod n = K**(-1)(z1-z2) mod n

  3. Multiply by K: K*(s1-s2)mod n = (z1-z2)mod n
  4. Divide by (s1-s2) to get K: k=(z1−z2)*(s1−s2)**(-1)mod n
  5. Get private key X: s=K**(-1)*(z+rX)mod n -> X=R**(-1)*(sK−z)mod n

Example for static K and two various private key:

Please note that for different private keys, resp. different public keys and, most importantly, the first value in the signature (the same R) is the same for different private keys, different public keys and different messages. I cited the algorithm for calculating the key above.

    Curve: secp256k1
    static K: 0x6f347e49ec1b25e50dd9bf56b2d0a7e340ad95bde99ac57fb65815742a0f869f

Private key: 0xc2ca56f311dc91cd15fb6b2a9b66b0579fed1f38a8e6fcbfd721a8c720d8d0d9
Public key(x,y): (0x91d1d4188286f780f879800794ea46b68dcfae941f5a76f7161255cd907443ab, 0x59508303be1539be3a2a73ed7867f6db94374cca8b40ccf1c740829d838fb110)
Message: b'Hello!'
Signature(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x9746c29bcc65fad45ddb533978d5a16cbc22a31ddeb98ba4dde5a5cd2b8922d2)
Verification: signature matches 

Private key1: 0xe61144621e67a5d78be714497bcf3777b18e43580b7b84ce49fcd559532b1062
Public key1(x,y): (0xcef0ce622b51c479f09f726172c8e7c28a6147a9cfa170f4242ee4ed70072f24, 0x3f1c6b2096c1d83fdd567a736ed9f760fcd9c89ed1588f5a4b7bf92a586c0122)
Message: b'I do not understand what is not clear'
Signature1(r,s): (0x760eb603ad708e7306d79f9c4c9f7b82c4720eed8051111c46106c5441899abf, 0x98d6440373ecc23e3a538edd5f12e090fd707852d24660b8f8f68a1cc6e2f691)
Verification: signature matches 

Scrypt python

this script was written by Andrea Corbellini, I just edited it a bit for static K.

P.S. By the way, I recommend reading his article, perhaps there will be additional clarity. (last link)

$\endgroup$
  • $\begingroup$ I believe your answer has an error or I may be reading it incorrectly. $(R_x, R_y)= R = kG$ and $r = R_x$ thus if $k$ is the same in both signatures, $r$ is the same in both signatures. $r$ should not depend in anyway on the secret key $x$. $\endgroup$ – Ethan Heilman Jul 21 at 4:27
  • $\begingroup$ Yes, right, I was wrong. R depends only on this K, and thus it can be concluded that it is impossible to use the same K. $\endgroup$ – vbujym Jul 21 at 11:01
  • $\begingroup$ The question is asking if you don't choose $k$ randomly but instead force $k$ to be the same. $\endgroup$ – Ethan Heilman Jul 22 at 1:56
  • $\begingroup$ I hope I understand you correctly, it is very important that K be as random as possible, its importance is equal to the importance of the private key $\endgroup$ – vbujym Jul 22 at 10:28
  • $\begingroup$ I agree, the question is asking what if $k$ is reused. That is what if we break one of the security critical assumptions of ECDSA ($k$ never being reused) but add a second assumption (different pubkeys on different messages). $\endgroup$ – Ethan Heilman Jul 22 at 21:24

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.