Hacker News Reader

Comment by john_alan | Hacker News Reader

2^255 - 19, describes the finite field over which the elliptic curve is defined.

The "keyspace" in the sense of valid public keys is really defined by the order of the curves generator, G, which in this case is approximately 2^252 ish. Due to the curve having a co-factor of 8.

View on HN

So when generating a private key, is any 256 bit random sequence good (it gets reduced down to the 252 bits available) or do you have to check you didn't pick one of the 2^4 keys that aren't valid? (Actually, is 2^4 even the right number? Seems awfully low, and hence I guess, unlikely)

Theoretically, when you generate a Curve25519 key, you're meant to "clamp" it, which premultiplies the key by the cofactor. In practice, you can get away with just taking any random 32-byte string. Clamping (and its practical importance) is a whole big discussion among Curve25519-heads.

other poster described clamping with is right.

But yep, any 256-bit string is good.

This article [0] has a good explanation of why clamping is necessary. But the process is very simple, you just generate 32 random bytes, clear the three least significant bits to avoid small-subgroup attacks, then clear the most significant bit and set the second most significant to avoid side-channel attacks which may occur if an implementation isn’t constant-time. The Libsodium source shows this pretty clearly: [1], lines 18-23.

0: https://www.jcraige.com/an-explainer-on-ed25519-clamping

1: https://github.com/jedisct1/libsodium/blob/master/src/libsod...

I'm not sure clamping has anything to do with constant-time and side-channel attacks.

In very rough terms, not accounting for the cofactor means that there are several related unexpected points for any given Curve25519 key. In theory, these points would allow you to conduct an invalid curve point attack; in practice, you have so few of these points that you leak only a couple bits of key information, unlike with the non-25519-vintage curves, where invalid curve points can leak the entire key over a series of probes. So, for DH systems, people sometimes shrug off clamping.

For Ed25519 and signing systems in general, it's a much bigger deal, because it implies that there are multiple possible validating signatures for a set of inputs, which breaks protocol assumptions.

Hm, with regard to timing attacks, I’m not talking about clearing the cofactor, but rather setting the most significant bit to zero & the second most significant to one. My understanding is that this is to defend against an insecure implementation of the scalar multiplication operation which takes a varying length of time depending on which bit is the first non-zero one, thereby revealing information about the key. The linked article supports this (I believe), but I’m always happy to be corrected about these kinds of things :)

Nope, you're probably right!

I think it is simpler, the algorithm used repeated doubling to find the point on the elliptic curve, so by setting the highest bit to one it ensured that the operation is done to a fixed number of times no matter the input

You’re correct!

I should clarify, not the curves generator, but the generator of the cyclic subgroup of the curve we work in.

Reply on news.ycombinator.com