8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 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 May 23 '17 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$ – TrinityTonic May 24 '17 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 May 24 '17 at 13:14

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.