4
$\begingroup$

On the Wikipedia page of ECDSA, it is stated in step 6 of the verification algorithm that If (x1,y1)=O then the signature is invalid.

In X9.62, it is also stated that If u1G + u2Q is the point at infinity, then reject the signature.

However, I cannot find explicit checking for this condition in multiple open-source libraries.

python-ecdsa for example:

xy = u1 * G + u2 * self.point
v = xy.x() % n
return v == r

Is there any implicit checking that I missed?

And is there any possible attacking against this, if such a verification was missed?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ In python-ecdsa, what is the value of your $v$ when $xy$ is the point at infinity ? $\endgroup$ – Ruggero Feb 25 '19 at 9:54
2
$\begingroup$

A lot of libraries will define the point at infinity as $\mathcal{O} = (0, 1, 0)$ (or as $(0, 1)$ if using affine coordinates). Note that the Wikipedia article you link states:

  1. Verify that $r$ and $s$ are integers in $[1,n-1]$. If not, the signature is invalid.

And a little further down:

  1. The signature is valid if $r\equiv x_1 \pmod{n}$, invalid otherwise.

So if we represent the point of infinity as having an x-coordinate of zero then we see that $r$ can never be equal to $x_1$ as $r$ must be explicitly checked to be in the range $[1, n-1]$ which implies $r > 0$.

python-ecdsa performs the checks from step 1 in lines 132-135. It does not, however, represent $\mathcal{O}$ as mentioned above, but rather sets INFINITY = Point(None, None, None). So If we get xy = INFINITY in the verification call the method will throw an exception as the modulo operator in v = xy.x() % n will be called on None.

It's not clear if this exception is caught or expected by the calling code, but in any case the verification call will not return that the signature is valid when this happens.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ On the short Weierstrass form of any curve, as ECDSA uses, the affine coordinates $(0, 1)$ don't represent the point at infinity; the point at infinity does not have affine coordinates. (This is not to say that your answer is wrong, just that it's not a matter of the definition of the point at infinity so much as a matter of using a kind of extended affine coordinate function that isn't really an affine coordinate function to noninvertibly give arbitrary values for the coordinates to the point at infinity.) $\endgroup$ – Squeamish Ossifrage Feb 25 '19 at 20:33
  • $\begingroup$ The answer is more geared towards what I have seen in the wild regarding ECDSA implementations, not necessarily what is correct. I make no judgement as to what the right way to implement the point at infinity for an ECDSA implementation is. Of course, from a more theoretical standpoint affine coordinates for the point make no sense if we have $(X,Y,Z) \mapsto (X/Z, Y/Z)$, but given that an implementation needs to define it somehow it seems some just drop $Z$ (since they can't divide by 0). $\endgroup$ – puzzlepalace Feb 25 '19 at 21:15

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.