RadioGatún es un primitivo hash criptográfico creado por Guido Bertoni, Joan Daemen , Michaël Peeters y Gilles Van Assche . Se presentó públicamente por primera vez en el segundo taller de hash criptográfico del NIST, celebrado en Santa Bárbara, California , del 24 al 25 de agosto de 2006, como parte del concurso de funciones hash del NIST . El mismo equipo que desarrolló RadioGatún pasó a realizar revisiones considerables a esta primitiva criptográfica , lo que llevó al algoritmo Keccak SHA-3. [1]
RadioGatún es una familia de 64 funciones hash diferentes, que se distinguen por un solo parámetro, el ancho de palabra en bits ( w ), ajustable entre 1 y 64. Los únicos tamaños de palabra con vectores de prueba oficiales son las variantes de 32 bits y 64 bits de RadioGatún. El algoritmo usa 58 palabras, cada una con w bits, para almacenar su estado interno, por lo que la versión de 32 bits necesita 232 bytes para almacenar su estado (ya que cada palabra necesita 32 bits o cuatro bytes, y 58 multiplicado por cuatro es 232) y la versión de 64 bits 464 bytes (cada palabra utiliza ocho bytes).
Aunque RadioGatún es un derivado de Panamá , un cifrado de flujo y una construcción de hash de fines de la década de 1990 cuya construcción de hash se ha roto, RadioGatún no tiene las debilidades de Panamá cuando se usa como función hash. A partir de 2019, RadioGatún sigue siendo una función hash segura; [2] [3] [4] la versión más grande de RadioGatún que está rota es la que tiene un tamaño de palabra de dos bits.
RadioGatún se puede utilizar como función hash o como cifrado de flujo; puede generar un flujo arbitrariamente largo de números pseudoaleatorios ; este tipo de construcción hash se conoce ahora como una "función de salida extensible" (XOF). [5]
Fuerza reclamada
Los diseñadores del algoritmo, en el artículo original de RadioGatún, afirmaron que los primeros 19 × w bits (donde w es el ancho de palabra utilizado) de la salida de RadioGatún es una función hash criptográficamente segura. [6]
Desde la publicación del artículo, los diseñadores revisaron su reclamo de seguridad, y ahora afirman que RadioGatún tiene la seguridad de una función de esponja criptográfica con una capacidad de 19 w . [7] Esto significa que la versión de 32 bits de RadioGatún se puede utilizar para hacer un hash con 304 bits de seguridad (tanto de ataques de colisión como de Preimage ), y la versión de 64 bits ofrece 608 bits de seguridad.
Detalles de implementacion
Los diseñadores llaman a RadioGatún una "función ideal para destrozar". RadioGatún utiliza un "cinturón" y un "molino" para procesar criptográficamente datos binarios, y la mayoría de las operaciones de manipulación se realizan en la parte del "molino" de RadioGatún. [8]
Keccak se quitó el cinturón, aumentó el tamaño del molino de 19 palabras a 25 palabras e hizo que la función del molino fuera algo más complicada. [9]
La función del cinturón central se ve así:
( A , B ) = R ( un , b ) para la fila = 0 a 2 hago para todo i hago B [ i , fila ] = b [ i + 1 mod 13 , fila ] extremo de extremo para { Belt función : sencilla rotación } para i = 0 a 11 do B [ i + 1 , i mod 3 ] = B [ i + 1 , i mod 3 ] ⊕ a [ i + 1 ] end for { Mill to belt feedforward } A = Mill ( a ) { Función de fresado } para i = 0 a 2 hacer A [ i + 13 ] = A [ i + 13 ] ⊕ b [ 12 , i ] final para { Cinta a fresar avance }
Y la función de molino Molino (A) se ve así:
{ Todos los índices deben ser tomados en módulo 19 , x » y denota bit a bit de rotación ( rotación x derecha Y pedacitos ) x ⊕ y denota exclusiva o x | ~ Y denota que realizan un bit a bit o entre X y el bit a bit negación de y } para todo i do a [ i ] = un [ i ] ⊕ ( una [ i + 1 ] | ~ un [ i + 2 ]) final de { γ : no - linealidad } para todo i hago un [ i ] = a [ 7 i ] » i ( i + 1 ) / 2 final para { π : intra - palabra y inter - palabra dispersión } para todo i hago a [ i ] = a [ i ] ⊕ un [ i + 1 ] ⊕ un [ i + 4 ] final para { θ : difusión } A [ 0 ] = A [ 0 ] ⊕ 1 { ι : asimetría }
La página de Wikilibros de RadioGatún proporciona detalles completos de implementación.
Criptoanálisis
En el artículo "Dos ataques a RadioGatún", Dmitry Khovratovich presenta dos ataques que no rompen las pretensiones de seguridad de los diseñadores, uno con una complejidad de 2 18 w y otro con una complejidad de 2 23,1 w . [10] Khovratovich también fue autor de un artículo, titulado "Criptoanálisis de funciones hash con estructuras", que describe un ataque con una complejidad de 2 18 w . [11]
En el trabajo "Análisis de la resistencia a colisiones de RadioGatún mediante técnicas algebraicas", Charles Bouillaguet y Pierre-Alain Fouque presentan una forma de generar colisiones con la versión de 1 bit del algoritmo mediante un ataque que necesita 2 24,5 operaciones. [12] El ataque no puede extenderse a versiones más grandes ya que "todas las pistas posibles que conocíamos para la versión de 1 bit resultaron imposibles de extender a versiones de n bits". Este ataque es menos efectivo que los otros ataques y tampoco rompe el reclamo de seguridad de RadioGatún.
El ataque más eficaz contra el algoritmo, uno con una complejidad de 2 11 w , se da en el artículo "Criptoanálisis de RadioGatun" de Thomas Fuhr y Thomas Peyrin. En el periódico, rompen la versión de 2 bits (tamaño de palabra de dos) de RadioGatún. [13] Si bien es más efectivo que los otros ataques, este ataque aún no rompe el reclamo de seguridad.
Los desarrolladores de RadioGatún han manifestado que sus "propios experimentos no inspiraron confianza en RadioGatún". [14]
Vectores de prueba
Las únicas variantes de RadioGatún para las que los diseñadores proporcionaron vectores de prueba (valores hash publicados para entradas de muestra para que los programadores puedan verificar que están implementando correctamente el algoritmo) son las versiones de 32 bits y 64 bits.
RadioGatún [32]
Estos vectores de prueba, generados usando la versión de 32 bits de RadioGatún, solo muestran los primeros 256 bits del flujo de salida arbitrariamente largo de RadioGatún [32]:
RadioGatun [32] ("") =F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun [32] ( "El rápido zorro marrón salta sobre el perezoso d og") =191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun [32] ("El rápido zorro marrón salta sobre el perezoso c og") =EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
RadioGatún [64]
Aquí hay hash para la versión de 64 bits:
RadioGatun [64] ("") =64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun [64] ( "El rápido zorro marrón salta sobre el perezoso d og") =6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun [64] ("El rápido zorro marrón salta sobre el perezoso c og") =C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
Referencias
- ^ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; Van Assche, Gilles. "El Camino de Panamá a Keccak vía RadioGatún" . Consultado el 20 de octubre de 2009 .
- ^ Kishore, Neha; Raina, Priya (2019). "Hashing criptográfico paralelo: Desarrollos en los últimos 25 años". Cryptologia . 43 (6): 504–535. doi : 10.1080 / 01611194.2019.1609130 .
RadioGatún (Bertoni et al. 2006) sigue siendo seguro
- ^ Thomas Pornin (3 de abril de 2011 ). "Necesita una sugerencia para una comparación más rápida de huellas dactilares / hash de Linux" .
Entre los que cito, las funciones de Radiogatun y Shabal están actualmente intactas.
- ^ Zooko Wilcox (24 de febrero de 2017). "Lecciones de la historia de los ataques a las funciones de hash seguro" . Consultado el 28 de junio de 2018 .
Tampoco hasta ahora ninguna nueva función hash segura (diseñada aproximadamente después del año 2000) ha sucumbido a los ataques de colisión.
- ^ http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
- ^ En la página 9 (Sección 6) de "RadioGatún, una función hash de cinta y molino" establece que "RadioGatún [l w ] ofrece un nivel de seguridad indicado por una capacidad c = 19 * w. Para la versión de 64 bits RadioGatún este es una capacidad de 1216 bits, para la versión de 32 bits y la versión de 16 bits esto da 608 y 304 bits respectivamente ".
- ^ http://radiogatun.noekeon.org/ "Ahora preferimos expresar el reclamo de seguridad para RadioGatún como un reclamo de esponja plana con capacidad 19 w "
- ^ "RadioGatún, una función hash de cinta y molino" (PDF) . 2006-07-20.
- ^ "El camino de Panamá a Keccak vía RadioGatún" (PDF) . Archivado desde el original (PDF) el 5 de agosto de 2018.
Para Keccak, por lo tanto, hemos decidido quitar el cinturón y, en cambio, aumentar el número de palabras en el molino.
- ^ Khovratovich, Dmitry. "Dos atentados a RadioGatún" (PDF) . Archivado desde el original (PDF) el 7 de agosto de 2018.
- ^ https://www.cryptolux.org/images/7/79/Struct.pdf
- ^ Bouillaguet, Charles; Fouque, Pierre-Alain. "Análisis de la resistencia a colisiones de RadioGatun mediante técnicas algebraicas" .
- ^ Fuhr, Thomas; Peyrin, Thomas. "Criptoanálisis de RadioGatun" .
- ^ "Keccak y la estandarización SHA-3" (PDF) .
enlaces externos
- La Familia de Funciones Hash de RadioGatún, página web oficial de RadioGatún, con la descripción oficial del hash, código de referencia de dominio público y vectores de prueba
- rg32hash , una implementación de dominio público independiente de la versión de 32 bits de RadioGatún