2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Isn't it the same as Curve25519. It has cofactor 4. One only needs a simple responsibility to avoid the small information leakage. And, it is also twist attack secure. $\endgroup$
    – kelalaka
    Jun 23 at 14:52
  • $\begingroup$ cr.yp.to is down at the moment but I'm sure it'll be back up shortly. In the meantime you can use web.archive.org/web/20210608014309/https://cr.yp.to/… $\endgroup$ Jun 23 at 15:55
  • $\begingroup$ Safecurves also evaluates the Curve448 (goldilocks) curve, so I was wondering if the part on "ladders" and "completeness" would not be of use here. $\endgroup$
    – Maarten Bodewes
    Jun 23 at 16:19
  • $\begingroup$ Also Thomas claims the same Security of elliptic curves $\endgroup$
    – kelalaka
    Jun 23 at 20:24
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Note that this answer is primarily for ECHE $\endgroup$
    – kelalaka
    Jun 23 at 20:56
  • $\begingroup$ Concretely, what are the x-coordinates of points of order 4? (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? $\endgroup$ Jun 24 at 8:08
  • $\begingroup$ @Gilles'SO-stopbeingevil' never seen them, give me little time to calculate them. $\endgroup$
    – kelalaka
    Jun 24 at 17:32
  • $\begingroup$ @Gilles'SO-stopbeingevil' I'm on it.. $\endgroup$
    – kelalaka
    Jul 13 at 8:35

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.