NIST hash function competition

Last updated

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. [1] "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)." [2] The competition ended on October 2, 2012, when NIST announced that Keccak would be the new SHA-3 hash algorithm. [3]

Contents

The winning hash function has been published as NIST FIPS 202 the "SHA-3 Standard", to complement FIPS 180-4, the Secure Hash Standard .

The NIST competition has inspired other competitions such as the Password Hashing Competition.

Process

Submissions were due October 31, 2008 and the list of candidates accepted for the first round was published on December 9, 2008. [4] NIST held a conference in late February 2009 where submitters presented their algorithms and NIST officials discussed criteria for narrowing down the field of candidates for Round 2. [5] The list of 14 candidates accepted to Round 2 was published on July 24, 2009. [6] Another conference was held on August 23–24, 2010 (after CRYPTO 2010) at the University of California, Santa Barbara, where the second-round candidates were discussed. [7] The announcement of the final round candidates occurred on December 10, 2010. [8] On October 2, 2012, NIST announced its winner, choosing Keccak, created by Guido Bertoni, Joan Daemen, and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP. [3]

Entrants

This is an incomplete list of known submissions. NIST selected 51 entries for round 1. [4] 14 of them advanced to round 2, [6] from which 5 finalists were selected.

Winner

The winner was announced to be Keccak on October 2, 2012. [9]

Finalists

NIST selected five SHA-3 candidate algorithms to advance to the third (and final) round: [10]

NIST noted some factors that figured into its selection as it announced the finalists: [11]

NIST has released a report explaining its evaluation algorithm-by-algorithm. [12] [13] [14]

Did not pass to final round

The following hash function submissions were accepted for round two, but did not make it to the final round. As noted in the announcement of the finalists, "none of these candidates was clearly broken".

Did not pass to round two

The following hash function submissions were accepted for round one but did not pass to round two. They have neither been conceded by the submitters nor have had substantial cryptographic weaknesses. However, most of them have some weaknesses in the design components, or performance issues.

Entrants with substantial weaknesses

The following non-conceded round one entrants have had substantial cryptographic weaknesses announced:

Conceded entrants

The following round one entrants have been officially retracted from the competition by their submitters; they are considered broken according to the NIST official round one candidates web site. [54] As such, they are withdrawn from the competition.

Rejected entrants

Several submissions received by NIST were not accepted as first-round candidates, following an internal review by NIST. [4] In general, NIST gave no details as to why each was rejected. NIST also has not given a comprehensive list of rejected algorithms; there are known to be 13, [4] [68] but only the following are public.

See also

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications hash 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.

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:

Joan Daemen is a Belgian cryptographer who co-designed with Vincent Rijmen the Rijndael cipher, which was selected as the Advanced Encryption Standard (AES) in 2001. More recently, he co-designed the Keccak cryptographic hash, which was selected as the new SHA-3 hash by NIST in October 2012. He has also designed or co-designed the MMB, Square, SHARK, NOEKEON, 3-Way, and BaseKing block ciphers. In 2017 he won the Levchin Prize for Real World Cryptography "for the development of AES and SHA3". He describes his development of encryption algorithms as creating the bricks which are needed to build the secure foundations online.

The Secure Hash Algorithms are a family of cryptographic hash functions published by the National Institute of Standards and Technology (NIST) as a U.S. Federal Information Processing Standard (FIPS), including:

<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.

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.

FORK-256 is a hash algorithm designed in response to security issues discovered in the earlier SHA-1 and MD5 algorithms. After substantial cryptanalysis, the algorithm is considered broken.

<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.

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

<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.

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.

The SANDstorm hash is a cryptographic hash function designed in 2008 by Mark Torgerson, Richard Schroeppel, Tim Draelos, Nathan Dautenhahn, Sean Malone, Andrea Walker, Michael Collins, and Hilarie Orman for the NIST SHA-3 competition.

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

In cryptography, rotational cryptanalysis is a generic cryptanalytic attack against algorithms that rely on three operations: modular addition, rotation and XOR — ARX for short. Algorithms relying on these operations are popular because they are relatively cheap in both hardware and software and run in constant time, making them safe from timing attacks in common implementations.

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.

<span class="mw-page-title-main">Sponge function</span> Theory of cryptography

In cryptography, a sponge function or sponge construction is any of a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length. Sponge functions have both theoretical and practical uses. They can be used to model or implement many cryptographic primitives, including cryptographic hashes, message authentication codes, mask generation functions, stream ciphers, pseudo-random number generators, and authenticated encryption.

Gilles Van Assche is a Belgian cryptographer who co-designed the Keccak cryptographic hash, which was selected as the new SHA-3 hash by NIST in October 2012. The SHA-3 standard was released by NIST on August 5, 2015.

<span class="mw-page-title-main">EnRUPT</span>

EnRUPT is a block cipher and a family of cryptographic algorithms based on XXTEA. EnRUPT hash function was submitted to SHA-3 competition but it wasn't selected to the second round.

Dmitry Khovratovich is a cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research. He developed, together with Alex Biryukov, the Equihash proof-of-work algorithm which is currently being used as consensus mechanism for the Zcash cryptocurrency, and the Argon2 key derivation function, which won the Password Hashing Competition in July 2015.

References

  1. ↑ "Federal Register / Vol. 72, No. 212" (PDF). Federal Register. Government Printing Office. November 2, 2007. Retrieved November 6, 2008.
  2. ↑ "cryptographic hash project – Background Information". Computer Security Resource Center. National Institute of Standards and Technology. November 2, 2007. Retrieved November 6, 2008.
  3. 1 2 "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. October 2, 2012. Retrieved October 2, 2012.
  4. 1 2 3 4 5 6 7 8 9 10 11 "Round 1". December 9, 2008. Retrieved December 10, 2008.
  5. ↑ National Institute of Standards and Technology (December 9, 2008). "The First SHA-3 Candidate Conference" . Retrieved December 23, 2008.
  6. 1 2 "Second Round Candidates". National Institute for Standards and Technology. July 24, 2009. Retrieved July 24, 2009.
  7. ↑ National Institute of Standards and Technology (June 30, 2010). "The Second SHA-3 Candidate Conference".
  8. ↑ "Tentative Timeline of the Development of New Hash Functions". NIST. December 10, 2008. Retrieved September 15, 2009.
  9. ↑ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
  10. ↑ Third (Final) Round Candidates Retrieved 9 Nov 2011
  11. ↑ SHA-3 Finalists Announced by NIST Archived July 9, 2011, at the Wayback Machine , blog post quoting NIST's announcement in full.
  12. ↑ Status Report on the first round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF).
  13. ↑ Status Report on the second round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011
  14. ↑ Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition (PDF).
  15. ↑ Svein Johan Knapskog; Danilo Gligoroski; Vlastimil Klima; Mohamed El-Hadedy; Jørn Amundsen; Stig Frode Mjølsnes (November 4, 2008). "blue_midnight_wish" . Retrieved November 10, 2008.
  16. ↑ Søren S. Thomsen (2009). "Pseudo-cryptanalysis of Blue Midnight Wish" (PDF). Archived from the original (PDF) on September 2, 2009. Retrieved May 19, 2009.
  17. ↑ Henri Gilbert; Ryad Benadjila; Olivier Billet; Gilles Macario-Rat; Thomas Peyrin; Matt Robshaw; Yannick Seurin (October 29, 2008). "SHA-3 Proposal: ECHO" (PDF). Retrieved December 11, 2008.
  18. ↑ Özgül Kücük (October 31, 2008). "The Hash Function Hamsi" (PDF). Retrieved December 11, 2008.
  19. ↑ Dai Watanabe; Christophe De Canniere; Hisayoshi Sato (October 31, 2008). "Hash Function Luffa: Specification" (PDF). Retrieved December 11, 2008.
  20. ↑ Jean-François Misarsky; Emmanuel Bresson; Anne Canteaut; Benoît Chevallier-Mames; Christophe Clavier; Thomas Fuhr; Aline Gouget; Thomas Icart; Jean-François Misarsky; Marìa Naya-Plasencia; Pascal Paillier; Thomas Pornin; Jean-René Reinhard; Céline Thuillet; Marion Videau (October 28, 2008). "Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition" (PDF). Retrieved December 11, 2008.
  21. ↑ Eli Biham; Orr Dunkelman. "The SHAvite-3 Hash Function" (PDF). Retrieved December 11, 2008.
  22. ↑ Jongin Lim; Donghoon Chang; Seokhie Hong; Changheon Kang; Jinkeon Kang; Jongsung Kim; Changhoon Lee; Jesang Lee; Jongtae Lee; Sangjin Lee; Yuseop Lee; Jaechul Sung (October 29, 2008). "ARIRANG" (PDF). Retrieved December 11, 2008.
  23. ↑ Philip Hawkes; Cameron McDonald (October 30, 2008). "Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms" (PDF). Retrieved November 11, 2008.
  24. ↑ Jacques Patarin; Louis Goubin; Mickael Ivascot; William Jalby; Olivier Ly; Valerie Nachef; Joana Treger; Emmanuel Volte. "CRUNCH". Archived from the original on January 29, 2009. Retrieved November 14, 2008.
  25. ↑ Hirotaka Yoshida; Shoichi Hirose; Hidenori Kuwakado (October 30, 2008). "SHA-3 Proposal: Lesamnta" (PDF). Retrieved December 11, 2008.
  26. ↑ Kerem Varıcı; Onur Özen; Çelebi Kocair. "The Sarmal Hash Function". Archived from the original on June 11, 2011. Retrieved October 12, 2010.
  27. ↑ Daniel Penazzi; Miguel Montes. "The TIB3 Hash" (PDF). Retrieved November 29, 2008.[ permanent dead link ]
  28. ↑ Tetsu Iwata; Kyoji Shibutani; Taizo Shirai; Shiho Moriai; Toru Akishita (October 31, 2008). "AURORA: A Cryptographic Hash Algorithm Family" (PDF). Retrieved December 11, 2008.
  29. ↑ Niels Ferguson; Stefan Lucks (2009). "Attacks on AURORA-512 and the Double-MIX Merkle–Damgård Transform" (PDF). Retrieved July 10, 2009.
  30. ↑ Colin Bradbury (October 25, 2008). "BLENDER: A Proposed New Family of Cryptographic Hash Algorithms" (PDF). Retrieved December 11, 2008.
  31. ↑ Craig Newbold. "Observations and Attacks On The SHA-3 Candidate Blender" (PDF). Retrieved December 23, 2008.
  32. ↑ Florian Mendel. "Preimage Attack on Blender" (PDF). Retrieved December 23, 2008.
  33. ↑ Dmitry Khovratovich; Alex Biryukov; Ivica Nikolić (October 30, 2008). "The Hash Function Cheetah: Specification and Supporting Documentation" (PDF). Retrieved December 11, 2008.
  34. ↑ Danilo Gligoroski (December 12, 2008). "Danilo Gligoroski – Cheetah hash function is not resistant against length-extension attack" . Retrieved December 21, 2008.
  35. ↑ Zijie Xu. "Dynamic SHA" (PDF). Retrieved December 11, 2008.
  36. ↑ Vlastimil Klima (December 14, 2008). "Dynamic SHA is vulnerable to generic attacks" . Retrieved December 21, 2008.
  37. ↑ Zijie Xu. "Dynamic SHA2" (PDF). NIST. Retrieved December 11, 2008.
  38. ↑ Vlastimil Klima (December 14, 2008). "Dynamic SHA2 is vulnerable to generic attacks" . Retrieved December 21, 2008.
  39. ↑ Danilo Gligoroski; Rune Steinsmo Ødegård; Marija Mihova; Svein Johan Knapskog; Ljupco Kocarev; Aleš Drápal (November 4, 2008). "edon-r" . Retrieved November 10, 2008.
  40. ↑ Dmitry Khovratovich; Ivica Nikolić; Ralf-Philipp Weinmann (2008). "Cryptanalysis of Edon-R" (PDF). Retrieved July 10, 2009.
  41. ↑ Sean O'Neil; Karsten Nohl; Luca Henzen (October 31, 2008). "EnRUPT – The Simpler The Better" . Retrieved November 10, 2008.
  42. ↑ Sebastiaan Indesteege (November 6, 2008). "Collisions for EnRUPT". Archived from the original on February 18, 2009. Retrieved November 7, 2008.
  43. ↑ Jason Worth Martin (October 21, 2008). "ESSENCE: A Candidate Hashing Algorithm for the NIST Competition" (PDF). Archived from the original (PDF) on June 12, 2010. Retrieved November 8, 2008.
  44. ↑ "Cryptanalysis of ESSENCE" (PDF).
  45. ↑ Ivica Nikolić; Alex Biryukov; Dmitry Khovratovich. "Hash family LUX – Algorithm Specifications and Supporting Documentation" (PDF). Retrieved December 11, 2008.
  46. ↑ Mikhail Maslennikov. "MCSSHA-3 hash algorithm". Archived from the original on May 2, 2009. Retrieved November 8, 2008.
  47. ↑ Jean-Philippe Aumasson; María Naya-Plasencia. "Second preimages on MCSSHA-3" (PDF). Retrieved November 14, 2008.[ permanent dead link ]
  48. ↑ Peter Maxwell (September 2008). "The Sgàil Cryptographic Hash Function" (PDF). Archived from the original (PDF) on November 12, 2013. Retrieved November 9, 2008.
  49. ↑ Peter Maxwell (November 5, 2008). "Aww, p*sh!". Archived from the original on November 9, 2008. Retrieved November 6, 2008.
  50. ↑ Michael Gorski; Ewan Fleischmann; Christian Forler (October 28, 2008). "The Twister Hash Function Family" (PDF). Retrieved December 11, 2008.
  51. ↑ Florian Mendel; Christian Rechberger; Martin Schläffer (2008). "Cryptanalysis of Twister" (PDF). Retrieved May 19, 2009.
  52. ↑ Michael Kounavis; Shay Gueron (November 3, 2008). "Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication" . Retrieved November 11, 2008.
  53. ↑ Jean-Philippe Aumasson; Orr Dunkelman; Florian Mendel; Christian Rechberger; Søren S. Thomsen (2009). "Cryptanalysis of Vortex" (PDF). Retrieved May 19, 2009.
  54. ↑ Computer Security Division, Information Technology Laboratory (January 4, 2017). "SHA-3 Project – Hash Functions". CSRC: NIST. Retrieved April 26, 2019.
  55. ↑ Neil Sholer (October 29, 2008). "Abacus: A Candidate for SHA-3" (PDF). Retrieved December 11, 2008.
  56. ↑ Gregory G. Rose. "Design and Primitive Specification for Boole" (PDF). Retrieved November 8, 2008.
  57. ↑ Gregory G. Rose (December 10, 2008). "Official Comment: Boole" (PDF). Retrieved December 23, 2008.
  58. ↑ David A. Wilson (October 23, 2008). "The DCH Hash Function" (PDF). Retrieved November 23, 2008.
  59. ↑ Natarajan Vijayarangan. "A New Hash Algorithm: Khichidi-1" (PDF). Retrieved December 11, 2008.
  60. ↑ Björn Fay. "MeshHash" (PDF). Retrieved November 30, 2008.
  61. ↑ Orhun Kara; Adem Atalay; Ferhat Karakoc; Cevat Manap. "SHAMATA hash function: A candidate algorithm for NIST competition". Archived from the original on February 1, 2009. Retrieved November 10, 2008.
  62. ↑ Michal Trojnara (October 14, 2008). "StreamHash Algorithm Specifications and Supporting Documentation" (PDF). Retrieved December 15, 2008.
  63. ↑ Rafael Alvarez; Gary McGuire; Antonio Zamora. "The Tangle Hash Function" (PDF). Retrieved December 11, 2008.
  64. ↑ John Washburn. "WaMM: A Candidate Algorithm for the SHA-3 Competition" (PDF). Archived from the original (PDF) on April 19, 2009. Retrieved November 9, 2008.
  65. ↑ "Official Comment: WaMM is Withdrawn" (PDFauthor=John Washburn). December 20, 2008. Retrieved December 23, 2008.
  66. ↑ Bob Hattersly (October 15, 2008). "Waterfall Hash – Algorithm Specification and Analysis" (PDF). Retrieved November 9, 2008.
  67. ↑ Bob Hattersley (December 20, 2008). "Official Comment: Waterfall is broken" (PDF). Retrieved December 23, 2008.
  68. ↑ Bruce Schneier (November 19, 2008). "Skein and SHA-3 News" . Retrieved December 23, 2008.
  69. ↑ Robert J. Jenkins Jr. "Algorithm Specification" . Retrieved December 15, 2008.
  70. ↑ Anne Canteaut & María Naya-Plasencia. "Internal collision attack on Maraca" (PDF). Retrieved December 15, 2008.
  71. ↑ Michael P. Frank. "Algorithm Specification for MIXIT: a SHA-3 Candidate Cryptographic Hash Algorithm" (PDF). Archived from the original (PDF) on March 4, 2016. Retrieved January 12, 2014.
  72. ↑ Geoffrey Park. "NKS 2D Cellular Automata Hash" (PDF). Retrieved November 9, 2008.
  73. ↑ Cristophe De Cannière (November 13, 2008). "Collisions for NKS2D-224" . Retrieved November 14, 2008.
  74. ↑ Brandon Enright (November 14, 2008). "Collisions for NKS2D-512" . Retrieved November 14, 2008.
  75. ↑ Peter Schmidt-Nielsen. "Ponic" (PDF). Retrieved November 9, 2008.
  76. ↑ María Naya-Plasencia. "Second preimage attack on Ponic" (PDF). Retrieved November 30, 2008.
  77. ↑ Nicolas T. Courtois; Carmi Gressel; Avi Hecht; Gregory V. Bard; Ran Granot. "ZK-Crypt Homepage". Archived from the original on February 9, 2009. Retrieved March 1, 2009.
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.