Luffa (función hash)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de abril de 2014; las comprobaciones requieren 16 ediciones .
luffa
Desarrolladores Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Creado 2008
publicado 2008
tamaño de hash 224, 256, 384, 512
Tipo de función hash

Lúffa [1] (función hash, pronunciada “luffa”) es un algoritmo criptográfico (familia de algoritmos) para hash de longitud de bit variable , desarrollado por Dai Watanabe ,  Hisayoshi Sato del Hitachi  Yokohama Research Laboratory y Christophe De Cannière ( Niderl. Christophe De Cannière ) del grupo de investigación COSIC ( en: COSIC ) de la Universidad Católica de Lovaina para participar en el concurso [2] , US National Institute of Standards and Technology ( NIST ). Luffa es una opción  función de esponja propuesta por Guido Bertoni et al., cuya seguridad criptográfica se basa únicamente en la aleatoriedad de la permutación subyacente .  A diferencia de la función de esponja original , Lúffa usa múltiples permutaciones paralelas y funciones de inyección de mensajes.

Historial de participación en la competencia NIST SHA-3 [2]

Algoritmo Lúffa [6]

El procesamiento de mensajes se realiza mediante una cadena de funciones de mezcla redonda con una longitud fija de entrada y salida, que es una función de esponja . La cadena consta de bloques intermedios de mezcla C' (funciones redondas) y un bloque de finalización C''. Las funciones redondas están formadas por una familia de permutaciones no lineales, las llamadas funciones escalonadas. La entrada de la función de primera ronda es : el primer bloque del mensaje y los valores de inicialización , donde  está el número de permutaciones. Los parámetros de entrada de la ronda -ésima son : la salida de la ronda anterior y el bloque de mensajes -ésima .

Finalización del mensaje

La adición de un mensaje de longitud hasta un múltiplo de 256 bits se realiza mediante la cadena , donde el número de ceros se determina a partir de la comparación .

Inicialización

Además del primer bloque del mensaje , los vectores se dan como valores de inicialización en la entrada de la función de primera ronda .

i j
0 una 2 3 cuatro 5 6 7
0 0x6d251e69 0x44b051e0 0x4eaa6fb4 0xdbf78465 0x6e292011 0x90152df4 0xee058139 0xdef610bb
una 0xc3b44b95 0xd9d2f256 0x70eee9a0 0xde099fa3 0x5d9b0557 0x8fc944b3 0xcf1ccf0e 0x746cd581
2 0xf7efc89d 0x5dba5781 0x04016ce5 0xad659c05 0x0306194f 0x666d1836 0x24aa230a 0x8b264ae7
3 0x858075d5 0x36d79cce 0xe571f7d7 0x204b1f67 0x35870c6a 0x57e9e923 0x14bcb808 0x7cde72ce
cuatro 0x6c68e9be 0x5ec41e22 0xc825b7c7 0xaffb4363 0xf5df3999 0x0fc688f1 0xb07224cc 0x03e86cea

Función redonda

La función de ronda es una aplicación secuencial de la función de inyección de mensajes MI y la función de permutación P.

Funciones de inyección de mensajes

La función de inyección de mensajes se puede representar como una matriz de transformación sobre un anillo . Campo generador de polinomios .

Funciones de inyección de mensajes

donde los números respectivamente denotan los polinomios

Funciones de inyección de mensajes

Funciones de inyección de mensajes

La función de permutación

La función de permutación no lineal tiene una entrada de bits, la longitud de la subpermutación se fija en la especificación Lúffa [6] , ; el número de permutaciones depende del tamaño del hash y se muestra en la tabla.

Longitud de hash Número de permutaciones
224 3
256 3
384 cuatro
512 5

La función de permutación es una iteración de 8 veces de la función paso a paso sobre el bloque obtenido de la función de inyección de mensajes . El bloque se representa como 8 palabras de 32 bits: . La función de paso consta de 3 funciones: SubCrumb, MixWord, AddConstant.

Permutar(a[8], j){ //Permutación Q_j para (r = 0; r < 8; r++){ SubCrumb(a[0],a[1],a[2],a[3]); SubCrumb(a[5],a[6],a[7],a[4]); para (k = 0; k < 4; k++) MezclaPalabra(a[k],a[k+4]); AñadirConstante(a, j, r); } } Subcrumb

SubCrumb  es la función de reemplazar bits l-th en o a lo largo del S-box , el resultado de la ejecución es el reemplazo , el índice S-box se obtiene concatenando los bits correspondientes : los bits se reemplazan con los bits correspondientes de acuerdo al siguiente esquema:

MixWord

MixWord  es una función de permutación lineal, toma y , como entrada ; la salida son y , obtenidos por el algoritmo:

  1. , (<<< 2 - girar a la izquierda 2 bits)
AgregarConstante

AddConstant  - función para agregar una constante a

En el apéndice B de la especificación Lúffa [6] se proporciona una tabla de constantes .

Bloque de finalización

La etapa final de la formación del resumen del mensaje consta de iteraciones sucesivas de la función de salida y la función de ronda con un bloque de mensaje cero 0x00 0 en la entrada. La función de salida es un XOR de todos los valores intermedios y el resultado es una palabra de 256 bits . En la i -ésima iteración, el valor de la función de salida se determina como

, donde , si , de lo contrario

Denote por palabras de 32 bits en , luego la salida de Lúffa se compone secuencialmente . Símbolo "||" significa concatenación.

Longitud de hash valor hash
224
256
384
512

El hash Lúffa-224 es en realidad el hash Lúffa-256 sin la última palabra de 32 bits.

Vectores de prueba [6]

Resúmenes del mensaje "abc" en diferentes tamaños de hash .

224 256 384 512
Z0.0 _ 0xf29311b8 0xf29311b8 0x9a7abb79 0xf4024597
Z0.1 _ 0x7e9e40de 0x7e9e40de 0x7a840e2d 0x3e80d79d
Z0.2 _ 0x7699be23 0x7699be23 0x423c34c9 0x0f4b9b20
Z 0.3 0xfbeb5a47 0xfbeb5a47 0x1f559f68 0x2ddd4505
Z0.4 _ 0xcb16ea4f 0xcb16ea4f 0x09bdb291 0xb81b8830
Z0.5 _ 0x5556d47c 0x5556d47c 0x6fb2e9ef 0x501bea31
Z0.6 _ 0xa40c12ad 0xa40c12ad 0xfec2fa0a 0x612b5817
Z 0.7 0x764a73bd 0x7a69881b 0xaae38792
Z1.0 _ 0xe9872480 0x1dcefd80
Z 1.1 0xc635d20d 0x8ca2c780
Z 1.2 0x2fd6e95d 0x20aff593
Z 1.3 0x046601a7 0x45d6f91f
Z 1.4 0x0ee6b2ee
Z1.5 _ 0xe113f0cb
Z1.6 _ 0xcf22b643
Z1.7 _ 0x81387e8a

Criptoanálisis

Durante la segunda ronda del concurso SHA-3 , Luffa-224 y Luffa-256 inicialmente mostraron una fuerza criptográfica baja y se requerían mensajes para un ataque exitoso. Después de eso, el algoritmo fue modificado por Dai Watanabe y se llamó Luffa v.2. Luffa v.2 [5] cambios :

  • función de finalización de ronda vacía agregada para todos los tamaños de hash
  • bloque S cambiado
  • aumentó el número de repeticiones de la función de paso de 7 a 8

Bart Preneel presentó un ataque de detección de colisión exitoso [7] para 4 rondas de la función de escalonamiento de Luffa para operaciones de hash y para 5 rondas, mostrando así la resistencia del diseño a la detección de colisión diferencial.

Rendimiento

En 2010, Thomas Oliviera y Giulio López realizaron con éxito una investigación [8] sobre la posibilidad de aumentar el rendimiento de la implementación original de Luffa. La implementación optimizada del algoritmo tiene un aumento de rendimiento del 20% en el cálculo del hash Luffa-512 cuando se ejecuta en 1 hilo; para Luffa-256/384, la ganancia de rendimiento de una implementación de un solo hilo en varias pruebas no es más que 5%. Los resultados de la prueba se muestran en la tabla en ciclos por byte :

  • En plataformas de 64 bits sin SSE:
Implementación del algoritmo Luffa-256 Luffa-384 Luffa-512
Implementación original 2009
Implementación de un solo subproceso 27 42 58
Tomás Olivera 2010
Implementación de un solo subproceso 24 42 46
Implementación multiproceso veinte 24 36
  • Usando SSE:
Implementación del algoritmo Luffa-256 Luffa-384 Luffa-512
Implementación original 2009
Implementación de un solo subproceso 17 19 treinta
Tomás Olivera 2010
Implementación de un solo subproceso quince dieciséis 24
Implementación multiproceso quince Dieciocho 25

A modo de comparación, la implementación de Keccak (el ganador de la competencia SHA-3 ) en pruebas [9] en un procesador similar usando SSE mostró los siguientes resultados: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Notas

  1. La familia de funciones hash Luffa . Consultado el 22 de noviembre de 2013. Archivado desde el original el 28 de diciembre de 2013.
  2. 12 competencia NIST sha-3 . Consultado el 22 de noviembre de 2013. Archivado desde el original el 9 de julio de 2011.
  3. 1 2 Candidatos a la segunda vuelta . Consultado el 28 de diciembre de 2013. Archivado desde el original el 10 de abril de 2012.
  4. La segunda conferencia de candidatos SHA-3 . Consultado el 28 de diciembre de 2013. Archivado desde el original el 12 de enero de 2014.
  5. 1 2 Informe de estado de la segunda ronda del SHA-3 . Consultado el 28 de diciembre de 2013. Archivado desde el original el 14 de marzo de 2011.
  6. 1 2 3 4 Especificación Luffa V.2.01 . Consultado el 29 de noviembre de 2013. Archivado desde el original el 20 de febrero de 2013.
  7. Encontrar colisiones para Luffa-256 v2 reducido . Fecha de acceso: 4 de enero de 2014. Archivado desde el original el 20 de febrero de 2013.
  8. Mejorar el rendimiento del algoritmo Luffa Hash . Consultado el 28 de diciembre de 2013. Archivado desde el original el 21 de marzo de 2014.
  9. La familia de funciones de esponja Keccak: rendimiento del software . Fecha de acceso: 4 de enero de 2014. Archivado desde el original el 4 de enero de 2014.

Literatura

Enlaces