NIST hash function competition

NIST hash function competition
Crypto key.svg Cryptography portal

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

Submissions were due October 31, 2008, with a list of candidates accepted for the first round published December 9, 2008.[3] NIST held a conference in late February 2009 where submitters gave presentations on their algorithms and NIST officials discussed criteria for narrowing down the field of candidates for Round 2.[4] The list of 14 candidates accepted to Round 2 was published on July 24, 2009.[5] Another conference was held August 23-24, 2010 (after CRYPTO 2010) at the University of California, Santa Barbara, where the second-round candidates were discussed.[6] The announcement of the final round candidates occurred on December 10, 2010 and the proclamation of a winner and publication of the new standard are scheduled to take place in 2012.[7]

Contents

Entrants

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

Finalists

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

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

  • 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 hash 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.[10]

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. 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.[3] 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,[3][63] but only the following are public.

References

  1. ^ "Federal Register / Vol. 72, No. 212" (PDF). Federal Register. Government Printing Office. Friday, November 2, 2007. http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf. Retrieved 2008-11-06. 
  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. Retrieved 2008-11-06. 
  3. ^ a b c d e f g h i j k "Round 1". 2008-12-09. http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/index.html. Retrieved 2008-12-10. 
  4. ^ 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. Retrieved 23 December 2008. 
  5. ^ a b "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. Retrieved July 24, 2009. 
  6. ^ 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/. 
  7. ^ "Tentative Timeline of the Development of New Hash Functions". NIST. December 10, 2008. http://csrc.nist.gov/groups/ST/hash/timeline.html. Retrieved September 15, 2009. 
  8. ^ THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011
  9. ^ SHA-3 Finalists Announced by NIST, blog post quoting NIST's announcement in full.
  10. ^ Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011
  11. ^ Svein Johan Knapskog; Danilo Gligoroski, Vlastimil Klima, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes (November 4, 2008). "blue_midnight_wish". http://www.item.ntnu.no/people/personalpages/fac/danilog/blue_midnight_wish. Retrieved 10 November 2008. 
  12. ^ Søren S. Thomsen (2009). "Pseudo-cryptanalysis of Blue Midnight Wish" (PDF). http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf. Retrieved 19 May 2009. 
  13. ^ Henri Gilbert; Ryad Benadjila, Olivier Billet, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin (October 29, 2008). "SHA-3 Proposal: ECHO" (PDF). http://ehash.iaik.tugraz.at/uploads/9/91/Echo.pdf. Retrieved 11 December 2008. 
  14. ^ Özgül Kücük (31 October 2008). "The Hash Function Hamsi" (PDF). http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf. Retrieved 11 December 2008. 
  15. ^ Dai Watanabe; Christophe De Canniere, Hisayoshi Sato (31 October 2008). "Hash Function Luffa: Specification" (PDF). http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf. Retrieved 11 December 2008. 
  16. ^ 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). http://ehash.iaik.tugraz.at/uploads/6/6c/Shabal.pdf. Retrieved 11 December 2008. 
  17. ^ Eli Biham; Orr Dunkelman. "The SHAvite-3 Hash Function" (PDF). http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf. Retrieved 11 December 2008. 
  18. ^ 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). http://ehash.iaik.tugraz.at/uploads/2/2c/Arirang.pdf. Retrieved 11 December 2008. 
  19. ^ "Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms". October 30, 2008. http://ehash.iaik.tugraz.at/uploads/2/2c/Chi_submission.pdf. Retrieved 11 November 2008. 
  20. ^ Jacques Patarin; Louis Goubin, Mickael Ivascot, William Jalby, Olivier Ly, Valerie Nachef, Joana Treger, Emmanuel Volte. "CRUNCH". http://www.voltee.com/crunch/. Retrieved 14 November 2008. 
  21. ^ Hirotaka Yoshida; Shoichi Hirose, Hidenori Kuwakado (30 October 2008). "SHA-3 Proposal: Lesamnta" (PDF). http://ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf. Retrieved 11 December 2008. 
  22. ^ Kerem Varıcı; Onur Özen and Çelebi Kocair. "The Sarmal Hash Function". http://homes.esat.kuleuven.be/~kvarici/sarmal_hash.html. Retrieved 12 October 2010. 
  23. ^ Daniel Penazzi; Miguel Montes. "The TIB3 Hash". http://www.famaf.unc.edu.ar/~penazzi/tib3/submitted/Supporting_Documentation/TIB3_Algorithm_Specification.pdf. Retrieved 2008-11-29. 
  24. ^ "AURORA: A Cryptographic Hash Algorithm Family" (PDF). October 31, 2008. http://ehash.iaik.tugraz.at/uploads/b/ba/AURORA.pdf. Retrieved 11 December 2008. 
  25. ^ "Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform" (PDF). 2009. http://eprint.iacr.org/2009/113.pdf. Retrieved 10 July 2009. 
  26. ^ 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. Retrieved 11 December 2008. 
  27. ^ Craig Newbold. "Observations and Attacks On The SHA-3 Candidate Blender" (PDF). http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf. Retrieved 23 December 2008. 
  28. ^ Florian Mendel. "Preimage Attack on Blender" (PDF). http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf. Retrieved 23 December 2008. 
  29. ^ Dmitry Khovratovich; Alex Biryukov, Ivica Nikolić (October 30, 2008). "The Hash Function Cheetah: Specification and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/c/ca/Cheetah.pdf. Retrieved 11 December 2008. 
  30. ^ 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. Retrieved 21 December 2008. 
  31. ^ Zijie Xu. "Dynamic SHA" (PDF). http://ehash.iaik.tugraz.at/uploads/e/e2/DyamicSHA.pdf. Retrieved 11 December 2008. 
  32. ^ 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. Retrieved 21 December 2008. 
  33. ^ Zijie Xu. "Dynamic SHA2" (PDF). NIST. http://ehash.iaik.tugraz.at/uploads/5/5b/DyamicSHA2.pdf. Retrieved 11 December 2008. 
  34. ^ 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. Retrieved 21 December 2008. 
  35. ^ Danilo Gligoroski; Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal (November 4, 2008). "edon-r". http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r. Retrieved 10 November 2008. 
  36. ^ "Cryptanalysis of Edon-R". 2008. http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf. Retrieved 10 July 2009. 
  37. ^ Sean O'Neil; Karsten Nohl, Luca Henzen (October 31, 2008). "EnRUPT - The Simpler The Better". http://www.enrupt.com/. Retrieved 10 November 2008. 
  38. ^ Sebastiaan Indesteege (November 6, 2008). "Collisions for EnRUPT". http://homes.esat.kuleuven.be/~sindeste/enrupt.html. Retrieved 2008-11-07. 
  39. ^ 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. Retrieved 2008-11-08. 
  40. ^ "Cryptanalysis of ESSENCE" (PDF). http://www.131002.net/data/papers/NRALLMP09.pdf. 
  41. ^ Ivica Nikolić; Alex Biryukov, Dmitry Khovratovich. "Hash family LUX - Algorithm Specifications and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/f/f3/LUX.pdf. Retrieved 11 December 2008. 
  42. ^ Mikhail Maslennikov. "MCSSHA-3 hash algorithm". http://registercsp.nets.co.kr/hash_competition.htm. Retrieved 2008-11-08. 
  43. ^ "Second preimages on MCSSHA-3" (PDF). http://131002.net/data/papers/AN.pdf. Retrieved 14 November 2008. 
  44. ^ Peter Maxwell (September 2008). "The Sgàil Cryptographic Hash Function" (PDF). http://www.allicient.co.uk/files/sgail/Supporting_Documentation/specification.pdf. Retrieved 9 11 2008. 
  45. ^ Peter Maxwell (November 5, 2008). "Aww, p*sh!". http://www.allicient.co.uk/2008/11/05/aww-psh/. Retrieved 2008-11-06. 
  46. ^ Michael Gorski; Ewan Fleischmann, Christian Forler (October 28, 2008). "The Twister Hash Function Family" (PDF). http://ehash.iaik.tugraz.at/uploads/3/39/Twister.pdf. Retrieved 11 December 2008. 
  47. ^ Florian Mendel, Christian Rechberger, Martin Schläffer (2008). "Cryptanalysis of Twister" (PDF). http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf. Retrieved 19 May 2009. 
  48. ^ 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. Retrieved 11 November 2008. 
  49. ^ Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen (2009). "Cryptanalysis of Vortex" (PDF). http://www.131002.net/data/papers/ADMRT09.pdf. Retrieved 19 May 2009. 
  50. ^ Neil Sholer (October 29, 2008). "Abacus: A Candidate for SHA-3" (PDF). http://ehash.iaik.tugraz.at/uploads/b/be/Abacus.pdf. Retrieved 11 December 2008. 
  51. ^ Gregory G. Rose. "Design and Primitive Specification for Boole" (PDF). http://ehash.iaik.tugraz.at/uploads/3/37/BoolePaper.pdf. Retrieved 2008-11-08. 
  52. ^ Gregory G. Rose (10 Dec 2008). "OFFICIAL COMMENT: BOOLE" (PDF). http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BOOLE_Comments.pdf. Retrieved 23 December 2008. 
  53. ^ David A. Wilson (October 23, 2008). "The DCH Hash Function" (PDF). http://web.mit.edu/dwilson/www/hash/dch/Supporting_Documentation/dch.pdf. Retrieved 23 November 2008. 
  54. ^ Natarajan Vijayarangan. "A NEW HASH ALGORITHM: Khichidi-1" (PDF). http://ehash.iaik.tugraz.at/uploads/d/d4/Khichidi-1.pdf. Retrieved 11 December 2008. 
  55. ^ Björn Fay. "MeshHash" (PDF). http://ehash.iaik.tugraz.at/uploads/5/5a/Specification_DIN-A4.pdf. Retrieved 30 November 2008. 
  56. ^ Orhun Kara; Adem Atalay, Ferhat Karakoc and Cevat Manap. "SHAMATA hash function: A candidate algorithm for NIST competition". http://www.uekae.tubitak.gov.tr/home.do?ot=1&sid=601&pid=547. Retrieved 10 November 2008. 
  57. ^ Michal Trojnara (October 14, 2008). "StreamHash Algorithm Specifications and Supporting Documentation" (PDF). http://ehash.iaik.tugraz.at/uploads/0/09/Streamhash.pdf. Retrieved 15 December 2008. 
  58. ^ Rafael Alvarez; Gary McGuire and Antonio Zamora. "The Tangle Hash Function" (PDF). http://ehash.iaik.tugraz.at/uploads/4/40/Tangle.pdf. Retrieved 11 December 2008. 
  59. ^ John Washburn. "WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION" (PDF). http://www.washburnresearch.org/cryptography/archive/WaMM-SHA3.pdf. Retrieved 9 11 2008. 
  60. ^ "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. Retrieved 23 December 2008. 
  61. ^ 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. Retrieved 9 11 2008. 
  62. ^ 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. Retrieved 23 December 2008. 
  63. ^ Bruce Schneier (November 19, 2008). "Skein and SHA-3 News". http://www.schneier.com/blog/archives/2008/11/skein_and_sha-3.html. Retrieved 23 December 2008. 
  64. ^ Jason Lee (November 6, 2008). "HASH 2X". TI BASIC Developer. http://tibasicdev.wikidot.com/archives:hash-2x. Retrieved 2008-11-06. 
  65. ^ "HASH 2X". TI BASIC Developer. November 6, 2008. http://tibasicdev.wikidot.com/archives:hash-2x/comments/show#post-302617. Retrieved 2008-11-06. 
  66. ^ Robert J. Jenkins Jr.. "Algorithm Specification". http://burtleburtle.net/bob/crypto/maraca/nist/. Retrieved 15 December 2008. 
  67. ^ "Internal collision attack on Maraca" (PDF). http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf. Retrieved 15 December 2008. 
  68. ^ Geoffrey Park. "NKS 2D Cellular Automata Hash" (PDF). http://geoffrey.park.googlepages.com/SHA3Submission01.pdf. Retrieved 9 11 2008. 
  69. ^ Cristophe De Cannière (November 13, 2008). "Collisions for NKS2D-224". http://ehash.iaik.tugraz.at/uploads/3/3f/NK2SD-224.txt. Retrieved 14 November 2008. 
  70. ^ Brandon Enright (November 14, 2008). "Collisions for NKS2D-512". http://ehash.iaik.tugraz.at/uploads/9/93/NK2SD-512.txt. Retrieved 14 November 2008. 
  71. ^ Peter Schmidt-Nielsen. "Ponic" (PDF). http://ehash.iaik.tugraz.at/uploads/3/3c/PonicSpecification.pdf. Retrieved 9 11 2008. 
  72. ^ María Naya-Plasencia. "Second preimage attack on Ponic" (PDF). http://131002.net/data/papers/ponic.pdf. Retrieved 30 November 2008. 
  73. ^ "ZK-Crypt Homepage". http://www.fortressgb.com/apage/39649.php. Retrieved 1 March 2009. 

External links

v · d · e Cryptographic hash functions and message authentication codes (MACs)
Common functions
MD5 · SHA-1 · SHA-2
Functions
FSB · SHA-3 · ECOH · GOST · HAS-160 · HAVAL · LM hash · MDC-2 · MD2 · MD4 · N-Hash · RadioGatún · RIPEMD · Snefru · SWIFFT · Tiger · VSH · WHIRLPOOL · crypt(3) (DES)
SHA-3 finalists
BLAKE · Grøstl · JH · Keccak · Skein
MAC algorithms
DAA · CBC-MAC · HMAC · OMAC/CMAC · PMAC · VMAC · UMAC · Poly1305-AES
Authenticated
encryption modes
CCM · CWC · EAX · GCM · IAPM · OCB
Attacks
Misc.
Standardization
CRYPTREC · NESSIE · NIST hash function competition
v · d · e Cryptography

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • NIST hash function competition — La NIST hash function competition est une compétition organisée par la NIST afin de trouver une nouvelle fonction de hachage (SHA 3) destinée à remplacer les anciennes fonctions SHA 1 et SHA 2. Sommaire 1 Participants 1.1 Finalistes 1.2 …   Wikipédia en Français

  • Cryptographic hash function — A cryptographic hash function (specifically, SHA 1) at work. Note that even small changes in the source input (here in the word over ) drastically change the resulting output, by the so called avalanche effect. A cryptographic hash function is a… …   Wikipedia

  • Maraca (hash function) — Infobox cryptographic hash function name = Maraca caption = designers = Bob Jenkins publish date = 2008 series = derived from = derived to = related to = certification = digest size = 1024 bits structure = rounds = cryptanalysis = Maraca is a… …   Wikipedia

  • Comparison of cryptographic hash functions — The following tables compare general and technical information for a number of cryptographic hash functions.[1] Contents 1 General information 1.1 Notes 2 Compression function …   Wikipedia

  • One-way compression function — In cryptography, a one way compression function is a function that transforms two fixed length inputs to an output of the same size as one of the inputs. The transformation is one way , meaning that it is difficult given a particular output to… …   Wikipedia

  • N-Hash — In cryptography, N Hash is a cryptographic hash function based on the FEAL round function, and is now considered insecure. It was proposed in 1990 by Miyaguchi et al.; weaknesses were published the following year. N Hash has a 128 bit hash size.… …   Wikipedia

  • LM hash — Lanman redirects here. For other uses, see Lanman (disambiguation). LM hash, LanMan, or LAN Manager hash was the primary hash that Microsoft LAN Manager and Microsoft Windows versions prior to Windows NT used to store user passwords. Support for… …   Wikipedia

  • SHA hash functions — The SHA hash functions are a set of cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm. The five algorithms …   Wikipedia

  • SHA-3 — NIST hash function competition La NIST hash function competition est une compétition organisée par la NIST afin de trouver une nouvelle fonction de hachage (SHA 3) destinée à remplacer les anciennes fonctions SHA 1 et SHA 2 Sommaire 1… …   Wikipédia en Français

  • 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… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”