Rivest, MD5’s Creator, RemovesEntry from NIST’s Hash Contest
MD6 Designed for Multicore Machines; Too Slow on Old Hardware
A team lead by Professor Ronald L. Rivest declared this summer that their new cryptographic hashing algorithm, MD6, was not suitable for the National Institute of Standards and Technology’s Secure Hash Algorithm (SHA-3) competition. Because of new performance requirements for the second round of the contest, the MD6 algorithm no longer met NIST’s requirements.
Essentially, hashing algorithms generate a nearly unique number, or hash, from a set of data, such as a file, message, or phrase. The algorithm must ensure that creating another message that has the same hash is extremely difficult. This property plays an important role in the process of digital message signing.
While MD6 passed round one of the competition, Rivest posted an e-mail on July 1, 2009 to the NIST hash competition mailing list explaining that MD6 was not ready for the next round because of a change in NIST’s requirements.
NIST’s competition winner effectively mandates the hashing algorithm trusted by the government until the next NIST hash competition.
Cryptographic hashing algorithms play an important role in ensuring data security. You may have used one while making sure the latest Linux distribution you just downloaded wasn’t corrupted, or if you’ve used a Web site that uses the secure socket layer (SSL, or https), to keep credit card numbers private.
Because of recent attacks on cryptographic hashing algorithms, NIST started the SHA-3 competition in 2007. Many of those attacks are against MD5, the very popular hash algorithm created by Rivest. MD6 is intended as a successor algorithm to MD5.
Eran Tromer, a postdoc at CSAIL and member of the MD6 project, explained that MD6 marked a departure from the construction of previous hashing algorithms, with gains in performance and changes to design methodology.
Tromer said that the computing industry is moving towards parallelized systems — specifically processors with moderate clock speeds, but many cores.
“MD6 is optimized for parallelized execution on such chips, and indeed we have demonstrated high-performance implementations on a 64-core machine using Professor Charles Leiserson’s cilk compiler, as well as Professor Anant Agarwal’s Tile64 chip,” Tromer said.
While performance was a concern with MD6’s design, the MD6 team wanted to avoid the same pitfalls that previous cryptographic hashing algorithms faced.
Tromer said in an e-mail that the security of previous hashing functions “relied, essentially, on intuition about what attacks people may come up with.” “Outsmarting future generations is a tough task and a worrisome prospect. That the old function withstood analysis for many years is an attestation to the ingenuity of their design, but can we do better?”
MD6’s divergence from the old algorithms lies in the use of proofs of resistance to a large number of attacks that previous algorithms were vulnerable to.
Tromer said in an e-mail that “These proofs invoke and extend many techniques developed in the nearly two decades since MD5 … we borrowed techniques from the Rijndael block cipher which won the AES competition,” referring to NIST’s Advanced Encryption Standard competition that ran from 1997–2001.
Unfortunately for the team, the damning factor for MD6 was NIST’s wishes for performance on older, non-parallelized architectures.
Tromer said in an e-mail that the death knell came for MD6’s continuation in the competition “once NIST stated that candidates should match the SHA-2 family in speed on older platforms that lack parallelism; our only way to comply would have been to reduce the amount of message mixing in MD6 by a factor of roughly three, and thus forfeit provable security.”
The team decided that since the proofs formerly constructed wouldn’t hold given these new restrictions, MD6 was not suitable for SHA-3.
The MD6 site asserts that there is a possibility to prove MD6 is suitable for NIST’s performance requirements (http://groups.csail.mit.edu/cis/md6/).
NIST announced the competition in late 2007. SHA-3 competitors had to submit their algorithms for evaluation by Oct. 31, 2008.