The Cost of Creating Collisions Using SHA-1

SHA-1 is a cryptographic hash algorithm that is most commonly used today in TLS/SSL certificates on the Internet. It has almost completely replaced older algorithms like MD2, MD4 and MD5, which were phased out when practical attacks against those algorithms became widely known.

If you do a simple web search, you’ll find a number of online services that claim to “crack” SHA-1 and other hash functions. These generally use a computer’s CPU to build and search through a rainbow table, which contains the hash value that results from a number of expected inputs, and allows you to “reverse” the hash algorithm. Give them a hash value and they will look in their table to see if they have the input that resulted in that hash value. If they haven’t pre-computed the hash value for the data you’re looking for, they won’t find anything. They’re intended as password recovery services, since many user authentication systems store the hash values of passwords rather than the passwords themselves. Many years ago, we thought this was safe since good hash functions were considered irreversible (if someone has the hash value without the corresponding input, they can’t reverse the algorithm to recover the input), and computers didn’t have enough memory or storage to save and process large rainbow tables. Today, rainbow tables are commonly used to associate hash values with passwords and vice versa.

Once the security industry understood how rainbow tables could be used to reverse a hash, we responded by introducing the concept of “salting”. Instead of just hashing a password, one would pick a pseudo-random number, attach it to the start of the password, and then hash the resulting combination. If one was careful to use a different pseudo-random number for each hashed password, one could defeat rainbow tables, since it wouldn’t be possible to build rainbow tables for all combinations of salt and expected password values.

Clearly, these rainbow table-based services can’t be used to crack the hash on a certificate, and generate another certificate that hashed to the same value as a target certificate. The best known attack is a brute-force attack, where you simply try all combinations (or as many as possible, until you give up). To effectively carry out that kind of attack, you really need special hardware to perform brute-force guessing.

Hardware to the Rescue

Initially, graphics processing units (GPUs) were used to achieve a much higher number of guesses-per-second since a GPU can be reprogrammed to run any kind of attack code. (This article explains why GPUs are faster than the CPUs in typical computers.) A researcher once used an Amazon GPU cluster to carry out such an attack, and specialized machines can also be used to find SHA-1 collisions.

Since so many brute-force guesses need to be tried to crack SHA-1, researchers (and probably attackers) moved on to try Field Programmable Gate Arrays (FPGAs). These can be incredibly fast, for example this Bitcoin miner. One downside of these devices is that they are generally built for a specific purpose, so a device based on an FPGA built for BitCoin mining (that performs SHA-2 hashes) would have to be reprogrammed to handle SHA-1.

Still faster are chips known as Application Specific Integrated Circuits (ASICs). This machine, for example, uses ASICs to mine Bitcoins. Like FPGAs, an ASIC is not reprogrammable.

SHA-1 hashes take less time to compute than SHA-256 hashes, but not much less: a SHA-1 hash can be done in around 70% of the time it takes to compute a SHA-256 hash. That means that an FPGA reprogrammed to do SHA-1 hashes can perform around 1.4 times as many SHA-1 hashes as its SHA-256 rating.

The take-away is that we have today a number of extremely powerful, relatively low-cost options for attempting a brute-force SHA-1 collision, and they’ll just get better and cheaper over time.

Why Should Anyone Care?

Nearly two years ago, noted cryptographer Bruce Schneier opined on when we’ll see a brute-force SHA-1 collision:[blockquote style=”3″]“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.”[/blockquote]