Tigre (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 13 de marzo de 2013; las comprobaciones requieren 20 ediciones .

Tiger es una función hash criptográfica desarrollada por Ros Anderson y Eli Biham en 1995.

Tiger fue diseñado para ejecutarse particularmente rápido en computadoras de 64 bits. Tiger no tiene restricciones de patente, se puede usar libremente tanto con la implementación de referencia como con sus modificaciones. El tamaño del valor hash es de 192 bits (Tiger/192), aunque también existen versiones más cortas por compatibilidad con SHA-1 (Tiger/160) y con MD4 , MD5 , RIPEMD, Snefru (Tiger/128). Velocidad de funcionamiento: 132 Mbps (probado en un procesador Alpha 7000, modelo 660). En los procesadores modernos es mucho más rápido (incluso cuando se prueba en un AMD Sempron 3000+ de 32 bits, la velocidad es de unos 225 Mbps).

Tiger2 es una versión de Tiger que difiere de la principal solo en un algoritmo de adición de bits diferente, similar a MD5 / SHA-1 . Los vectores de prueba están disponibles para Tiger2.

Orígenes

El algoritmo fue desarrollado en 1995 por Ross Anderson y Eli Biham. Esa época se caracterizó por el hecho de que ya se encontraban colisiones para las populares funciones hash MD4 y Snefru . Estos últimos, según los autores, pusieron en duda la fiabilidad de sus derivados, como MD5 y Snefru-8 . Los principales objetivos en el desarrollo de Tiger fueron:

seguridad ;
trabajo rápido en los nuevos procesadores de 64 bits con una velocidad razonable en los de 32 bits;
posible sustitución de las series MD y SHA.

Algoritmo

El número de S-boxes utilizados es 4. S-box convierte 8 bits a 64 bits. Es decir, cada uno de ellos tiene 256 palabras de 64 bits y la cantidad total de memoria requerida para almacenar S-boxes es 4*256*8 = 8192 = 8 KB. Para ello basta con la memoria caché de la mayoría de los procesadores, aunque puede ser difícil de implementar en microcontroladores.

Al igual que con la familia MD4 , se agrega un bit "1" al mensaje seguido de ceros. Los datos de entrada se dividen en n bloques de 512 bits.

Seleccione el primer bloque de 512 bits. Este bloque se divide en ocho palabras de 64 bits x0, x1, ..., x7. El orden de los bytes es little-endian .

Se toman tres registros de 64 bits con valores iniciales (valor hash ): $h_{0}$

a = 0x0123456789ABCDEF b=0xFEDCBA9876543210 c = 0xF096A5B4C3B2E187

Ahora, para pasar de valor a valor , se realizan las siguientes operaciones: $hola}$ $h_{{yo+1}}$

guardar_abc
pasar (a, b, c, 5)
horario_clave
pase (c, a, b, 7)
horario_clave
pase (b, c, a, 9)
retroalimentación

Aquí save_abc guarda el valor : $hola}$

aa = un bb = segundo cc=c

pass(a, b, c, mul) significa:

ronda(a,b,c,x0,mul) redondo (b, c, a, x1, mul) ronda(c,a,b,x2,mul) ronda(a,b,c,x3,mul) redondo (b, c, a, x4, mul) ronda(c,a,b,x5,mul) ronda(a,b,c,x6,mul) redondo (b, c, a, x7, mul)

donde ronda (a, b, c, x, mul) :

c ^ = x a -= t1[c_0] ^ t2[c_2] ^ t3[c_4] ^ t4[c_6] b += t4[c_1] ^ t3[c_3] ^ t2[c_5] ^ t1[c_7] b *= mul

c_i — i-ésimo byte c (0 <= i <= 7);

^ - operación XOR;

ti - i-ésima caja S

key_schedule - generación de claves, una función reversible que es responsable de cambiar una pequeña cantidad de bits del mensaje x para hacer que cambie una gran cantidad de bits en la siguiente ejecución de pass :

x0 -= x7^0xA5A5A5A5A5A5A5A5 x1 ^= x0 x2 += x1 x3 -= x2 ^ ((~x1)<<19) x4 ^= x3 x5 += x4 x6 -= x5 ^ ((~x4)>>23) x7 ^= x6 x0 += x7 x1 -= x0 ^ ((~x7)<<19) x2 ^= x1 x3 += x2 x4 -= x3 ^ ((~x2)>>23) x5 ^= x4 x6 += x5 x7 -= x6^0x0123456789ABCDEF

donde <<y >> son desplazamientos lógicos a izquierda y derecha, ~ es la inversión

realimentación - retroalimentación:

un ^ = aa b -= bb c += cc

Es decir, obtenemos 24 rondas en total. La concatenación de los valores recibidos a , b , c da un valor hash intermedio , que se utiliza como valor inicial para el siguiente bloque de datos de 512 bits. Un valor intermedio en el último bloque da un valor Tiger/192 de 192 bits. $h_{{yo+1}}$ $h_{n}$

Vectores de prueba

Ejemplos de valores hash obtenidos con el programa testtiger de la página del autor [1] .

Hash("") = 24F0130C63AC9332 16166E76B1BB925F F373DE2D49584E7A Hash("Tigre") = 9F00F599072300DD 276ABB38C8EB6DEC 37790C116F9D2BDF

Hash("abc") = F258C1E88414AB2A 527AB541FFC5B8BF 935F7B951C132951 Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-") = 87FB2A9083851CF7 470D2CF810E6DF9E B586445034A5A386

Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZ=abcdefghijklmnopqrstuvwxyz+0123456789") = 467DB80863EBCE48 8DF1CD1261655DE9 57896565975F9197

Seguridad

Aspectos clave de seguridad del Tiger:

no linealidad de transformación de S-boxes;
el uso de registros de 64 bits acelera el cambio de avalancha de los tres registros cuando cambia cualquier bit del mensaje;
la generación de claves proporciona cambios significativos en todos los bits en conversiones posteriores con un ligero cambio en el mensaje;
multiplicar el registro b en cada ronda también promueve el barajado y aumenta la resistencia a los ataques a las teclas relacionadas;
la retroalimentación evita los ataques de cumpleaños intermedios .

Un ataque de clave vinculada es un ataque en el que un criptoanalista puede calcular un hash para varios valores diferentes de vectores de inicialización que no conoce, pero conoce alguna relación entre ellos (por ejemplo, que difieren en un bit o que alguna parte de todos los vectores es uno y el mismo). Debido a este tipo de ataque, el cifrado WEP tuvo que cambiarse a WPA .

Un ataque de cumpleaños intermedio es un ataque de cumpleaños aplicado en rondas intermedias para lograr los valores hash deseados. Aunque, según los autores, es poco probable que los ataques de este tipo conduzcan a una menor complejidad (de acuerdo con la paradoja del cumpleaños ). $2^{{96}}$

Criptoanálisis

Sea h(x, m) una función hash , donde x es un vector de inicialización, m es un bloque de mensaje. ^ es la operación XOR, w{} es el peso de Hamming (el número de componentes distintos de cero del número binario ). Después:

Por colisión entendemos la situación en la que w{h(x, m1) ^ h(x, m2)} = 0;
bajo casi colisión - w{h(x, m1) ^ h(x, m2)} = a, donde a es un valor pequeño;
bajo pseudo - colisión-w{h(x1,m1) ^ h(x2,m2)} = 0;
bajo casi pseudo - colisión-w{h(x1,m1) ^ h(x2,m2)} = a, donde a es un valor pequeño.

Idealmente, de acuerdo con la paradoja del cumpleaños , encontrar una colisión de una función hash de N bits requeriría al menos operaciones. $O(2^{{N/2}})$

En 2006, John Kelsey y Stefan Lax introdujeron una colisión Tiger-16 (con 16 rondas en lugar de 24) con dificultad y una casi pseudo-colisión para Tiger-20 con dificultad . Más tarde ese año, Florian Mendel et al., mostraron cómo aplicar la técnica de ataque de John Kelsey y Stefan Lax para conseguir una colisión del Tiger-19, y también propusieron dos técnicas diferentes para conseguir esta colisión con y . $2^{{44}}$ $2^{{48}}$ $2^{{62}}$ $2^{{69}}$

Descripción general de los ataques a Tiger

Número de rondas	Tipo de	Complejidad	Descripción
Tigre-16	colisión	$2^{{44}}$	[Articulo 1]
tigre-19	colisión	$2^{{62}}$ y $2^{{69}}$	[Artículo 2]
tigre-19	pseudocolisión	$2^{{44}}$	[Artículo 2]
Tigre-21	pseudocolisión	$2^{{66}}$	[Artículo 2]
Tigre-23/128	pseudocolisión	$2^{{44}}$	[Artículo 2]
Tigre-23	pseudocolisión	$2^{47}$	[artículo 3]
Tigre-20	casi pseudo-colisión	$2^{{48}}$	[Articulo 1]
Tigre-21	casi pseudo-colisión	$2^{{44}}$	[Artículo 2]
tigre-22	casi pseudo-colisión	$2^{{44}}$	[Artículo 2]
Tigre-24	casi pseudo-colisión	$2^{47}$	[artículo 3]

Ataque al Tiger-16

Expliquemos la idea de encontrar una colisión para Tiger-16, es decir, para un Tiger con 16 rondas, descrita por John Kelsey y Stefan Laks [artículo 1] .

Consideramos palabras de 64 bits. Estaremos tratando con una diferencia entre dos tipos de palabras: la diferencia xor y la diferencia aditiva . El primero de ellos es el resultado del módulo de diferencia habitual , y el segundo es el resultado de la operación XOR. Por lo general, la transformación de un tipo de diferencia en otro es una cuestión de azar. Pero hay un caso en el que dos tipos de diferencias son iguales entre sí con probabilidad 1. Es decir, cuando la diferencia , es válida en este caso, las palabras simplemente difieren entre sí por el bit más significativo. También notamos la propiedad de diferencia: no cambia si la palabra se multiplica por un número impar (lo cual es muy conveniente, ya que el algoritmo usa impar mul = 5, 7, 9). $2^{64}$ $yo=2^{63}$

deja _ bajo conjunto $yo=2^{63}$

(I0, I1, I2, I3, I4, I5, I6, I7)

queremos decir que la diferencia entre las j-ésimas (j = 0, 1, ..., 7) palabras de 64 bits de las claves es igual (no importa de qué tipo, ya que solo consideraremos diferencias y 0) . Es decir, = xj ^ xj'. $yo$ $2^{{63}}$ $yo$

John Kelsey y Stefan Laks propusieron tomar dos bloques (512 bits cada uno) con un vector de diferencia . Si sigue el algoritmo, teniendo en cuenta las propiedades de las diferencias, puede mostrar que después del primer paso (después de las rondas 0, 1, ..., 7) y key_schedule habrá un vector . Después de las rondas 8-9 obtenemos , y las rondas 10-15 no afectan la diferencia. Por lo tanto, obtenemos la técnica de mantener diferencias entre claves con una probabilidad de 1. $(yo,yo,yo,yo,0,0,0,0)$ $(yo,yo,0,0,0,0,0,0)$ $(0,0,0,0,0,0,0,0)$

Al mismo tiempo, con la ayuda de modificaciones de mensajes a través de ataques intermedios de cumpleaños , se resuelve el problema de mantener la diferencia en los valores hash a, b, c, de modo que después de la ronda 6 había un vector de diferencia , y después de las rondas 7-9 - . La técnica de modificación de mensajes es la que más tiempo consume, que es donde se obtiene la complejidad resultante . Las rondas 10-15 no harán ninguna diferencia (de hecho, las claves de este paso ya son las mismas). $(yo, yo, 0)$ $(0,0,0)$ $2^{{44}}$

Es decir, después de 16 rondas, los valores hash coincidirán.

Uso

Tiger se utiliza en la tecnología TTH , donde el hash se calcula en forma de árbol. TTH , a su vez, se utiliza en los protocolos de intercambio de archivos Gnutella , Gnutella2 , Direct Connect , así como en el alojamiento de archivos Phex, BearShare, LimeWire , Shareaza , DC++ y Valknut .

Notas

↑ Resultados de la prueba de testtiger . Consultado el 30 de septiembre de 2017. Archivado desde el original el 8 de mayo de 2018. (indefinido)

Artículos

↑ 1 2 3 John Kelsey y Stefan Lucks, Collisions and Near-Collisions for Reduced-Round Tiger Archivado el 4 de marzo de 2016 en Wayback Machine , actas de Fast Software Encryption 13, Graz, 2006 ( PDF )
↑ 1 2 3 4 5 6 Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida y Dai Watanabe, Update on Tiger (enlace no disponible) , actas de Indocrypt 7, Calcuta, 2006 ( PDF )
↑ 1 2 Mendel, Florián; Rijmen Vincent., Criptoanálisis de la función Tiger Hash (enlace no disponible) , ASIACRYPT 2007. Springer Berlin / Heidelberg. páginas. 536-550 ( PDF )

Enlaces

Página de autores de tigre

Funciones hash
propósito general	Adler-32 CDN Suma de comprobación de Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Árbol de hachís picadillo de jenkins suma de hash
Criptográfico	Stribog GOST R 34.11-94 Cinturón BLAKE BMW CubeHash ECO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna Hachís de LM luffa MD2 MD4 MD5 MD6 N-hachís RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD RÁPIDO Piel Snefru Tigre Torbellino
Funciones de generación de claves	cripta PBKDF2 cripta Argón2 Lyra2
Número de cheque ( comparación )	Suma de verificación Algoritmo de Verhouff Algoritmo lunar Maldito algoritmo Código de barras cuentas bancarias tarjetas bancarias ES EN SNILES OKPO ESTAÑO OKATO ISBN OGRN y OGRNIP VIN
Hachís	Comparación de números de cheque Protocolos de autenticación Comparación de códigos de barras Criptografía Enlace magnético firma Merkle ed2k URNA