SHA-3

Conjunto de funciones hash criptográficas

SHA-3 ( Secure Hash Algorithm 3 ) es el último ^[4] miembro de la familia de estándares Secure Hash Algorithm , publicado por NIST el 5 de agosto de 2015. ^{[5] [6] [7]} Aunque es parte de la misma serie de estándares, SHA-3 es internamente diferente de la estructura similar a MD5 de SHA-1 y SHA-2 .

SHA-3 es un subconjunto de la familia criptográfica más amplia de primitivos Keccak ( /ˈkɛtʃæk/ o /ˈkɛtʃɑːk/ ) , [ 8 ] [ 9 ] diseñada por Guido Bertoni ^{, Joan} Daemen , Michaël Peeters y Gilles Van Assche , basándose en RadioGatún . Los autores de Keccak han propuesto usos adicionales para la función, no estandarizados (aún) por el NIST, incluyendo un cifrado de flujo , un sistema de cifrado autenticado , un esquema de hash de "árbol" para un hash más rápido en ciertas arquitecturas, ^{[10] [11]} y los cifrados AEAD Keyak y Ketje. ^{[12] [13]}

Keccak se basa en un enfoque novedoso llamado construcción de esponjas . ^[14] La construcción de esponjas se basa en una amplia función aleatoria o permutación aleatoria , y permite introducir ("absorber" en la terminología de las esponjas) cualquier cantidad de datos y extraer ("comprimir") cualquier cantidad de datos, mientras actúa como una función pseudoaleatoria con respecto a todas las entradas anteriores. Esto conduce a una gran flexibilidad.

A partir de 2007, el NIST no tenía previsto retirar SHA-2 ni eliminarlo del Estándar de Hash Seguro revisado. ^{[ ¿Necesita actualización? ]} El propósito de SHA-3 es que pueda sustituirse directamente por SHA-2 en las aplicaciones actuales si es necesario, y mejorar significativamente la robustez del conjunto de herramientas de algoritmos hash general del NIST. ^[15]

Para mensajes de tamaño pequeño, los creadores de los algoritmos Keccak y las funciones SHA-3 sugieren utilizar la función más rápida KangarooTwelve con parámetros ajustados y un nuevo modo de hash de árbol sin sobrecarga adicional.

Historia

El algoritmo Keccak es obra de Guido Bertoni, Joan Daemen (quien también codiseñó el cifrado Rijndael con Vincent Rijmen ), Michaël Peeters y Gilles Van Assche . Se basa en los diseños de funciones hash anteriores PANAMA y RadioGatún . PANAMA fue diseñado por Daemen y Craig Clapp en 1998. RadioGatún, un sucesor de PANAMA, fue diseñado por Daemen, Peeters y Van Assche, y fue presentado en el NIST Hash Workshop en 2006. ^[16] El código fuente de la implementación de referencia fue dedicado al dominio público a través de una exención CC0 . ^[17]

En 2006, el NIST comenzó a organizar la competencia de funciones hash del NIST para crear un nuevo estándar hash, SHA-3. SHA-3 no está destinado a reemplazar a SHA-2 , ya que no se ha demostrado públicamente ningún ataque significativo a SHA-2 ^{[ necesita actualización ]} . Debido a los ataques exitosos a MD5 , SHA-0 y SHA-1 , ^{[18] [19]} el NIST percibió la necesidad de un hash criptográfico alternativo y diferente, que se convirtió en SHA-3.

Después de un período de preparación, las admisiones debían presentarse a fines de 2008. Keccak fue aceptado como uno de los 51 candidatos. En julio de 2009, se seleccionaron 14 algoritmos para la segunda ronda. Keccak avanzó a la última ronda en diciembre de 2010. ^[20]

Durante la competición, a los participantes se les permitió "modificar" sus algoritmos para solucionar los problemas que se descubrieron. Los cambios que se han realizado en Keccak son: ^{[21] [22]}

• El número de rondas se incrementó de 12 + ℓ a 12 + 2ℓ para ser más conservadores en cuanto a la seguridad.
• El relleno del mensaje se cambió de un esquema más complejo al patrón simple 10 ^* 1 que se describe a continuación.
• La tasa r se incrementó hasta el límite de seguridad, en lugar de redondearse a la potencia de 2 más cercana.

El 2 de octubre de 2012, Keccak fue seleccionado como el ganador del concurso. ^[8]

En 2014, el NIST publicó un borrador de FIPS 202 "Estándar SHA-3: funciones de salida extensibles y hash basadas en permutación". ^[23] FIPS 202 fue aprobado el 5 de agosto de 2015. ^[24]

El 5 de agosto de 2015, el NIST anunció que SHA-3 se había convertido en un estándar de hash. ^[25]

La controversia se debilita

A principios de 2013, el NIST anunció que seleccionaría valores diferentes para la "capacidad", el parámetro general de fuerza vs. velocidad, para el estándar SHA-3, en comparación con la presentación. ^{[26] [27]} Los cambios provocaron cierta agitación.

La competencia de funciones hash exigía funciones hash al menos tan seguras como las instancias SHA-2. Esto significa que una salida de d bits debería tener una resistencia de d /2 bits a ataques de colisión y una resistencia de d bits a ataques de preimagen , el máximo alcanzable para d bits de salida. La prueba de seguridad de Keccak permite un nivel ajustable de seguridad basado en una "capacidad" c , proporcionando una resistencia de c /2 bits tanto a ataques de colisión como de preimagen. Para cumplir con las reglas de competencia originales, los autores de Keccak propusieron c = 2 d . El cambio anunciado fue aceptar la misma seguridad de d /2 bits para todas las formas de ataque y estandarizar c = d . Esto habría acelerado Keccak al permitir que se aplicaran hashes a d bits adicionales de entrada en cada iteración. Sin embargo, las funciones hash ya no habrían sido reemplazos directos con la misma resistencia de preimagen que SHA-2; se habrían reducido a la mitad, lo que la habría vuelto vulnerable a los avances en computación cuántica, que efectivamente la reducirían a la mitad una vez más. ^[28]

En septiembre de 2013, Daniel J. Bernstein sugirió en la lista de correo del foro de hash del NIST ^[29] reforzar la seguridad a la capacidad de 576 bits que se propuso originalmente como la predeterminada para Keccak, además de las especificaciones SHA-3 y no incluidas en ellas. ^[30] Esto habría proporcionado al menos un SHA3-224 y SHA3-256 con la misma resistencia a la preimagen que sus predecesores SHA-2, pero SHA3-384 y SHA3-512 habrían tenido una resistencia a la preimagen significativamente menor que sus predecesores SHA-2. A fines de septiembre, el equipo de Keccak respondió afirmando que habían propuesto una seguridad de 128 bits al establecer c = 256 como una opción ya en su propuesta SHA-3. ^[31] Aunque la capacidad reducida era justificable en su opinión, a la luz de la respuesta negativa, propusieron aumentar la capacidad a c = 512 bits para todas las instancias. Esto sería igual a cualquier estándar anterior hasta el nivel de seguridad de 256 bits, al tiempo que ofrecería una eficiencia razonable, ^[32] pero no la resistencia de preimagen de 384/512 bits que ofrecen SHA2-384 y SHA2-512. Los autores afirmaron que "afirmar o confiar en niveles de seguridad superiores a 256 bits no tiene sentido".

A principios de octubre de 2013, Bruce Schneier criticó la decisión del NIST basándose en sus posibles efectos perjudiciales para la aceptación del algoritmo, diciendo:

Hay demasiada desconfianza en el aire. El NIST corre el riesgo de publicar un algoritmo en el que nadie confiará y que nadie (excepto aquellos obligados) utilizará. ^[33]

Más tarde se retractó de su declaración anterior, diciendo:

Me equivoqué al escribir que el NIST hizo "cambios internos" al algoritmo. Fue un descuido de mi parte. La permutación de Keccak permanece inalterada. Lo que propuso el NIST fue reducir la capacidad de la función hash en nombre del rendimiento. Una de las características interesantes de Keccak es que es altamente ajustable. ^[33]

Paul Crowley, criptógrafo y desarrollador senior de una empresa de desarrollo de software independiente, expresó su apoyo a la decisión y dijo que se supone que Keccak es ajustable y que no hay razón para que haya diferentes niveles de seguridad dentro de un mismo código primitivo. También agregó:

Sí, es una pena que la competencia exigiera un determinado nivel de seguridad a los participantes y luego publicara una norma con un nivel diferente. Pero no hay nada que se pueda hacer para solucionarlo ahora, excepto reabrir la competencia. Exigirles que se ciñan a su error no mejora las cosas para nadie. ^[34]

Hubo cierta confusión sobre si se pudieron haber realizado cambios internos en Keccak, que fueron aclarados por el equipo original, afirmando que la propuesta del NIST para SHA-3 es un subconjunto de la familia Keccak, para la cual se pueden generar vectores de prueba utilizando su código de referencia enviado al concurso, y que esta propuesta fue el resultado de una serie de discusiones entre ellos y el equipo hash del NIST. ^[35]

En respuesta a la controversia, en noviembre de 2013 John Kelsey del NIST propuso volver a la propuesta original c = 2 d para todas las instancias de reemplazo directo de SHA-2. ^[36] La reversión se confirmó en borradores posteriores ^[37] y en la versión final. ^[5]

Diseño

La construcción de esponja para funciones hash. P _i son la entrada, Z _i son la salida hash. La "capacidad" no utilizada c debe ser el doble de la resistencia deseada a los ataques de colisión o preimagen .

SHA-3 utiliza la construcción de esponja ^[14] , en la que los datos son "absorbidos" en la esponja, luego el resultado es "exprimido". En la fase de absorción, los bloques de mensajes se combinan con XOR en un subconjunto del estado, que luego se transforma como un todo utilizando una función de permutación . (Llamar a una permutación puede ser confuso. Técnicamente es una permutación del espacio de estado, por lo tanto una permutación de un conjunto con elementos, pero hace más que simplemente permutar los bits del vector de estado. ^{[ cita requerida ]} ) En la fase de "expresión", los bloques de salida se leen del mismo subconjunto del estado, alternados con la función de transformación de estado . El tamaño de la parte del estado que se escribe y lee se llama "tasa" (denotada como ), y el tamaño de la parte que no es tocada por la entrada/salida se llama "capacidad" (denotada como ). La capacidad determina la seguridad del esquema. El nivel máximo de seguridad es la mitad de la capacidad. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle 2^{1600}\approx 4.4\cdot 10^{481}}$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle c}$

Dada una cadena de bits de entrada , una función de relleno , una función de permutación que opera en bloques de bits de ancho , una tasa y una longitud de salida , tenemos capacidad y la construcción de esponja , que produce una cadena de bits de longitud , funciona de la siguiente manera: ^{[6] : 18} ${\displaystyle N}$ ${\displaystyle pad}$ ${\displaystyle f}$ ${\displaystyle b}$ ${\displaystyle r}$ ${\displaystyle d}$ ${\displaystyle c=b-r}$ ${\displaystyle Z={\text{sponge}}[f,pad,r](N,d)}$ ${\displaystyle Z}$ ${\displaystyle d}$

• Rellene la entrada N utilizando la función pad, lo que produce una cadena de bits rellena P con una longitud divisible por (tal que es un entero) ${\displaystyle r}$ ${\displaystyle n={\text{len}}(P)/r}$
• dividir P en n fragmentos consecutivos de r bits P ₀ , ..., P _{n −1}
• inicializa el estado S a una cadena de b bits cero
• absorber la entrada en el estado: para cada bloque P _i :
  • Extiende P _i al final con una cadena de c bits cero, lo que produce uno de longitud b
  • XOR que con S
  • aplicar la permutación de bloque f al resultado, obteniendo un nuevo estado S
• inicializar Z para que sea la cadena vacía
• mientras la longitud de Z sea menor que d :
  • añade los primeros r bits de S a Z
  • Si Z todavía tiene una longitud menor a d bits, aplique f a S , lo que produce un nuevo estado S
• truncar los bits Z a d

El hecho de que el estado interno S contenga c bits de información adicionales a los que se envían a Z evita los ataques de extensión de longitud a los que son susceptibles SHA-2, SHA-1, MD5 y otros hashes basados ​​en la construcción Merkle–Damgård .

En SHA-3, el estado S consiste en una matriz de 5 × 5 palabras de w bits (con w = 64), b = 5 × 5 × w = 5 × 5 × 64 = 1600 bits en total. Keccak también se define para tamaños de palabra de potencia de 2 más pequeños, w hasta 1 bit (estado total de 25 bits). Los tamaños de estado pequeños se pueden utilizar para probar ataques criptoanalíticos, y los tamaños de estado intermedios (desde w = 8,200 bits, hasta w = 32,800 bits) se pueden utilizar en aplicaciones prácticas y livianas. ^{[12] [13]}

En el caso de las instancias SHA3-224, SHA3-256, SHA3-384 y SHA3-512, r es mayor que d , por lo que no es necesario realizar permutaciones de bloques adicionales en la fase de compresión; los d bits iniciales del estado son el hash deseado. Sin embargo, SHAKE128 y SHAKE256 permiten una longitud de salida arbitraria, lo que resulta útil en aplicaciones como el relleno de cifrado asimétrico óptimo .

Relleno

Para garantizar que el mensaje se pueda dividir de manera uniforme en bloques de r bits, se requiere relleno. SHA-3 utiliza el patrón 10…01 en su función de relleno: un bit 1, seguido de cero o más bits 0 (máximo r − 1 ) y un bit 1 final.

El máximo de r − 1 bits cero se produce cuando el último bloque de mensaje tiene una longitud de r − 1 bits. Luego se agrega otro bloque después del bit 1 inicial, que contiene r − 1 bits cero antes del bit 1 final.

Los dos bits 1 se añadirán incluso si la longitud del mensaje ya es divisible por r . ^{[6] : 5.1} En este caso, se añade otro bloque al mensaje, que contiene un bit 1, seguido de un bloque de r − 2 bits cero y otro bit 1. Esto es necesario para que un mensaje con una longitud divisible por r que termina en algo que parece relleno no produzca el mismo hash que el mensaje con esos bits eliminados.

Se requiere el bit 1 inicial para que los mensajes que difieren solo en unos pocos bits 0 adicionales al final no produzcan el mismo hash.

La posición del último bit 1 indica qué tasa r se utilizó (relleno multitasa), lo cual es necesario para que la prueba de seguridad funcione para diferentes variantes de hash. Sin él, las diferentes variantes de hash del mismo mensaje corto serían las mismas hasta el truncamiento.

La permutación de bloques

La transformación de bloques f , que es Keccak-f[1600] para SHA-3, es una permutación que utiliza operaciones XOR , AND y NOT , y está diseñada para una fácil implementación tanto en software como en hardware.

Se define para cualquier tamaño de palabra potencia de dos , w = 2 ^ℓ bits. La presentación principal de SHA-3 utiliza palabras de 64 bits, ℓ = 6 .

El estado puede considerarse como una matriz de bits de 5 × 5 × w . Sea a [ i ][  j ][ k ] el bit (5 i + j ) × w + k de la entrada, utilizando una convención de numeración de bits little-endian e indexación por fila principal . Es decir, i selecciona la fila, j la columna y k el bit.

La aritmética del índice se realiza módulo 5 para las dos primeras dimensiones y módulo w para la tercera.

La función básica de permutación de bloques consta de 12 + 2 ℓ rondas de cinco pasos:

θ (theta)

Calcular la paridad de cada una de las 5 columnas de 5 bits w (320, cuando w = 64 ) y aplicar la operación O-exclusiva en dos columnas cercanas siguiendo un patrón regular. Para ser precisos, a [ i ][  j ][ k ] ← a [ i ][  j ][ k ] ⊕ paridad(a[0...4][ j -1][ k ]) ⊕ paridad(a[0...4][ j +1][ k −1])

ρ (rho)

Gire bit a bit cada una de las 25 palabras por un número triangular diferente 0, 1, 3, 6, 10, 15, .... Para ser precisos, a [0][0] no se gira, y para todos los 0 ≤ t < 24 , a [ i ][  j ][ k ] ← a [ i ][  j ][ k −( t +1)( t +2)/2] , donde . ${\displaystyle {\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}}$

π (pi)

Permuta las 25 palabras en un patrón fijo. a [3 i +2 j ][ i ] ← a [  i ][ j ] .

χ (chi)

Combinación bit a bit a lo largo de las filas, utilizando x ← x ⊕ (¬ y & z ) . Para ser precisos, a [ i ][  j ][ k ] ← a [ i ][  j ][ k ] ⊕ (¬ a [ i ][  j + 1 ][ k ] & a [ i ][  j + 2 ][ k ]) . Esta es la única operación no lineal en SHA-3.

ι (iota)

Exclusivo-o una constante redonda en una palabra del estado. Para ser precisos, en la ronda n , para 0 ≤ m ≤ ℓ , se aplica una operación XOR a [0][0][2 ^m −1] con el bit m + 7 n de una secuencia LFSR de grado 8. Esto rompe la simetría que se conserva con los otros pasos.

Velocidad

La velocidad del hash SHA-3 de mensajes largos está dominada por el cálculo de f = Keccak-f[1600] y la operación XOR de S con el P _i extendido , una operación sobre b = 1600 bits. Sin embargo, dado que los últimos c bits del P _i extendido son 0 de todos modos, y la operación XOR con 0 es un NOP, es suficiente realizar operaciones XOR solo para r bits ( r = 1600 − 2 × 224 = 1152 bits para SHA3-224, 1088 bits para SHA3-256, 832 bits para SHA3-384 y 576 bits para SHA3-512). Cuanto menor sea r (y, a la inversa, cuanto mayor sea c = b − r = 1600 − r ), menos eficiente pero más seguro se vuelve el hash, ya que se pueden aplicar XOR a menos bits del mensaje en el estado (una operación rápida) antes de cada aplicación de f , que es computacionalmente costosa . Los autores informan las siguientes velocidades para las implementaciones de software de Keccak-f[1600] más XORing de 1024 bits, ^[1] que corresponde aproximadamente a SHA3-256:

• 57,4 cpb en IA-32, Intel Pentium 3 ^[38]
• 41 cpb en IA-32+MMX, Intel Pentium 3
• 20 cpb en IA-32+SSE, Intel Core 2 Duo o AMD Athlon 64
• 12,6 cpb en una máquina típica basada en x86-64
• 6–7 cpb en IA-64 ^[1]

Para el SHA3-256 exacto en x86-64, Bernstein mide 11,7–12,25 cpb dependiendo de la CPU. ^{[39] : 7} SHA-3 ha sido criticado por ser lento en arquitecturas de conjunto de instrucciones (CPU) que no tienen instrucciones diseñadas especialmente para calcular funciones Keccak más rápido: SHA2-512 es más del doble de rápido que SHA3-512, y SHA-1 es más del triple de rápido en un procesador Intel Skylake con una velocidad de reloj de 3,2 GHz. ^[40] Los autores han reaccionado a esta crítica sugiriendo utilizar SHAKE128 y SHAKE256 en lugar de SHA3-256 y SHA3-512, a expensas de reducir la resistencia de preimagen a la mitad (pero manteniendo la resistencia a la colisión). Con esto, el rendimiento está a la par con SHA2-256 y SHA2-512.

Sin embargo, en las implementaciones de hardware , SHA-3 es notablemente más rápido que todos los demás finalistas, ^[41] y también más rápido que SHA-2 y SHA-1. ^[40]

A partir de 2018, la arquitectura ARMv8 ^[42] de ARM incluye instrucciones especiales que permiten que los algoritmos Keccak se ejecuten más rápido y la arquitectura z/Architecture ^[43] de IBM incluye una implementación completa de SHA-3 y SHAKE en una sola instrucción. También ha habido propuestas de extensión para RISC-V para agregar instrucciones específicas de Keccak. ^[44]

Instancias

El estándar NIST define las siguientes instancias, para el mensaje M y la longitud de salida d : ^{[6] : 20, 23}

Con las siguientes definiciones

• Keccak[ c ]( N , d ) = esponja[Keccak-f[1600], almohadilla10 ^* 1, r ]( N , d ) ^{[6] : 20}
• Keccak-f[1600] = Keccak-p[1600, 24] ^{[6] : 17}
• c es la capacidad
• r es la tasa = 1600 − c
• N es la cadena de bits de entrada

Las instancias SHA-3 son reemplazos directos de SHA-2, diseñados para tener propiedades de seguridad idénticas.

SHAKE generará tantos bits de su esponja como se le solicite, por lo que es una función de salida extensible (XOF). Por ejemplo, SHAKE128(M, 256) se puede utilizar como una función hash con un flujo de bits de 256 caracteres con una seguridad de 128 bits. Se pueden utilizar longitudes arbitrariamente grandes como generadores de números pseudoaleatorios. Alternativamente, SHAKE256(M, 128) se puede utilizar como una función hash con una longitud de 128 bits y una resistencia de 128 bits. ^[6]

Todas las instancias añaden algunos bits al mensaje, de los cuales el más a la derecha representa el sufijo de separación de dominios . El propósito de esto es garantizar que no sea posible construir mensajes que produzcan la misma salida hash para diferentes aplicaciones de la función hash de Keccak. Existen los siguientes sufijos de separación de dominios: ^{[6] [45]}

Instancias adicionales

En diciembre de 2016, el NIST publicó un nuevo documento, NIST SP.800-185, ^[46] que describe funciones adicionales derivadas de SHA-3:

• X es la cadena de bits de entrada principal. Puede tener cualquier longitud, incluido cero.

• L es un entero que representa la longitud de salida solicitada en bits.

• N es una cadena de bits que representa el nombre de una función y que utiliza NIST para definir funciones basadas en cSHAKE. Cuando no se desea ninguna función que no sea cSHAKE, N se establece en la cadena vacía.

• S es una cadena de bits de personalización. El usuario selecciona esta cadena para definir una variante de la función. Cuando no se desea ninguna personalización, S se establece en la cadena vacía.

• K es una cadena de bits clave de cualquier longitud, incluido cero.

• B es el tamaño del bloque en bytes para el hash paralelo. Puede ser cualquier número entero tal que 0 < B < 2 ²⁰⁴⁰ .

Desarrollos posteriores

Canguro Doce

En 2016, el mismo equipo que creó las funciones SHA-3 y el algoritmo Keccak introdujo alternativas de rondas reducidas más rápidas (reducidas a 12 y 14 rondas, de las 24 en SHA-3) que pueden explotar la disponibilidad de ejecución paralela gracias al uso de hash de árbol : KangarooTwelve y MarsupilamiFourteen. ^[48]

Estas funciones se diferencian de ParallelHash, la función hash paralelizable basada en Keccak estandarizada por FIPS, con respecto al paralelismo, en que son más rápidas que ParallelHash para tamaños de mensajes pequeños.

El número reducido de rondas se justifica por el enorme esfuerzo criptoanalítico centrado en Keccak, que no produjo ataques prácticos a nada cercano a un Keccak de doce rondas. Estos algoritmos de mayor velocidad no son parte de SHA-3 (ya que son un desarrollo posterior) y, por lo tanto, no son compatibles con FIPS; pero debido a que utilizan la misma permutación de Keccak, son seguros siempre que no haya ataques a SHA-3 reducido a 12 rondas. ^[48]

KangarooTwelve es una versión de Keccak de rondas reducidas (de 24 a 12 rondas) y mayor rendimiento que afirma tener 128 bits de seguridad ^[49] mientras que tiene un rendimiento de hasta 0,55 ciclos por byte en una CPU Skylake . ^[50] Este algoritmo es un borrador de RFC de IETF . ^[51]

MarsupilamiFourteen, una ligera variación de KangarooTwelve, utiliza 14 rondas de la permutación Keccak y afirma tener 256 bits de seguridad. Nótese que la seguridad de 256 bits no es más útil en la práctica que la seguridad de 128 bits, pero puede ser requerida por algunos estándares. ^[49] 128 bits ya son suficientes para derrotar ataques de fuerza bruta en el hardware actual, por lo que tener seguridad de 256 bits no agrega valor práctico, a menos que el usuario esté preocupado por avances significativos en la velocidad de las computadoras clásicas . Para la resistencia contra las computadoras cuánticas , consulte a continuación.

KangarooTwelve y MarsupilamiFourteen son funciones de salida extensible, similares a SHAKE, por lo que generan una salida estrechamente relacionada para un mensaje común con diferente longitud de salida (la salida más larga es una extensión de la salida más corta). Esta propiedad no se exhibe en funciones hash como SHA-3 o ParallelHash (excepto las variantes XOF). ^[6]

La construcción de Farfalle

En 2016, el equipo de Keccak lanzó una construcción diferente llamada construcción Farfalle, y Kravatte, una instancia de Farfalle que utiliza la permutación Keccak-p, ^[52] así como dos algoritmos de cifrado autenticados Kravatte-SANE y Kravatte-SANSE ^[53].

Hashing de árboles de Sakura

RawSHAKE es la base de la codificación Sakura para el hash de árboles, que aún no se ha estandarizado. Sakura utiliza un sufijo de 1111 para nodos individuales, equivalente a SHAKE, y otros sufijos generados según la forma del árbol. ^{[45] : 16}

Seguridad contra ataques cuánticos

Hay un resultado general ( algoritmo de Grover ) de que las computadoras cuánticas pueden realizar un ataque de preimagen estructurado en , mientras que un ataque de fuerza bruta clásico necesita 2 ^d . Un ataque de preimagen estructurado implica un segundo ataque de preimagen ^[28] y, por lo tanto, un ataque de colisión . Una computadora cuántica también puede realizar un ataque de cumpleaños , rompiendo así la resistencia a la colisión, en ^[54] (aunque esto es discutido). ^[55] Observando que la fuerza máxima puede ser , esto da los siguientes límites superiores ^[56] en la seguridad cuántica de SHA-3: ${\displaystyle {\sqrt {2^{d}}}=2^{d/2}}$ ${\displaystyle {\sqrt[{3}]{2^{d}}}=2^{d/3}}$ ${\displaystyle c/2}$

Se ha demostrado que la construcción de Merkle–Damgård , tal como se utiliza en SHA-2, es colapsable y, en consecuencia, resistente a colisiones cuánticas, ^[57] pero para la construcción de esponja utilizada por SHA-3, los autores proporcionan pruebas solo para el caso en que la función de bloque f no es eficientemente invertible; Keccak-f[1600], sin embargo, es eficientemente invertible, por lo que su prueba no se aplica. ^{[58] [ investigación original ]}

Ejemplos de variantes de SHA-3

Los siguientes valores hash son de NIST.gov: ^[59]

SHA3-224("")6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7SHA3-256("")a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434aSHA3-384("")0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004SHA3-512("")a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26AGITAR128("", 256)7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26SHAKE256("", 512)46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

Cambiar un solo bit hace que cada bit de la salida cambie con un 50 % de probabilidad, lo que demuestra un efecto de avalancha :

SHAKE128("El rápido zorro marrón salta sobre el perro perezoso", 256)f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66eSHAKE128("El rápido zorro marrón salta sobre el perezoso perro " , 256)853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Comparación de funciones SHA

En la siguiente tabla, el estado interno significa la cantidad de bits que se transfieren al siguiente bloque.

La implementación optimizada de SHA3-256 utilizando AVX-512VL (es decir, de OpenSSL , que se ejecuta en CPU Skylake-X ) logra aproximadamente 6,4 ciclos por byte para mensajes grandes, ^[65] y aproximadamente 7,8 ciclos por byte cuando se utiliza AVX2 en CPU Skylake . ^[66] El rendimiento en otras CPU x86, Power y ARM, según las instrucciones utilizadas y el modelo exacto de CPU, varía de aproximadamente 8 a 15 ciclos por byte, ^{[67] [68] [69]} con algunas CPU x86 más antiguas hasta 25–40 ciclos por byte. ^[70]

Implementaciones

A continuación se muestra una lista de bibliotecas de criptografía que admiten SHA-3:

• Sha3 de Rust
• Botánica
• Castillo inflable
• Criptomoneda++
• Libgcrypt
• Ortiga
• OpenSSL
• lobo SSL
• SDK criptográfico MIRACL
• x/crypto/sha3 de Golang
• libkeccak

Aceleración de hardware

Los núcleos de CPU SoC de seis núcleos ARMv8 de Apple A13 tienen soporte ^[71] para acelerar SHA-3 (y SHA-512) utilizando instrucciones especializadas (EOR3, RAX1, XAR, BCAX) del conjunto de extensión criptográfica ARMv8.2-SHA. ^[72]

Algunas bibliotecas de software utilizan las funciones de vectorización de las CPU para acelerar el uso de SHA-3. Por ejemplo, Crypto++ puede utilizar SSE2 en x86 para acelerar SHA3, ^[73] y OpenSSL puede utilizar MMX , AVX-512 o AVX-512VL también en muchos sistemas x86. ^[74] Además, las CPU POWER8 implementan la rotación de vectores de 2x64 bits, definida en PowerISA 2.07, que puede acelerar las implementaciones de SHA-3. ^[75] La mayoría de las implementaciones para ARM no utilizan instrucciones vectoriales Neon , ya que el código escalar es más rápido. Sin embargo, las implementaciones ARM se pueden acelerar utilizando instrucciones vectoriales SVE y SVE2; estas están disponibles en la CPU Fujitsu A64FX , por ejemplo. ^[76]

IBM z/Architecture admite SHA-3 desde 2017 como parte de Message-Security-Assist Extension 6. ^[77] Los procesadores admiten una implementación completa de todos los algoritmos SHA-3 y SHAKE a través de las instrucciones KIMD y KLMD utilizando un motor de asistencia de hardware integrado en cada núcleo.

Uso en protocolos

• Ethereum § Éter

Véase también

• Ethash : otro hash basado en Keccak

Referencias

1. Bertoni, Guido; Daemen, Joan ; Peeters, Michael; van Assche, Gilles (29 de mayo de 2012). "Descripción general de la implementación de Keccak" (PDF) . pag. 25 . Consultado el 27 de marzo de 2023 .
2. Morawiecki, Paweł; Pieprzyk, Josef; Srebrny, Marian (2013). "Criptoanálisis rotacional de Keccak de reducción circular" (PDF) . En Moriai, S (ed.). Fast Software Encryption . Fast Software Encryption Lecture Notes in Computer Science. Vol. 8424. págs. 241–262. doi :10.1007/978-3-662-43933-3_13. ISBN 978-3-662-43932-6. Archivado (PDF) del original el 8 de enero de 2013 . Consultado el 8 de febrero de 2019 .
3. Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles (14 de enero de 2011). «The Keccak SHA-3 submission» (PDF) . keccak.team . Archivado (PDF) del original el 19 de agosto de 2011 . Consultado el 27 de marzo de 2023 .
4. División de Seguridad Informática, Laboratorio de Tecnología de la Información (4 de enero de 2017). «Funciones hash | CSRC | CSRC». CSRC | NIST . Consultado el 19 de abril de 2024 .
5. "Funciones hash". NIST . 22 de junio de 2020 . Consultado el 17 de febrero de 2021 .
6. Laboratorio de Tecnología de la Información (agosto de 2015). Estándar SHA-3: Hash basado en permutación y funciones de salida extensibles (PDF) . Instituto Nacional de Estándares y Tecnología . doi :10.6028/NIST.FIPS.202. S2CID  64734386. Publicación 202 del Estándar Federal de Procesamiento de Información . Consultado el 29 de febrero de 2020 .
7. Dworkin, Morris J. (4 de agosto de 2015). "Estándar SHA-3: funciones de hash basadas en permutación y de salida extensible". Estándares federales de procesamiento de información (NIST FIPS).
8. "NIST selecciona al ganador de la competencia del algoritmo hash seguro (SHA-3)". NIST . 2 de octubre de 2012 . Consultado el 2 de octubre de 2012 .
9. Cruz, José RC (7 de mayo de 2013). "Keccak: El nuevo estándar de cifrado SHA-3". Dr. Dobbs .
10. Bertoni, Guido; Daemen, Joan; Peeters, Michael; Van Assche, Gilles. "Resumen de especificaciones de Keccak" . Consultado el 27 de marzo de 2023 .
11. Chang, Shu-jen; Perlner, Ray; Burr, William E.; Sonmez Turan, Meltem; Kelsey, John M.; Paul, Souradyuti; Bassham, Lawrence E. (noviembre de 2012). Informe de la tercera ronda de la competencia de algoritmos hash criptográficos SHA-3 (PDF) . doi :10.6028/NIST.IR.7896 . Consultado el 29 de febrero de 2020 .Las secciones 5.1.2.1 (que menciona el "modo árbol"), 6.2 ("otras características", que menciona el cifrado autenticado) y 7 (que dice "extras" podrían estandarizarse en el futuro).
12. Bertoni, Guido; Daemen, Joan; Peeters, Michael; Van Assche, Gilles; Van Keer, Ronny (13 de marzo de 2014). "Presentación CAESAR: Ketje v1" (PDF) . Consultado el 29 de febrero de 2020 .
13. Bertoni, Guido; Daemen, Joan; Peeters, Michael; Van Assche, Gilles; Van Keer, Ronny (13 de marzo de 2014). "Presentación CAESAR: Keyak v1" (PDF) . Consultado el 29 de febrero de 2020 .
14. Bertoni, Guido; Daemen, Joan; Peeters, Michael; van Assche, Giles. «La esponja y las construcciones dúplex» . Consultado el 27 de marzo de 2023 .
15. "Anuncio de solicitud de nominaciones de algoritmos candidatos para una nueva familia de algoritmos hash criptográficos (SHA-3) [Registro Federal de EE. UU., vol. 72, n.º 212]" (PDF) . 2 de noviembre de 2007. Archivado (PDF) desde el original el 31 de marzo de 2011. Consultado el 18 de julio de 2017 .
16. Bertoni, Guido; Daemen, Joan; Peeters, Michael; Van Assche, Gilles. «El camino de Panamá a Keccak vía RadioGatún» (PDF) . Consultado el 27 de marzo de 2023 .
17. KeccakReferenceAndOptimized-3.2.zip mainReference.c "La función de esponja de Keccak, diseñada por Guido Bertoni, Joan Daemen, Michaël Peeters y Gilles Van Assche. Para obtener más información, comentarios o preguntas, consulte nuestro sitio web: http://keccak.noekeon.org/Implementation ^{[ enlace muerto permanente ]} por los diseñadores, a los que se denomina "el implementador". En la medida de lo posible según la ley, el implementador ha renunciado a todos los derechos de autor y derechos relacionados o vecinos del código fuente de este archivo. https://creativecommons.org/publicdomain/zero/1.0/"
18. Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik. "La primera colisión para SHA-1 completo" (PDF) . Consultado el 23 de febrero de 2017 .
19. Leurent, Gaëtan; Peyrin, Tomás. "SHA-1 es un desastre" . Consultado el 8 de enero de 2020 .
20. "División de Seguridad Informática del NIST – Competencia de algoritmos hash criptográficos SHA-3, noviembre de 2007 – octubre de 2012". 4 de enero de 2017.
21. "Cambios en los parámetros de Keccak para la ronda 2". Equipo Keccak . 22 de septiembre de 2009. Archivado desde el original el 13 de noviembre de 2017. Consultado el 29 de febrero de 2020 .
22. "Simplificando la regla de relleno de Keccak para la ronda 3". Equipo Keccak . 17 de enero de 2011. Consultado el 27 de marzo de 2023 .
23. "Estandarización SHA-3". NIST . Consultado el 16 de abril de 2015 .
24. Instituto Nacional de Estándares y Tecnología (5 de agosto de 2015). «Estándares federales de procesamiento de información: funciones de hash basadas en permutación y de salida extensible, etc.» . Consultado el 5 de agosto de 2015 .
25. "Anuncio de la aprobación del Estándar de procesamiento de información federal (FIPS) 202, estándar SHA-3: funciones de hash basadas en permutación y de salida extensible, y revisión de la cláusula de aplicabilidad del estándar FIPS 180-4, estándar de hash seguro". 5 de agosto de 2015.
26. Kelsey, John. "SHA3: dónde hemos estado y hacia dónde vamos" (PDF) . Conferencia RSA 2013.
27. Kelsey, John. "SHA3, pasado, presente y futuro". CHES 2013.
28. "Resumen" (PDF) . cr.yp.to .
29. "Lista de correo del foro de hash del NIST". 4 de enero de 2017.
30. "La presentación de Keccak SHA-3" (PDF) . 14 de enero de 2011. Consultado el 27 de marzo de 2023 .
31. "Sobre la seguridad de 128 bits". 2 de octubre de 2013. Consultado el 27 de marzo de 2023 .
32. "Una propuesta concreta". 2 de octubre de 2013. Consultado el 27 de marzo de 2023 .
33. "Schneier sobre seguridad: ¿Keccak = SHA-3?".
34. "LShift: Por qué apoyo que el gobierno de EE. UU. debilite el estándar de criptografía".
35. "¡Sí, este es Keccak!". 4 de octubre de 2013. Consultado el 27 de marzo de 2023 .
36. "Avanzando con SHA-3" (PDF) .
37. División de Seguridad Informática (CSD) del NIST. "Estándar SHA-3: Hash basado en permutación y funciones de salida extensibles" (PDF) . NIST.
38. "unos 41 ciclos/byte [...] representan una aceleración del 40% en comparación con una implementación que utiliza sólo instrucciones de 32 bits". Por fórmula obtenemos ${\displaystyle {\frac {1}{x}}\times 1.40={\frac {1}{41}}}$ ${\displaystyle x=57.4}$
39. Bernstein, Daniel J. (4 de enero de 2012). "Errores de optimización en software SHA-3" (PDF) . cr.yp.to . Consultado el 29 de febrero de 2020 .
40. "¿SHA-3 es lento?". 12 de junio de 2017. Consultado el 27 de marzo de 2023 .
41. Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick (agosto de 2010), "Evaluación de desempeño justa y completa de 14 implementaciones de ASIC SHA-3 de segunda ronda" (PDF) , NIST 2nd SHA-3 Candidate Conference : 12 , consultado el 18 de febrero de 2011Keccak ocupa el segundo lugar, detrás de Luffa, que no avanzó a la ronda final.
42. ARM corporation, manual de referencia de arquitectura ARM ARMv8, para el perfil de arquitectura ARMv8-A, documento ARM DDI 0487C.a (ID121917), https://www.arm.com
43. http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr011.pdf pág. 672
44. Rawat, Hemendra; Schaumont, Patrick (2017). "Extensiones del conjunto de instrucciones vectoriales para el cálculo eficiente de <sc>Keccak</sc>". IEEE Transactions on Computers . 66 (10): 1778–1789. doi :10.1109/TC.2017.2700795.
45. "Sakura: una codificación flexible para el hash de árboles" (PDF) . Equipo Keccak . 2014. Consultado el 29 de febrero de 2020 .
46. Funciones derivadas de SHA-3: cSHAKE, KMAC, TupleHash y ParallelHash Este artículo incorpora texto de esta fuente, que se encuentra en el dominio público .
47. "Cifras de rendimiento del software".
48. "Equipo Keccak: KangarooTwelve". Equipo Keccak.
49. "KangarooTwelve: hash rápido basado en Keccak-p" (PDF) . Asociación Internacional para la Investigación Criptológica . 2016.
50. "Diapositivas de KangarooTwelve presentadas en ACNS 2018" (PDF) . Equipo Keccak.
51. "draft-irtf-cfrg-kangarootwelve-00 – KangarooTwelve". Ietf Datatracker . IETF . Consultado el 17 de enero de 2020 .
52. Bertoni, Guido; Daemen, Joan; Hoffert, Seth; Peeters, Michael; Van Assche, Gilles; Van Keer, Ronny (29 de diciembre de 2016). "Farfalle: criptografía basada en permutaciones paralelas". Archivo ePrint de criptología .
53. Guido Bertoni; Joan Daemen; Seth Hoffert; Michael Peeters; Gilles Van Assche; Ronny Van Keer (12 de octubre de 2018). "Los esquemas de cifrado autenticados Kravatte-SANE y Kravatte-SANSE". Archivo ePrint de criptología .
54. Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998). "Criptoanálisis cuántico de funciones hash y claw-free". Resumen . Lecture Notes in Computer Science. Vol. 1380. págs. 163–169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6.S2CID118940551  .​
55. "Análisis de costos" (PDF) . cr.yp.to .
56. "Problema de colisión" (PDF) . scottaaronson.com .
57. "Documento" (PDF) . eprint.iacr.org . 2016.
58. "Resumen" (PDF) . eprint.iacr.org . 2017.
59. "NIST.gov – División de Seguridad Informática – Centro de Recursos de Seguridad Informática". 29 de diciembre de 2016.
60. "Tabla de medidas". bench.cr.yp.to .
61. Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). Ataque de colisión rápida en MD5 (PDF) . Archivo de impresión electrónica de criptología (informe técnico). IACR .
62. Stevens, Marc ; Bursztein, Elie ; Karpman, Pierre; Albertini, Ange; Markov, Yarik. La primera colisión para SHA-1 completo (PDF) (Informe técnico). Investigación de Google .
    • Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov; Alex Petit Bianco; Clement Baisse (23 de febrero de 2017). "Anuncio de la primera colisión SHA1". Blog de seguridad de Google .
63. Sin truncamiento, se conoce el estado interno completo de la función hash, independientemente de la resistencia a la colisión. Si se trunca la salida, se debe buscar y encontrar la parte eliminada del estado antes de que se pueda reanudar la función hash, lo que permite que continúe el ataque.
64. "La familia de funciones de la esponja de Keccak" . Consultado el 27 de enero de 2016 .
65. "openssl/openssl – kecak1600-avx512vl.pl". GitHub . Consultado el 25 de junio de 2020 .
66. "openssl/openssl – keccak1600-avx2.pl". GitHub . Noviembre de 2021.
67. "openssl/openssl – keccak1600-x86_64.pl". GitHub . Consultado el 25 de junio de 2020 .
68. "openssl/openssl – keccak1600-armv8.pl". GitHub . Noviembre de 2021.
69. "openssl/openssl – keccak1600-ppc64.pl". GitHub . Consultado el 25 de junio de 2020 .
70. "openssl/openssl – kccak1600-mmx.pl". GitHub . Consultado el 25 de junio de 2020 .
71. "llvm/llvm-project – AArch64.td". GitHub . Consultado el 24 de junio de 2020 .
72. "ARMv8 – ARM – WikiChip". en.wikichip.org . Consultado el 24 de junio de 2020 .
73. "weidai11/cryptopp". GitHub . Consultado el 25 de junio de 2020 .
74. "openssl/openssl". GitHub . Consultado el 25 de junio de 2020 .
75. "openssl/openssl". GitHub . Noviembre de 2021.
76. "apple/llvm-project – lib/Target/AArch64/AArch64SVEInstrInfo.td". GitHub . Consultado el 25 de junio de 2020 .
77. Principios de funcionamiento de IBM z/Architecture, número de publicación SA22-7832. Consulte las instrucciones KIMD y KLMD en el Capítulo 7.

Enlaces externos

• El sitio web de Keccak
• Estándar SHA-3