Grano (cifrado)

Grain es un cifrador de flujo presentado a eSTREAM en 2004 por Martin Hell , Thomas Johansson y Willi Meier . Fue seleccionado para el portafolio final de eSTREAM para el Perfil 2 por el proyecto eSTREAM. Grain está diseñado principalmente para entornos de hardware restringidos. Acepta una clave de 80 bits y un vector de inicialización (IV) de 64 bits . Las especificaciones no recomiendan una longitud máxima de salida por par (clave, IV). Se han identificado y corregido varias debilidades potenciales en el cifrador en Grain 128a , que ahora es el cifrador recomendado para entornos de hardware que proporcionan seguridad y autenticación de 128 bits.

El estado interno de 160 bits de Grain consta de un registro de desplazamiento con retroalimentación lineal (LFSR) de 80 bits y un registro de desplazamiento con retroalimentación no lineal (NLFSR) de 80 bits . Grain actualiza un bit del estado del LFSR y un bit del estado del NLFSR por cada bit de texto cifrado liberado por una función de filtro no lineal. El NLFSR de 80 bits se actualiza con una función booleana no lineal de 5 a 1 y una entrada lineal de 1 bit seleccionada del LFSR. La función no lineal de 5 a 1 toma como entrada 5 bits del estado del NLFSR. El LFSR de 80 bits se actualiza con una función lineal de 6 a 1. Durante las operaciones de cifrado, la salida del cifrado se realimenta adicionalmente como entradas lineales a las funciones de actualización del NLFSR y del LFSR.

En la versión original 0.0 de Grain, se suministra un bit del NLFSR de 80 bits y cuatro bits del LFSR de 80 bits a una función booleana no lineal de 5 a 1 (que se elige para que sea equilibrada, inmune a la correlación de primer orden y tenga grado algebraico 3) y la salida se combina linealmente con 1 bit del NLFSR de 80 bits y se libera como salida.

En la versión 1.0 actualizada de Grain, un bit del NLFSR de 80 bits y cuatro bits del LFSR de 80 bits se suministran a una función booleana no lineal de 5 a 1 (ligeramente revisada) y la salida se combina linealmente con 7 bits del NLFSR de 80 bits y se libera como salida.

Para inicializar el cifrado, la clave de 80 bits se carga directamente en el NLFSR de 80 bits y el IV de 64 bits se carga en los 64 bits inferiores del LFSR; los 16 bits superiores restantes del LFSR se rellenan con unos. El cifrado se mantiene sellado durante 160 rondas, durante las cuales los 160 bits de la secuencia de claves generada se retroalimentan linealmente a las funciones de actualización del LFSR y del NLFSR. El cifrado no libera ninguna secuencia de claves durante el proceso de inicialización.

Los autores de Grain analizan las tasas de difusión completas del proceso de inicialización de Grain en las especificaciones de la versión 1.0 de Grain: "Para la inicialización con dos vectores de inicialización (IV) diferentes, que difieren en un solo bit, la probabilidad de que un bit del registro de desplazamiento sea el mismo para ambas inicializaciones debería ser cercana a 0,5. Las simulaciones muestran que esto se logra después de 160 ciclos de reloj".

El cifrado está diseñado para permitir que se realicen hasta 16 rondas en paralelo, lo que permite implementaciones más rápidas a costa de un mayor uso de hardware.

El tamaño de la clave es de 80 bits y el tamaño del IV se especifica en 64 bits. Los autores afirman que el cifrado está diseñado de tal manera que no debería ser posible ningún ataque más rápido que la búsqueda exhaustiva de la clave, por lo que el mejor ataque debería requerir una complejidad computacional no significativamente menor que 2 ⁸⁰ .

En las especificaciones originales de Grain Versión 0.0, ^{[ 1 ]} los autores afirman: «Grain proporciona una seguridad superior a la de otros cifrados conocidos diseñados para su uso en aplicaciones de hardware. Ejemplos conocidos de estos cifrados son E0, utilizado en Bluetooth , y A5/1, utilizado en GSM . Si bien estos cifrados también requieren una implementación de hardware muy sencilla, se ha demostrado que son muy inseguros. En comparación con E0 y A5/1 , Grain ofrece una mayor seguridad manteniendo una baja complejidad de hardware».

Los autores citan el ataque contra E0 ^{[ 2 ]} que requiere una complejidad de ^2⁴⁰ y ^2³⁵ tramas (una trama tiene 2745  bits de longitud). El cifrado original Grain Versión 0.0 fue roto por un ataque de recuperación de clave ^{[ 3 ]} que requirió una complejidad de ^2⁴³ cálculos y ^2³⁸ bits de flujo de clave para determinar la clave de 80 bits.

En las especificaciones revisadas de Grain Versión 1.0, ^{[ 4 ]} el cifrador presenta una función de salida ligeramente modificada y la función de retroalimentación del NLFSR ha recibido un cambio menor. Las especificaciones afirman: "La función de filtro es bastante pequeña, con solo 5 variables y una no linealidad de 12. Sin embargo, esto se compensa parcialmente con el hecho de que una de las entradas se toma del NLFSR. El bit de entrada del NLFSR dependerá de forma no lineal [ sic ] de otros bits en el estado, tanto del LFSR como del NLFSR. La pequeña función de filtro también se compensa añadiendo linealmente 7 bits [ sic ] del NLFSR en posiciones adecuadas para formar la función de salida."

A fecha de octubre de 2006, no se conocen ataques de recuperación de claves mejores que el ataque de fuerza bruta contra Grain Versión 1.0.

Sin embargo, en septiembre de 2006, Ozgul Kucuk publicó un ataque de clave relacionada en el artículo «Ataque de resincronización de deslizamiento en la inicialización de Grain 1.0». ^{[ 5 ]} El artículo afirma: «Encontramos claves relacionadas y valores iniciales del cifrador de flujo Grain 1.0. Para cualquier par (K,IV) existe un par relacionado (K',IV') con una probabilidad de 1/22 que genera una secuencia de clave desplazada 1 bit. Si bien esto aún no resulta en un ataque eficiente de recuperación de clave, indica una debilidad en la inicialización que podría superarse [ sic ] con un poco de esfuerzo».

• Página de eSTREAM sobre Grain archivada el 6 de octubre de 2008 en Wayback Machine.