SHA-3

Conjunto de funciones hash criptográficas

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

SHA-3 es un subconjunto de la familia primitiva criptográfica más amplia Keccak ( / ˈ k ɛ tʃ æ k / o / ˈ k ɛ tʃ ɑː k / ), ^{[7] [8]} diseñado 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 estandarizada (todavía) por NIST, incluido 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, ^{[9] [10]} y cifrados AEAD . Keyak y Ketje. ^{[11] [12]}

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

Actualmente, el NIST no planea retirar SHA-2 ni eliminarlo del Secure Hash Standard revisado. ^{[¿ necesita actualización? ]} El propósito de SHA-3 es que pueda sustituir directamente a SHA-2 en las aplicaciones actuales si es necesario, y mejorar significativamente la solidez del conjunto de herramientas de algoritmo hash general del NIST. ^[14]

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 gastos generales adicionales.

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 diseños anteriores de funciones hash 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 se presentó en el NIST Hash Workshop en 2006. ^[15] El código fuente de implementación de referencia se dedicó al dominio público a través de la exención CC0 . ^[dieciséis]

En 2006, el NIST comenzó a organizar el concurso de funciones hash del NIST para crear un nuevo estándar hash, SHA-3. SHA-3 no pretende reemplazar a SHA-2 , ya que no se ha demostrado ningún ataque significativo a SHA-2 ^{[ necesita actualización ]} . Debido a los ataques exitosos a MD5 , SHA-0 y SHA-1 , ^{[17] [18]} 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 finales 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. ^[19]

Durante la competencia, a los participantes se les permitió "modificar" sus algoritmos para abordar los problemas descubiertos. Los cambios que se han realizado en Keccak son: ^{[20] [21]}

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

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

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

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

Debilitamiento de la controversia

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

La competencia de funciones hash requería funciones hash al menos tan seguras como las instancias SHA-2. Significa que una salida de d bits debe tener una resistencia de d /2 bits a los ataques de colisión y una resistencia de d bits a los 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 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 d /2 bits para todas las formas de ataque y estandarizar c = d . Esto habría acelerado Keccak al permitir que se aplicaran hash de 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ía reducido a la mitad, haciéndolo vulnerable a los avances en la computación cuántica, que efectivamente lo reduciría a la mitad una vez más. ^[27]

En septiembre de 2013, Daniel J. Bernstein sugirió en la lista de correo del foro hash del NIST ^[28] fortalecer la seguridad de la capacidad de 576 bits que se propuso originalmente como el Keccak predeterminado, además y no incluido en el SHA-3. especificaciones. ^[29] 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 finales de septiembre, el equipo de Keccak respondió afirmando que habían propuesto seguridad de 128 bits estableciendo c = 256 como una opción ya en su propuesta SHA-3. ^[30] Aunque la reducción de capacidad era justificable en su opinión, a la luz de la respuesta negativa, propusieron aumentar la capacidad a c = 512 bits para todos los casos. Esto sería tanto como cualquier estándar anterior hasta el nivel de seguridad de 256 bits, al tiempo que proporciona una eficiencia razonable, ^[31] 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 sobre 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á. ^[32]

Más tarde se retractó de su declaración anterior y dijo:

Me equivoqué cuando escribí que el NIST realizó "cambios internos" en el algoritmo. Eso fue descuidado de mi parte. La permutación de Keccak permanece sin cambios. Lo que propuso el NIST fue reducir la capacidad de la función hash en nombre del rendimiento. Una de las buenas características de Keccak es que es altamente sintonizable. ^[32]

Paul Crowley, criptógrafo y desarrollador senior de una empresa independiente de desarrollo de software, expresó su apoyo a la decisión, diciendo que se supone que Keccak es ajustable y que no hay razón para diferentes niveles de seguridad dentro de una primitiva. También añadió:

Sí, es un poco vergonzoso para la competencia que exigieran un cierto nivel de seguridad a los participantes y luego publicaran un estándar con otro diferente. Pero no se puede hacer nada para solucionarlo ahora, salvo reabrir la competición. Exigir que se ciñan a su error no mejora las cosas para nadie. ^[33]

Hubo cierta confusión sobre la posibilidad de que se hayan 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. presentado al concurso, y que esta propuesta fue el resultado de una serie de discusiones entre ellos y el equipo de hash del NIST. ^[34]

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 SHA-2. ^[35] La reversión fue confirmada en borradores posteriores ^[36] y en la versión final. ^[4]

Diseño

La construcción de esponja para funciones hash. P _i son entradas, Z _i son salidas hash. La "capacidad" c no utilizada debe ser el doble de la resistencia deseada a colisiones o ataques previos a la imagen .

SHA-3 utiliza la construcción de esponja , ^[13] en la que los datos se "absorben" en la esponja y luego el resultado se "exprime". En la fase de absorción, los bloques de mensajes se someten a XOR en un subconjunto del estado, que luego se transforma como un todo mediante una función de permutación . (Llamar a una permutación puede resultar confuso. Técnicamente es una permutación del espacio de estados, 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 necesaria ]} ) En el "comprimir "fase, 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 ), y el tamaño de la parte que no es tocada por la entrada/salida se llama "capacidad" (denotada ). La capacidad determina la seguridad del esquema. El nivel máximo de seguridad es la mitad del aforo. ${\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 velocidad 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: ^{[5] : 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}$

• rellenar la entrada N utilizando la función pad, lo que produce una cadena de bits rellenada P con una longitud divisible por (de modo que sea un número entero) ${\displaystyle r}$ ${\displaystyle n={\text{len}}(P)/r}$
• dividir P en n piezas consecutivas de r bits P ₀ , ..., P _{n −1}
• inicializar el estado S en una cadena de b bits cero
• absorber la entrada en el estado: para cada bloque P _i :
  • extender P _i al final por una cadena de c cero bits, produciendo uno de longitud b
  • XOR que con S
  • aplicar la permutación de bloques f al resultado, produciendo un nuevo estado S
• inicializar Z para que sea la cadena vacía
• mientras que la longitud de Z es menor que d :
  • agregar los primeros r bits de S a Z
  • si Z todavía tiene menos de d bits de largo, aplique f a S , produciendo un nuevo estado S
• truncar Z a d bits

El hecho de que el estado interno S contenga c bits de información adicionales además de lo que se envía 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 consta de una matriz de 5 × 5 de 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 palabras de potencia de 2 más pequeños w hasta 1 bit (estado total de 25 bits). Se pueden utilizar tamaños de estado pequeños para probar ataques criptoanalíticos, y tamaños de estado intermedios (desde w = 8.200 bits hasta w = 32.800 bits) se pueden utilizar en aplicaciones prácticas y ligeras. ^{[11] [12]}

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

Relleno

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

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

Los dos bits 1 se sumarán incluso si la longitud del mensaje ya es divisible por r . ^{[5] : 5.1} En este caso, se agrega otro bloque al mensaje, que contiene 1 bit, seguido de un bloque de r − 2 bits cero y otro de 1 bit. 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 al que se le quitaron esos bits.

El 1 bit inicial es necesario para que los mensajes que difieran sólo en unos pocos 0 bits adicionales al final no produzcan el mismo hash.

La posición del último bit indica qué tasa r se utilizó (relleno de múltiples tasas), que se requiere para que la prueba de seguridad funcione para diferentes variantes de hash. Sin él, diferentes variantes de hash del mismo mensaje corto serían iguales hasta el truncamiento.

La permutación de bloques

La transformación de bloque 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 de potencia de dos , w = 2 ^ℓ bits. El envío principal de SHA-3 utiliza palabras de 64 bits, ℓ = 6 .

Se puede considerar que el estado es 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 y una indexación de filas principales . Es decir, i selecciona la fila, j la columna y k el bit.

La aritmética de índices se realiza en módulo 5 para las dos primeras dimensiones y en 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)

Calcule la paridad de cada una de las 5 w (320, cuando w = 64 ) columnas de 5 bits, y excluyalas en dos columnas cercanas en 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])

ρ (ro)

Gire bit a bit cada una de las 25 palabras en un número triangular diferente 0, 1, 3, 6, 10, 15, .... Para ser precisos, un [0][0] no se rota, y para todos 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. un [3 yo +2 j ][ yo ] ← un [  yo ][ j ] .

χ (chi)

Combine bit a bit a lo largo de filas, usando 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 ≤ ℓ , a [0][0][2 ^m −1] se aplica XOR con el bit m + 7 n de una secuencia LFSR de grado 8 . Esto rompe la simetría que conservan los demás escalones.

Velocidad

La velocidad del hash SHA-3 de mensajes largos está dominada por el cálculo de f = Keccak-f[1600] y XORing S con el Pi _extendido , una operación en b = 1600 bits. Sin embargo, dado que los últimos c bits del P _i extendido son 0 de todos modos, y 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 es r (y, a la inversa, cuanto mayor 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 del computacionalmente costoso f . Los autores informan las siguientes velocidades para 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 ^[37]
• 41 cbb 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 cbb en IA-64 ^[1]

Para SHA3-256 exacto en x86-64, Bernstein mide entre 11,7 y 12,25 cpb dependiendo de la CPU. ^{[38] : 7} SHA-3 ha sido criticado por ser lento en arquitecturas de conjuntos de instrucciones (CPU) que no tienen instrucciones diseñadas especialmente para calcular las funciones de Keccak más rápido: SHA2-512 es más del doble de rápido que SHA3-512 y SHA. -1 es más de tres veces más rápido en un procesador Intel Skylake con frecuencia de 3,2 GHz. ^[39] Los autores han reaccionado a esta crítica sugiriendo usar 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 implementaciones de hardware , SHA-3 es notablemente más rápido que todos los demás finalistas, ^[40] y también más rápido que SHA-2 y SHA-1. ^[39]

A partir de 2018, las arquitecturas ARMv8 ^[41] de ARM y s390x de IBM incluyen instrucciones especiales que permiten que los algoritmos Keccak se ejecuten más rápido.

Instancias

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

Con las siguientes definiciones

• Keccak[ c ]( N , d ) = esponja[Keccak-f[1600], pad10 ^* 1, r ]( N , d ) ^{[5] : 20}
• Keccak-f[1600] = Keccak-p[1600, 24] ^{[5] : 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 y están destinadas a tener propiedades de seguridad idénticas.

SHAKE generará tantos bits de su esponja como se solicite, siendo así funciones de salida extensibles (XOF). Por ejemplo, SHAKE128(M, 256) se puede utilizar como función hash con un flujo de bits de 256 caracteres con un nivel de seguridad de 128 bits. Se pueden utilizar longitudes arbitrariamente grandes como generadores de números pseudoaleatorios. Alternativamente, SHAKE256(M, 128) se puede utilizar como función hash con una longitud de 128 bits y una resistencia de 128 bits. ^[5]

Todas las instancias añaden algunos bits al mensaje, el más a la derecha de los cuales representa el sufijo de separación de dominio . 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 Keccak. Existen los siguientes sufijos de separación de dominios: ^{[5] [42]}

Instancias adicionales

En diciembre de 2016, NIST publicó un nuevo documento, NIST SP.800-185, ^[43] 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 número entero que representa la longitud de salida solicitada en bits.

• N es una cadena de bits de nombre de función, utilizada por NIST para definir funciones basadas en cSHAKE. Cuando no se desea ninguna función distinta a 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 hash paralelo. Puede ser cualquier número entero tal que 0 < B < 2 ²⁰⁴⁰ .

Desarrollos posteriores

CanguroDoce

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 debido al uso de árbol. hash : KangarooTwelve y MarsupilamiFourteen. ^[45]

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 mensajes de tamaño pequeño.

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

KangarooTwelve es una versión de Keccak de ronda reducida (de 24 a 12 rondas) de mayor rendimiento que afirma tener 128 bits de seguridad ^[46] y un rendimiento de hasta 0,55 ciclos por byte en una CPU Skylake . ^[47] Este algoritmo es un borrador RFC del IETF . ^[48]

MarsupilamiFourteen, una ligera variación de KangarooTwelve, utiliza 14 rondas de la permutación Keccak y reclama 256 bits de seguridad. Tenga en cuenta que la seguridad de 256 bits no es más útil en la práctica que la seguridad de 128 bits, pero algunos estándares pueden exigirla. ^[46] 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 conocer la resistencia contra las computadoras cuánticas , consulte a continuación.

KangarooTwelve y MarsupilamiFourteen son funciones de salida extensible, similares a SHAKE, por lo tanto, 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 la exhiben funciones hash como SHA-3 o ParallelHash (excepto las variantes XOF). ^[5]

La construcción 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, ^[49] así como dos algoritmos de cifrado autenticados Kravatte-SANE y Kravatte-SANSE ^[50].

Hashing del árbol de Sakura

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

Seguridad contra ataques cuánticos

Existe un resultado general ( algoritmo de Grover ) de que las computadoras cuánticas pueden realizar un ataque de preimagen estructurado en , mientras que un ataque clásico de fuerza bruta necesita 2 ^d . Un ataque de preimagen estructurado implica un segundo ataque de preimagen ^[27] y, por 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 ^[51] (aunque eso está en disputa). ^[52] Teniendo en cuenta que la fuerza máxima puede ser , esto da los siguientes límites superiores ^[53] sobre 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 Merkle-Damgård , tal como la utiliza SHA-2, colapsa y, en consecuencia, es resistente a las colisiones cuánticas, ^[54] pero para la construcción de esponja utilizada por SHA-3, los autores proporcionan pruebas sólo para el caso en el que la función de bloque f no es invertible eficientemente; Keccak-f[1600], sin embargo, es eficientemente invertible, por lo que su prueba no se aplica. ^{[55] [ investigación original ]}

Ejemplos de variantes SHA-3

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

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

Cambiar un solo bit hace que cada bit en 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 veloz zorro marrón salta sobre el perezoso do f ", 256)853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Comparación de funciones SHA

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

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

Implementaciones

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

• sha3 de óxido
• botánico
• Castillo inflable
• Cripto++
• Libgcrypt
• Ortiga
• AbiertoSSL
• loboSSL
• SDK criptográfico MIRACL
• x/crypto/sha3 de Golang
• libkeccak

Aceleracion de hardware

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

Algunas bibliotecas de software utilizan funciones de vectorización de las CPU para acelerar el uso de SHA-3. Por ejemplo, Crypto++ puede usar SSE2 en x86 para acelerar SHA3, ^[70] y OpenSSL también puede usar MMX , AVX-512 o AVX-512VL en muchos sistemas x86. ^[71] Además, las CPU POWER8 implementan rotación vectorial de 2x64 bits, definida en PowerISA 2.07, que puede acelerar las implementaciones SHA-3. ^[72] La mayoría de las implementaciones para ARM no utilizan instrucciones vectoriales de neón 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; Estos están disponibles, por ejemplo, en la CPU Fujitsu A64FX . ^[73]

IBM z/Architecture admite SHA-3 desde 2017 como parte de Message-Security-Assist Extension 6. ^[74] 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 hardware Motor de asistencia integrado en cada núcleo.

Uso en protocolos

• Etereum § Éter

Ver también

• Ethash : otro hachís 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 reducido en rondas" (PDF) . En Moriai, S (ed.). Cifrado de software rápido . Apuntes de conferencias sobre cifrado rápido de software en informática. vol. 8424, págs. 241–262. doi :10.1007/978-3-662-43933-3_13. ISBN 978-3-662-43932-6. Archivado (PDF) desde el original el 8 de enero de 2013 . Consultado el 8 de febrero de 2019 .
3. Bertoni, Guido; Daemen, Joan; Peeters, Michael; van Assche, Giles (14 de enero de 2011). "La presentación de Keccak SHA-3" (PDF) . equipo.keccak . Archivado (PDF) desde el original el 19 de agosto de 2011 . Consultado el 27 de marzo de 2023 .
4. "Funciones hash". NIST . 22 de junio de 2020 . Consultado el 17 de febrero de 2021 .
5. Laboratorio de Tecnología de la Información abcdefghi (agosto de 2015). Estándar SHA-3: hash basado en permutaciones y funciones de salida extensibles (PDF) . Instituto Nacional de Estándares y Tecnología . doi :10.6028/NIST.FIPS.202. S2CID  64734386. Publicación del estándar federal de procesamiento de información 202 . Consultado el 29 de febrero de 2020 .
6. Dworkin, Morris J. (4 de agosto de 2015). "Estándar SHA-3: Hash basado en permutación y funciones de salida extensible". Estándares federales de procesamiento de información (NIST FIPS).
7. "NIST selecciona al ganador del concurso de algoritmo Hash seguro (SHA-3)". NIST . 2 de octubre de 2012 . Consultado el 2 de octubre de 2012 .
8. Cruz, José RC (7 de mayo de 2013). "Keccak: el nuevo estándar de cifrado SHA-3". Doctor Dobbs .
9. Bertoni, Guido; Daemen, Joan; Peeters, Michael; Van Assche, Gilles. "Resumen de especificaciones de Keccak" . Consultado el 27 de marzo de 2023 .
10. Chang, Shu-jen; Perlner, Ray; Burr, William E.; Sonmez Turan, Meltem; Kelsey, John M.; Pablo, Souradyuti; Bassham, Lawrence E. (noviembre de 2012). Informe de la tercera ronda del concurso de algoritmo hash criptográfico 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 de árbol"), 6.2 ("otras características", que menciona el cifrado autenticado) y 7 (que dice "extras" puede estandarizarse en el futuro).
11. 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 .
12. 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 .
13. Bertoni, Guido; Daemen, Joan; Peeters, Michael; van Assche, Giles. «La esponja y las construcciones dúplex» . Consultado el 27 de marzo de 2023 .
14. "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 No. 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 .
15. 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 .
16. KeccakReferenceAndOptimized-3.2.zip mainReference.c "La función de esponja 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, denominados "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 conexos con el código fuente de este archivo. https: //creativecommons.org/publicdomain/zero/1.0/"
17. Stevens, Marc; Bursztein, Elie; Karpman, Pedro; Albertini, Ángel; Markov, Yarik. "La primera colisión para SHA-1 completo" (PDF) . Consultado el 23 de febrero de 2017 .
18. Leurent, Gaëtan; Peyrin, Tomás. "SHA-1 es un desastre" . Consultado el 8 de enero de 2020 .
19. "División de seguridad informática del NIST: concurso de algoritmo hash criptográfico SHA-3, noviembre de 2007 - octubre de 2012". 4 de enero de 2017.
20. "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 .
21. "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 .
22. "Estandarización SHA-3". NIST . Consultado el 16 de abril de 2015 .
23. Instituto Nacional de Estándares y Tecnología (5 de agosto de 2015). "Estándares federales de procesamiento de información: hash basado en permutación y funciones de salida extensible, etc." . Consultado el 5 de agosto de 2015 .
24. "Anuncio de la aprobación del estándar federal de procesamiento de información (FIPS) 202, estándar SHA-3: hash basado en permutación y funciones de salida extensible, y revisión de la cláusula de aplicabilidad de FIPS 180-4, estándar Hash seguro". 5 de agosto de 2015.
25. Kelsey, John. "SHA3, dónde hemos estado, hacia dónde vamos" (PDF) . Conferencia RSA 2013.
26. Kelsey, John. "SHA3, pasado, presente y futuro". CHÉS 2013.
27. "Resumen" (PDF) . cr.yp.to. _
28. "Lista de correo del foro de hash del NIST". 4 de enero de 2017.
29. "La presentación de Keccak SHA-3" (PDF) . 14 de enero de 2011 . Consultado el 27 de marzo de 2023 .
30. "Sobre seguridad de 128 bits". 2 de octubre de 2013 . Consultado el 27 de marzo de 2023 .
31. "Una propuesta concreta". 2 de octubre de 2013 . Consultado el 27 de marzo de 2023 .
32. "Schneier sobre seguridad: ¿Keccak = SHA-3?".
33. "LShift: Por qué apoyo que el gobierno de EE. UU. debilite un estándar de criptografía".
34. "¡Sí, este es Keccak!". 4 de octubre de 2013 . Consultado el 27 de marzo de 2023 .
35. "Avanzando con SHA-3" (PDF) .
36. División de Seguridad Informática (CSD) del NIST. "Estándar SHA-3: hash basado en permutaciones y funciones de salida extensibles" (PDF) . NIST.
37. "aproximadamente 41 ciclos/byte [...] representa 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}$
38. Bernstein, Daniel J. (4 de enero de 2012). «Fallos de optimización en software SHA-3» (PDF) . cr.yp.to. _ Consultado el 29 de febrero de 2020 .
39. "¿Es SHA-3 lento?". 12 de junio de 2017 . Consultado el 27 de marzo de 2023 .
40. Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick (agosto de 2010), "Evaluación de desempeño justa e integral de 14 implementaciones ASIC SHA-3 de segunda ronda" (PDF) , Segunda conferencia de candidatos SHA-3 del NIST : 12 , consultado el 18 de febrero de 2011Keccak es superado sólo por Luffa, que no avanzó a la ronda final.
41. ARM Corporation, manual de referencia de arquitectura ARM ARMv8, para perfil de arquitectura ARMv8-A, documento ARM DDI 0487C.a (ID121917), https://www.arm.com
42. "Sakura: una codificación flexible para el hash de árboles" (PDF) . Equipo Keccak . 2014 . Consultado el 29 de febrero de 2020 .
43. Funciones derivadas de SHA-3: cSHAKE, KMAC, TupleHash y ParallelHash Este artículo incorpora texto de esta fuente, que es de dominio público .
44. "Cifras de rendimiento del software".
45. "Equipo Keccak: KangarooTwelve". Equipo Keccak.
46. "KangarooTwelve: hash rápido basado en Keccak-p" (PDF) . Asociación Internacional para la Investigación Criptológica . 2016.
47. "KangarooTwelve diapositivas presentadas en ACNS 2018" (PDF) . Equipo Keccak.
48. "draft-irtf-cfrg-kangarootwelve-00 - KangarooTwelve". Rastreador de datos del IETF . IETF . Consultado el 17 de enero de 2020 .
49. 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 .
50. 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 .
51. Brassard, Gilles; Hoyer, Peter; Tapp, Alain (1998). "Criptoanálisis cuántico de funciones hash y sin garras". Abstracto . Apuntes de conferencias sobre informática. vol. 1380. págs. 163-169. arXiv : quant-ph/9705002 . doi :10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID  118940551.
52. "Análisis de costos" (PDF) . cr.yp.to. _
53. "Problema de colisión" (PDF) . scottaaronson.com .
54. "Papel" (PDF) . eprint.iacr.org . 2016.
55. "Resumen" (PDF) . eprint.iacr.org . 2017.
56. "NIST.gov - División de seguridad informática - Centro de recursos de seguridad informática". 29 de diciembre de 2016.
57. "Tabla de medidas". banca.cr.yp.to .
58. Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). Ataque de colisión rápida en MD5 (PDF) . Archivo ePrint de criptología (Informe técnico). IACR .
59. Stevens, Marc ; Bursztein, Elie ; Karpman, Pedro; Albertini, Ángel; Markov, Yarik. La primera colisión para SHA-1 completo (PDF) (Informe técnico). Investigación de Google .
    • Marc Stevens; Elie Bursztein; Pierre Karpman; Ángel Albertini; Yarik Markov; Álex Petit Bianco; Clément Baisse (23 de febrero de 2017). "Anuncio de la primera colisión SHA1". Blog de seguridad de Google .
60. Sin truncamiento, se conoce el estado interno completo de la función hash, independientemente de la resistencia a la colisión. Si la salida se trunca, se debe buscar y encontrar la parte eliminada del estado antes de que se pueda reanudar la función hash, permitiendo que el ataque continúe.
61. "La familia de funciones de esponjas Keccak" . Consultado el 27 de enero de 2016 .
62. "openssl/openssl - kecak1600-avx512vl.pl". GitHub . Consultado el 25 de junio de 2020 .
63. "openssl/openssl - keccak1600-avx2.pl". GitHub . Noviembre de 2021.
64. "openssl/openssl - keccak1600-x86_64.pl". GitHub . Consultado el 25 de junio de 2020 .
65. "openssl/openssl - keccak1600-armv8.pl". GitHub . Noviembre de 2021.
66. "openssl/openssl - keccak1600-ppc64.pl". GitHub . Consultado el 25 de junio de 2020 .
67. "openssl/openssl - kccak1600-mmx.pl". GitHub . Consultado el 25 de junio de 2020 .
68. "llvm/llvm-proyecto - AArch64.td". GitHub . Consultado el 24 de junio de 2020 .
69. "ARMv8 – ARM – WikiChip". es.wikichip.org . Consultado el 24 de junio de 2020 .
70. "weidai11/criptopp". GitHub . Consultado el 25 de junio de 2020 .
71. "openssl/openssl". GitHub . Consultado el 25 de junio de 2020 .
72. "openssl/openssl". GitHub . Noviembre de 2021.
73. "apple/llvm-project - lib/Target/AArch64/AArch64SVEInstrInfo.td". GitHub . Consultado el 25 de junio de 2020 .
74. IBM z/Architecture Principios de funcionamiento, número de publicación SA22-7832. Consulte las instrucciones de KIMD y KLMD en el Capítulo 7.

enlaces externos

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