It’s been just a few days since NIST approved Keccak as the winner of the SHA-3 competition, and it likely will be some time before we begin seeing the new hash algorithm popping up in common products and services. However, some in the cryptography community say it may not be a bad idea to start making plans to move away from the older SHA-1 algorithm fairly soon, given the quickly dropping cost of compute power.
The SHA family of hash algorithms was introduced nearly 20 years ago and various versions of it have been used as the government’s approved secure hash algorithm since then. The National Institute for Standards and Technology began a search for a replacement algorithm five years ago, and Keccak emerged as the winner this week.
In a message on the mailing list dedicated to the SHA-3 competition, Jesse Walker, a co-author of Skein, one of the finalists in the competition, showed some quick calculations based on the current and future costs of commodity compute power and came up with some interesting conclusions about how soon we might see a practical attack that can produce a hash collision on SHA-1.
First, using a known attack as a starting point and some calculations of how many cycles one can get from a given processor right now, Walker calculated the value of a “commodity server year” as 2^63 cycles/year in 2015 and 2^65 cycles/year in 2018, assuming that Moore’s Law continues to hold true for the next decade or so. He then computed the number of such years it would take to carry out the Stevens attack and found that by 2015 it would take 2^11 commodity server years to execute the attack.
In 2018 the time needed for the attack could be as little as 2^7 commodity server years. That’s a major decrease in the amount of time needed for a complex attack, and as Walker pointed out in his message, could put the attack within reach of some well-funded attackers within a few years.
Given that Amazon charges about $0.04 per hour to rent time on a commodity server, Walker estimates that the monetary cost of this attack would be about $173,000 by 2018, assuming again that Moore’s Law remains valid. The cost could drop to $43,000 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,” Walker wrote in the message, which Bruce Schneier, also a co-author of Skein, published on his blog, Schneier on Security.
SHA-1 is the older of the two SHA versions still in use and there are several known attacks against that have been published over the years. SHA-1 was phased out in favor of the stronger SHA-2 several years ago. Schneier said in his post that the calculations Walker provides should show that now is the time to move away from any remaining SHA-1 implementations.
“The point is that we in the community need to start the migration away from SHA-1 and to SHA-2/SHA-3 now,” he wrote.
