Security elite hash out encryption alternatives

At this week’s Cryptographic Hash Workshop in Washington, DC, the giants of the cryptography field met to discuss the problem of our disintegrating hash algorithms. Today, the security of the algorithms that protect our online banking and digital signature systems is crumbling, and no one has a simple answer to the problem.

The event kicked off with a discussion from Dr. Xiaoyun Wang of China’s Shandong University, whose team’s finding of practical collisions in the MD5 hash algorithm sparked a series of cracking methods that have rendered that algorithm useless for serious security implementations. Earlier this year they turned the cryptography world on its ear when they discovered weaknesses in SHA1 that reduces its protection level from 2^80 to 2^63. One could say that Dr. Wang’s team is largely responsible for this collection of industry and academic giants who have converged on the NIST campus to spend two days talking about what to do with one of our favorite, and now endangered, cryptographic primitives, the hash algorithm.

Following Dr. Wang’s presentation the group discussed the severity of the situation, what alternatives exist, and what guidance to give developers for the near term while the crypto community tries to plug this hole.

Heavy hitters in attendance included Bruce Schneier of Counterpane Security, Niels Ferguson of Microsoft, Whitfield Diffie of Sun Microsystems and co-creator of Diffie-Hellman Key Agreement, Eric Rescorla of TLS/SSL fame, Steven Bellovin of Columbia University, Antoine Joux of DBA and UVSQ, Hugo Krawczyk of IBM Research Center, John Kelsey of NIST and cowriter of Twofish, and Bart Preneel of KUL.

What are hashes?

Cryptographic hashes are one of the cornerstones of modern encryption systems. Bruce Schneier described them as “the workhorse of modern cryptography.” Hashes are one-way mathematical functions that create a cryptographic summary of a message. You feed text into a hash function and it returns a fixed length block of cipher text that cannot be reversed back to the original message. There are many uses for this transformation, including enabling digital signatures, protecting key distribution functions, random number generation, and providing verification for file distribution systems. Hashes are key elements in financial transaction systems, non-repudiation services, host-based intrusion detection systems, and the VPNs many people connect to every day. Everyone who uses the Internet for banking, bill paying, or purchasing is using hashing algorithms as part of the cryptographic web that protects their transactions. Hash algorithms are a key enabling technology for the Internet — the glue that binds crypto-systems together.

The problem in depth

One of the characteristics of a good hash algorithm is the absence of collisions. A collision occurs when you run multiple original messages through a hash function and create the same summary. When this happens, you can no longer trust the algorithm to assure your information’s integrity. Worse yet, attackers can use this weakness to trick your system into thinking dangerous or incorrect information is actually valid. For example, Dr. Wang’s team created two PKI certificates with different information that both hash to the same MD5 summary, and that’s scary.

Until Dr. Wang’s team hit the scene, our leading hash algorithm, SHA1, contained no known weaknesses, offering a designed protection level of 2^80. Over the last couple years, Dr. Wang and her team have discovered vulnerabilities in SHA1 that have reduced its protection level to 2^63. This amount of protection is still outside the brute force abilities of contemporary computers, but two concerns remain. One is the increase in available computing power. We all know that Moore’s Law predicts increases in computational speed by a factor of two every 18 months or so, and the appearance of bot nets well in excess of 1 million machines are moving brute force of a 2^63 key space closer to reality.

The more present danger is the fact that attacks against crypto systems never get worse, they almost always get better. The discovery of any weakness in SHA1 is likely the beginning of a full-scale dismantling of the algorithm. It might not happen next month or next year, but precedent tells us it is coming. As a reference, MD5 was released in 1991 and survived 13 years. SHA1 was released in 1993 and started showing serious weakness 12 years later. Today no one knows how much longer it has.

So what do we do? There are a few options, but none of them stands out as the clear path. Likely a combination of these choices will progress in parallel.

Write a new hash algorithm

There was more than a little talk about NIST sponsoring a contest to develop a new hash algorithm — similar to the contest used to select the Advanced Encryption Standard (AES). Such a contest would likely yield several excellent new hash algorithms, just as the AES contest produced a stable of solid symmetric options (Twofish, Serpent, RC6, MARS). It would be great to have a fast, new, secure hash algorithm with one or two more good alternatives waiting in the wings.

Many of the conference attendees were in favor of having some pre-contest workshops to flesh out criteria that would become requirements for the next generation of hash algorithms. This is a sensible plan, as we want to really dig into what we are creating, how it will be used, and what characteristics are vital to an algorithm we want to use for the longest time possible. Unfortunately, this process takes more time, and our timeline is already getting dangerously short.

The time it takes to develop a new algorithm, bake it into vendor products, and then deploy it to the user community is estimated to be four to eight years. Many people in the crypto community don’t expect SHA1 to hold together much longer than 2010, which is on the short side of that window. If we’re going to go this route, we’d better giddyup. Expect to see movement in this area in the near future.

Use an existing algorithm that provides better protection

In the SHA algorithm family we still have some firepower. SHA1’s big brother, SHA256, is looking good as a possible replacement for the near term. SHA256 offers much greater security than its ailing predecessor, having a designed protection factor of 2^128 which has stood up to cryptanalysis. While SHA256 isn’t perfect, it is Johnny on the spot in this instance, having good protection and acceptable performance for most tasks, and lacking any other real competitors, especially in the performance area. There are a lot of secure hash algorithms out there but it’s tough to make them fast.

The obvious downside to SHA256 is that it is also based on the SHA family, and cryptanalysts are already making headway into reducing its viability (the first 24 rounds have been bypassed and more are on the way). The good news is many of the current tools for breaking SHA family algorithms have been tried on SHA256 and returned limit results, so we likely have some time before it falls to the same fate as SHA1. New tools and techniques are on the horizon though, so the experts agree that SHA256 is just a bridge to a more robust solution.

One of the hard choices with picking SHA256 as a replacement is the time and expense involved in changing a primary hash algorithm. Vendors will spend huge amounts of time and money on implementing a new algorithm and will not want to make that investment in SHA256 only to find out that they need to do it again in a few years when it starts to fall apart. Complicating matters is SHA256’s 256-bit block size. SHA1 is 160 bits, and there is a good bit of crypto infrastructure out there that was designed to work with 160-bit or smaller hashes. This leads us into our next option….

Fix SHA1

Several speakers presented papers on various techniques to fix the SHA1 algorithm. Most of these focused on strategies for defending against existing attacks. Unfortunately, these repairs tended to have unacceptable performance implications. Ron Rivest offered a dithering plan and Hugo Krawczyk recommended a randomization method, both of which seemed to have promise, but the leading repair idea was truncation.

There was much talk about simply creating a 256-bit hash string with SHA256, and then chopping off (truncating) 96 bits to make a 160-bit string. This will effectively create a hash that is compatible with all the current systems that work with SHA1, but avoid the collisions found in the weaker algorithm. The folks at NIST are keen on this idea, as it spells fast relief with minimal expense. And it’s not a bad idea, especially as a bridge to a more robust solution, but there has been little testing of this truncation and its possible impact on cryptographic strength. While this method seems to make sense intuitively, NIST is hesitant to endorse any system that cannot be supported with a high level of assurance, or that has not been subjected to significant public review. The review is going on now, and truncation may turn out to be a decent stopgap measure.

Advice for developers and administrators

So what do you do if you’re developing a system and need to make a choice on a hash algorithm right now? The guidance from a panel including Niels Ferguson, Steve Bellovin, Hugo Krawczyk, Georg Illies, and James Randell was unanimous: “Don’t commit new sins.” If you’re developing something today, do it with SHA256. Better yet, implement your new application to be “algorithm agile,” meaning plan for the reality that crypto algorithms have a relatively short lifespan and the algorithm you start with will likely become insecure before your application becomes obsolete.

For existing systems the guidance was extended: If you have legacy systems running SHA1, start working on a strategy to change them out over the next few years. And if you still have systems running MD5, run for the hills, because the sky has already fallen.