3
$\begingroup$

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:

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.

$\endgroup$
3
  • $\begingroup$ OpenSource and disclosure a bit conflicting. Actually, we want the reference to see the source of the problem. $\endgroup$
    – kelalaka
    Oct 14, 2020 at 13:20
  • $\begingroup$ The entropy of the output cannot be larger than the input for any KDF. Which part of the shared key is in use? If the upper part, then it might not be 128-bit security. $\endgroup$
    – kelalaka
    Oct 14, 2020 at 13:23
  • $\begingroup$ Did any of the answers solve your question or doubt? If so, please accept an answer. If not, then please indicate what's missing. I'm really curious if / how this was resolved, it was a vexing problem. $\endgroup$
    – Maarten Bodewes
    Oct 27, 2020 at 17:31

2 Answers 2

4
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ +1 for noting that perhaps it is used 256 bits out of 512, not 128 our of 256 as stated, which I had missed; and that P256 only has 128-bit security in the first place! $\endgroup$
    – fgrieu
    Oct 14, 2020 at 14:40
  • $\begingroup$ Actually, I was expecting the OP links to the library. But they did not clarify it so that we can talk actual case. $\endgroup$
    – kelalaka
    Oct 14, 2020 at 18:42
  • 1
    $\begingroup$ I don't think this is correct. ECDH (except the Bernstein variant) computes a point, but AFAIK everything uses only the x-coordinate. X9.63 costs, but SEC1 is intended to be compatible and 3.3 says x-coordinate. P1363 costs, but TLS RFCs 4492,8422,8446 reference it and say x-coordinate. NIST SP800-56A 5.7.1.2 is stated to be from X9.63 and says x-coordinate. (All of these then apply a KDF to the x-coordinate, although TLS uses the identity because the TLS premaster from any keyexchange goes into a PRF or HKDF.) $\endgroup$ Oct 15, 2020 at 1:17
  • $\begingroup$ Sure thing, the protocols say that, but I've definitely seen libs that return a full point after a DH calculation. $\endgroup$
    – Maarten Bodewes
    Oct 15, 2020 at 8:54
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The only meaningful attack on AES-128 is the multi target, +1 about the upper. secp256r1 prime p = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF $p = 2^{224}(2^{32}- 1) + 2^{192} + 2^{96}$ $\endgroup$
    – kelalaka
    Oct 14, 2020 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.