Am I losing any entropy when using KDFs, such as the ones in NIST Special Publication 800-108?
For example, can I derive 128-bit session keys from a (uniformly random) 128-bit master key?


When you use a PRF to derive a key, there is the potential for collisions. If you derived a 128-bit key from each possible 128-bit number, you'd expect some of them to collide. Specifically, you'd expect only about 63% of all the inputs ($1-e^{-1}$) to appear as outputs.

That means you lose less than a bit of entropy even if the original key had the full 128 bits of entropy, like your random 128-bit string. With a lower entropy key you'd lose less. That doesn't matter in practice, since in the worst case it wouldn't even halve attack time. 127-bit security is enough.

In general, if you use a PRF to derive an $n$-bit key from one with $k$ bits of entropy, the resulting key will have at least $\min(n, k) - 1$ bits of entropy, approaching $\min(n, k)$ when $k \ll n$ or $k \gg n$.

| improve this answer | |
  • $\begingroup$ Good answer, but I guess you also need to state that if you provide more than 128 bits of entropy that the entropy loss will be the difference between 128 and the amount of entropy (+ possibly part of a single bit?). $\endgroup$ – Maarten Bodewes Aug 19 '14 at 16:24
  • $\begingroup$ @owlstead, the question was $128 \mapsto 128$, but sure, added a paragraph. $\endgroup$ – otus Aug 19 '14 at 17:57
  • 1
    $\begingroup$ Well, it was "for example" :P Besides the pun, lets not specialize answers too much. Thanks for the edit, had already voted up... $\endgroup$ – Maarten Bodewes Aug 19 '14 at 18:06
  • $\begingroup$ Thanks for the answer. Can you add a reference for $1-e^{-1}$? $\endgroup$ – Konny Aug 20 '14 at 8:56
  • $\begingroup$ Apparently, some KDFs do not suffer from collisions. For example, a block cipher-based KDF in counter mode won't output the same key twice unless a counter value is reused. This is because block ciphers are bijective. $\endgroup$ – Konny Aug 20 '14 at 12:59

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.