Is the quality of hash function essential in HKDF?

Question

Hash functions have a number of properties needed, including the property that no collisions must be able to be found. Generally, if we can find collisions for hash functions, we consider the hash function broken.

However, not all uses of hash functions need such strict properties from the function.

One case where hash functions are used is HKDF, to generate potentially multiple keys from a limited length of cryptographical quality keying material.

Let's say I would do something as ridiculous as using MD4 for HKDF, in an application where 128-bit long keys are considered sufficient (for 256-bit long keys maybe HKDF-MD4 wouldn't be secure). MD4 has been broken a long time ago.

Would using MD4 for HKDF create a vulnerability? Or is the quality of MD4 and other broken hash functions like MD5 and SHA-1 sufficient for usage in HKDF, assuming the digest size is considered long enough?

The reason I'm interested is that I'm developing an application where I'm planning to use HKDF, and obviously I'm going to use SHA-256, but I'm wondering whether I should offer the option of using SHA-512 and maybe SHA-3 for future-proofing it. If finding collisions in SHA-256 (the most plausible way it will be broken) does not make it unsafe for HKDF, then SHA-512 and SHA-3 implementations maybe are not needed.

Answer 1

Would using MD4 for HKDF create a vulnerability? Or is the quality of MD4 and other broken hash functions like MD5 and SHA-1 sufficient for usage in HKDF, assuming the digest size is considered long enough?

Yes, using a cryptographically broken hash function can cause vulnerabilities with HKDF.

As an example, if you used HKDF with HMAC-SHA1 to derive a non-committing AEAD (e.g. AES-GCM) encryption key and a key (or context) commitment tag, you wouldn't have key (or context) commitment. This is because AEAD commitment depends on collision resistance, and HMAC-SHA1 isn't collision resistant.

This demonstrates that the mentality of not all uses of hash functions need such strict properties from the function is a good way to shoot yourself in the foot.

obviously I'm going to use SHA-256, but I'm wondering whether I should offer the option of using SHA-512 and maybe SHA-3 for future-proofing it.

This kind of cryptographic agility is unnecessary. Pick one and avoid exposing choice to the user, like WireGuard. They're all secure, and you should be more informed than the user.

In terms of SHA-256 vs SHA-512, SHA-256 can be hardware accelerated on newer devices and should be faster on small inputs regardless. However, it makes sense to use SHA-512 when doing a symmetric-key ratchet aiming for a 256-bit security level.

For SHA-3, it would make more sense/be more efficient to use KMAC.

Answer 2

As for many things, the answer always depends on what security property you are looking at. A hash function $H(x) = 0$ for all $x$ wouldn't have much use. For the standard uses of HKDF (and the underlying HMAC), the security is achieved even without guaranteed collision resistance of the hash function. Although this knowledge is useful, wisdom would indicate that broken hash functions should not be used within HKDF. Furthermore, it's important to understand that some usages of HKDF are outside the initial security model.

First, let's consider KDF security as defined by the paper Cryptographic Extraction and Key Derivation: The HKDF Scheme, which aslo introduced HKDF was.

HKDF is an extract-then-expand KDF built on top of HMAC. HKDK uses HMAC internally as a (computational) randomness extractor and a (variable-output length) PRF with a feedback mode wrapper. HMAC exploits the hash function's “cascade structure” for randomness extraction to argue for extraction security in various contexts. Furthermore, HMAC's PRF security is based on the compression function's PRF behavior. Unsalted HKDF-extract is still proven to be a good extraction by showing that it is indifferentiable from a random oracle. Beyond that, HMAC has also been proven to be a dual-PRF (you can swap inputs and keys) for some inputs. Dual PRFs are useful for deriving keys from two keying inputs in a way that remains secure as long as one of the keys is secure.

An essential takeaway at this point is that the "right" view of HMAC is a mode of operation of compression function families, and not merely that of some hash function as is commonly seen. HMAC cleverly takes advantage of the Merkle–Damgård construction to achieve all kinds of things.

Non-standard usage: The security notions introduced before only hold against an attacker who doesn't know or control the input material to HKDF. It doesn't attempt to say anything about an attacker who knows or influences the key. Therefore, applications that expect these “advanced properties” should know this and use the appropriate schemes. One such example is a key commitment, as discussed in this answer.

One remark: the KDF security notion defined for HKDF doesn't generically provide key commitment. The KDF needs to be additionally collision-resistant on its own. Consider a generic extract-then-expand KDF; it's not too hard to modify such a KDF and make it non-collision resistant while retaining KDF security (i.e., use a different non-collision, resistant PRF for the expand part).