Can Curve25519 shared secret be safely truncated to half its size?

Question

I am planning to use a key agreement mechanism in an application needing ephemeral keys, and Curve25519 looks promising, specifically because it offers 128 bits of security, just fine for AES-128 which is my symmetric cryptographic algorithm of choice (https://en.wikipedia.org/wiki/Curve25519):

In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security (256-bit key size) and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme

As a bonus, I can use public domain code to implement it, which doesn't cause any licensing issues.

However, the shared secret size of Curve25519 seems to be 32 bytes (256 bits). This is troubling me somewhat. I need only 128 bits.

Can I safely take only half of the bits generated by Curve25519, or is it a common property of Curve25519 that the number of bits of security is half of the number of bits used? So if I use only half of the bits, does it mean I have still 128 bits of security (safe), or 64 bits of security (unsafe)?

Of course, if it's unsafe to truncate, I could use some kind of hash function and take half of the bits of the hash function output, but I wouldn't want to do this unless absolutely needed.

Answer 1

Can Curve25519 shared secret be safely truncated to half its size?

TL;DR: don't do this, mostly because you need several keys. Use a KDF, even a cheap one.

---

The shared secret in Curve25519 is 256-bit. It can take about 2²⁵² 32-byte values. Notice that 256-bit values for 128-bit security makes sense in many contexts. For example for 128-bit security against collision, a hash needs to be at least about 256-bit.

To turn Curve25519's shared secret (or more generally the outcome of Diffie-Hellman, ECDH or not) into 128-bit keys for symmetric cryptography, the academic thing to do is to feed a Key Derivation Function this secret and a constant characteristic of the intended usage of the key, to obtain a 128-bit output. The KDF needs not be purposely slow (contrary to KDFs processing passwords). This key derivation serves two goals:

• We get as many keys as needed from a single shared secret. Often, in the context a sessions, we need at least one encryption keys in each direction as a simple way to block reflection attacks; perhaps two in each direction if we use separate encryption and integrity keys. We might also need an extra value to be signed, in order to protect the session against MitM. As the saying goes: one usage, one key.
• The output of a KDF appears uniformly random, when the shared secret of (EC)DH is often not, thus merely extracting bits from the secret is not ideal. If you extract the wrong ones, security drops (I think, by about 1 bit in the worst case for Curve25519 if the other bits are dropped, but don't bet the house on that).

The poor man's KDF is a truncated hash. You won't be bitten by using the first 16 bytes of $\operatorname{SHA-256}(\text{DerivationConstant}\mathbin\|\text{SharedSecret})$ where $\text{DerivationConstant}$ is some 8 bytes characteristic of the intended key usage. A more academic one is truncated HMAC-SHA-256 with key $\text{SharedSecret}$, message $\text{DerivationConstant}$. NIST has a standard for KDFs.

The answer is the same for wider symmetric keys e.g. 192-bit or 256-bit, adapting

• the curve (Curve25519 would be inconsistent, Curve448 is fine, secp521r1 might be required in contexts where AES-256 is)
• the output width of the KDF
• and while we are at it basing the KDF on a stronger hash (e.g. SHA-512).

Answer 2

The usual encoding of the points in Elliptic Curves over a finite field is structured and non-uniform since it must satisfy the curve equation.

If we look at Curve25519, it is defined over the field $x \in \mathbb Z/(2^{255} - 19)\mathbb Z$ and using the curve equation $y^2 = x^3 + 486662 x^2 + x$. Immedialately we can see this $x^3 + 486662 x^2 + x$ is always a square for the points. This already makes the encoding not uniform.

It is common advice to use a KDF on the ECDH output as AES keys since it may create attack points.

Further, if you want to hide the fact you are sending points ( they may check with the curve equation so they can distinguish it from random) you may use Elligator;

When do you need Elligator?

Elligator addresses a specific problem: you need to perform a cryptographic key exchange protocol, and hide the very fact that you are using cryptography.

Answer 3

You'll want to use a KDF to derive the AES key, for example HKDF-SHA256.

You could specify a 128-bit output key from HKDF, but if you want a 128-bit security level you should use AES-256 anyway.