6
$\begingroup$

My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo a number that is not a power of 2, and is thus non-uniform if represented as a bit-string).

Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

$\endgroup$
7
$\begingroup$

Do you really need a KDF when you have a PRF?

Maybe.

The security contract of a PRF requires that the key be a uniform random bit string. If you have a DH secret or a diceware phrase, then what you have is not uniform random as a bit string, and so your contractual obligations are not satisfied and the PRF may give no security. You need something a little stronger to hash a DH secret or diceware pass phrase into a uniform random bit string, which is what the ‘extract’ step does.

Here's an example. Let $F_k$ be a PRF and let $H$ be a random oracle. Define $$F'_{x,y}(s) := F_{H(u)}(s), \quad u = (y^2 - x^3 - 7) \bmod p,$$ where $p = 2^{256} - 2^{32} - 977$. $F'$ is also a PRF, because when $(x, y)$ is uniformly distributed among 512-bit strings, the probability of collisions in $u$ is small. But if $(x, y)$ is the outcome of a DH key agreement on secp256k1, then $y^2 \equiv x^3 + 7 \pmod p$ so $u$ is always zero and hence $F'_{x,y}(s) = F_{H(0)}(s)$ for all $x$ and $y$—that is, the DH key agreement doesn't affect the output at all, so the system gives no security whatsoever!

If what you have is a uniform random bit string as a master key already, and you just need to derive subkeys from it with distinct labels, then a PRF is all you need, and the ‘expand’ step is, in fact, a PRF. If you look closely at HKDF, for example, you will see that $$\operatorname{HKDF-Expand}_k(L) = \operatorname{HMAC-}\!H_k(L \mathbin\| \mathtt{0x01}),$$ if the desired output size matches the output size of $H$; if more bytes are requested, just repeatedly call $\operatorname{HMAC-}\!H$ with consecutive counters and the previous chunk prepended to $L$, and concatenate the outputs. You could, of course, substitute for $\operatorname{HMAC-}\!H$ your favorite PRF like keyed BLAKE2b, KMAC128, KangarooTwelve, Kravatte, prefix-keyed Gimli-Hash, or ChaCha $\circ$ Poly1305, and while it wouldn't be HKDF it would be just as good for deriving subkeys.

My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo a number that is not a power of 2, and is thus non-uniform if represented as a bit-string).

Correct: The purpose of collecting the concepts of extract-with-salt and expand-with-label into a single term KDF is that often the two steps are close by—you have a DH secret, or a master diceware phrase, which is not uniform in bit strings but which has high entropy, and you want to derive many secret keys from it for different labeled purposes.

Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

The security contract for many cryptographic primitives requires the input to be uniform random. Violate the contract, and the security may evaporate. Obviously you can choose the input by a pseudorandom function under a uniform random key—if that broke the composition, merely using the composition would then serve as a distinguisher for the pseudorandom function. But it's not a priori clear whether highly structured keys like the bit encodings of points on particular curves might be exploitable in downstream cryptosystems. Maybe you'll be bitten by a bad interaction like in the contrived secp256k1 example above; maybe you won't be. Using HKDF-Extract, or otherwise hashing the input, renders these concerns moot so you don't even have to think about them.

$\endgroup$
  • $\begingroup$ hey thanks for the answer! I feel like it is still not answering the question though: "do you really need a KDF when you have a PRF". I could use a PRF over the DH secret to obtain a uniform symmetric key. It still doesn't sound like I need the extract step. $\endgroup$ – David 天宇 Wong Jun 11 at 21:56
  • $\begingroup$ It sounds to me like the only big different is that the KDF takes an arbitrary length input while the PRF takes a fixed length input. $\endgroup$ – David 天宇 Wong Jun 11 at 21:59
  • $\begingroup$ @David天宇Wong A PRF is not what you need to hash a DH secret. The premise of a PRF is that the key is a uniform random bit string. If you feed the DH secret in as the PRF key, then you're violating the PRF contract and you may get no security; if you feed the DH secret in as the PRF input, then you need to specify a key too—and if the two peers already had a secret uniform random bit string to use as the PRF key, why would you need to do DH? In contrast, the contract of a KDF extractor is merely that the secret have high min-entropy. $\endgroup$ – Squeamish Ossifrage Jun 11 at 22:04
  • $\begingroup$ @David天宇Wong But once you have hashed the DH secret with (say) HKDF-Extract, all you need to derive subkeys from the master key is a PRF, which is why HKDF-Expand really is just a PRF; you could safely use other PRFs too instead of HKDF-Expand. Some PRFs have short inputs (like ChaCha), some PRFs have long inputs (like KMAC128); that's not a characteristic by which KDFs and PRFs are distinguished. $\endgroup$ – Squeamish Ossifrage Jun 11 at 22:05
  • $\begingroup$ @David天宇Wong I expanded a little bit on the main question. Does that help? $\endgroup$ – Squeamish Ossifrage Jun 11 at 22:34
4
$\begingroup$

Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, [...]

While people normally say that the key of a symmetric algorithm must be chosen uniformly at random, that's strictly speaking false. What the math actually says is that if the key is chosen uniformly at random and kept secret, then the cryptographic scheme has such-and-such security properties. This doesn't preclude that the system could be secure with some other, non-uniform method of choosing keys. ("If P then Q" doesn't imply "If Q then P.")

The reason we want a key derivation step is keys that are sampled from a pseudorandom distribution (i.e., a distribution that cannot be efficiently distinguished from a uniform random distribution) are one such method. These keys are strictly speaking not uniform random, but as Squeamish Ossifrage notes in passing, if an adversary can exploit this fact to attack the scheme when we use the KDF to generate keys for it, then that can be translated into an attack on the KDF itself—one that shows the generated keys can in fact be distinguished from uniform random.

Or in simpler words, pseudorandom keys aren't uniform random keys but can substitute for them, and that's why we use them—they make the "if the key is uniform random, then [security property]" statements carry over indirectly. In very inelegant English:

  • If it is the case that:
    • if the key is uniform random
    • then [security property],
  • Then:
    • if the key is pseudorandom
    • then [security property].

[...] but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

ECDH is a scenario where we've got a shared secret value that has plenty of entropy. That means that there's no reason you'd want to "add entropy" to it or slow down the key derivation—concerns that suggest you're getting mixed up between password based KDFs (where those are common themes) and non-password based ones.

But as you've said, the ECDH secret is not pseudorandom in the sense of being indistinguishable from a uniform distribution over bit strings. Which means if you use it directly as a symmetric key you can't avail yourself of security arguments like the above.

$\endgroup$
  • $\begingroup$ I see what you are saying. This still doesn't answer the question: why not use a PRF to make a secret uniform instead of a KDF? It sounds to me like the only big different is that the KDF takes an arbitrary length input while the PRF takes a fixed length input. $\endgroup$ – David 天宇 Wong Jun 11 at 21:58
  • $\begingroup$ @David天宇Wong: Because a PRF wants you to already have a uniform secret (the key). If the only secret value you have at hand is an ECDH shared secret, which is not uniform, what are you going to use as the key for the PRF? $\endgroup$ – Luis Casillas Jun 12 at 17:43
  • $\begingroup$ I see. I got tricked because SHAKE is both a PRF and a (pseudo?) RO. So I guess, the question is now, if you have a hash function and a PRF (or a XOF), why use HKDF? Or is HKDF exactly this (a XOF)? $\endgroup$ – David 天宇 Wong Jun 12 at 23:18
  • 1
    $\begingroup$ As to why use HKDF, you should glance at the paper, but the key point is that HKDF-Extract bills itself not as a PRF or XOF, but as a (computational) randomness extractor, a function that turns high-entropy but non-uniform inputs into indistinguishable-from-uniform outputs. Any function that can promise the same will do as a KDF. But this promise isn't identical to what PRFs or XOFs promise (although some functions may be usable, directly or indirectly through construction, in all three roles). $\endgroup$ – Luis Casillas Jun 13 at 1:47
  • 1
    $\begingroup$ The promise of a PRF is that if you pick the secret key uniformly at random then it's indistinguishable from a random function. The promise of a KDF is if the secret input has sufficient min-entropy then the output is indistinguishable from random. The antecedents of the statements (i.e., the "if" preconditions) are critically important. $\endgroup$ – Luis Casillas Jun 14 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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