Goofs that could creep in ECDSA signature verification?

Question

What are goofs that could creep in ECDSA signature verification, perhaps with focus on curves based on prime-order $\mathbb Z_p$, specifically P-256 aka secp256r1? Is it possible to construct test cases for these, and how (perhaps with distinction between various degrees of blackboxness)? How relevant is that in practice (risk of accepting an invalid/forged signature, or rejecting a valid one)?

I'm disregarding as off-topic the ASN.1 formatting checks, and the hashing; and consider that nothing is secret, hence side-channel leakage is a non-issue (the question would be much harder for ECDSA signature generation).

That leaves at least exceptional cases in modular reductions (be it modulo $p$ or modulo the curve's group order $n$); the possibility to hit the point at infinity/neutral element; validating inputs are on the curve, and other input checks.

Answer 1

Checks for $r$ and $s$

You should perform checking on $r$ and $s$ inside your signature verificatioin function. To be more specific you should check that $r$ and $s$ are integers in the interval $[1, n-1]$ as there are known attacks on related ElGamal signature schemes that do not have this check included. This could be a plausible attack on ECDSA if you do not check that $r \neq 0$ (or more generally, $r\not\equiv0 \pmod n$):

Suppose that $A$ is using an elliptic curve $y^2=x^3+ax+b$ over a field $\mathbb{F}_p$, where $b$ is a quadratic residue modulo $p$, and suppose that $A$ is using a base point $G = (0, \sqrt{b})$ of prime order $n$. This might be plausible as some entities might want to select a base point with $0$ $x$-coordinate in order to minimize the size of domain parameters. The adversary can now forge $A$'s signature on any message $m$ of its choice by computing $e=\mathrm{hash}(m)$. You can easily check that $(r=0, s=e)$ is a valid signature for any $m$.

Reduction mod $n$ after reduction mod $p$

During ECDSA signature verification you will have to compute $R=u_1G + u_2Q$. Your elliptic curve operations might be implemented in a way that the multiplication and / or addition will automatically perform a reduction$\mod p$ (order of the prime field). Note however, that you have to reduce the $x$-coordinate again, this time$\mod n$ (order of the generator). For me (and for the testvectors I had used), verification always worked without the reduction$\mod n$, which in my opinion, is the dangerous thing here. There might be curves / testvectors for which verification would fail without this last reduction step. I will implement some more curves (atm I had only used brainpool curves) and will post an update about this.

Answer 2

On top that answer:

Hitting a case where point addition really is point doubling

When computing $R=u\,G+v\,Q$ with $u$ and $v$ on $\ell$ bits as part of ECDSA signature verification, a possible optimization is Shamir's trick, which in it's simplest form does

• $S:=G+Q$
• $R:=1$
• for $j$ from $\ell-1$ down to $0$
  • $R:=R+R$ (point doubling)
  • if $(u_j,v_j)=(1,1)$ then $R:=R+S$ (point addition)
  • else if $(u_j,v_j)=(1,0)$ then $R:=R+G$ (point addition)
  • else if $(u_j,v_j)=(0,1)$ then $R:=R+Q$ (point addition)

The result $R$ is the same, and compared to the straightforward algorithm replaces about $\ell$ point doublings with about $\ell/4$ point additions, which is beneficial.

But a potential problem is, one of the point addition could be a point doubling. This can't happen with regular point multiplication. Thus this has the potential to trigger a rare edge case.

On the other hand, finding such a case by accident is unlikely to the utmost. And, not coincidentally, revealing an example allows to find the private key. Thus this is not much of a practical concern.