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.


2 Answers 2


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.

  • 1
    $\begingroup$ It wouldn't be hard to deliberately create a message/signature/public key that deliberately tickled the $\bmod n$ action; you'd have no idea what the corresponding private key was, but that's not the point of the test... $\endgroup$
    – poncho
    Commented May 23, 2017 at 3:31
  • $\begingroup$ No private information is leaked, as you say. But nevertheless it might invoke a signature verification failure in cases where the signature is okay. $\endgroup$ Commented May 24, 2017 at 11:05
  • $\begingroup$ I believe you misunderstood what I meant; by going through the validation routine and working backwards, you could select a message and a signature where the final $x$ coordinate is $\ge N$ (hence the final point reduction is required), and work backwards to what the public key must be. This isn't the normal way to generate a public key; however it would validate properly (unless the validation routine doesn't do the $\bmod n$ properly), however as it is not the normal public key generation method, we don't know the corresponding private key. $\endgroup$
    – poncho
    Commented May 24, 2017 at 13:14

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.