RadioGatún
RadioGatún è una funzione di hash crittografica creata da Guido Bertoni, Joan Daemen, Michaël Peeters e Gilles Van Assche. Fu presentata al pubblico per la prima volta al NIST Second Cryptographic Hash Workshop a Santa Barbara, California, il 24-25 agosto 2006, come parte della Competizione NIST delle funzioni hash.
Sebbene RadioGatún sia un derivato di Panama, un cifrario a flusso e struttura hash degli anni 1990, in seguito decifrata, non ha le sue stesse debolezze quando viene usata come funzione hash.
RadioGatún è attualmente una famiglia di 64 differenti funzioni hash, distinte da un singolo parametro: la larghezza della parola in bit (w), regolabile da 1 a 64. L'algoritmo usa 58 parole, ognuna della lunghezza w, per memorizzare il suo stato interno. Quindi, per esempio, la versione 32-bit ha bisogno di 232 byte per memorizzare lo stato, mentre la versione 64-bit di 464 byte.
RadioGatún può essere usato sia come funzione hash, sia come cifrario a flusso; può dare in output un lungo flusso arbitrario di numeri pseudo-casuali; questo tipo di struttura hash è ora conosciuta come un "Extendable-Output Function" (XOF)[1].
Lo stesso team che ha sviluppato l'algoritmo ha continuato a fare considerevoli revisioni a questa funzione di hash, conducendosi all'algoritmo Keccak SHA-3[2].
Robustezza[modifica | modifica wikitesto]
Nel documento originale di RadioGatún, gli sviluppatori affermarono che i primi 19 × w bit (dove w è la lunghezza della parola usata) dell'output fossero una funzione hash "crittograficamente sicura"[3]. In altre parole, affermarono che i primi 608 bit della versione 32-bit e i primi 1216 bit della versione 64-bit potevano essere usati come valore hash.
Considerando l'attacco del compleanno, questo significa che per una data lunghezza w, l'algoritmo è progettato per non avere un attacco con complessità inferiore a 29.5w. Questo corrisponde a 2304 (32-bit) e 2608 (64-bit).
Fin dalla pubblicazione del documento, gli sviluppatori rividero la loro pretesa sulla sicurezza e ora affermano che RadioGatún ha la sicurezza di una funzione spugna con una capacità di 19w[4]. Ciò significa che la versione a 32-bit dell'algoritmo può essere usata per creare hash con 304 bit di sicurezza e la versione 64-bit per crearne 608.
Criptoanalisi[modifica | modifica wikitesto]
Nel documento "Two attacks on RadioGatún", Dmitry Khovratovich e Alex Biryukov presentano due attacchi che non riescono a rompere la sicurezza dichiarata dagli sviluppatori, uno con complessità di 218w e un altro di 223.1w[5]. Khovratovich fu anche l'autore di "Cryptanalysis of hash functions with structures", che descrive un attacco con complessità 218w[6].
Nel documento "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Charles Bouillaguet e Pierre-Alain Fouque presentano un modo di generare collisioni con la versione 1-bit dell'algoritmo, usando un attacco che necessita di 224.5 operazioni[7]. L'attacco non può essere esteso alle versioni più grandi fino a che "tutte le possibili piste che conoscevamo per la versione 1-bit non si siano rivelate impossibili da estendere alle versioni n-bit". Questo attacco è meno efficace di altri attacchi, oltre a non rompere la sicurezza dichiarata di RadioGatún.
L'attacco che si è rivelato più efficace contro RadioGatún aveva una complessità di 211w ed è presente nel documento "Cryptanalysis of RadioGatun" di Thomas Fuhr and Thomas Peyrin[8]. Sebbene fosse l'attacco più efficace, questo non è comunque riuscito a scalfire la sicurezza.
Gli sviluppatori di RadioGatún hanno dichiarato che i loro "personali esperimenti non ispirano confidenza in RadioGatún"[9].
Esempi[modifica | modifica wikitesto]
Le uniche versioni che supportano vettori di test sono quelle a 32-bit e a 64-bit.
Questi vettori di test mostrano solamente i primi 256 bit dell'output del lungo flusso di uscita di RadioGatún:
RadioGatun[32]("") =
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun[32]("The quick brown fox jumps over the lazy dog") =
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun[32]("The quick brown fox jumps over the lazy cog") =
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
E gli hash in versione 64-bit:
RadioGatun[64]("") =
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun[64]("The quick brown fox jumps over the lazy dog") =
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun[64]("The quick brown fox jumps over the lazy cog") =
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
Note[modifica | modifica wikitesto]
- ^ http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
- ^ Bertoni, Guido, Daemen, Joan, Peeters, Michaël e Van Assche, Gilles, The Road from Panama to Keccak via RadioGatún, su drops.dagstuhl.de. URL consultato il 20 ottobre 2009.
- ^ Page 9 (Section 6) of "RadioGatún, a belt-and-mill hash function" states that "RadioGatún [lw] offers a security level indicated by a capacity c = 19 * w. For the 64-bit version RadioGatún this is a capacity of 1216 bits, for the 32-bit version and 16-bit version this gives 608 and 304 bits respectively."
- ^ http://radiogatun.noekeon.org/ "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19w"
- ^ Dmitry Khovratovich e Alex Biryukov, Two attacks on RadioGatún (PDF), su lj.streamclub.ru.[collegamento interrotto]
- ^ https://www.cryptolux.org/images/7/79/Struct.pdf
- ^ Charles Bouillaguet e Pierre-Alain Fouque, Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques, su hal.archives-ouvertes.fr.
- ^ Thomas Fuhr e Thomas Peyrin, Cryptanalysis of RadioGatun, su eprint.iacr.org.
- ^ Keccak and the SHA-3 Standardization (PDF), su csrc.nist.gov.
Collegamenti esterni[modifica | modifica wikitesto]
- Sito web ufficiale di RadioGatún, con la descrizione ufficiale dell'hash, riferimenti e vettori di test.
- rg32hash, un'implementazione indipendente e di dominio pubblico della versione 32-bit di RadioGatún
