4
$\begingroup$

For a given private key $d$, random $k$ and message hash $h$ is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same signature using $\text{secp256k1}$ curve?

$\endgroup$
5
  • 1
    $\begingroup$ Which signature are we talking? Probably ECDSA since you are using Secp256k1. The answer yes, the finding is hard. Simple argument, the signature space is not belong to nobody. $\endgroup$ – kelalaka May 5 at 18:29
  • $\begingroup$ @kelalaka Yeah, I am talking about ECDSA. It would nice if you could give more detailed explanation of why is it possible $\endgroup$ – Yaroslav May 5 at 18:30
  • 5
    $\begingroup$ There's an infinite message space and a finite signature space. Thus there must be an infinite number of instances where the same signature is used. As kelalaka noted, finding them is hard because the signature space, will finite, is vast. $\endgroup$ – Swashbuckler May 5 at 19:00
  • 1
    $\begingroup$ @Swashbuckler, I refer to message hash as its space is also finite. Edited, thx! $\endgroup$ – Yaroslav May 5 at 19:33
  • $\begingroup$ Now the question is how many bits have k and h combined, and how many has the created signature? If k+h > sig then collisions are unavoidable. $\endgroup$ – Peter - Reinstate Monica May 6 at 17:51
5
$\begingroup$

We want $(r,s)$ same for two different set of $d,k,h$

In ECDSA

  • $r = x_0([k]G) \bmod n$ where $k \in [1,n-1]$ and $x_o$ is the x-coordinate of the scalar multiplication $[k]G$
  • $s = k^{-1}\cdot (h+r\cdot d)$ where $h$ is the left most bits of $h$ to fit in the group order ( for simplicity we called it $h$ again).

Now we want same $(r,s)$ for $d,k,h$ and $d',k',h'$

  • $r = x_0([k]G) = x_0([k']G)$ although this may indicate that $k=k'$ it is not. The reason is that the coordinate field $p$ is smaller than the order $n$ of the base point. Therefore we can have solutions other than the trivial.

  • $s = k^{-1}\cdot (h+r\cdot d) = k'^{-1}\cdot (h'+r\cdot d')$,

    then with $k'=k$ we have;

    \begin{align} (d'-d)\cdot r &= (h-h') \\ \end{align}

    then with $k'\neq k$ with $c = k^{-1}$ and $c' = k'^{-1}$ ( for our eyes) we have;

    \begin{align} c'\cdot h + c' \cdot r \cdot d &= c\cdot h' + c \cdot r \cdot d' \\ c'\cdot h -c\cdot h' &= c \cdot c \cdot d' -c' \cdot r \cdot d \\ c'\cdot h -c\cdot h' &= r \cdot ( c \cdot d' -c' \cdot d) \\ \end{align}

As we can see by knowing $r$;

Either

  • we need to find a proper $d'$ for a given $d$ for given different hash values. This is free since we found the private key by just arithmetics.
  • OR, we need to find a message that produces desired hash value $h'$ so that we have equality. This is hard since we need to break pre-image resistance of SHA256.

As we can see it is possible but hard.

For the case $k'\neq k$ the calculations are similar.

$\endgroup$
14
  • $\begingroup$ For easy to understand I've only look the case $k=k'$. Arguments are similar. $\endgroup$ – kelalaka May 5 at 19:03
  • $\begingroup$ Thanks for explanation! The side question was if signature can be used to check message equality and as I can see, omitting hash collision, that there are exists different d, h and k which belongs to the same field and can produce matching signature $\endgroup$ – Yaroslav May 5 at 19:24
  • $\begingroup$ @Yaroslav why do you need a signature to test the quality of the messages? In theory, signature security is not about the security of the messages. It is about forging a signature. As you see that is a hard problem. You need to compare securely see Socialist millionaire problem $\endgroup$ – kelalaka May 5 at 19:35
  • $\begingroup$ The wikipedia article en.wikipedia.org/wiki/… calculates s as 𝑠=π‘˜βˆ’1β‹…(β„Ž+π‘Ÿβ‹…π‘‘) which is different from equation in your answer 𝑠=π‘˜βˆ’1β‹…β„Ž+π‘Ÿβ‹…π‘‘. Are they equal? $\endgroup$ – Yaroslav May 5 at 19:49
  • 1
    $\begingroup$ I think k and k' should be power -1 in your equations for π‘˜β€²β‰ π‘˜ case $\endgroup$ – Yaroslav May 6 at 10:41
4
$\begingroup$

For a given private key $d$, random $k$ and message hash $h$: is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same ECDSA signature using the $\text{secp256k1}$ curve?

Yes, and further it's easy to explicitly compute an alternate $(d',k',h')$ that matches all reasonable meanings of "different set of $d$, $k$ and $h$":

  • different tuples: $(d',k',h')\ne(d,k,h)$
  • pairwise different values: $d'\ne d$, $k'\ne k$, and $h'\ne h$ (which implies the above)
  • different sets: $\{d',k',h'\}\ne\{d,k,h\}$, which is literally what's asked, but rather exotic: order of elements does not matter in sets, thus $\{1,2,3\}=\{2,3,1\}$, and $\{1,1,2\}=\{2,2,1\}$. Also, that set equality has two different possible meanings depending on if we assimilate hashes (like $h$) to integers (like $k$ and $d$) for the purpose of comparison, which is a matter of convention.

"Same signature" means $(r,s)$ is unchanged, that is $r$ and $s$ both are unchanged.

In ECDSA, $r$ is unchanged if and only if $k'=k$ or $k'=n-k$. I settle for $k'=n-k$, which implies $k'\ne k$ because $n$ is odd.

Given the above, $s$ is unchanged if and only $k'^{-1}\,(h'+r\,d')\equiv k^{-1}\,(h+r\,d)\pmod n$. That is $h+h'+r\,(d+d')\equiv0\pmod n$, thus $d'=-d-r^{-1}\,(h+h')\bmod n$.

Thus we only need to

  • compute $r$ the normal way (if it's not a given),
  • select a different $h'$ (overwhelmingly likely, it's enough to hash a different message; otherwise, we retry with another message),
  • compute $k'\gets n-k$ and $d'\gets-d-r^{-1}\,(h+h')\bmod n$.

That insures $(d',k',h')$ yields the same signature $(r,s)$ as $(d,k,h)$ does, with $k'\ne k$ and $h'\ne h$, and overwhelmingly likely $d'\ne d$ (otherwise, we retry with another message/$h'$).

If we do not assimilate bitsrings and integers, $h'\ne h\implies\{d',k',h'\}\ne\{d,k,h\}$. If we do, it's overwhelmingly likely that $h'$ is neither $d'$ nor $k'$ (otherwise, we retry with another message/$h'$).

$\endgroup$
3
  • $\begingroup$ Thanks for the answer! Isn't s equals to 𝑠=π‘˜βˆ’1β‹…(β„Ž+π‘Ÿβ‹…π‘‘)? According to wikipedia en.wikipedia.org/wiki/… $\endgroup$ – Yaroslav May 5 at 20:34
  • $\begingroup$ Based on @kelalaka answer (π‘‘β€²βˆ’π‘‘)β‹…π‘Ÿ=(β„Žβˆ’β„Žβ€²) states that for equal h and h prime for any random k and r respectively there is only one d that can produce the same signature for given h and k, is that right? $\endgroup$ – Yaroslav May 5 at 20:39
  • $\begingroup$ @Yaoslav: Oups, fixed the missing parenthesis and a sign error. My answer differs from kelalaka's because I took $k'=n-k$, because it's unclear what you mean by "different set of $d$, $k$ and $h$", and thus I decided to change as much components of $(d,k,h)$ as possible. $\endgroup$ – fgrieu May 5 at 21:22
2
$\begingroup$

It is totally possible and fairly easy to see without any advanced maths. The curve has order n (n Points in the curve) the private key d is [0... n-1] and the random number k [1... n-1] and there are 2^256 possible values for h. So there are n*(n-1)*2^256 possible inputs (d, k, h combinations). The output is r, s. Where r is there x part of a point so there are definitely not more (actually less) values than there are points on the curve and s is taken mod n, so there are not more than n possible values for that either.

So in total there are around nn2^256 inputs for maximal than n*n signatures. So the pigeonhole principle tells us that there must be multiple inputs that produce the same output.

$\endgroup$
4
  • $\begingroup$ That's a proof of existence for the different tuples reading of the question. It does not work for the pairwise different reading, and I scratch my head at if it can be made to work for the different set wording. $\endgroup$ – fgrieu May 6 at 14:44
  • $\begingroup$ @fgrieu I am not sure if I understand correctly what you mean, but it also works when all d', k' and h' are different from d, k and h. This just reduces each factor by 1. So it does not really reduce the total number of possible inputs that much. $\endgroup$ – jjj May 6 at 15:21
  • $\begingroup$ I mean: take $(r,s)=f(d,k,h)$ with $r$ some unspecified function of $(d,k,h)$ and $s=k$. Then there exists no $d',k',h'$ with $f(d',k',h')=f(d,k,h)$ and pairwise different values: $d'\ne d$, $k'\ne k$, and $h'\ne h$. The pigeonhole principle is not enough for a pairwise different reading of the question. It's more difficult to exhibit a counterexample for the pigeonhole principle in the literal reading of the question: "different set", but I think that's possible. $\endgroup$ – fgrieu May 6 at 15:28
  • $\begingroup$ Ah, ok, yes your right $\endgroup$ – jjj May 6 at 15:37

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.