3
$\begingroup$

How many different keys can be derived with HKDF before two outputs are identical?

This question is about collision resistance, not about generating different keys with different parameters (eg. different salts/info parameters).

For HKDF with SHA-256 would it be $2^{128}$ since the collision resistance of HMAC-SHA-256 is 128 bit?

$\endgroup$
10
  • 1
    $\begingroup$ Does this answer your question Multiple AES Key Derivation from a master key ? $\endgroup$ – kelalaka Feb 24 at 11:13
  • 1
    $\begingroup$ HKDF has parameters: a hash, salt, IKM, info and L. What can we assume about these parameters? Can you confirm that the question asks an approximation of the number of different outputs of HKDF when the parameters vary within said limits? Or is it asked how many times HKDF can be safely used before it becomes likely that two outputs are identical? Alternatively, clarify what the count asked exactly is. $\endgroup$ – fgrieu Feb 24 at 11:26
  • $\begingroup$ @kelalaka that does discuss my question, although it doesn't answer it in a very comprehensible way. That makes it sound like number of keys would be 2^256 for SHA256 since it said double 'usual collision attack'. $\endgroup$ – Franzi Feb 24 at 11:54
  • $\begingroup$ @fgrieu I have clarified the question now. I'm asking about how likely it is that two outputs are identical. $\endgroup$ – Franzi Feb 24 at 11:55
  • 1
    $\begingroup$ Does this answer your question? Multiple AES Key Derivation from a master key $\endgroup$ – AleksanderRas Feb 24 at 14:06
3
$\begingroup$

I've seen this a few times, so I want to point out something that is a general misconception. People often think that for key derivation, it's really important that I don't get repetition, since that is a break. However, this is actually very not true, and the opposite is true. I will explain.

The "ideal situation" is to just choose keys, truly at random. In this case, if I am working with 128-bit keys, the birthday paradox still holds. As such, after generating $2^{64}$ truly random keys, they will repeat. This is not a problem at all. On the contrary, it guarantees that even if you saw all of the previously generated keys, you have no information on the next one. Furthermore, all (symmetric) encryption uses an IV, so you'd need the random IV and the key to collide in order to be able to detect that two different people/cases are using the same key.

One would think that it would be better to choose keys purposefully so that they don't repeat. But this would mean that keys get less and less random, and have lower entropy as time goes on. In particular, given past keys, the new key is known to not equal any of those. So, we actually do not want to do that.

Just to stress this, using AES for key derivation directly (e.g., in CTR mode), the quality of the key derivation goes down when you get close to the birthday bound because the keys can't repeat. Thus, since the keys can't repeat, that means that the key does not look like a random one. I know that this is the opposite of most people's intuition, which is why I felt it important to point out.

$\endgroup$
2
  • 1
    $\begingroup$ You are correct, and I have now added a preamble to that effect in my answer. I want to point that (a) The reduction in security by avoiding derived key collisions (as some KDF used in the industry do, by using encryption of a counter as derived key) have a vanishingly low negative impact on security when resistance to key search is adequate. (b) Such measure can (slightly) increase security when the derived key is first "streched" before use as an encryption key. (c) Removing a technically pointless but easily met requirement is a luxury practitioners often can't afford. $\endgroup$ – fgrieu Feb 24 at 15:26
  • $\begingroup$ I might note that when the counter-based nonce is generated for the CTR and GCM then the key collision is a catastrophe if the counter restart for a fresh key. $\endgroup$ – kelalaka Feb 25 at 14:00
1
$\begingroup$

The present answer is made for the sake of answering an answerable question, and the cases where collisions actually matter: like, they are observed and we want to rule out it's by chance; or some authority specified that each smurf must have a unique key, and lack of a convincing argument for that separates the rubber stamp from the paperwork. See Yehuda Lindell's answer about why collisions at the output of a Key Derivation Function actually do not harm the security of encryption with the derived keys.

We'll use the definition of HKDF and the notations of RFC 5869.

How many different keys can be derived with HKDF before two outputs are identical?

Under standard assumptions about the $\mathtt{Hash}$ used, assuming the combination of the inputs $\mathtt{IKM}$¹ and $\mathtt{salt}$ does not repeat, fixed $\mathtt{info}$, and no intend of creating collision² in the choice of inputs, that number of generations before collision depends primarily on:

  • $\mathtt{L}$, the size in byte of the output of HKDF (the generated key typically is $8\mathtt{L}$‑bit)
  • $\mathtt{HashLen}$, the size in byte of the output of $\mathtt{Hash}$, that is 32 for SHA‑256.

A useful approximation is $16^{\min(\mathtt{L},\mathtt{HashLen})}$ or equivalently $2^{4\min(\mathtt{L},\mathtt{HashLen})}$, at a residual probability of collision of about 39% when $\mathtt{L}\ne\mathtt{HashLen}$, 63% when $\mathtt{L}=\mathtt{HashLen}$.

When we are interested in low probability $\epsilon$ of collision, that goes $\sqrt{2\,\epsilon}\,2^{4\min(\mathtt{L},\mathtt{HashLen})}$ when $\mathtt{L}\ne\mathtt{HashLen}$, or $\sqrt{\epsilon}\,2^{4\mathtt{L}}$ when $\mathtt{L}=\mathtt{HashLen}$.

For example, for SHA‑256, if we want residual probability of collision of $2^{-20}$ (less than one in a million) and 256‑bit generated key ($\mathtt{L}=32$), that's $2^{118}$ uses. For 128-bit keys, that's "down" to $2^{54.5}$ uses.

This first-order approximation considers that a collision can occur in the Extract step of HKDF with probability per the birthday bound as controlled by $\mathtt{HashLen}$, or in the Expand step as controlled by $\mathtt{L}$.


¹ More precisely, what matters is the value of master key $\mathtt{IKM}$ after replacing by its hash any value of $\mathtt{IKM}$ longer than the block size of $\mathtt{Hash}$, that is 64 bytes for SHA‑256. Notice that this replacement makes it trivial to generate a collision of HKDF for two values of $\mathtt{IKM}$ (one within the block size, the other larger) and the same $\mathtt{salt}$ and $\mathtt{info}$.

² Intend of creating collision would matter e.g. for $\mathtt{L}=16$ (that is 128‑bit generated keys) or lower, and an adversary was in a position to write the piece of code choosing $\mathtt{salt}$ or $\mathtt{info}$, and that piece of code had knowledge of $\mathtt{IKM}$.

$\endgroup$

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.