Score:2

Why must ECDSA verification ensure the point is on the curve?

kp flag
Joe

In ECDSA, when parsing the public key a test is made to ensure the public key really lies on the curve. What vulnerabilities appear if one does not do this?

DannyNiu avatar
vu flag
https://safecurves.cr.yp.to/twist.html Maybe you just didn't know the keywords?
fgrieu avatar
ng flag
@DannyNiu: I see why this link deals with reasons to check DH ephemeral keys, not ECDSA public keys.
Score:3
ng flag

From the theoretical standpoint of making ECDSA signature un-forgeable (including Existentially Un-Forgeable under Chosen Message Attack), it's not necessary to check that the public key is on the curve†: it's an assumption in the EUF-CMA experiment that the public key has been generated per the genuine key generation algorithm, which only outputs points on the curve.

From a practical standpoint, the interest of such check is limited by the fact that an adversary able to alter or set the public key as they desire can put another public key with a matching private key they know, which the check won't catch, and which then allows to circumvent the purpose of signing.

Depending on the format of the public key, the check would catch a random alteration with near certainty (for key in uncompressed format, where the verification checks the curve's equation is matches by $x$ and $y$ coordinates), or moderate probability (for key in compressed format, where it's checked that an $y$ exists matching the $x$ in the public key, which has probability near 50% for many common curves).

The reasons I see to make such check (which is common) are

  • It is an assumption on the inputs of signature verification that the public key is a valid curve point, and the check can catch a mistake or malfunction affecting that input before it causes undefined behavior in the signature verification code; and that check is relatively cheap (for uncompressed keys) or not too expensive (for compressed keys) compared to the whole signature verification process.
  • Making the check makes it easy for the verifier‡ to repel an argument on the tune of "but you did not perform the point-on-curve check suggested/mandated in [some reference]", or "but you verify that signature against a public key that's invalid in the first place!" (however that's not effective against the more general argument "but you verify my/their signature against a public key that's not mine/theirs!").
  • To better resist fault attacks against implementations. It's conceivable that an altered public key as in a verification device submitted to deliberate fault attack would cause the computation of $R$ at step 5 in ECDSA verification to output a value independent of the altered public key (or one of few such values), thus making $R$ essentially independent of the component $r$ of the signature or otherwise predictable, which would make it easy to craft a signature that passes verification. Details would depend heavily on how this computation is made, and there are many ways.
  • UPDATE: As rightly pointed in comment, substituting a legitimate public key with one fake that makes all messages/signature pairs verify could be of use to some attackers. Mechanisms by which an invalid key could lead to such a universal "pass" at verification may depend on the curve, on the method used for point arithmetic, and on other details in the verification code. Although I don't see how that could reasonably happen for ECDSA, a check that the point is on the curve is sure to prevent that for standard curves in a prime field (which cofactor $h=1$), and the full check does for all curves.

That check is required for the verifying entity by the de-facto ECDSA standard, but can be indirect, e.g. because it's assumed to have been made by a certification authority, and needs only to be performed once. The rationale given for the check is:

either to prevent malicious insertion of an invalid public key to enable attacks like small subgroup attacks, or to detect inadvertent coding or transmission errors.

Small subgroup attacks are primarily a concern for ECDH. In ECDSA, they are no worse than insertion of a valid public key of the attacker's choice, which again seems about as easy, and less detectable.


† ECDSA actually assumes that the public key is a (non-neutral) member of the group generated by the base point. For standard curves in a prime field most used by ECDSA, "generated by the base point" is equivalent to "on the curve", since cofactor $h=1$. I discuss mostly the "on the curve" criteria, since that's what the question asks. The whole discussion largely applies to both criteria, except for the cost of testing "generated by the base point" on curves with cofactor $h>1$.

‡ Including a certification authority verifying a Certification Signing Request

Joe avatar
kp flag
Joe
What if, for some application, the adversary could insert a public key (or rather, a somewhat random string that is just parsed as a point even if not on the curve) but which the adversary does not know the corresponding private key (indeed it would not exist if it's not on the curve, right?)? Is the answer "maybe fault attacks but this is complex"?
fgrieu avatar
ng flag
@Joe: it could allow generation of messages which signature verify. It's not so much that it's complicated: it's heavily implementation-dependent. I see fault attacks as a way to replace the public key by a somewhat random string.
id flag
Some attack scenarios involve someone who has trusted access to something rigging it to allow access to associates. If an adversary with access to modify a public key used for verification were to change it to something for which the attacker knew the private key, attempts to authenticate by the holder of the private key for the legitimate public key would be rejected, thus calling attention to the alteration. If, however, it were possible to write a bogus key which would treat *all* requests for verification as successful, that alternation might manage to escape notice.
I sit in a Tesla and translated this thread with Ai:

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.