Score:2

How do I validate Curve448 public keys?

cn flag

Performing an ECDH calculation with an invalid public key can leak information about your own private key. With Weierstrass curves, it's important to verify that the peer's public key is actually a point on the curve, and not the point at infinity. (See “Validation of Elliptic Curve Public Keys” by Antipa et al. §3, also Why do public keys need to be validated?).

With Curve25519, all 32-byte strings are valid public keys for ECDH. However a few values must be rejected in protocols that want to ensure contributory behavior. “May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519” by Genkin et al. also recommends rejecting these points to avoid a timing side channel in mostly-but-not-completely-constant-time implementations.

What about Curve448? Do Curve448 public keys need to be validated or is any 56-byte string valid? The original paper and RFC 7748 do not mention any such need, but maybe there is newer wisdom on the topic.

kelalaka avatar
in flag
Isn't it the same as [Curve25519](https://crypto.stackexchange.com/a/87711/18298). It has cofactor 4. One only needs a simple responsibility to avoid the small information leakage. And, it is also twist attack secure.
Gilles 'SO- stop being evil' avatar
cn flag
cr.yp.to is down at the moment but I'm sure it'll be back up shortly. In the meantime you can use https://web.archive.org/web/20210608014309/https://cr.yp.to/ecdh.html#validate
Maarten Bodewes avatar
in flag
Safecurves also evaluates the Curve448 (goldilocks) curve, so I was wondering if the part on "ladders" and "completeness" would not be of use here.
kelalaka avatar
in flag
Also Thomas claims the same [Security of elliptic curves](https://crypto.stackexchange.com/q/44337/18298)
Score:2
in flag

The Curve448

Curve448 is an Edward curve that has defined over a Solinas prime $p = 2^{448} − 2^{224} − 1$ with the equation $$x^2+y^2 = 1-39081x^2y^2$$

Base Point

The basepoint $G$ of Curve448 has prime order as Curve25519. It has cofactor $h=4$ this mean that $$h = \dfrac{|\#E|}{ord(G)}$$ The order of $G$ is $$\small ord(G) = 2^{446} - 13818066809895115352007386748515426880336692474882178609894547503885$$

ECDH

Now turn to ECDH in which Alice has a private key (integer) $k_A$ and public key $[k_A]G$ (a point on the curve) and Bob has a private key $k_B$ and the public key is $[k_B]G$.

When Alice and Bob exchange the public keys what does happen ( don't consider the man in the middle)? The below;

$$[k_A k_B]G$$

So, as long as the basepoint is correct, any 56-byte values from a valid public key. There is no need for validation since we have

$$[k_A]G = [k_A \bmod \operatorname{ord}(G)]G$$

$$[k_A k_B]G = [k_A k_B \bmod \operatorname{ord}(G)]G$$

We will not consider the never-gonna-happen event of two users will have the same private key.

Small-Subgroup attack

What about Bob executes a small subgroup attack (Lim–Lee active small-subgroup attacks)?

In the small subgroup attack, the attacker Bob chooses a small order $P$ as the public point where the discrete logarithm is easy. During the protocol, the legitimate user Alice will reveal $[k_A]P$ to the attacker. Now, how much information can the attacker learn about $k_A$ from $[K_A]P$?

  • The answer is given as information revealed by $[K_A]P$ is at most $\lceil log_2 h\rceil$ bits.

Since the cofactor is 4, one will only reveal at most two bits of the private key. If you fear that losing 2 bit from 224 is dangerous then validate that the $P$ don't have order 2 or 4 by checking $[4]P \overset{?}{=}\mathcal{O}$

Twist Security

Curve448's twist has $4$ as a cofactor, so it has secure twist, too.


Note: in this article Optimized Architectures for Elliptic Curve Cryptography over Curve448 mentioned that

Moreover, public keys of Curve448 are reasonably short and do not require validation as long as the resulting shared secret is not zero

and Mike Hamburg was aware of this article before publish since in the Acknowledgment

Also, we thank Mike Hamburg for his constructive comments

kelalaka avatar
in flag
Note that this answer is primarily for ECHE
Gilles 'SO- stop being evil' avatar
cn flag
Concretely, what are the x-coordinates of points of order 4? (https://cr.yp.to/ecdh.html#validate lists 12 values for Curve25519, which correspond to 5 x-coordinates after reduction mod $P$). And what about the May the Fourth side channel — are the risky cases the low-order points for Curve448 as well?
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' never seen them, give me little time to calculate them.
kelalaka avatar
in flag
@Gilles'SO-stopbeingevil' I'm on it..
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.