1
$\begingroup$

I have a scenario where $k_2 = -k_1$ while $z_1$ and $z_2$ are identical but the values $s_1$ and $s_2$ are different.

So we have $r_1 = r_2$ and $z_1 = z_2$ but $s_1 \neq s_2$.

Does this mean an attacker can recover my secret key or I am protected?

$\endgroup$
8
  • 2
    $\begingroup$ I don't understand the question. If both $k$ and $z$ are identical then how can the $s$ not be identical? Aren't the nonce and the message the only parameters that can change given a key and domain parameters? $\endgroup$
    – Maarten Bodewes
    Nov 10, 2023 at 2:38
  • $\begingroup$ @MaartenBodewes that happens if other k is negative $\endgroup$ Nov 10, 2023 at 3:14
  • 1
    $\begingroup$ Use deterministic ECDSA $\endgroup$
    – kelalaka
    Nov 10, 2023 at 5:51
  • 1
    $\begingroup$ In your setting, based on the comment above, it isn't true that the same nonce is used for both signatures: k is one and -k is the other. The signatures are (r,s) and (r,-s). Since anyone can construct such a pair of signatures from any valid signature, a way to recover the key for that information would obviously break plain ECDSA. Since ECDSA is as far as we know not broken, you can draw the obvious conclusion. $\endgroup$ Nov 10, 2023 at 10:25
  • 1
    $\begingroup$ @MehdiTibouchi by (r,s) and (r,-s), you mean s1-s2 = 0 then no but I guess I can conclude that I am safe $\endgroup$ Nov 10, 2023 at 10:56

2 Answers 2

1
$\begingroup$

No, ECDSA can not be broken in the situation in the question (which is not quite that in the question's title).

We have two different ECDSA signatures $(r,s_1)$ and $(r,s_2)$ valid for the same truncated message hash $z=z_1=z_2$ and public key. And we are told this is because with $k$ the ephemeral secret in the first signature, the ephemeral secret in the second signature is $n-k$ (which implies the ephemeral points share the same X coordinate, thus that $r$ is identical in both signatures).

With $d$ the private key, it holds $s_1=k^{-1}(z+rd)\bmod n$ and $s_2=(n-k)^{-1}(z+rd)\bmod n$, thus $s_2=n-s_1$. Thus the second signature $(r,s_2)$ brings us no more information than $(r,s_1)$ does. Thus we are just as safe as for normal ECDSA (leaving aside side-channel attacks).

Things would be radically different for $z_1\ne z_2$ and both known (e.g. because the signed messages are distinct and known).


Note: for some curves with $n<p$ including secp256k1 and secp256r1, there mathematically exist valid distinct signatures for the same message and public key sharing $r$ that (contrary to the question) are not using the same $k$ within sign. That can happen because $r$ is the X coordinate reduced modulo $n$, thus we can exhibit two points on the curve that have X coordinates $x_1$ and $x_2$ with $0<x_1<x_2=x_1+n<p$. But I do not see that we can generate two valid signatures using the two points as ephemeral points, a message and a public key making the two signatures valid. I asked there.

$\endgroup$
-1
$\begingroup$

No, an attacker can not recover secret key based on only s1 and s2. In this scenario k2 is equal to -k1 therefore rendering different values for s2 and s1 but since s1+s2 mod n = 0, The attack is impossible but keep in mind that if the values k1 is less that 256 bits then the Most Significant Bits of k2 will be disclosed instantly making lattice attack possible.

Thanks to the comments

$\endgroup$
2
  • $\begingroup$ Next I need to see if an attacker can determine length of k that was used, I will comment here later $\endgroup$ Nov 10, 2023 at 12:38
  • 1
    $\begingroup$ That last sentence needs some kind of proof either as a reference or within the answer itself. $\endgroup$
    – Maarten Bodewes
    Nov 10, 2023 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.