Trivium (cifrado)

Trivium es un cifrador de flujo síncrono diseñado para proporcionar un equilibrio flexible entre velocidad y número de puertas lógicas en el hardware, y una implementación de software razonablemente eficiente.

Trivium fue presentado al Perfil II (hardware) del concurso eSTREAM por sus autores, Christophe De Cannière y Bart Preneel , y ha sido seleccionado como parte del portafolio de cifradores de hardware de área reducida (Perfil 2) del proyecto eSTREAM. No está patentado y ha sido especificado como estándar internacional según la norma ISO/IEC 29192-3. ^{[ 1 ]}

Genera hasta ^2⁶⁴ bits de salida a partir de una clave de 80 bits y un vector de inicialización (IV) de 80 bits . Es el participante más sencillo de eSTREAM; si bien muestra una notable resistencia al criptoanálisis por su simplicidad y rendimiento, los ataques recientes dejan el margen de seguridad bastante reducido.

El estado interno de 288 bits de Trivium consta de tres registros de desplazamiento de distinta longitud. En cada ronda, se introduce un bit en cada uno de los tres registros de desplazamiento mediante una combinación no lineal de tomas de ese registro y de otro; se produce un bit de salida. Para inicializar el cifrado, la clave y el vector de inicialización (IV) se escriben en dos de los registros de desplazamiento, y los bits restantes siguen un patrón fijo; el estado del cifrado se actualiza 4 × 288 = 1152 veces, de modo que cada bit del estado interno depende de cada bit de la clave y del IV de una manera compleja y no lineal.

No se registran cambios en los primeros 65 bits de cada registro de desplazamiento, por lo que cada bit de estado nuevo no se utiliza hasta al menos 65 rondas después de su generación. Esta es la clave del rendimiento del software de Trivium y su flexibilidad en el hardware.

Trivium se puede especificar de forma muy concisa utilizando tres ecuaciones recursivas. ^{[ 2 ]} Cada variable es un elemento de GF (2); se pueden representar como bits , donde "+" es XOR y "•" es AND .

• a _i = c _{i −66} + c _{i −111} + c _{i −110} • c _{i −109} + a _{i −69}
• b _i = a _{i −66} + a _{i −93} + a _{i −92} • a _{i −91} + b _{i −78}
• c_i = b_i−69 + b_i−84 + b_i−83 • b_i−82 + c_i−87

The output bits r₀ ... r_2⁶⁴−1 are then generated by

• r_i = c_i−66 + c_i−111 + a_i−66 + a_i−93 + b_i−69 + b_i−84

Given an 80-bit key k₀ ... k₇₉ and an l-bit IV v₀ ... v_l−1 (where 0 ≤ l < 80), Trivium is initialized as follows:

• (a₋₁₂₄₅ ... a₋₁₁₅₃) = (0, 0 ... 0, k₀ ... k₇₉)
• (b₋₁₂₃₆ ... b₋₁₁₅₃) = (0, 0 ... 0, v₀ ... v_l−1)
• (c₋₁₂₆₃ ... c₋₁₁₅₃) = (1, 1, 1, 0, 0 ... 0)

The large negative indices on the initial values reflect the 1152 steps that must take place before output is produced.

To map a stream of bits r to a stream of bytes R, we use the LSb-first mapping R_i = Σ_{j=0, ..., 7} 2^jr_8i+j.

A straightforward hardware implementation of Trivium would use 3488 logic gates and produce one bit per clock cycle. However, because each state bit is not used for at least 64 rounds, 64 state bits can be generated in parallel at a higher hardware cost of 5504 gates. Different tradeoffs between speed and area are also possible.

The same property allows an efficient bitslice implementation in software; performance testing by eSTREAM give bulk encryption speeds of around 4 cycles/byte on some x86 platforms, which compares well to the 19 cycles/byte of the AES reference implementation on the same platform.

[Trivium] fue diseñado como un ejercicio para explorar hasta qué punto se puede simplificar un cifrador de flujo sin sacrificar su seguridad, velocidad o flexibilidad. Si bien los diseños simples son más propensos a ser vulnerables a ataques simples, y posiblemente devastadores (por lo que desaconsejamos firmemente el uso de Trivium en esta etapa), sin duda inspiran más confianza que los esquemas complejos, si sobreviven a un largo período de escrutinio público a pesar de su simplicidad. ^{[ 3 ]}

A partir de abril de 2015 No se conocen ataques criptoanalíticos mejores que el ataque de fuerza bruta , pero varios ataques se acercan. El ataque del cubo requiere 2 ⁶⁸ pasos para romper una variante de Trivium donde el número de rondas de inicialización se reduce a 799. ^{[ 4 ]} Anteriormente, otros autores especularon que estas técnicas podrían conducir a una ruptura para 1100 rondas de inicialización, o "quizás incluso el cifrado original". ^{[ 5 ]} Esto se basa en un ataque debido a Michael Vielhaber que rompe 576 rondas de inicialización en solo 2 ^12.3 pasos. ^{[ 6 ]}

Otro ataque recupera el estado interno (y por lo tanto la clave) del cifrado completo en aproximadamente 2 ^89,5 pasos (donde cada paso es aproximadamente el costo de un solo intento en una búsqueda exhaustiva). ^{[ 7 ]} Se han roto variantes reducidas de Trivium que utilizan los mismos principios de diseño utilizando una técnica de resolución de ecuaciones. ^{[ 8 ]} Estos ataques mejoran el conocido ataque de compensación tiempo-espacio en los cifrados de flujo, que con el estado interno de 288 bits de Trivium tomaría 2 ¹⁴⁴ pasos, y muestran que una variante de Trivium que no hiciera ningún cambio excepto aumentar la longitud de la clave más allá de los 80 bits exigidos por el perfil eSTREAM 2 no sería segura. Utilizando una estrategia de resolución optimizada, es posible reducir aún más la complejidad de recuperación del estado a 2 ¹³² pasos. ^{[ 9 ]}

^{En el artículo titulado "Una construcción de cifrado de flujo inspirada en los principios de diseño de cifrado por bloques" [ 10 ]} se ofrece una justificación detallada del diseño de Trivium.

• Página de eSTREAM en Trivium archivada el 23/09/2015 en Wayback Machine .
• Implementación de eSTREAM archivada el 20 de septiembre de 2015 en Wayback Machine .