Score:3

Why check for point-at-infinity during ECDSA verification?

kr flag

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...)

Score:3
ng flag

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.

Maarten Bodewes avatar
in flag
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.
R.. GitHub STOP HELPING ICE avatar
cn flag
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.
fgrieu avatar
ng flag
@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...
R.. GitHub STOP HELPING ICE avatar
cn flag
@fgrieu: I read the question as asking why the standard mandates it, not as asking why an implementor would follow the standard as specified.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.