MD6

Last updated
MD6
General
Designers Ronald Rivest, Benjamin Agre, Dan Bailey, Sarah Cheng, Christopher Crutchfield, Yevgeniy Dodis, Kermin Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Eran Tromer, Yiqun Lisa Yin
First published2008
Series MD2, MD4, MD5, MD6
Detail
Digest sizes Variable, 0<d≤512 bits
StructureMerkle tree
Rounds Variable. Default, Unkeyed=40+[d/4], Keyed=max(80,40+(d/4)) [1]
Best public cryptanalysis
Key-recovery attack of a 14-round MD6 function in 222 operations. [2]

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. [3] The source code of the reference implementation was released under MIT license. [4]

Contents

Speeds in excess of 1 GB/s have been reported to be possible for long messages on 16-core CPU architecture. [1]

In December 2008, Douglas Held of Fortify Software discovered a buffer overflow in the original MD6 hash algorithm's reference implementation. This error was later made public by Ron Rivest on 19 February 2009, with a release of a corrected reference implementation in advance of the Fortify Report. [5]

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, [6] although Rivest also stated at the MD6 website that it is not withdrawn formally. [7] 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 [8] was posted to the MD6 website. [9]

MD6 hash test vectors

MD6("The quick brown fox jumps over the lazy dog") =   977592608c45c9923340338450fdcccc21a68888e1e6350e133c5186cd9736ee

A change in even a single bit of the message will, with overwhelming probability, result in a completely different message digest due to the avalanche effect:

MD6("The quick brown fox jumps over the lazy cog") =   85fe717a5896a085a31be5d9457b4da75a6ebc003eded96d7cb0ff1737235bba

The hash of the zero-length string is:

MD6("") = bca38b24a804aa37d821d31af00f5598230122c5bbfc4c4ad5ed40e4258f04ca

See also

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications authentication algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1995 for efficiency on 64-bit platforms. The size of a Tiger hash value is 192 bits. Truncated versions can be used for compatibility with protocols assuming a particular hash size. Unlike the SHA-2 family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.

<span class="mw-page-title-main">MD4</span> Cryptographic hash function

The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest".

The MD2 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1989. The algorithm is optimized for 8-bit computers. MD2 is specified in IETF RFC 1319. The "MD" in MD2 stands for "Message Digest".

<span class="mw-page-title-main">Nothing-up-my-sleeve number</span> Numbers used by cryptographers to show that they are working in good faith

In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes. The cryptographer may wish to pick these values in a way that demonstrates the constants were not selected for a nefarious purpose, for example, to create a backdoor to the algorithm. These fears can be allayed by using numbers created in a way that leaves little room for adjustment. An example would be the use of initial digits from the number π as the constants. Using digits of π millions of places after the decimal point would not be considered trustworthy because the algorithm designer might have selected that starting point because it created a secret weakness the designer could later exploit—though even with natural-seeming selections, enough entropy exists in the possible choices that the utility of these numbers has been questioned.

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

<span class="mw-page-title-main">RadioGatún</span> Cryptographic hash primitive

RadioGatún is a cryptographic hash primitive created by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. It was first publicly presented at the NIST Second Cryptographic Hash Workshop, held in Santa Barbara, California, on August 24–25, 2006, as part of the NIST hash function competition. The same team that developed RadioGatún went on to make considerable revisions to this cryptographic primitive, leading to the Keccak SHA-3 algorithm.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

The NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally announced in the Federal Register on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES)." The competition ended on October 2, 2012, when NIST announced that Keccak would be the new SHA-3 hash algorithm.

SHA-3 is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like structure of SHA-1 and SHA-2.

Grøstl is a cryptographic hash function submitted to the NIST hash function competition by Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses the same S-box as AES in a custom construction. The authors claim speeds of up to 21.4 cycles per byte on an Intel Core 2 Duo, and 9.6 cycles/byte on an Intel i7 with AES-NI.

JH is a cryptographic hash function submitted to the NIST hash function competition by Hongjun Wu. Though chosen as one of the five finalists of the competition, in 2012 JH ultimately lost to NIST hash candidate Keccak. JH has a 1024-bit state, and works on 512-bit input blocks. Processing an input block consists of three steps:

  1. XOR the input block into the left half of the state.
  2. Apply a 42-round unkeyed permutation (encryption function) to the state. This consists of 42 repetitions of:
    1. Break the input into 256 4-bit blocks, and map each through one of two 4-bit S-boxes, the choice being made by a 256-bit round-dependent key schedule. Equivalently, combine each input block with a key bit, and map the result through a 5→4 bit S-box.
    2. Mix adjacent 4-bit blocks using a maximum distance separable code over GF(24).
    3. Permute 4-bit blocks so that they will be adjacent to different blocks in following rounds.
  3. XOR the input block into the right half of the state.

The following outline is provided as an overview of and topical guide to cryptography:

BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

SipHash is an add–rotate–xor (ARX) based family of pseudorandom functions created by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, in response to a spate of "hash flooding" denial-of-service attacks (HashDoS) in late 2011.

Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. It is of interest as a type of post-quantum cryptography.

References

  1. 1 2 Ronald L. Rivest; et al. "The MD6 Hash Function" (PDF). Archived from the original (PDF) on 2017-08-12. Retrieved 2024-01-29.
  2. ↑ Aumasson, Jean-Philippe; Dinur, Itai; Meier, Willi; Shamir, Adi (2009). "Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium". Fast Software Encryption. Vol. 5665. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 1–22. doi:10.1007/978-3-642-03317-9_1. ISBN   978-3-642-03316-2.
  3. ↑ Ronald L. Rivest. "The MD6 hash function A proposal to NIST for SHA-3". Archived from the original on 2020-11-09. Retrieved 2008-10-07. (Microsoft PowerPoint file)
  4. ↑ readme.txt
  5. ↑ "Fortify-SHA-3-Report" (PDF). Archived from the original (PDF) on 2012-02-22.
  6. ↑ Rivest, Ronald (July 1, 2009). "OFFICIAL COMMENT: MD6" . Retrieved September 27, 2011.
  7. ↑ Schneier, Bruce (July 1, 2009). "MD6 Withdrawn from SHA-3 Competition" . Retrieved July 9, 2009.
  8. ↑ Heilman, Ethan (July 10, 2011). "Restoring the Differential Resistance of MD6" . Retrieved September 27, 2011.
  9. ↑ Heilman, Ethan (September 2011). "Improved Differential Analysis" . Retrieved September 27, 2011.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.