NIST hash function competition

From HandWiki
Short description: Competition to develop SHA-3


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]

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]

  • BLAKE (Aumasson et al.)
  • Grøstl (Knudsen et al.)
  • JH (Hongjun Wu)
  • Keccak (Keccak team, Daemen et al.)
  • Skein (Schneier et al.)

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

  • Performance: "A couple of algorithms were wounded or eliminated by very large [hardware gate] area requirement – it seemed that the area they required precluded their use in too much of the potential application space."
  • Security: "We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us 'nervous,' even though we knew of no clear attack against the full algorithm."
  • Analysis: "NIST eliminated several algorithms because of the extent of their second-round tweaks or because of a relative lack of reported cryptanalysis – either tended to create the suspicion that the design might not yet be fully tested and mature."
  • Diversity: The finalists included hashes based on different modes of operation, including the HAIFA and sponge function constructions, and with different internal structures, including ones based on AES, bitslicing, and alternating XOR with addition.

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

References

  1. ↑ "Federal Register / Vol. 72, No. 212" (PDF). Federal Register. Government Printing Office. November 2, 2007. http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf. 
  2. ↑ "cryptographic hash project – Background Information". Computer Security Resource Center. National Institute of Standards and Technology. November 2, 2007. http://csrc.nist.gov/groups/ST/hash/index.html. 
  3. ↑ 3.0 3.1 "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. October 2, 2012. https://www.nist.gov/itl/csd/sha-100212.cfm. 
  4. ↑ 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.10 "Round 1". 2008-12-09. http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/index.html. 
  5. ↑ National Institute of Standards and Technology (December 9, 2008). "The First SHA-3 Candidate Conference". http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html. 
  6. ↑ 6.0 6.1 "Second Round Candidates". National Institute for Standards and Technology. July 24, 2009. http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/submissions_rnd2.html. 
  7. ↑ National Institute of Standards and Technology (June 30, 2010). "The Second SHA-3 Candidate Conference". http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/. 
  8. ↑ "Tentative Timeline of the Development of New Hash Functions". NIST. December 10, 2008. http://csrc.nist.gov/groups/ST/hash/timeline.html. 
  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 , 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 (November 4, 2008). "blue_midnight_wish". http://www.item.ntnu.no/people/personalpages/fac/danilog/blue_midnight_wish. 
  16. ↑ Søren S. Thomsen (2009). "Pseudo-cryptanalysis of Blue Midnight Wish" (PDF). http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf. 
  17. ↑ Henri Gilbert; Ryad Benadjila (October 29, 2008). "SHA-3 Proposal: ECHO" (PDF). http://ehash.iaik.tugraz.at/uploads/9/91/Echo.pdf. 
  18. ↑ Özgül Kücük (31 October 2008). "The Hash Function Hamsi" (PDF). http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf. 
  19. ↑ Dai Watanabe; Christophe De Canniere (31 October 2008). "Hash Function Luffa: Specification" (PDF). http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf. 
  20. ↑ Jean-François Misarsky; Emmanuel Bresson (October 28, 2008). "Shabal, a Submission to NIST's Cryptographic Hash Algorithm Competition" (PDF). http://ehash.iaik.tugraz.at/uploads/6/6c/Shabal.pdf. 
  21. ↑ Eli Biham; Orr Dunkelman. "The SHAvite-3 Hash Function" (PDF). http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf. 
  22. ↑ Jongin Lim; Donghoon Chang (October 29, 2008). "ARIRANG" (PDF). http://ehash.iaik.tugraz.at/uploads/2/2c/Arirang.pdf. 
  23. ↑ Philip Hawkes; Cameron McDonald (October 30, 2008). "Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms". http://ehash.iaik.tugraz.at/uploads/2/2c/Chi_submission.pdf. 
  24. ↑ Jacques Patarin; Louis Goubin. "CRUNCH". http://www.voltee.com/crunch/. 
  25. ↑ Hirotaka Yoshida; Shoichi Hirose (30 October 2008). "SHA-3 Proposal: Lesamnta" (PDF). http://ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf. 
  26. ↑ Kerem Varıcı; Onur Özen. "The Sarmal Hash Function". http://homes.esat.kuleuven.be/~kvarici/sarmal_hash.html. 
  27. ↑ Daniel Penazzi; Miguel Montes. "The TIB3 Hash". http://www.famaf.unc.edu.ar/~penazzi/tib3/submitted/Supporting_Documentation/TIB3_Algorithm_Specification.pdf. 
  28. ↑ Tetsu Iwata; Kyoji Shibutani (October 31, 2008). "AURORA: A Cryptographic Hash Algorithm Family" (PDF). http://ehash.iaik.tugraz.at/uploads/b/ba/AURORA.pdf. 
  29. ↑ Niels Ferguson; Stefan Lucks (2009). "Attacks on AURORA-512 and the Double-MIX Merkle–Damgård Transform" (PDF). http://eprint.iacr.org/2009/113.pdf. 
  30. ↑ Colin Bradbury (25 October 2008). "BLENDER: A Proposed New Family of Cryptographic Hash Algorithms" (PDF). http://ehash.iaik.tugraz.at/uploads/5/5e/Blender.pdf. 
  31. ↑ Craig Newbold. "Observations and Attacks On The SHA-3 Candidate Blender" (PDF). http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf. 
  32. ↑ Florian Mendel. "Preimage Attack on Blender" (PDF). http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf. 
  33. ↑ Dmitry Khovratovich; Alex Biryukov (October 30, 2008). "The Hash Function Cheetah: Specification and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/c/ca/Cheetah.pdf. 
  34. ↑ Danilo Gligoroski (2008-12-12). "Danilo Gligoroski – Cheetah hash function is not resistant against length-extension attack". http://ehash.iaik.tugraz.at/uploads/d/d9/Cheetah_length-extension.txt. 
  35. ↑ Zijie Xu. "Dynamic SHA" (PDF). http://ehash.iaik.tugraz.at/uploads/e/e2/DyamicSHA.pdf. 
  36. ↑ Vlastimil Klima (2008-12-14). "Dynamic SHA is vulnerable to generic attacks". http://ehash.iaik.tugraz.at/uploads/e/e7/Dynamic-sha_length-extension.txt. 
  37. ↑ Zijie Xu. "Dynamic SHA2" (PDF). NIST. http://ehash.iaik.tugraz.at/uploads/5/5b/DyamicSHA2.pdf. 
  38. ↑ Vlastimil Klima (2008-12-14). "Dynamic SHA2 is vulnerable to generic attacks". http://ehash.iaik.tugraz.at/uploads/0/0e/Dynamic-sha2_length-extension.txt. 
  39. ↑ Danilo Gligoroski; Rune Steinsmo Ødegård (November 4, 2008). "edon-r". http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r. 
  40. ↑ "Cryptanalysis of Edon-R". 2008. http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf. 
  41. ↑ Sean O'Neil; Karsten Nohl (October 31, 2008). "EnRUPT – The Simpler The Better". http://www.enrupt.com/. 
  42. ↑ Sebastiaan Indesteege (November 6, 2008). "Collisions for EnRUPT". http://homes.esat.kuleuven.be/~sindeste/enrupt.html. 
  43. ↑ Jason Worth Martin (October 21, 2008). "ESSENCE: A Candidate Hashing Algorithm for the NIST Competition" (PDF). http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_NIST.pdf. 
  44. ↑ "Cryptanalysis of ESSENCE" (PDF). http://www.131002.net/data/papers/NRALLMP09.pdf. 
  45. ↑ Ivica Nikolić; Alex Biryukov. "Hash family LUX – Algorithm Specifications and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/f/f3/LUX.pdf. 
  46. ↑ Mikhail Maslennikov. "MCSSHA-3 hash algorithm". http://registercsp.nets.co.kr/hash_competition.htm. 
  47. ↑ Jean-Philippe Aumasson; María Naya-Plasencia. "Second preimages on MCSSHA-3" (PDF). http://131002.net/data/papers/AN.pdf. 
  48. ↑ Peter Maxwell (September 2008). "The Sgàil Cryptographic Hash Function" (PDF). http://www.allicient.co.uk/files/sgail/Supporting_Documentation/specification.pdf. 
  49. ↑ Peter Maxwell (November 5, 2008). "Aww, p*sh!". http://www.allicient.co.uk/2008/11/05/aww-psh/. 
  50. ↑ Michael Gorski; Ewan Fleischmann (October 28, 2008). "The Twister Hash Function Family" (PDF). http://ehash.iaik.tugraz.at/uploads/3/39/Twister.pdf. 
  51. ↑ "Cryptanalysis of Twister" (PDF). 2008. http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf. 
  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". http://eprint.iacr.org/2008/464. 
  53. ↑ "Cryptanalysis of Vortex" (PDF). 2009. http://www.131002.net/data/papers/ADMRT09.pdf. 
  54. ↑ Computer Security Division, Information Technology Laboratory (4 January 2017). "SHA-3 Project – Hash Functions". https://csrc.nist.gov/projects/hash-functions/sha-3-project. 
  55. ↑ Neil Sholer (October 29, 2008). "Abacus: A Candidate for SHA-3" (PDF). http://ehash.iaik.tugraz.at/uploads/b/be/Abacus.pdf. 
  56. ↑ Gregory G. Rose. "Design and Primitive Specification for Boole" (PDF). http://ehash.iaik.tugraz.at/uploads/3/37/BoolePaper.pdf. 
  57. ↑ Gregory G. Rose (10 Dec 2008). "Official Comment: Boole" (PDF). http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BOOLE_Comments.pdf. 
  58. ↑ David A. Wilson (October 23, 2008). "The DCH Hash Function" (PDF). http://web.mit.edu/dwilson/www/hash/dch/Supporting_Documentation/dch.pdf. 
  59. ↑ Natarajan Vijayarangan. "A New Hash Algorithm: Khichidi-1" (PDF). http://ehash.iaik.tugraz.at/uploads/d/d4/Khichidi-1.pdf. 
  60. ↑ Björn Fay. "MeshHash" (PDF). http://ehash.iaik.tugraz.at/uploads/5/5a/Specification_DIN-A4.pdf. 
  61. ↑ Orhun Kara; Adem Atalay. "SHAMATA hash function: A candidate algorithm for NIST competition". http://www.uekae.tubitak.gov.tr/home.do?ot=1&sid=601&pid=547. 
  62. ↑ Michal Trojnara (October 14, 2008). "StreamHash Algorithm Specifications and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/0/09/Streamhash.pdf. 
  63. ↑ Rafael Alvarez; Gary McGuire. "The Tangle Hash Function" (PDF). http://ehash.iaik.tugraz.at/uploads/4/40/Tangle.pdf. 
  64. ↑ John Washburn. "WaMM: A Candidate Algorithm for the SHA-3 Competition" (PDF). http://www.washburnresearch.org/cryptography/archive/WaMM-SHA3.pdf. 
  65. ↑ "Official Comment: WaMM is Withdrawn" (PDFauthor=John Washburn). 20 Dec 2008. http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/WaMM_Comments.pdf. 
  66. ↑ Bob Hattersly (October 15, 2008). "Waterfall Hash – Algorithm Specification and Analysis" (PDF). http://ehash.iaik.tugraz.at/uploads/1/19/Waterfall_Specification_1.0.pdf. 
  67. ↑ Bob Hattersley (20 Dec 2008). "Official Comment: Waterfall is broken" (PDF). http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Waterfall_Comments.pdf. 
  68. ↑ Bruce Schneier (November 19, 2008). "Skein and SHA-3 News". http://www.schneier.com/blog/archives/2008/11/skein_and_sha-3.html. 
  69. ↑ Robert J. Jenkins Jr.. "Algorithm Specification". http://burtleburtle.net/bob/crypto/maraca/nist/. 
  70. ↑ Anne Canteaut; María Naya-Plasencia. "Internal collision attack on Maraca" (PDF). http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf. 
  71. ↑ Michael P. Frank. "Algorithm Specification for MIXIT: a SHA-3 Candidate Cryptographic Hash Algorithm". https://dl.dropboxusercontent.com/u/3133557/Bitcoin/mixit-spec.pdf. 
  72. ↑ Geoffrey Park. "NKS 2D Cellular Automata Hash" (PDF). http://geoffrey.park.googlepages.com/SHA3Submission01.pdf. 
  73. ↑ Cristophe De Cannière (November 13, 2008). "Collisions for NKS2D-224". http://ehash.iaik.tugraz.at/uploads/3/3f/NK2SD-224.txt. 
  74. ↑ Brandon Enright (November 14, 2008). "Collisions for NKS2D-512". http://ehash.iaik.tugraz.at/uploads/9/93/NK2SD-512.txt. 
  75. ↑ Peter Schmidt-Nielsen. "Ponic" (PDF). http://ehash.iaik.tugraz.at/uploads/3/3c/PonicSpecification.pdf. 
  76. ↑ María Naya-Plasencia. "Second preimage attack on Ponic" (PDF). http://131002.net/data/papers/ponic.pdf. 
  77. ↑ Nicolas T. Courtois; Carmi Gressel. "ZK-Crypt Homepage". http://www.fortressgb.com/apage/39649.php. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=NIST_hash_function_competition&oldid=3379593"