SHA1 crypto algorithm underpinning Internet security could f
Source: Dan Goodin
The principle of detecting near-collisions in cryptographic algorithms such as MD5 and SHA1.
Marc Stevens
A widely used cryptographic algorithm used to secure sensitive websites, software, and corporate servers is weak enough that well-financed criminals could crack it in the next six years, a cryptographer said.
The prediction about the SHA1 algorithm, posted recently to a hash function mailing list sponsored by the National Institute of Standards and Technology, is based on calculations its author and fellow cryptographers admit are rough. The back-of-the-envelope math also incorporates several assumptions that are by no means certain. At the same time, the ability to carry out a reliable "collision attack" on SHA1 would have catastrophic effects on the security of the Internet.
Similar collision attacks on the weaker MD5 algorithm provide an example of how dire and widespread the resulting harm could be. The Flame espionage malware, which the US and Israel are believed to have unleashed to spy on sensitive Iranian networks, wielded such an exploit to hijack Microsoft's Windows Update mechanism so the malicious program could spread from computer to computer inside an infected network. Separately, in 2008, a team of computer scientists and security researchers used the technique to forge a master secure sockets layer certificate that could authenticate virtually any website of their choosing.
SHA1 is considerably more resistant than MD5 to collision attacks, in which two different plaintext sources generate the same ciphertext, or digital signature. As a result, SSL certificate authorities, software companies, and most other security-minded organizations have discontinued use of MD5 in favor of SHA1, or better yet SHA2, which is believed to be stronger still. (Just this week, NIST designated an algorithm known as Keccak to be SHA3.) Cryptographers have long presumed these more advanced algorithms will suffer the same fate as MD5, as computers' processing speeds become ever faster. With SHA1 a staple in digital certificates that certify the authenticity of websites, commercial software, and credentials used to administer corporate servers, a practical attack on it anytime soon would come with dire consequences.
"When it does happen, it's going to be a disaster, because SHA1 is everywhere," said Matthew Green, a professor specializing in cryptography at Johns Hopkins University. "You could be Microsoft, you could be Google, if you were able to get an attack on SHA1."
Some provisions mandated by the Federal Information Processing Standard currently require the use of SHA1.
SHA1 and other hash algorithms generate a digital fingerprint that in theory is unique for each different file or text input they sign. When the underlying plaintext is altered in even miniscule ways, the signature changes. The algorithms are used cryptographically to prove that no unauthorized changes have been made to websites or software code. Collision attacks undermine this assurance by allowing attackers to forge the cryptographic signatures provided by the algorithm.
Based on the rough calculations of Jesse Walker, an Intel employee and a designer of a SHA3 runner-up algorithm known as Skein, SHA1 may fall sooner than many expected. He reached that conclusion based on the continuing growth of computing speed and the advent of cloud services such as Amazon's EC2, which allow people to rent commodity servers for as little as 4 cents per hour.
"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, according to a transcript included in a blog post by fellow cryptographer Bruce Schneier. Walker went on to say his assumptions didn't take into consideration the use of graphical processing units and other optimized hardware, so "the need to transition from SHA-1 for collision resistance functions is probably more urgent than this back-of-the-envelope analysis suggests."
Walker's estimate is also based on the assumption a collision attack exploiting SHA1 would be based on a technique laid out earlier this year by Marc Stevens, a cryptographer from the Centrum Wiskunde & Informatica in Amsterdam. If attackers came up with a more efficient method for bringing about a collision attack―as the world-class cryptographers behind Flame did―that might also be a factor that would accelerate the downfall of SHA1. The estimate also assumes that Moore's Law, the observation that computing speed capacity doubles roughly every 18 months, will continue for the foreseeable future.
"The point is," Schneier concluded, "that we in the community need to start the migration away from SHA-1 and to SHA-2/SHA-3 now."
| }
|