If P256 ECDH shared secret contains ~128 bits of security, does using first half of the secret (= 128 bits) contain only 64 bits of security?

Question

There's this rather popular open source project (I'd rather not name it before possible responsible disclosure) that computes a P256 ECDH shared secret (256 bits) and uses only first half of it, rams it through a KDF, and uses the result as a 128-bit AES key.

I'm wondering if that's problematic regarding its security since it looks like it's trying to offer 128-bit security, but I wonder if the result is 64-bit security because even if you take 128 bits of data that has 64 bits of security (i.e. "true randomness") and pipe it through a KDF, it still has 64 bits of security?

Here's my thinking as a drawing:

Am I right in thinking they should've piped the whole shared secret through the KDF to "compress" the 256 bits to 128 bits to retain 128-bit security?

The assumptions I am running on are that P256 ECDH shared secret contains 128 bits of security, and that if you take any single byte from the shared secret, only 4 of the bits inside the byte are truly random.

Answer 1

First of all, generally, the shared secret is split in half because it consists of an X and Y coordinate. It is after all the point resulting in multiplying a public key point with a private key / vector, resulting in another point on the curve. Now the X and Y coordinate are related, so generally, only the X coordinate is used as a shared secret.

Currently, you are assuming that the total result is 256 bits. However, for Elliptic Curves, each coordinate of the curve is 256 bits, making a total of 512 bits. So generally you would be left with 256 bits - not 128 bits - once you split the full outcome of the ECDH key agreement. I'd make sure if that's not what is meant because it would make a whole lot more sense. Please make sure that the result is precisely 64 bytes in that case (if it is more then the header should be removed in such a way that a 64-byte X-coordinate is left - how depends on the format of the point that is generated).

Furthermore, the (classic) security of ECDH with a key size of 256 bits is 128 bits because that's what level of security finite field will produce. It is an indication of the security in bits (compared to e.g. AES) that ECDH produces. However, that doesn't mean that the X-coordinate is not well distributed; to my knowledge it is. So even if you would split the X-coordinate in half you'd still be left with 128 bits of security. Finally, even if there would be an algorithmic weakness then the one-way property of the KDF would, with a very high degree of certainty, remove such weaknesses.

All that said: if indeed 128 bits are used instead of 256 then the protocol doesn't make all that much sense. Using the full 256 bits of a (constant sized) X-coordinate should be preferred.

---

Notes:

• I'd use AES-256 instead of AES-128 and also generate a random IV where required;
• 256-bit curves only provide 128-bit security against classical crypto-analysis, full-fledged quantum computers would certainly reduce that by a significant amount, rendering the algorithm insecure.

Answer 2

Am I right in thinking they should've piped the whole shared secret through the KDF to "compress" the 256 bits to 128 bits to retain 128-bit security?

Using only 128 bits would not be the best practice, but does not open to attack as far as I know, for standard KDFs (which use all the entropy in their input). There's still effectively 128-bit security for the confidentiality given by the AES-128 encryption step, if otherwise carried correctly. That 128-bit security is all the ECDH step aims to offer, given the curve used.

Argument: the first half of the ECDH secret (taken as the 256-bit X coordinate of the resulting point) is nearly indistinguishable from random (we can make a distinguisher using that the high 128 bits of a random integer reduced modulo $p$ of P256 aka secp256r1 have average slightly below $2^{127}$ and is always less than $\left\lfloor p/2^{128}\right\rfloor$, but that does not get much better). A standard KDF would not appreciably lower that (if that was a cryptographic hash like SHA-256, we'd loose only ≈0.8272 bit out of nearly 128, see this). The time the KDF takes even makes brute force attack rather harder than with no KDF.