Security Post-it #1 – SHA-1 is broken, not HMAC

In a real-life scenario, let's calculate the minimum length of an HMAC key to be breakable in more than 10 years, which is 315360000 seconds. I will theoretically take eight Nvidia GTX 1080s, using this performance sheet.

By approximating, we consider that HMAC performs two SHA-1s and one XOR (0.5 times the number of SHA-1 per second). With this configuration, it is possible to generate about \(6.87 \times 10^{10}\) SHA-1 per second.

Let k be the length in bit of an HMAC key. The number of possibilities is \(2^k\) and we will take an average of \(2^{k-1}\) keys tested before recovering the HMAC key.

$$\frac{2^{k-1}}{0.5 \times 6.87 \times 10^{10}}=315360000 $$ $$2^{k-1}=315360000 \times 0.5 \times 6.87 \times 10^{10}$$ $$k=log_2(1083261600 \times 10^{10}) + 1$$ $$k \approx 64$$

k is around 64 bits, which is an 8 bytes long string...

It seems like a common password could easily be broken, but the recommended 20 bytes for the HMAC are safe.

To break a SHA-1, the calculation is the same but the time spent is twice less.

Breaking SHA-1 by brute-force attack is not a solution.

In 2017, Google has found how to collide two SHA-1 hashes. At the time, it cost approximately 130k$ and relies on the birthday paradox. In May 2019, some french and singapourien researches have found how to reduce the number of try to collide prefixes.

We are currently working on further improvements (unpublished yet), and we evaluate now that one can find a chosen-prefix collision for SHA-1 with a budget of less than $100,000, which is really practical.

First SHA1 was shattered. https://t.co/CnnYJiLtxP
Now it's reduced to shambles.
It's time to stop using SHA1. (HMAC-SHA1 is still okay.)

The compression function of HMAC successively applies several SHA-1s. Having the power to make collisions of SHA-1 does not predict the output of an HMAC.

A much deeper break of SHA-1's round function would be needed to break HMAC. M. Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance shows that the security of HMAC holds assuming only weaker properties on its round function than needed for collision resistance of the corresponding hash.