At this week’s Crypto 2004 conference in California, several papers were presented that demonstrated vulnerabilities in algorithms that are often used to create digital signatures. Although the results are preliminary, many in the security community are concerned about what such weaknesses might mean for digital signature use in the future.
The algorithms in question are MD5, with is often used with digital signatures, as well as SHA-0 and SHA-1, both popular in security development.
Even though there is buzz about the reports, there is not much shock, said Steve Mathews, CEO of security firm ArticSoft and one of the authors of BS ISO/IEC 17799 Code of Practice for Information Security Management.
In an interview with LinuxInsider, Mathews stated, “I am not surprised by the news on MD5. There have been concerns in the technical communities for some time that there could be a weakness, and SHA-1 has been preferred.”
He added that the implications for SHA-0 and SHA-1 are definitely a concern.
Unveiling the Weaknesses
The round of vulnerability announcements started on Thursday, when a French computer scientist, Antoine Joux, discussed a flaw he had found in MD5. Invented in 1991, MD5 has not had a reported vulnerability before.
The announcement immediately sparked concern because of the algorithm’s popularity and use with the Apache Web server. Sun Microsystems also uses MD5 in its Fingerprint Database product.
Mathews noted that his company’s products only use SHA-1, but has to accept signatures using MD5 as well. He said, “We will likely have to include a ‘health warning’ for MD5 going forward.”
Two more announcements, from Chinese and Israeli researchers, identified ways to circumvent security in SHA-0, and early results with vulnerabilities in SHA-1.
Certified by the National Institute of Standards and Technology in 1992, SHA-1 is used in programs like PGP and SSL, as well as in the U.S. government’s Digital Signature Standard.
The conference’s reports have prompted organizers to develop a Webcast on the topic of hash collisions, which will present additional findings.
Sign of the Times
The results of the announcements for the future of digital signatures is not yet known, but Stanford University security researcher Neil Daswani told LinuxInsider that “digital signature schemes will have to be modified to use other hash functions, if good candidates are available.”
Researchers and developers might have some time to investigate such avenues, noted Mathews.
“As far as digital signatures are concerned, there are no indications that the SHA-based ones will become unreliable and we have to abandon current technologies, although it would be sensible to start looking for a new technique,” he said.
Although MD5 and SHA-1 are popular, Daswani said many other hash algorithms have been proposed. It is likely that given the recent announcements, researchers will begin investigating these algorithms to discover new sources of security.
In general, programming is unlikely to be affected by vulnerabilities found in a few hash functions, according to Daswani. “However,” he said, “the topic of developing secure hash functions may become more active in the security research community.”
Mathews added that programmers will have to face the realization that a new, previously unknown attack against an algorithm scheme has been found, and progress from there. That could affect programming more broadly.
“That means designing systems where we can quickly add in new and dump out old,” said Mathews. “There also needs to be a management system in place that allows this to happen.”
He noted that such a system currently goes against most of the regulations governing the export of cryptography, which do not allow the customer to change algorithms that have been implemented. Changing the situation would allow for moving everyone affected by scheme breakdowns to move over to a new scheme quickly, cleanly and safely, said Mathews.
Such issues will likely be addressed in coming months as security researchers explore the implications of the conference’s announcements more fully. “It’s a bit like having Y2K again, with a bigger threat and less time to fix it,” Mathews noted.
There is an error in attribution. Antoine Joux broke SHA-0, Xiaoyun Wang et al. broke MD5 (as well as RIPEMD, HAVAL-128, and for kicks, they simplified MD4 collisions to the point where they can be calculated by hand).