1
$\begingroup$

Wikipedia's description of the ECDSA verification algorithm suggests verifiers should confirm that step 6 doesn't produce the identity point:

Calculate the curve point ${(x_{1},y_{1})=u_{1}G + u_{2}Q_{A}}$ If $(x_{1},y_{1})=O$ then the signature is invalid.

Can a forged signature force this condition? If so, does the entity producing this signature need to know the private scalar for $Q_{A}$? What about forcing this condition for a given message?

$\endgroup$
2
$\begingroup$

The reason for that check is not one of security, but of definition. The verification algorithm entails computing the point $u_1 G + u_2 Q_A$, and use its $x$ coordinate to compare it with the value $r$ (modulo $q$). The "point-at-infinity" (the neutral element on the curve) does not have any coordinate $x$ or $y$, since that point is not part of the plane. Thus, what should happen when a point-at-infinity is obtained is unclear; the rule you cite solves the issue by mandating a signature rejection.

If you remove that rule, then what happens depends a lot on the implementation: rule or not rule, the point-at-infinity still has no coordinates $x$ and $y$. A correct implementation should still refuse to output any value in such a case, and report an error. An incorrect implementation may do... about anything. Including accepting the signature as "valid".

In practice, signature verification is done as:

  • $w = s^{-1} \mod q$
  • $u_1 = h(m) w \mod q$
  • $u_2 = rw \mod q$
  • compute the point $u_1 G + u_2 Q_A$

The values $u_1$ and $u_2$ can be recomputed by anybody. Thus, in order to produce a signature $(r,s)$ such that the point-at-infinity is obtained, one of the two following must hold:

  • $u_1 = u_2 = 0$
  • $u_2 \neq 0$ and $u_1 = -x_A u_2$ (with $x_A$ being the private key)

The second case thus requires knowledge of the private key $x_A$, which is, by definition, unknown to the attacker. And, for the first case, it requires $h(m) = 0 \bmod q$, and simply finding a message $m$ that fits that property is a preimage attack on the hash function, with average cost $O(q)$, thus nominally unfeasible with existing technology.

What might happen with a real-world careless implementation is the following:

  • The computations on curve points are done with projective coordinates. Each point $(x,y)$ is represented by a triplet $(X:Y:Z)$ such that $x = X/Z$ and $y= Y/Z$. This is a classic representation that allows the use of efficient formulas. The point-at-infinity is then represented by $Z = 0$.

  • The inversion of $s$ during verification ($w = s^{-1}$) is done with modular exponentiation ($w = s^{q-2} \bmod q$). This is not the fastest possible inversion algorithm, but it is easier to implement than an extended GCD.

  • The implementer, having obtained the point in projective coordinates $(X:Y:Z)$, instead of computing $x = X/Z$ and then comparing it with $r$, finds it smart to check that $X = Zr$, which avoids an inversion.

Under these three conditions, the "signature" $(r,s) = (0,0)$ will be accepted as valid, systematically, for all public keys and all messages! Note that this entails an implementation that gets it wrong twice:

  1. the implementation gleefully computes $1/s$ for $s = 0$ (and obtains $0$);
  2. the verification on the final $x$ is done without checking that the point is not, indeed, the point-at-infinity.

It is an unfortunate fact that such implementations have existed (I won't give names).

$\endgroup$
  • $\begingroup$ Checking $0 < r,s < q$ should be the first step of the signature verification and will avoid all these attacks. The case $u_1=-x_Au_2$ requires (or will give away) the private key so no need to avoid it. Not mentioned in the answer, but it could happen, is the fact that an error in the implementation of the double base ladder could lead to the point at infinity. $\endgroup$ – Ruggero Mar 19 '18 at 10:26

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.