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.
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].
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.
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.
^abcdefghijk(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.
^ab(EN) Second Round Candidates, su csrc.nist.gov, National Institute for Standards and Technology, 24 luglio 2009. URL consultato il 24 luglio 2009.
^(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).
^(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) 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) 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) 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) 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) 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.