Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

NIST hash function competition

From Wikipedia, the free encyclopedia

Competition to develop SHA-3

TheNIST hash function competition was an open competition held by the USNational Institute of Standards and Technology (NIST) to develop a newhash function calledSHA-3 to complement the olderSHA-1 andSHA-2. The competition was formally announced in theFederal 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 thedevelopment process for theAdvanced Encryption Standard (AES)."[2] The competition ended on October 2, 2012, when NIST announced thatKeccak 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, theSecure Hash Standard.

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

Process

[edit]

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 (afterCRYPTO 2010) at theUniversity 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, choosingKeccak, created by Guido Bertoni, Joan Daemen, and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP.[3]

Entrants

[edit]

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

[edit]

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

Finalists

[edit]

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]

  • 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 reportedcryptanalysis – 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 andsponge 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

[edit]

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

[edit]

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

[edit]

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

Conceded entrants

[edit]

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

[edit]

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

[edit]

References

[edit]
  1. ^"Federal Register / Vol. 72, No. 212"(PDF).Federal Register. Government Printing Office. November 2, 2007. RetrievedNovember 6, 2008.
  2. ^"cryptographic hash project – Background Information".Computer Security Resource Center. National Institute of Standards and Technology. November 2, 2007. RetrievedNovember 6, 2008.
  3. ^ab"NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. October 2, 2012. RetrievedOctober 2, 2012.
  4. ^abcdefghijk"Round 1". December 9, 2008. RetrievedDecember 10, 2008.
  5. ^National Institute of Standards and Technology (December 9, 2008)."The First SHA-3 Candidate Conference". RetrievedDecember 23, 2008.
  6. ^ab"Second Round Candidates". National Institute for Standards and Technology. July 24, 2009. RetrievedJuly 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. RetrievedSeptember 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 NISTArchived July 9, 2011, at theWayback 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". Archived fromthe original on November 12, 2013. RetrievedNovember 10, 2008.
  16. ^Søren S. Thomsen (2009)."Pseudo-cryptanalysis of Blue Midnight Wish"(PDF). Archived fromthe original(PDF) on September 2, 2009. RetrievedMay 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). RetrievedDecember 11, 2008.
  18. ^Özgül Kücük (October 31, 2008)."The Hash Function Hamsi"(PDF). RetrievedDecember 11, 2008.
  19. ^Dai Watanabe; Christophe De Canniere; Hisayoshi Sato (October 31, 2008)."Hash Function Luffa: Specification"(PDF). RetrievedDecember 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). RetrievedDecember 11, 2008.
  21. ^Eli Biham; Orr Dunkelman."The SHAvite-3 Hash Function"(PDF). RetrievedDecember 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). RetrievedDecember 11, 2008.
  23. ^Philip Hawkes; Cameron McDonald (October 30, 2008)."Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms"(PDF). RetrievedNovember 11, 2008.
  24. ^Jacques Patarin; Louis Goubin; Mickael Ivascot; William Jalby; Olivier Ly; Valerie Nachef; Joana Treger; Emmanuel Volte."CRUNCH". Archived fromthe original on January 29, 2009. RetrievedNovember 14, 2008.
  25. ^Hirotaka Yoshida; Shoichi Hirose; Hidenori Kuwakado (October 30, 2008)."SHA-3 Proposal: Lesamnta"(PDF). RetrievedDecember 11, 2008.
  26. ^Kerem Varıcı; Onur Özen; Çelebi Kocair."The Sarmal Hash Function". Archived fromthe original on June 11, 2011. RetrievedOctober 12, 2010.
  27. ^Daniel Penazzi; Miguel Montes."The TIB3 Hash"(PDF). RetrievedNovember 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). RetrievedDecember 11, 2008.
  29. ^Niels Ferguson;Stefan Lucks (2009)."Attacks on AURORA-512 and the Double-MIX Merkle–Damgård Transform"(PDF). RetrievedJuly 10, 2009.
  30. ^Colin Bradbury (October 25, 2008)."BLENDER: A Proposed New Family of Cryptographic Hash Algorithms"(PDF). RetrievedDecember 11, 2008.
  31. ^Craig Newbold."Observations and Attacks On The SHA-3 Candidate Blender"(PDF). RetrievedDecember 23, 2008.
  32. ^Florian Mendel."Preimage Attack on Blender"(PDF). RetrievedDecember 23, 2008.
  33. ^Dmitry Khovratovich; Alex Biryukov; Ivica Nikolić (October 30, 2008)."The Hash Function Cheetah: Specification and Supporting Documentation"(PDF). RetrievedDecember 11, 2008.
  34. ^Danilo Gligoroski (December 12, 2008)."Danilo Gligoroski – Cheetah hash function is not resistant against length-extension attack". RetrievedDecember 21, 2008.
  35. ^Zijie Xu."Dynamic SHA"(PDF). RetrievedDecember 11, 2008.
  36. ^Vlastimil Klima (December 14, 2008)."Dynamic SHA is vulnerable to generic attacks". RetrievedDecember 21, 2008.
  37. ^Zijie Xu."Dynamic SHA2"(PDF). NIST. RetrievedDecember 11, 2008.
  38. ^Vlastimil Klima (December 14, 2008)."Dynamic SHA2 is vulnerable to generic attacks". RetrievedDecember 21, 2008.
  39. ^Danilo Gligoroski; Rune Steinsmo Ødegård; Marija Mihova; Svein Johan Knapskog; Ljupco Kocarev; Aleš Drápal (November 4, 2008)."edon-r". Archived fromthe original on November 12, 2013. RetrievedNovember 10, 2008.
  40. ^Dmitry Khovratovich; Ivica Nikolić; Ralf-Philipp Weinmann (2008)."Cryptanalysis of Edon-R"(PDF). RetrievedJuly 10, 2009.
  41. ^Sean O'Neil; Karsten Nohl; Luca Henzen (October 31, 2008)."EnRUPT – The Simpler The Better". RetrievedNovember 10, 2008.
  42. ^Sebastiaan Indesteege (November 6, 2008)."Collisions for EnRUPT". Archived fromthe original on February 18, 2009. RetrievedNovember 7, 2008.
  43. ^Jason Worth Martin (October 21, 2008)."ESSENCE: A Candidate Hashing Algorithm for the NIST Competition"(PDF). Archived fromthe original(PDF) on June 12, 2010. RetrievedNovember 8, 2008.
  44. ^"Cryptanalysis of ESSENCE"(PDF).
  45. ^Ivica Nikolić; Alex Biryukov; Dmitry Khovratovich."Hash family LUX – Algorithm Specifications and Supporting Documentation"(PDF). RetrievedDecember 11, 2008.
  46. ^Mikhail Maslennikov."MCSSHA-3 hash algorithm". Archived fromthe original on May 2, 2009. RetrievedNovember 8, 2008.
  47. ^Jean-Philippe Aumasson; María Naya-Plasencia."Second preimages on MCSSHA-3"(PDF). RetrievedNovember 14, 2008.[permanent dead link]
  48. ^Peter Maxwell (September 2008)."The Sgàil Cryptographic Hash Function"(PDF). Archived fromthe original(PDF) on November 12, 2013. RetrievedNovember 9, 2008.
  49. ^Peter Maxwell (November 5, 2008)."Aww, p*sh!". Archived fromthe original on November 9, 2008. RetrievedNovember 6, 2008.
  50. ^Michael Gorski; Ewan Fleischmann; Christian Forler (October 28, 2008)."The Twister Hash Function Family"(PDF). RetrievedDecember 11, 2008.
  51. ^Florian Mendel; Christian Rechberger; Martin Schläffer (2008)."Cryptanalysis of Twister"(PDF). RetrievedMay 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". RetrievedNovember 11, 2008.
  53. ^Jean-Philippe Aumasson; Orr Dunkelman; Florian Mendel; Christian Rechberger; Søren S. Thomsen (2009)."Cryptanalysis of Vortex"(PDF). RetrievedMay 19, 2009.
  54. ^Computer Security Division, Information Technology Laboratory (January 4, 2017)."SHA-3 Project – Hash Functions".CSRC: NIST. RetrievedApril 26, 2019.
  55. ^Neil Sholer (October 29, 2008)."Abacus: A Candidate for SHA-3"(PDF). RetrievedDecember 11, 2008.
  56. ^Gregory G. Rose."Design and Primitive Specification for Boole"(PDF). RetrievedNovember 8, 2008.
  57. ^Gregory G. Rose (December 10, 2008)."Official Comment: Boole"(PDF). RetrievedDecember 23, 2008.
  58. ^David A. Wilson (October 23, 2008)."The DCH Hash Function"(PDF). RetrievedNovember 23, 2008.
  59. ^Natarajan Vijayarangan."A New Hash Algorithm: Khichidi-1"(PDF). RetrievedDecember 11, 2008.
  60. ^Björn Fay."MeshHash"(PDF). RetrievedNovember 30, 2008.
  61. ^Orhun Kara; Adem Atalay; Ferhat Karakoc; Cevat Manap."SHAMATA hash function: A candidate algorithm for NIST competition". Archived fromthe original on February 1, 2009. RetrievedNovember 10, 2008.
  62. ^Michal Trojnara (October 14, 2008)."StreamHash Algorithm Specifications and Supporting Documentation"(PDF). RetrievedDecember 15, 2008.
  63. ^Rafael Alvarez; Gary McGuire; Antonio Zamora."The Tangle Hash Function"(PDF). RetrievedDecember 11, 2008.
  64. ^John Washburn."WaMM: A Candidate Algorithm for the SHA-3 Competition"(PDF). Archived fromthe original(PDF) on April 19, 2009. RetrievedNovember 9, 2008.
  65. ^"Official Comment: WaMM is Withdrawn"(PDFauthor=John Washburn). December 20, 2008. RetrievedDecember 23, 2008.
  66. ^Bob Hattersly (October 15, 2008)."Waterfall Hash – Algorithm Specification and Analysis"(PDF). RetrievedNovember 9, 2008.
  67. ^Bob Hattersley (December 20, 2008)."Official Comment: Waterfall is broken"(PDF). RetrievedDecember 23, 2008.
  68. ^Bruce Schneier (November 19, 2008)."Skein and SHA-3 News". RetrievedDecember 23, 2008.
  69. ^Robert J. Jenkins Jr."Algorithm Specification". RetrievedDecember 15, 2008.
  70. ^Anne Canteaut & María Naya-Plasencia."Internal collision attack on Maraca"(PDF). RetrievedDecember 15, 2008.
  71. ^Michael P. Frank."Algorithm Specification for MIXIT: a SHA-3 Candidate Cryptographic Hash Algorithm"(PDF). Archived fromthe original(PDF) on March 4, 2016. RetrievedJanuary 12, 2014.
  72. ^Geoffrey Park."NKS 2D Cellular Automata Hash"(PDF). RetrievedNovember 9, 2008.
  73. ^Cristophe De Cannière (November 13, 2008)."Collisions for NKS2D-224". RetrievedNovember 14, 2008.
  74. ^Brandon Enright (November 14, 2008)."Collisions for NKS2D-512". RetrievedNovember 14, 2008.
  75. ^Peter Schmidt-Nielsen."Ponic"(PDF). RetrievedNovember 9, 2008.
  76. ^María Naya-Plasencia."Second preimage attack on Ponic"(PDF). RetrievedNovember 30, 2008.
  77. ^Nicolas T. Courtois; Carmi Gressel; Avi Hecht; Gregory V. Bard; Ran Granot."ZK-Crypt Homepage". Archived fromthe original on February 9, 2009. RetrievedMarch 1, 2009.

External links

[edit]
Common functions
SHA-3 finalists
Other functions
Password hashing/
key stretching functions
General purpose
key derivation functions
MAC functions
Authenticated
encryption modes
Attacks
Design
Standardization
Utilization
General
Mathematics
Retrieved from "https://en.wikipedia.org/w/index.php?title=NIST_hash_function_competition&oldid=1337162703"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp