Competizione NIST per funzioni hash

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Di seguito viene riportata la lista dei partecipanti che sono stati esclusi nella fase iniziale della competizione.

Partecipanti scartati[modifica | modifica sorgente]

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 indivudati 13,[4][9] ma solo i seguenti sono stati pubblicati.

Partecipanti ritirati[modifica | modifica sorgente]

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

Partecipanti iniziali con problemi sostanziali[modifica | modifica sorgente]

I seguenti algoritmi non sono riusciti a passare al primo turno. Sono state riscontrate debolezze dal punto di vista crittografico.

Partecipanti esclusi a primo turno[modifica | modifica sorgente]

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.

Partecipanti esclusi al secondo turno[modifica | modifica sorgente]

Le seguenti funzioni di hashing furono accettate per il secondo turno, ma non riuscirono a passare al turno finale.

Finalisti[modifica | modifica sorgente]

NIST selezionò cinque algoritmi candidati a divenire il nuovo SHA-3. Questi algoritmi vennero scelti per passari al terzo (ed ultimo) turno:[73]

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 algiritmo.[75][76]

Vincitore[modifica | modifica sorgente]

Il 2 Ottobre 2012 venne annunciato il vincitore: Keccak[77]

Note[modifica | modifica sorgente]

  1. ^ (EN) Federal Register / Vol. 72, No. 212 (PDF) in Federal Register, Government Printing Office, 2 novembre 2007. URL consultato il 6 novembre 2008.
  2. ^ (EN) cryptographic hash project - Background Information in Computer Security Resource Center, National Institute of Standards and Technology, 2 novembre 2007. URL consultato il 6 novembre 2008.
  3. ^ a b (EN) NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition, NIST, 2 ottobre 2012. URL consultato il 2 ottobre 2012.
  4. ^ a b c d e f g h i j k (EN) Round 1, 9 dicembre 2008. URL consultato il 10 dicembre 2008.
  5. ^ (EN) National Institute of Standards and Technology, The First SHA-3 Candidate Conference, 9 dicembre 2008. URL consultato il 23 dicembre 2008.
  6. ^ a b (EN) Second Round Candidates, National Institute for Standards and Technology, 24 luglio 2009. URL consultato il 24 luglio 2009.
  7. ^ (EN) National Institute of Standards and Technology, The Second SHA-3 Candidate Conference, 30 giugno 2010.
  8. ^ (EN) Tentative Timeline of the Development of New Hash Functions, NIST, 10 dicembre 2008. URL consultato il 15 settembre 2009.
  9. ^ (EN) Bruce Schneier, Skein and SHA-3 News, 19 novembre 2008. URL consultato il 23 dicembre 2008.
  10. ^ (EN) Jason Lee, HASH 2X in TI BASIC Developer, 6 novembre 2008. URL consultato il 6 novembre 2008.
  11. ^ (EN) HASH 2X in TI BASIC Developer, 6 novembre 2008. URL consultato il 6 novembre 2008.
  12. ^ (EN) Robert J. Jenkins Jr., Algorithm Specification. URL consultato il 15 dicembre 2008.
  13. ^ (EN) Anne Canteaut and María Naya-Plasencia, Internal collision attack on Maraca (PDF). URL consultato il 15 dicembre 2008.
  14. ^ (EN) Geoffrey Park, NKS 2D Cellular Automata Hash (PDF). URL consultato il 9 novembre 2008.
  15. ^ (EN) Cristophe De Cannière, Collisions for NKS2D-224, 13 novembre 2008. URL consultato il 14 novembre 2008.
  16. ^ (EN) Brandon Enright, Collisions for NKS2D-512, 14 novembre 2008. URL consultato il 14 novembre 2008.
  17. ^ (EN) Peter Schmidt-Nielsen, Ponic (PDF). URL consultato il 9 novembre 2008.
  18. ^ (EN) María Naya-Plasencia, Second preimage attack on Ponic (PDF). URL consultato il 30 novembre 2008.
  19. ^ (EN) Nicolas T. Courtois, Carmi Gressel, Avi Hecht, Gregory V. Bard, Ran Granot, ZK-Crypt Homepage. URL consultato il 1 marzo 2009.
  20. ^ NIST official Round One Candidates web site
  21. ^ (EN) Neil Sholer, Abacus: A Candidate for SHA-3 (PDF), 29 ottobre 2008. URL consultato l'11 dicembre 2008.
  22. ^ (EN) Gregory G. Rose, Design and Primitive Specification for Boole (PDF). URL consultato il 2008-11-08.
  23. ^ (EN) Gregory G. Rose, OFFICIAL COMMENT: BOOLE (PDF), 10 Dec 2008. URL consultato il 23 dicembre 2008.
  24. ^ (EN) David A. Wilson, The DCH Hash Function (PDF), 23 ottobre 2008. URL consultato il 23 novembre 2008.
  25. ^ (EN) Natarajan Vijayarangan, A NEW HASH ALGORITHM: Khichidi-1 (PDF). URL consultato l'11 dicembre 2008.
  26. ^ (EN) Björn Fay, MeshHash (PDF). URL consultato il 30 novembre 2008.
  27. ^ (EN) Orhun Kara, Adem Atalay, Ferhat Karakoc and Cevat Manap, SHAMATA hash function: A candidate algorithm for NIST competition. URL consultato il 10 novembre 2008.
  28. ^ (EN) Michal Trojnara, StreamHash Algorithm Specifications and Supporting Documentation (PDF), 14 ottobre 2008. URL consultato il 15 dicembre 2008.
  29. ^ (EN) Rafael Alvarez, Gary McGuire and Antonio Zamora, The Tangle Hash Function (PDF). URL consultato l'11 dicembre 2008.
  30. ^ (EN) John Washburn, WAMM: A CANDIDATE ALGORITHM FOR THE SHA-3 COMPETITION (PDF). URL consultato il 9 11 2008.
  31. ^ (EN) OFFICIAL COMMENT: WaMM is Withdrawn (PDFauthor=John Washburn), 20 Dec 2008. URL consultato il 23 dicembre 2008.
  32. ^ (EN) Bob Hattersly, Waterfall Hash - Algorithm Specification and Analysis (PDF), 15 ottobre 2008. URL consultato il 9 11 2008.
  33. ^ (EN) Bob Hattersley, OFFICIAL COMMENT: Waterfall is broken (PDF), 20 Dec 2008. URL consultato il 23 dicembre 2008.
  34. ^ (EN) Tetsu Iwata, Kyoji Shibutani, Taizo Shirai, Shiho Moriai, Toru Akishita, AURORA: A Cryptographic Hash Algorithm Family (PDF), October 31, 2008. URL consultato l'11 December 2008.
  35. ^ (EN) Niels Ferguson, Stefan Lucks, Attacks on AURORA-512 and the Double-Mix Merkle-Damgaard Transform (PDF), 2009. URL consultato il 10 luglio 2009.
  36. ^ (EN) Colin Bradbury, BLENDER: A Proposed New Family of Cryptographic Hash Algorithms (PDF), 25 ottobre 2008. URL consultato l'11 dicembre 2008.
  37. ^ (EN) Craig Newbold, Observations and Attacks On The SHA-3 Candidate Blender (PDF). URL consultato il 23 December 2008.
  38. ^ (EN) Florian Mendel, Preimage Attack on Blender (PDF). URL consultato il 23 dicembre 2008.
  39. ^ (EN) Dmitry Khovratovich, Alex Biryukov, Ivica Nikolić, The Hash Function Cheetah: Specification and Supporting Documentation (PDF), 30 ottobre 2008. URL consultato l'11 dicembre 2008.
  40. ^ (EN) Danilo Gligoroski, Danilo Gligoroski - Cheetah hash function is not resistant against length-extension attack, 2008-12-12. URL consultato il 21 dicembre 2008.
  41. ^ (EN) Zijie Xu, Dynamic SHA (PDF). URL consultato l'11 dicembre 2008.
  42. ^ (EN) Vlastimil Klima, Dynamic SHA is vulnerable to generic attacks, 2008-12-14. URL consultato il 21 dicembre 2008.
  43. ^ (EN) Zijie Xu, Dynamic SHA2 (PDF), NIST. URL consultato l'11 dicembre 2008.
  44. ^ (EN) Vlastimil Klima, Dynamic SHA2 is vulnerable to generic attacks, 2008-12-14. URL consultato il 21 dicembre 2008.
  45. ^ (EN) Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, edon-r, November 4, 2008. URL consultato il 10 November 2008.
  46. ^ (EN) Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann, Cryptanalysis of Edon-R, 2008. URL consultato il 10 luglio 2009.
  47. ^ (EN) Sean O'Neil, Karsten Nohl, Luca Henzen, EnRUPT - The Simpler The Better, 31 ottobre 2008. URL consultato il 10 novembre 2008.
  48. ^ (EN) Sebastiaan Indesteege, Collisions for EnRUPT, 6 novembre 2008. URL consultato il 2008-11-07.
  49. ^ (EN) Jason Worth Martin, ESSENCE: A Candidate Hashing Algorithm for the NIST Competition (PDF), October 21, 2008. URL consultato il 2008-11-08.
  50. ^ (EN) Cryptanalysis of ESSENCE (PDF).
  51. ^ (EN) Ivica Nikolić, Alex Biryukov, Dmitry Khovratovich, Hash family LUX - Algorithm Specifications and Supporting Documentation (PDF). URL consultato l'11 dicembre 2008.
  52. ^ (EN) Mikhail Maslennikov, MCSSHA-3 hash algorithm. URL consultato il 2008-11-08.
  53. ^ (EN) Jean-Philippe Aumasson and María Naya-Plasencia, Second preimages on MCSSHA-3 (PDF). URL consultato il 14 novembre 2008.
  54. ^ (EN) Peter Maxwell, The Sgàil Cryptographic Hash Function (PDF), settembre 2008. URL consultato il 9 11 2008.
  55. ^ (EN) Peter Maxwell, Aww, p*sh!, 5 novembre 2008. URL consultato il 2008-11-06.
  56. ^ (EN) Michael Gorski, Ewan Fleischmann, Christian Forler, The Twister Hash Function Family (PDF), 28 ottobre 2008. URL consultato l'11 December 2008.
  57. ^ (EN) Florian Mendel, Christian Rechberger, Martin Schläffer, Cryptanalysis of Twister (PDF), 2008. URL consultato il 19 maggio 2009.
  58. ^ (EN) Michael Kounavis, Shay Gueron, Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication, November 3, 2008. URL consultato l'11 novembre 2008.
  59. ^ (EN) Jean-Philippe Aumasson, Orr Dunkelman, Florian Mendel, Christian Rechberger, Søren S. Thomsen, Cryptanalysis of Vortex (PDF), 2009. URL consultato il 19 maggio 2009.
  60. ^ (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), 29 ottobre 2008. URL consultato l'11 dicembre 2008.
  61. ^ (EN) Philip Hawkes, Cameron McDonald, Submission to the SHA-3 Competition: The CHI Family of Cryptographic Hash Algorithms, 30 ottobre 2008. URL consultato l'11 novembre 2008.
  62. ^ (EN) Jacques Patarin, Louis Goubin, Mickael Ivascot, William Jalby, Olivier Ly, Valerie Nachef, Joana Treger, Emmanuel Volte, CRUNCH. URL consultato il 14 novembre 2008.
  63. ^ (EN) Hirotaka Yoshida, Shoichi Hirose, Hidenori Kuwakado, SHA-3 Proposal: Lesamnta (PDF), 30 ottobre 2008. URL consultato l'11 dicembre 2008.
  64. ^ (EN) Kerem Varıcı, Onur Özen and Çelebi Kocair, The Sarmal Hash Function. URL consultato il 12 ottobre 2010.
  65. ^ (EN) Daniel Penazzi, Miguel Montes, The TIB3 Hash. URL consultato il 2008-11-29.
  66. ^ (EN) Svein Johan Knapskog, Danilo Gligoroski, Vlastimil Klima, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes, blue_midnight_wish, November 4, 2008. URL consultato il 10 November 2008.
  67. ^ (EN) Søren S. Thomsen, Pseudo-cryptanalysis of Blue Midnight Wish (PDF), 2009. URL consultato il 19 maggio 2009.
  68. ^ (EN) Henri Gilbert, Ryad Benadjila, Olivier Billet, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin, SHA-3 Proposal: ECHO (PDF), 29 ottobre 2008. URL consultato l'11 dicembre 2008.
  69. ^ (EN) Özgül Kücük, The Hash Function Hamsi (PDF), 31 ottobre 2008. URL consultato l'11 dicembre 2008.
  70. ^ (EN) Dai Watanabe, Christophe De Canniere, Hisayoshi Sato, Hash Function Luffa: Specification (PDF), 31 ottobre 2008. URL consultato l'11 dicembre 2008.
  71. ^ (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), 28 ottobre 2008. URL consultato l'11 dicembre 2008.
  72. ^ (EN) Eli Biham, Orr Dunkelman, The SHAvite-3 Hash Function (PDF). URL consultato l'11 dicembre 2008.
  73. ^ (EN) THIRD (FINAL) ROUND CANDIDATES Retrieved 9 Nov 2011
  74. ^ (EN) SHA-3 Finalists Announced by NIST
  75. ^ (EN) Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competition
  76. ^ (EN) Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (PDF). Retrieved 2 March 2011
  77. ^ (EN) NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition

Collegamenti esterni[modifica | modifica sorgente]