Trivium (cifrado)

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 31 de diciembre de 2018; las comprobaciones requieren 4 ediciones .

Trivium  es un algoritmo de cifrado de transmisión síncrona simétrica centrado principalmente en la implementación de hardware con un equilibrio flexible entre la velocidad y la cantidad de elementos, que también tiene la posibilidad de una implementación de software bastante eficiente.

El cifrado se introdujo en diciembre de 2008 como parte de la cartera del proyecto europeo eSTREAM , perfil 2 (cifrados orientados al hardware). Los autores del cifrado son Christophe De Kannier y Bart Prenel.

Este cifrado de flujo genera hasta bits del flujo de salida a partir de 80 bits de la clave y 80 bits de IV (vector de inicialización). Este es el cifrado más simple del proyecto eSTREAM, que muestra excelentes resultados en términos de estabilidad criptográfica.

Trivium está incluido en el estándar ISO/IEC 29192-3 como un cifrado de flujo ligero.

Descripción

El estado inicial de Trivium es de 3 registros de desplazamiento con una longitud total de 288 bits. Cada ciclo de reloj cambia los bits en los registros de desplazamiento por medio de una combinación no lineal de avance y retroalimentación. Para inicializar el cifrado se escribe la clave K y el vector de inicialización IV en 2 de 3 registros y se ejecuta el algoritmo 4x288 = 1152 veces, lo que garantiza que cada bit del estado inicial depende de cada bit de la clave y de cada bit del vector de inicialización.

Después de pasar la etapa de inicialización, en cada ciclo se genera un nuevo miembro del flujo de claves Z , que pasa el procedimiento XOR con el siguiente miembro del texto. El procedimiento de descifrado ocurre en orden inverso: cada miembro del texto cifrado se somete a XOR con cada miembro del flujo de claves Z. [una]

Algoritmo

Cifrados de flujo

Trivium genera una secuencia Z , el llamado flujo de claves, de hasta bits de longitud. Para cifrar un mensaje, es necesario XOR el mensaje y el flujo de claves. El descifrado se realiza de manera similar, la operación XOR se realiza a partir del texto cifrado y el flujo de claves.

Inicialización

El algoritmo se inicializa cargando una clave de 80 bits y un vector de inicialización de 80 bits en un estado inicial de 288 bits. La inicialización se puede describir mediante el siguiente pseudocódigo .

El procedimiento de inicialización asegura que cada bit del estado inicial dependa de cada bit de la clave y de cada bit del vector de inicialización. Este efecto ya se logra después de 2 pases completos (ejecuciones de 2*288 ciclos). 2 pases más están diseñados para complicar las relaciones de bits. Por ejemplo, los primeros 128 bytes del flujo de clave Z , obtenidos de la clave nula y el vector de inicialización, tienen aproximadamente el mismo número de 1 y 0 distribuidos uniformemente Incluso con las claves más simples e idénticas, el algoritmo Trivium produce una secuencia de números que están cerca del azar.

Los primeros 128 bytes del flujo de claves, generados a partir de ceros K y IV en hexadecimal 0000000 e0 fb 26 bf 59 58 1b 05 7a 51 4e 2e 9f 23 7f c9 0000010 32 56 16 03 07 19 2d cf a8 e7 0f 79 b2 a1 cd e9 0000020 52 f7 03 92 68 02 38 b7 4c 2b 75 1a a2 9a 9a 59 0000030 55 28 98 49 74 6e 59 80 80 03 4c 1a a5 b5 f2 d4 0000040 34 69 bb 86 ca 52 15 b3 ae 80 12 69 73 55 9a 31 0000050 b2 6c 0e f5 16 40 20 d6 30 7f 4e 3f 48 16 cc 24 0000060 25 5c ad c4 10 a1 c9 1b bb e8 01 4e dc fc 2e 27 0000070 9e fa ae 02 a2 48 05 b2 2e fb f4 4f 27 76 56 27 0000080 3e 5e b7 06 4e e6 4a 57 7b ad a2 3a 1c 52 en adelante 48 0000090 f3 92 f8 87 ff 98 aa 87 e6 bf f6 19 38 3c ff 19 00000a0 3f 0a a5 fd 01 ce d0 d8 fa f0 fa 87 09 a1 4e ee 00000b0 63 29 9f 9b 31 ef 95 a5 c7 76 19 8d c7 e0 df 55 00000c0 1b 0f 50 e9 b8 91 85 ea 06 7b d5 2a anuncio 2b 77 f4 00000d0 ca 84 9b 6d 3f 2e a9 85 99 d7 04 95 02 33 fd f0 00000e0 b7 f8 5b 6e b7 c8 f0 b4 46 aa 20 cd a0 dd dd 4f

Como puede ver, después de 4 ciclos de inicialización, las unidades escritas en las celdas afectaron a todos los demás bits del estado inicial y , por lo tanto, incluso con las claves más simples e idénticas, cada byte del mensaje cambiará como resultado de la encriptación. algoritmo.

Operación del algoritmo

El generador de flujo utiliza 15 bits de un estado inicial de 288 bits para cambiar 3 bits del estado y calcular 1 bit del flujo de claves . Como resultado del algoritmo, se pueden obtener hasta bits del flujo de claves . El algoritmo se puede describir mediante el siguiente pseudocódigo.

En este pseudocódigo, todos los cálculos se realizan módulo 2. Es decir, las operaciones de suma y multiplicación son operaciones XOR y AND .

Período

El período de flujo clave es difícil de determinar debido a la naturaleza no lineal de los cambios de estado inicial. Incluso si todos los disparadores tienen AND, lo que da como resultado un circuito completamente lineal, se puede demostrar que cualquier par de clave y vector de inicialización dará como resultado la generación de un flujo de clave con un período de la orden (que ya excede la longitud de flujo de clave requerida ).

Si asumimos que Trivium comienza a generar un flujo de clave aleatoria después de un pequeño número de iteraciones, entonces todas las secuencias generadas hasta la longitud serán igualmente probables. Además de la probabilidad de que el par de vectores clave/inicialización genere un flujo de claves con un período inferior a aproximadamente [2] .

Cifrados de la familia Trivium

Las modificaciones de este cifrado difieren en el número de registros de desplazamiento y sus longitudes.

Univium

El cifrado de flujo Univium consta de un solo registro de desplazamiento y solo se necesita una clave que no supere la longitud del registro para la codificación. [una]

Bivium

Junto con Trivium, sus autores propusieron el cifrado Bivium, que implementa solo 2 registros de desplazamiento con una longitud total de 177 bits. El proceso de inicialización es similar a Trivium. Cada ciclo, se cambian 2 bits de estado y se genera un nuevo bit del flujo de clave. Según la generación de la key stream Z , existen 2 versiones: Bivium-A y Bivium-B (Bivium). En Bivium-A, se implementa una dependencia directa del nuevo miembro Z del bit de estado cambiado , a partir de la diferencia con Bivium-B (Bivium) . [3]

Trivium-toy y Bivium-toy

Las versiones de juguete se obtuvieron mediante la reducción de las longitudes de los registros, lo que redujo la complejidad computacional del algoritmo, al tiempo que conservaba todas las propiedades matemáticas. La longitud de cada registro se redujo 3 veces, y el Bivium-toy también constaba de solo dos registros.

Cada modificación del cifrado Trivium fue creada para simplificar su descripción matemática, lo que tiene más un propósito educativo que el propósito de usarlos en herramientas de seguridad de la información. [cuatro]

Rendimiento

La implementación de hardware estándar del algoritmo requiere 3488 puertas y produce 1 bit del flujo de claves por ciclo de reloj. Pero, dado que cada nuevo estado de un bit no cambia durante al menos 64 rondas, se pueden generar 64 estados más en paralelo cuando la cantidad de elementos lógicos aumenta a 5504. Además, son posibles varias variaciones de rendimiento según la cantidad de elementos. usó.

La interpretación del software de este algoritmo también es bastante efectiva. La implementación C de Trivium en AthlonXP 1600+ ofrece más de 2,4 Mbps de cifrado

Seguridad

A diferencia de los primeros cifrados de flujo como RC4 , el algoritmo Trivium, además de la clave privada ( K ), también tiene un vector de inicialización ( IV ), que es la clave pública. El uso de IV permite múltiples sesiones de cifrado/descifrado independientes usando solo 1 clave y múltiples vectores de inicialización (uno para cada sesión). También es posible utilizar múltiples vectores de inicialización para la misma sesión, utilizando un nuevo IV para cada nuevo mensaje.

Por el momento, no se conocen métodos de ataque a este algoritmo que sean más efectivos que la enumeración secuencial . La complejidad de este ataque depende de la longitud del mensaje y es del orden de .

Hay estudios de métodos de ataque (por ejemplo, el ataque cúbico [5] ), que tienen una eficiencia cercana a la enumeración. Además, existe un método de ataque que le permite recuperar K de IV y keystream. La complejidad de este ataque es igual y disminuye ligeramente con un aumento en el número de vectores de inicialización utilizados con una tecla. Los ataques también son posibles con el estudio de la secuencia pseudoaleatoria del flujo de claves para encontrar patrones y predecir bits posteriores del flujo, pero estos ataques requieren la solución de ecuaciones no lineales complejas. La complejidad resultante más pequeña de tal ataque es [6] [7]

Métodos de investigación

Casi todos los logros de piratería de Trivium son intentos de usar ataques llevados a cabo con éxito en versiones truncadas del algoritmo [1] . A menudo, se utiliza una versión del algoritmo Bivium como la que se está estudiando, que utiliza solo 2 registros de desplazamiento con una longitud total de 192 bits [1] .

Notas

  1. 1 2 3 4 Copia archivada . Consultado el 23 de diciembre de 2009. Archivado desde el original el 25 de septiembre de 2018.
  2. Copia archivada . Consultado el 23 de diciembre de 2009. Archivado desde el original el 20 de octubre de 2016.
  3. Dos ataques triviales a Trivium | SpringerLink . Consultado el 27 de julio de 2018. Archivado desde el original el 27 de julio de 2018.
  4. Copia archivada . Consultado el 10 de marzo de 2017. Archivado desde el original el 12 de marzo de 2017.
  5. Copia archivada . Consultado el 23 de diciembre de 2009. Archivado desde el original el 17 de mayo de 2017.
  6. Copia archivada . Consultado el 23 de diciembre de 2009. Archivado desde el original el 26 de agosto de 2016.
  7. Copia archivada . Consultado el 23 de diciembre de 2009. Archivado desde el original el 30 de julio de 2016.

Enlaces