Note: this post assumes some familiarity with elliptic curve cryptography (ECC). There are numerous tutorials online, such as this one.
If you know a little about ECC, you will almost certainly have come across Daniel Bernstein’s Curve25519. This curve, so called because all arithmetic is carried out modulo the prime 2255 – 19, has become widely adopted because it allows very fast implementations of typical cryptographic functions that are also secure against some kinds of side-channel attacks. But one aspect of the definition of the curve causes some confusion: the “clamping” done to private keys before they are used. It confused me at first too, but it’s actually not too complicated once you realise what it is doing. This article will attempt to explain it for anyone else that finds themselves puzzled.
The clamping function looks like this:
t &= 248;
t &= 127;
t |= 64;
Here t is the private key, a 32-byte value interpreted as an integer in little-endian format. The first line clears the least significant three bits. The second line clears the most significant bit, and the last line then sets the next-most significant bit. But why?
Without going too much into the details, points on an elliptic curve (over a finite field) form an Abelian group. There’s a definition for what it means to add two points together to get another point, and a definition to add a point to itself. For example, if we have a point P and add it to itself we might end up at another point Q, so P + P = Q. We can also write this as 2*P = Q, or more often using the notation P = Q. You can extend this naturally to other numbers, such as P = P + P + P, P = P + P + P + P, and so on. This is known as scalar multiplication, where a point P is multiplied by an integer by repeated point addition.
In the elliptic curve groups used in cryptography, if you keep adding a point P to itself you will eventually end up back at point P again. In other words, the group is finite and cyclic. Just before you get back to P you will reach a point O, known as the point at infinity, which is the identity element (like 0) for the group. The number of times that you have to add P to itself to get to O is known as the order of the point P. For example, if you had to add P to itself 9 times to get to O, i.e., P = O, then we would say that P is a point of order 9. Adding P to itself one more time will get you back to P, so P = P in this case. For security we’d ideally like all the points on a curve to have an order which is a very large prime number, which we will call q. In practice, for the curves we care about, most points will be on the same large sub-group of order q, but there will be a few points of small-order that have a much smaller order such as 1, or 2, or 8.
The total number of points on an elliptic curve (over a finite field) is given by an equation n = hq where q is the order of the large prime sub-group and h is a small integer known as the cofactor. The points of small-order always have an order that is either h or a divisor of h. For example, in Curve25519 the cofactor is 8, so there can be points of order 1, 2, 4, and 8. Many commonly used elliptic curves, such as the popular secp256r1 curve (“P-256”), or Bitcoin’s secp256k1, have a cofactor of 1, so there is only a single point of small order: O (the point at infinity).
In ECC, a private key is a secret scalar value, d. A public key is a point P on the elliptic curve, which is generated from a standard “base point” G, such that P = [d]G. In Diffie-Hellman key agreement using elliptic curves, Alice takes Bob’s public key Q and performs scalar multiplication against her private key d to get a point R = [d]Q. Bob does the same with Alice’s public key and his own private key, and they magically end up with the same point R. They then both extract the x-coordinate of that point, throw it into a key-derivation function, and out comes a shared AES key they can use to communicate.
Alice and Bob should choose their public keys to be points on the large prime-order sub-group (otherwise it will be really easy to work out what their private key is). If this sub-group has order q, then this means that they should choose a value between 1 and q-1 as their secret scalar value (private key). (Choosing either 0 or q will leave you with O as your public key, which is useless as it has order 1 and for any n, [n]O = O).
For Curve25519, q is 2^252 plus a smallish constant. So scalar values should be chosen between 1 and 2^252 – 1. (Ignoring the extra constant doesn’t reduce security by any appreciable amount). But there are two reasons why you might not want to use the full range:
- Small values for the private key, such as 1, are obviously not very secure. That said, they are also very unlikely to be picked at random so this isn’t something you need to worry about.
- Some implementations of scalar multiplication take a different amount of time depending on whether the first bit of the scalar value is a 0 or a 1. This can let an observer work out which of the two values it was, leaking one bit of your private key.
You can “solve” both of these problems by picking your private scalar to be between 2^251 and 2^252 – 1. This ensures that the scalar is always large and the highest bit is always a 1. Of course, it does this at the cost of cutting the space of possible private keys in half, effectively giving away 1 bit of the private key anyway.
Another issue is that if Bob sends Alice a public key that is actually a point of small-order, say 8, then there are only 8 possible values for the resulting scalar multiplication. Bob therefore will learn the value of Alice’s private key modulo 8. He can send different keys of small order to learn Alice’s private key modulo different values. If he can send enough of these for different orders then he can eventually recover Alice’s whole private key. In practice, because the points of small order are divisors of the cofactor, h, which is typically very small, Bob can usually only recover a few bits of the private key this way. (He can do better by sending points on a completely different curve, known as an invalid curve attack, but we’ll ignore that here). For Curve25519, where h = 8, Bob can recover the least significant 3 bits of Alice’s private key.
You can prevent this attack by validating that Bob’s public key is on the main prime-order subgroup, by ensuring that [q]Q = O. But this is expensive. Alternatively, your protocol can multiply Alice’s secret scalar by the cofactor, so that instead of computing [d]Q she instead computes [hd]Q (and Bob makes the same adjustment). This ensures that if Bob does pass in a point of small order then Alice will always compute O as the result of scalar multiplication and Bob learns nothing about her private key. This is what NIST calls Cofactor Diffie-Hellman, and is the ECC DH primitive they standardized.
For Curve25519, h = 8, and multiplying by 8 is the same as a binary left-shift by 3 bits. If you take a secret scalar value between 2^251 and 2^252 – 1 and left-shift by 3 bits then you end up with a 255-bit number with the most significant bit set to 1 and the least-significant three bits set to 0. The Curve25519 clamping operation takes an arbitrary 256-bit random value and clears the most-significant bit (making it a 255-bit number), sets the next bit, and then clears the 3 least-significant bits. In other words, it directly creates a scalar value that is in the right form and pre-multiplied by the cofactor.
I think the confusion comes from thinking that what you supply to Curve25519 as the private key is already a scalar value. It’s not, it’s a uniformly random key. Curve25519 then applies a surjective mapping function (clamping) to this key to derive a suitable scalar value. (Essentially, 5 bits of the key are ignored, leaving 2^251 distinct keys). It’s not pretty, but it gets the job done and is fast.