Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken?

Question

As we know, MD5 and SHA1 (to some extent) are broken, and older algorithms like SHA0 or MD4 and MD2 are very broken.

Does this also imply that the corresponding HMACs are also broken?

Obviously nobody should use e.g. HMAC_MD4 anymore. But I'm just trying to understand the underlying security risk from a theoretical point of view.

Is it feasible to generate a collision for something like HMAC_MD2 or HMAC_MD5?

Answer 1

In 2006, Mihir Bellare, in their article

• New Proofs for NMAC and HMAC: Security without Collision-Resistance

proved that if the compression function is a PRF then HMAC is a PRF ( this is a short story, see below).

As a result, HMAC like HMAC-MD5 does not suffer the weaknesses of MD5. However, still prefer HMAC-SHA256 or KMAC of the SHA-3 series. Keep yourself away from MD5 and SHA-1.

---

However, the story is not finished There:

In 2006, Jongsung Kim, Alex Biryukov, Bart Preneel, and Seokhie Hong showed that they can distinguish HMAC if instantiated with reduced versions of MD5 and SHA-1 or instantiated full versions of HAVAL, MD4, and SHA-0 from a random function or HMAC with a random function.

In 2012, Koblitz–Menezes published a paper Another look at HMAC ( from the abstract);

1. First, we describe a security issue that arises because of inconsistencies in the standards and the published literature regarding keylength. We prove a separation result between two versions of HMAC, which we denote $\operatorname{HMAC}^{std}$ and $\operatorname{HMAC}^{Bel}$, the former being the real-world version standardized by Bellare et al. in 1997 and the latter being the version described in Bellare’s proof of security in his Crypto 2006 paper.
2. Second, we describe how $\operatorname{HMAC}^{NIST}$ (the FIPS version standardized by NIST), while provably secure (in the single-user setting), succumbs to a practical attack in the multi-user setting.
3. Third, we describe a fundamental defect from a practice-oriented standpoint in Bellare’s 2006 security result for HMAC, and show that because of this defect his proof gives a security guarantee that is of little value in practice.
4. We give a new proof of NMAC security that gives a stronger result for NMAC and HMAC and we discuss why even this stronger result by itself fails to give convincing assurance of HMAC security.

from conclusion;

1. When HMAC is used with a hash function that is not collision-resistant, confidence in its security cannot come from the proof in [1] – or even from our proof in §10 – but rather must be based upon the large number of person-years that engineers and cryptanalysts have devoted to testing it. This is especially the case in an application where one needs pseudorandomness and where short-term security is not enough.

There is a slide from Bernstein that covers the brawl around the above paper

• 2012 - The HMAC brawl