Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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:
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}$.
