Competizione NIST per funzioni hash
![Questa voce è da wikificare](http://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Wikitext.svg/50px-Wikitext.svg.png)
La Competizione NIST per funzioni hash o Competizione SHA-3 è stata una competizione promossa dall'ente americano NIST per sviluppare una nuova funzione di hashing chiamata SHA-3 per rafforzare le vecchie funzioni SHA-1 e SHA-2. La competizione fu formalmente annunciata nel Registro Federale americano il 2 novembre 2007.[1] "NIST sta per impegnarsi a sviluppare uno o più algoritmi di hashing in una competizione pubblica, simile al processo che ha portato allo sviluppo di Advanced Encryption Standard (AES)."[2] La competizione si è conclusa il 2 ottobre 2012, quando il NIST ha annunciato il vincitore: Keccak sarebbe stato il nuovo algoritmo di hashing SHA-3.[3]
Svolgimento
Le candidature furono ricevute fino al 31 ottobre 2008 e la lista dei candidati accettati per il primo turno fu pubblicato il 9 dicembre 2008.[4] Il NIST organizzò una conferenza nel febbraio del 2009 dove i candidati presentarono i loro algoritmi. Vennero discussi i criteri per restringere il gruppo di candidati per il secondo turno.[5] La lista dei 14 candidati accettati per il secondo turno fu pubblicata il 21 luglio 2009.[6] Venne organizzata una seconda conferenza il 23 e 24 agosto 2010, dopo la Conferenza Internazionale di Crittologia (CRYPTO) 2010, all'Università della California (Santa Barbara), dove furono esaminate le candidature del secondo turno.[7] L'annuncio del gruppo finale di candidati avvenne il 20 dicembre 2010.[8] Il 2 ottobre 2012, il NIST annunciò il vincitore, scegliendo Keccak, creato da Guido Bertoni, Joan Daemen, Gilles Van Assche di STMicroelectronics e Michaël Peeters di NXP.[3]
Partecipanti
Di seguito è riportata una lista non ancora completa di candidature. Il NIST selezionò 51 proposte per il primo turno,[4] 14 delle quali avanzarono al secondo turno.[6] Tra questi vennero selezionati i 5 finalisti.
Partecipanti esclusi in fase iniziale
Di seguito viene riportata la lista dei partecipanti che sono stati esclusi nella fase iniziale della competizione.
Partecipanti scartati
Molte proposte ricevute dal NIST non sono state accettate per partecipare al primo turno, in base ad un'analisi interna del NIST.[4] In generale non sono state date motivazioni del rifiuto. Il NIST non ha neppure pubblicato la lista dei candidati che sono stati rifiutati, tuttavia ne sono stati individuati 13,[4][9] ma solo i seguenti sono stati pubblicati.
- HASH 2X[10][11]
- Maraca[12][13]
- NKS 2D[14][15][16]
- Ponic[17][18]
- ZK-Crypt[19]
Partecipanti ritirati
I seguenti algoritmi, presentati per partecipare al primo turno, sono stati ufficialmente ritirati da parte dei loro autori; sono stati considerati inadatti in base a alle direttive[20].
- Abacus[4][21]
- Boole[22][23]
- DCH[4][24]
- Khichidi-1[4][25]
- MeshHash[4][26]
- SHAMATA[4][27]
- StreamHash[4][28]
- Tangle[4][29]
- WaMM[30][31]
- Waterfall[32][33]
Partecipanti iniziali con problemi sostanziali
I seguenti algoritmi non sono riusciti a passare al primo turno. Sono state riscontrate debolezze dal punto di vista crittografico.
- AURORA (Sony and Nagoya University)[34][35]
- Blender[36][37][38]
- Cheetah[39][40]
- Dynamic SHA[41][42]
- Dynamic SHA2[43][44]
- ECOH
- Edon-R[45][46]
- EnRUPT[47][48]
- ESSENCE[49][50]
- LUX[51]
- MCSSHA-3[52][53]
- NaSHA
- Sgàil[54][55]
- Spectral Hash
- Twister[56][57]
- Vortex[58][59]
Partecipanti esclusi a primo turno
Le funzioni di hashing seguenti sono state accettate per gareggiare nel primo turno ma non sono passate al secondo turno. Non hanno avuto particolari problemi dal punto di vista crittografico né sono stati ritirati dalla competizione dai loro autori, ma sono stati riscontrati problemi nel design delle componenti o problemi di prestazioni.
- ARIRANG[60] (CIST - Korea University)
- CHI[61]
- CRUNCH[62]
- FSB
- Lane
- Lesamnta[63]
- MD6 (Rivest et al.)
- SANDstorm (Sandia National Laboratories)
- Sarmal[64]
- SWIFFTX
- TIB3[65]
Partecipanti esclusi al secondo turno
Le seguenti funzioni di hashing furono accettate per il secondo turno, ma non riuscirono a passare al turno finale.
- Blue Midnight Wish[66][67]
- CubeHash (Bernstein)
- ECHO (France Télécom)[68]
- Fugue (IBM)
- Hamsi[69]
- Luffa[70]
- Shabal[71]
- SHAvite-3[72]
- SIMD
Finalisti
NIST selezionò cinque algoritmi candidati a divenire il nuovo SHA-3. Questi algoritmi vennero scelti per passari al terzo (ed ultimo) turno:[73]
- BLAKE
- Grøstl (Knudsen et al.)
- JH
- Keccak (Keccak team, Daemen et al.)
- Skein (Schneier et al.)
NIST individuò alcune caratteristiche che vennero considerate nella selezione. Gli aspetti degli algoritmi selezionati vennero descritti nel post:[74].
- Prestazioni: "Un paio di algoritmi sono stati penalizzati o eliminati a causa di eccessivi requisiti in termini di spazio di calcolo. Lo spazio di calcolo che richiedevano precludeva il loro utilizzo a molte potenziali applicazioni."
- Sicurezza: "Abbiamo preferito rimanere previdenti rispetto alla sicurezza, e in alcuni casi abbiamo scartato algoritmi con performance eccezionali, principalmente a causa di un certo 'nervosismo', nonostante sapessimo che non erano noti attacchi all'algoritmo."
- Analisi: "Il NIST ha eliminato parecchi algoritmi a causa della presenza di aggiustamenti durante il secondo turno o a causa di mancanza di crittoanalisi; entrambi i fattori hanno creato il sospetto che il design dell'algoritmo non fosse sufficientemente maturo e sottoposto a test."
- Differenza: "I finalisti hanno incluso funzioni di hashing basare su diverse metodologie, includendo costruzioni HAIFA e funzioni spugna, e con differenti strutture interne, includendo algoritmi basati su AES, bit slicing e addizioni alternate con XOR.".
NIST rilasciò un rapporto che spiegava la propria valutazione di ogni singolo algoritmo.[75][76]
Vincitore
Il 2 ottobre 2012 venne annunciato il vincitore: Keccak[77]
Note
- ^ (EN) Federal Register / Vol. 72, No. 212 (PDF), su Federal Register, Government Printing Office, 2 novembre 2007. URL consultato il 6 novembre 2008.
- ^ (EN) cryptographic hash project - Background Information, su Computer Security Resource Center, National Institute of Standards and Technology, 2 novembre 2007. URL consultato il 6 novembre 2008.
- ^ a b (EN) NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition, su nist.gov, NIST, 2 ottobre 2012. URL consultato il 2 ottobre 2012.
- ^ a b c d e f g h i j k (EN) Round 1, su csrc.nist.gov, 9 dicembre 2008. URL consultato il 10 dicembre 2008.
- ^ (EN) National Institute of Standards and Technology, The First SHA-3 Candidate Conference, su csrc.nist.gov, 9 dicembre 2008. URL consultato il 23 dicembre 2008.
- ^ a b (EN) Second Round Candidates, su csrc.nist.gov, National Institute for Standards and Technology, 24 luglio 2009. URL consultato il 24 luglio 2009.
- ^ (EN) National Institute of Standards and Technology, The Second SHA-3 Candidate Conference, su csrc.nist.gov, 30 giugno 2010.
- ^ (EN) Tentative Timeline of the Development of New Hash Functions, su csrc.nist.gov, NIST, 10 dicembre 2008. URL consultato il 15 settembre 2009.
- ^ (EN) Bruce Schneier, Skein and SHA-3 News, su schneier.com, 19 novembre 2008. URL consultato il 23 dicembre 2008.
- ^ (EN) Jason Lee, HASH 2X, su TI BASIC Developer, 6 novembre 2008. URL consultato il 6 novembre 2008.
- ^ (EN) HASH 2X, su TI BASIC Developer, 6 novembre 2008. URL consultato il 6 novembre 2008.
- ^ (EN) Robert J. Jenkins Jr., Algorithm Specification, su burtleburtle.net. URL consultato il 15 dicembre 2008.
- ^ (EN) Anne Canteaut and María Naya-Plasencia, Internal collision attack on Maraca (PDF), su ehash.iaik.tugraz.at. URL consultato il 15 dicembre 2008.
- ^ (EN) Geoffrey Park, NKS 2D Cellular Automata Hash (PDF) [collegamento interrotto], su geoffrey.park.googlepages.com. URL consultato il 9 novembre 2008.
- ^ (EN) Cristophe De Cannière, Collisions for NKS2D-224 (TXT), su ehash.iaik.tugraz.at, 13 novembre 2008. URL consultato il 14 novembre 2008.
- ^ (EN) Brandon Enright, Collisions for NKS2D-512 (TXT), su ehash.iaik.tugraz.at, 14 novembre 2008. URL consultato il 14 novembre 2008.
- ^ (EN) Peter Schmidt-Nielsen, Ponic (PDF), su ehash.iaik.tugraz.at. URL consultato il 9 novembre 2008.
- ^ (EN) María Naya-Plasencia, Second preimage attack on Ponic (PDF), su 131002.net. URL consultato il 30 novembre 2008.
- ^ (EN) Nicolas T. Courtois, Carmi Gressel, Avi Hecht, Gregory V. Bard, Ran Granot, ZK-Crypt Homepage, su fortressgb.com. URL consultato il 1º marzo 2009 (archiviato dall'url originale il 9 febbraio 2009).
- ^ NIST official Round One Candidates web site
- ^ (EN) Neil Sholer, Abacus: A Candidate for SHA-3 (PDF), su ehash.iaik.tugraz.at, 29 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Gregory G. Rose, Design and Primitive Specification for Boole (PDF), su ehash.iaik.tugraz.at. URL consultato l'8 novembre 2008.
- ^ (EN) Gregory G. Rose, OFFICIAL COMMENT: BOOLE (PDF), su csrc.nist.gov, 10 dicembre 2008. URL consultato il 23 dicembre 2008.
- ^ (EN) David A. Wilson, The DCH Hash Function (PDF), su web.mit.edu, 23 ottobre 2008. URL consultato il 23 novembre 2008.
- ^ (EN) Natarajan Vijayarangan, A NEW HASH ALGORITHM: Khichidi-1 (PDF), su ehash.iaik.tugraz.at. URL consultato l'11 dicembre 2008.
- ^ (EN) Björn Fay, MeshHash (PDF), su ehash.iaik.tugraz.at. URL consultato il 30 novembre 2008.
- ^ (EN) Orhun Kara, Adem Atalay, Ferhat Karakoc and Cevat Manap, SHAMATA hash function: A candidate algorithm for NIST competition, su uekae.tubitak.gov.tr. URL consultato il 10 novembre 2008 (archiviato dall'url originale il 1º febbraio 2009).
- ^ (EN) Michal Trojnara, StreamHash Algorithm Specifications and Supporting Documentation (PDF), su ehash.iaik.tugraz.at, 14 ottobre 2008. URL consultato il 15 dicembre 2008.
- ^ (EN) Rafael Alvarez, Gary McGuire and Antonio Zamora, The Tangle Hash Function (PDF), su ehash.iaik.tugraz.at. URL consultato l'11 dicembre 2008.
- ^ (EN) John Washburn, WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION (PDF), su washburnresearch.org. URL consultato il 9 novembre 2008 (archiviato dall'url originale il 19 novembre 2008).
- ^ (EN) John Washburn, OFFICIAL COMMENT: WaMM is Withdrawn (PDF), su csrc.nist.gov, 20 dicembre 2008. URL consultato il 23 dicembre 2008.
- ^ (EN) Bob Hattersly, Waterfall Hash - Algorithm Specification and Analysis (PDF), su ehash.iaik.tugraz.at, 15 ottobre 2008. URL consultato il 9 novembre 2008.
- ^ (EN) Bob Hattersley, OFFICIAL COMMENT: Waterfall is broken (PDF), su csrc.nist.gov, 20 dicembre 2008. URL consultato il 23 dicembre 2008.
- ^ (EN) Tetsu Iwata, Kyoji Shibutani, Taizo Shirai, Shiho Moriai, Toru Akishita, AURORA: A Cryptographic Hash Algorithm Family (PDF), su ehash.iaik.tugraz.at, 31 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Niels Ferguson, Stefan Lucks, Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform (PDF), su eprint.iacr.org, 2009. URL consultato il 10 luglio 2009.
- ^ (EN) Colin Bradbury, BLENDER: A Proposed New Family of Cryptographic Hash Algorithms (PDF), su ehash.iaik.tugraz.at, 25 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Craig Newbold, Observations and Attacks On The SHA-3 Candidate Blender (PDF), su ehash.iaik.tugraz.at. URL consultato il 23 dicembre 2008.
- ^ (EN) Florian Mendel, Preimage Attack on Blender (PDF), su ehash.iaik.tugraz.at. URL consultato il 23 dicembre 2008.
- ^ (EN) Dmitry Khovratovich, Alex Biryukov, Ivica Nikolić, The Hash Function Cheetah: Specification and Supporting Documentation (PDF), su ehash.iaik.tugraz.at, 30 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Danilo Gligoroski, Danilo Gligoroski - Cheetah hash function is not resistant against length-extension attack (TXT), su ehash.iaik.tugraz.at, 12 dicembre 2008. URL consultato il 21 dicembre 2008.
- ^ (EN) Zijie Xu, Dynamic SHA (PDF), su ehash.iaik.tugraz.at. URL consultato l'11 dicembre 2008.
- ^ (EN) Vlastimil Klima, Dynamic SHA is vulnerable to generic attacks (TXT), su ehash.iaik.tugraz.at, 14 dicembre 2008. URL consultato il 21 dicembre 2008.
- ^ (EN) Zijie Xu, Dynamic SHA2 (PDF), su ehash.iaik.tugraz.at, NIST. URL consultato l'11 dicembre 2008.
- ^ (EN) Vlastimil Klima, Dynamic SHA2 is vulnerable to generic attacks (TXT), su ehash.iaik.tugraz.at, 14 dicembre 2008. URL consultato il 21 dicembre 2008.
- ^ (EN) Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, edon-r, su item.ntnu.no, 4 novembre 2008. URL consultato il 10 novembre 2008.
- ^ (EN) Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann, Cryptanalysis of Edon-R (PDF), su ehash.iaik.tugraz.at, 2008. URL consultato il 10 luglio 2009.
- ^ (EN) Sean O'Neil, Karsten Nohl, Luca Henzen, EnRUPT - The Simpler The Better, su enrupt.com, 31 ottobre 2008. URL consultato il 10 novembre 2008.
- ^ (EN) Sebastiaan Indesteege, Collisions for EnRUPT, su homes.esat.kuleuven.be, 6 novembre 2008. URL consultato il 7 novembre 2008 (archiviato dall'url originale il 18 febbraio 2009).
- ^ (EN) Jason Worth Martin, ESSENCE: A Candidate Hashing Algorithm for the NIST Competition (PDF), su math.jmu.edu, 21 ottobre 2008. URL consultato l'8 novembre 2008 (archiviato dall'url originale il 12 giugno 2010).
- ^ (EN) Cryptanalysis of ESSENCE (PDF), su 131002.net.
- ^ (EN) Ivica Nikolić, Alex Biryukov, Dmitry Khovratovich, Hash family LUX - Algorithm Specifications and Supporting Documentation (PDF), su ehash.iaik.tugraz.at. URL consultato l'11 dicembre 2008.
- ^ (EN) Mikhail Maslennikov, MCSSHA-3 hash algorithm, su registercsp.nets.co.kr. URL consultato l'8 novembre 2008 (archiviato dall'url originale il 2 maggio 2009).
- ^ (EN) Jean-Philippe Aumasson and María Naya-Plasencia, Second preimages on MCSSHA-3 (PDF) [collegamento interrotto], su 131002.net. URL consultato il 14 novembre 2008.
- ^ (EN) Peter Maxwell, The Sgàil Cryptographic Hash Function (PDF), su allicient.co.uk, settembre 2008. URL consultato il 9 novembre 2008 (archiviato dall'url originale il 12 novembre 2013).
- ^ (EN) Peter Maxwell, Aww, p*sh!, su allicient.co.uk, 5 novembre 2008. URL consultato il 6 novembre 2008 (archiviato dall'url originale il 9 novembre 2008).
- ^ (EN) Michael Gorski, Ewan Fleischmann, Christian Forler, The Twister Hash Function Family (PDF), su ehash.iaik.tugraz.at, 28 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Florian Mendel, Christian Rechberger, Martin Schläffer, Cryptanalysis of Twister (PDF), su ehash.iaik.tugraz.at, 2008. URL consultato il 19 maggio 2009.
- ^ (EN) Michael Kounavis, Shay Gueron, Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication, su eprint.iacr.org, 3 novembre 2008. URL consultato l'11 novembre 2008.
- ^ (EN) Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen, Cryptanalysis of Vortex (PDF), su 131002.net, 2009. URL consultato il 19 maggio 2009.
- ^ (EN) Jongin Lim, Donghoon Chang, Seokhie Hong, Changheon Kang, Jinkeon Kang, Jongsung Kim, Changhoon Lee, Jesang Lee, Jongtae Lee, Sangjin Lee, Yuseop Lee, Jaechul Sung, ARIRANG (PDF), su ehash.iaik.tugraz.at, 29 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Philip Hawkes, Cameron McDonald, Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms (PDF), su ehash.iaik.tugraz.at, 30 ottobre 2008. URL consultato l'11 novembre 2008.
- ^ (EN) Jacques Patarin, Louis Goubin, Mickael Ivascot, William Jalby, Olivier Ly, Valerie Nachef, Joana Treger, Emmanuel Volte, CRUNCH, su voltee.com. URL consultato il 14 novembre 2008 (archiviato dall'url originale il 29 gennaio 2009).
- ^ (EN) Hirotaka Yoshida, Shoichi Hirose, Hidenori Kuwakado, SHA-3 Proposal: Lesamnta (PDF), su ehash.iaik.tugraz.at, 30 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Kerem Varıcı, Onur Özen and Çelebi Kocair, The Sarmal Hash Function, su homes.esat.kuleuven.be. URL consultato il 12 ottobre 2010 (archiviato dall'url originale l'11 giugno 2011).
- ^ (EN) Daniel Penazzi, Miguel Montes, The TIB3 Hash (PDF) [collegamento interrotto], su famaf.unc.edu.ar. URL consultato il 29 novembre 2008.
- ^ (EN) Svein Johan Knapskog, Danilo Gligoroski, Vlastimil Klima, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes, blue_midnight_wish, su item.ntnu.no, 4 novembre 2008. URL consultato il 10 novembre 2008.
- ^ (EN) Søren S. Thomsen, Pseudo-cryptanalysis of Blue Midnight Wish (PDF), su mat.dtu.dk, 2009. URL consultato il 19 maggio 2009 (archiviato dall'url originale il 2 settembre 2009).
- ^ (EN) Henri Gilbert, Ryad Benadjila, Olivier Billet, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin, SHA-3 Proposal: ECHO (PDF), su ehash.iaik.tugraz.at, 29 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Özgül Kücük, The Hash Function Hamsi (PDF), su ehash.iaik.tugraz.at, 31 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Dai Watanabe, Christophe De Canniere, Hisayoshi Sato, Hash Function Luffa: Specification (PDF), su ehash.iaik.tugraz.at, 31 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) 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, Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition (PDF), su ehash.iaik.tugraz.at, 28 ottobre 2008. URL consultato l'11 dicembre 2008.
- ^ (EN) Eli Biham, Orr Dunkelman, The SHAvite-3 Hash Function (PDF), su ehash.iaik.tugraz.at. URL consultato l'11 dicembre 2008.
- ^ (EN) THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011
- ^ (EN) SHA-3 Finalists Announced by NIST Archiviato il 9 luglio 2011 in Internet Archive.
- ^ (EN) Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition
- ^ (EN) Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011
- ^ (EN) NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition
Collegamenti esterni
- (EN) Sito web della competizione NIST, su csrc.nist.gov.
- (EN) Lista ufficiale dei candidati al secondo turno, su csrc.nist.gov.
- (EN) Lista ufficiale dei candidati al primo turno, su csrc.nist.gov.
- (EN) SHA-3 Zoo, su ehash.iaik.tugraz.at.
- (EN) Classifica dei candidati SHA-3 (PDF), su eprint.iacr.org.
- (EN) Hash Function Lounge, su larc.usp.br. URL consultato il 26 dicembre 2008 (archiviato dall'url originale il 25 dicembre 2008).
- (EN) Codice sorgente VHDL sviluppato dal Cryptographic Engineering Research Group (CERG) alla George Mason University, su cryptography.gmu.edu.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Ambox_padlock_green.svg/25px-Ambox_padlock_green.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Gnome-system-lock-screen.svg/25px-Gnome-system-lock-screen.svg.png)