3
$\begingroup$

From Wikipedia:

  • Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are otherwise valid.
  • Check that $Q_a$ lies on the curve.
  • Check that $n*Q_a = O$
  • Verify that $r$ and $s$ are integers in $[\![1;n-1]\!]$. If not, the signature is invalid.

What is the mathematical reason for these checks and what can an attacker do if these checks are not carried out properly?

$\endgroup$
2
  • 1
    $\begingroup$ first 3 is to make sure that we are working in the correct setup. 4th for preventing simple forgeries by sending $r+n$ and $s+n$ instead of $r$ and $s$ $\endgroup$
    – kelalaka
    Sep 17 '19 at 22:17
  • $\begingroup$ @kelalaka could you explain this in more detail? $\endgroup$ Sep 18 '19 at 6:02
6
$\begingroup$

The original paper (Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA), International Journal of Information Security volume 1, 2001, pp. 36–63) is surprisingly quiet about the rationale for all of these.

  • Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are otherwise valid.

If $Q_a=O$, then the step $(x_1,y_1)=u_1\times G+u_2\times Q_a$ turns into $(x_1,y_1)=u_1\times G$ because the identity element multiplied with anything ends up being the identity element – the same as normal math ($0\cdot a=0$).

Let's start with the verification equation and roll it back with the assumption that $Q_a=O$. As a reminder, the signature is $(r, s)$. The signature is valid if and only if $r \equiv x_1 \pmod{n}$.

$(x_1, \_) = u_1\times G+u_2\times Q_a = u_1 \times G + O= u_1 \times G$, where $u_1 = zs^{-1} \mod{n}$.

An attacker trying to forge a signature for a new message has control over:

  1. $z$ is a trimmed hash of the message. The attacker can compute this.
  2. $(r, s)$ are signature parameters and thus provided by the attacker along with the message.

Because $Q_a$ is gone from the picture, the part that effectively binds the private key into the signature, a valid signature becomes trivial:

  1. Compute $z$.
  2. Pick any $s$ at random in the range $0 < s < n$.
  3. Compute $u_1 = zs^{-1} \mod{n}$.
  4. Compute $(r, y_1) = u_1\times G$.

Because the verifier skips verification that $Q_a \ne O$, this checks out.

(Note that this requires a way for the attacker to supply a public key $Q_a$. In many cases, the public key is pre-shared or otherwise hard-coded so this issue rarely arises in practice. Often, there may not even be a way for an attacker to force $Q_a=O$ if there's no accepted bit representation of $O$ depending on the implementation.)

  • Check that $Q_a$ lies on the curve.
  • Check that $n*Q_a = O$

If $Q_a$ is not on the curve or has an order that does not equal the expected $n$ for the curve, it may lie on another curve $E'$, chosen by the attacker; $E'$ would typically be a curve that has a small order and then use the Chinese remainder theorem to discover information about the private key in Diffie–Hellman settings.

This can be abused in the context of a certificate authority (CA) using ECDSA as a proof of possession of the private key for $Q_a$ when $Q_a$ is not validated (adapted from Adrian Antipa et al. Validation of Elliptic Curve Public Keys, section 4.3), though this is all in the context of ECMQV and thus a special case:

  1. Select two values for $s$ and $u_2$ between $1$ and $n-1$ inclusive.
  2. Compute $z$ and $u_1$ for ECDSA as normal; the message for $z$ may be chosen by the CA.
  3. Compute $T_1=u_1\times G$ on curve $E$.
  4. Compute $T_2=u_2\times Q_a$ on curve $E'$.
  5. Compute $V=T_1+T_2$ using point addition as if both points were on curve $E$; the result will be on neither curve.
  6. Set $r$ to the x-coordinate of $V$.
  7. Compute $u_2'=rs^{-1}\mod{l}$, where $l$ is the order of a point with small, prime order on $E'$ that contains $Q_a$.
  8. Repeat this procedure unless $u_2\equiv u_2'$
  9. Output the signature $(r,s)$.
  • Verify that $r$ and $s$ are integers in $[\![1;n-1]\!]$. If not, the signature is invalid.

The original paper by Johnson et al. notes on p. 48 that (a) this mitigates attacks related to ElGamal signatures without such checks, and (b) the check that $r>0$ in particular avoids an issue specifically relating to a base point $G=(0,\sqrt{b})$ (with $b$ from the short Weierstrass curve parameter for $E$: $y^2=x^3+ax+b$), though I am unaware of any elliptic curve standard specifying a base point with an x-coordinate of zero.

This also helps prevent malleability so that given an existing $(r, s)$ and existing message $m$, no new signature for the same $m$ can be made without possession of the private key. The group generated by the generator $G$ is a cyclic group of order $n$, which means that the cycle repeats after $n$ additions of $G$ to itself: $n\times G=O$, $(n+1)\times G=G$, …, therefore for every $(r, s)$, the tuple $(r + cn, r + cn)$ is also a valid signature for the same message for every integer $c>1$. Note that $(r, -s\mod{n})$ is already another valid signature that may need to be guarded against as well.

$\endgroup$

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.