3
$\begingroup$

The ECDSA standard mandates that during verification we check that an intermediate calculation does not lead to the point-at-infinity (see Step 5. in this summary on Wikipedia ). But why do we check for this? That is, how do you as an attacker actually trigger this event without knowledge of the private key?

In the above I assume that all the other checks of ECDSA are in place ($r,s \in [1,n-1]$, public key is on the curve, and so on...)

$\endgroup$

1 Answer 1

3
$\begingroup$

Indeed, the industry-standard specification of ECDSA has a step (5) requiring to reject the signature if the point at infinity is encountered.

This condition can happen at least

  1. If the holder of the private key generated a suitable (invalid) signature, with $r=-e\,q_u^{-1}\bmod n$ or something on that tune. Granted, that reveals the private key, and (thus) an attacker not holding the private key can't willfully generate such suitable signature.
  2. Accidentally for random input to the signature verification. Granted, probability is so small that is can be discounted, but then good luck to convince some holders of rubber stamp about this.
  3. Due to some software implementation mistake or execution error in 5 or earlier, accidental of by fault injection.

It is found that anything that can go wrong at sea generally does go wrong sooner or later
Alfred Holt, in 1877-78 minutes of the Institution of Civil Engineers, published in London.

and that generalizes well to other human activities, crypto included. During well-administered conformance or security evaluation, the case at hand should even be tested, thru method 1. So something has to be done in this case, and it must not lead to the signature being accepted. Going on undisturbed with the rest of the computation would lead to undefined behavior, because there is no such thing as the x coordinate of the point at infinity. A safe, simple and unobjectionable course of action is to reject the signature and stop.

There is no risk of side-channel leakage (by timing or DPA) under the standard (and usually true) assumption that message, signature and public key are public.

$\endgroup$
4
  • $\begingroup$ You could argue that this is a defense in-depth. It's always somewhat contentious to have to check a value that in principle cannot be wrong with a high degree of certainty, but that assumes a perfect system. $\endgroup$
    – Maarten Bodewes
    Sep 4, 2021 at 15:46
  • $\begingroup$ I still don't have a good understanding of why you would check for an exceptional case that can only happen by chance on invalid data with a probability equal to or smaller than the probability of the attacker guessing a valid signature or gussing the private key. $\endgroup$ Sep 4, 2021 at 18:37
  • $\begingroup$ @R..GitHubSTOPHELPINGICE: what about reason 3? Also what about: it's mandated and testable, thus will be tested, and perhaps we'd rather not have to explain to the man with the rubber stamp that yes that test signature caused some glitch requiring reset because extracting the X coordinate of the point at infinity has caused an exception with the new release of the ECC framework, when the previous one just returned zero; but that was just a test, really, it can't happen on the field; suuuuure let me explain you, it's easy math... $\endgroup$
    – fgrieu
    Sep 4, 2021 at 18:51
  • 1
    $\begingroup$ @fgrieu: I read the question as asking why the standard mandates it, not as asking why an implementor would follow the standard as specified. $\endgroup$ Sep 4, 2021 at 19:50

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.