MD6
Encyclopedia
The MD6 Message-Digest Algorithm is a cryptographic hash function
. It uses a Merkle tree-like structure to allow for immense parallel computation of hashes for very long inputs. Authors claim a performance of 28 cycles per byte
for MD6-256 on an Intel Core 2 Duo and provable resistance against differential cryptanalysis
.
Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture.
The design of Merkle tree is based on the claims from Intel describing the future of hardware processors with tens and thousands of cores instead of the conventional uni-core systems. With this in mind, Merkle tree hash structures exploit full potential of such hardware while being appropriate for current uni/dual core architectures.
In December 2008, a researcher at Fortify Software
discovered a buffer overflow
in the original MD6 hash algorithm's reference implementation. This error was later made public by professor Ron Rivest
on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report.
MD6 was submitted to the NIST SHA-3 competition
. However, on July 1, 2009, Rivest posted a comment at NIST that MD6 is not yet ready to be a candidate for SHA-3 because of speed issues, a "gap in the proof that the submitted version of MD6 is resistant to differential attacks", and an inability to supply such a proof for a faster reduced-round version, although Rivest also stated at MD6 web site that it is not withdrawn formally. MD6 did not advance to the second round of the SHA-3 competition. In September 2011, a paper presenting an improved proof that MD6 and faster reduced-round versions are resistant to differential attacks was posted to the MD6 website.
The algorithm's first known production use was in the Conficker.B
worm in December 2008; the worm's authors subsequently updated Conficker with the corrected implementation once the buffer overflow vulnerability became known.
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
. It uses a Merkle tree-like structure to allow for immense parallel computation of hashes for very long inputs. Authors claim a performance of 28 cycles per byte
Cycles per byte
Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....
for MD6-256 on an Intel Core 2 Duo and provable resistance against differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
.
Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture.
The design of Merkle tree is based on the claims from Intel describing the future of hardware processors with tens and thousands of cores instead of the conventional uni-core systems. With this in mind, Merkle tree hash structures exploit full potential of such hardware while being appropriate for current uni/dual core architectures.
In December 2008, a researcher at Fortify Software
Fortify Software
Fortify Software is a San Mateo, California-based software vendor. The company was founded in 2003 and provides products that identify and remove security vulnerabilities from software applications. Its initial funding was provided by Kleiner, Perkins, Caufield & Byers. In September, 2010, the...
discovered a buffer overflow
Buffer overflow
In computer security and programming, a buffer overflow, or buffer overrun, is an anomaly where a program, while writing data to a buffer, overruns the buffer's boundary and overwrites adjacent memory. This is a special case of violation of memory safety....
in the original MD6 hash algorithm's reference implementation. This error was later made public by professor Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report.
MD6 was submitted to the NIST SHA-3 competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
. However, on July 1, 2009, Rivest posted a comment at NIST that MD6 is not yet ready to be a candidate for SHA-3 because of speed issues, a "gap in the proof that the submitted version of MD6 is resistant to differential attacks", and an inability to supply such a proof for a faster reduced-round version, although Rivest also stated at MD6 web site that it is not withdrawn formally. MD6 did not advance to the second round of the SHA-3 competition. In September 2011, a paper presenting an improved proof that MD6 and faster reduced-round versions are resistant to differential attacks was posted to the MD6 website.
The algorithm's first known production use was in the Conficker.B
Conficker
Conficker, also known as Downup, Downadup and Kido, is a computer worm targeting the Microsoft Windows operating system that was first detected in November 2008...
worm in December 2008; the worm's authors subsequently updated Conficker with the corrected implementation once the buffer overflow vulnerability became known.