Requirements for attacker-controlled ECDSA identity point signature

Question

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?

Answer 1

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).