Estimating possible collisions of SHA-1

In a recent post, bruce schneier reprinted an analysis made by Jesse Walker (Skein team member) about the time needed to see a practical collision for SHA-1. It was interesting for me the way the writer goes through the calculations:

According to E-BASH, the cost of one block of a SHA-1 operation on already deployed commodity microprocessors is about 2¹⁴ cycles. If Stevens' attack of 2⁶⁰ SHA-1 operations serves as the baseline, then finding a collision costs about 2¹⁴ * 2⁶⁰ ~ 2⁷⁴ cycles.

A core today provides about 2³¹ cycles/sec; the state of the art is 8 = 2³ cores per processor for a total of 2³ * 2³¹ = 2³⁴ cycles/sec. A server typically has 4 processors, increasing the total to 2² * 2³⁴ = 2³⁶ cycles/sec. Since there are about 2²⁵ sec/year, this means one server delivers about 2²⁵ * 2³⁶ = 2⁶¹ cycles per year, which we can call a "server year."

There is ample evidence that Moore's law will continue through the mid 2020s. Hence the number of doublings in processor power we can expect between now and 2021 is:

3/1.5 = 2 times by 2015 (3 = 2015 - 2012)

6/1.5 = 4 times by 2018 (6 = 2018 - 2012)

9/1.5 = 6 times by 2021 (9 = 2021 - 2012)

So a commodity server year should be about:

2⁶¹ cycles/year in 2012

2² * 2⁶¹ = 2⁶³ cycles/year by 2015

2⁴ * 2⁶¹ = 2⁶⁵ cycles/year by 2018

2⁶ * 2⁶¹ = 2⁶⁷ cycles/year by 2021

Therefore, on commodity hardware, Stevens' attack should cost approximately:

2⁷⁴ / 2⁶¹ = 2¹³ server years in 2012

2⁷⁴ / 2⁶³ = 2¹¹ server years by 2015

2⁷⁴ / 2⁶⁵ = 2⁹ server years by 2018

2⁷⁴ / 2⁶⁷ = 2⁷ server years by 2021

Today Amazon rents compute time on commodity servers for about $0.04 / hour ~ $350 /year. Assume compute rental fees remain fixed while server capacity keeps pace with Moore's law. Then, since log₂(350) ~ 8.4 the cost of the attack will be approximately:

2¹³ * 2^8.4 = 2^21.4 ~ $2.77M in 2012

2¹¹ * 2^8.4 = 2^19.4 ~ $700K by 2015

2⁹ * 2^8.4 = 2^17.4 ~ $173K by 2018

2⁷ * 2^8.4 = 2^15.4 ~ $43K by 2021

A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.

Since this argument only takes into account commodity hardware and not instruction set improvements (e.g., ARM 8 specifies a SHA-1 instruction), other commodity computing devices with even greater processing power (e.g., GPUs), and custom hardware, the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests.