En criptografía , el cifrado QUAD es un cifrado de flujo relativamente nuevo , que se diseñó teniendo en cuenta argumentos de seguridad demostrables.
General | |
---|---|
Diseñadores | Côme Berbain, Henri Gilbert y Jacques Patarin |
Publicado por primera vez | 28 de mayo de 2006 (en Eurocrypt) |
Detalle de cifrado | |
Tamaños de clave | 80 bits |
Estructura | sistema multivariado de ecuaciones cuadráticas |
Descripción
QUAD se basa en la iteración de un sistema cuadrático multivariado elegido al azar S = (Q 1 , ..., Q m ) de m = kn ecuaciones en n incógnitas sobre un campo finito GF (q). El proceso de generación de keystream consiste simplemente en iterar los tres pasos siguientes para producir (k -1) n GF (q) valores de keystream en cada iteración.
- Calcule la kn-tupla de los valores de GF (q) S (x) = (Q 1 (x), ..., Q kn (x)) donde x es el valor actual del estado interno;
- Genere la secuencia (Q n + 1 (x), ..., Q kn (x)) de (k-1) n GF (q) valores de flujo de claves
- Actualice el estado interno x con la secuencia de n GF (q) primeros valores generados (Q 1 (x), ..., Q n (x))
QUAD es un cifrado de flujo moderno, es decir, utiliza una clave y un valor de inicialización (IV) para producir una secuencia de flujo de claves. También se define una configuración clave e IV que también se basa en un sistema cuadrático multivariante.
Seguridad
La seguridad de la generación de la secuencia de claves de QUAD es probablemente reducible a la intratabilidad conjeturada del problema MQ, es decir, la resolución de un sistema multivariado de ecuaciones cuadráticas. La primera prueba se realizó sobre el campo GF (2) para un cifrado de flujo anticuado (donde la clave es el estado inicial). Más tarde, Berbain y Gilbert lo ampliaron para tener en cuenta el procedimiento de configuración de un cifrado moderno (con una etapa de configuración que deriva el estado inicial de la clave). La seguridad de todo el cifrado como una función pseudoaleatoria puede relacionarse con la intratabilidad conjeturada del problema MQ. Los autores también estudiaron la resistencia del cifrado contra los ataques clásicos.
Parámetros recomendados
Los autores recomiendan utilizar una versión de QUAD con una clave de 80 bits, IV de 80 bits y un estado interno de n = 160 bits. Genera 160 bits de flujo de claves (m = 320) en cada iteración hasta que se hayan producido 2 40 bits de flujo de claves.
En Eurocrypt 2006, se presentaron informes de velocidad para instancias QUAD con estado de 160 bits y bloque de salida en los campos GF (2), GF (16) y GF (256). Estos informes de velocidad fueron parte de un análisis de "Implementaciones eficientes de sistemas cuadráticos multivariados" que fue publicado por Berbain, Billet y Gilbert en SAC 2006. Este análisis (que también cubre varios esquemas de clave pública multivariante, así como el cifrado de flujo QUAD ) estudiaron en parte el impacto de cambiar el tamaño del campo en las actuaciones sin considerar el aspecto de seguridad.
Discusión sobre parámetros
El teorema de seguridad inicial para QUAD es válido solo para el campo GF (2), y los parámetros recomendados no consiguen contradecir la prueba de seguridad. Los autores de QUAD que dieron el teorema de seguridad reconocieron que una ruptura de QUAD en sus parámetros sugeridos no contradice los teoremas de prueba de seguridad cuando propusieron el esquema en Eurocrypt 2006. Sin embargo, parecía que los autores los habían considerado suficientes para proporcionar el nivel de seguridad deseado de aproximadamente 2 80 .
Yang, Chen, Bernstein y Chen estudiaron la seguridad de los diferentes conjuntos de parámetros en el documento "Análisis de Quad" y encontraron algunos de ellos muy inseguros. Su artículo analiza los aspectos teóricos y prácticos de atacar QUAD y de atacar el problema difícil subyacente. Por ejemplo, este documento muestra cómo utilizar XL-Wiedemann para romper la instancia de GF (256) QUAD (256, 20, 20) en aproximadamente 2 66 ciclos de Opteron, y para resolver el problema subyacente en aproximadamente 2 45 ciclos, que fue llevado a cabo con éxito. Sin embargo, según este artículo, se necesitarían alrededor de 2 110 para resolver una instancia de la versión QUAD (2,160,160) recomendada por los autores de QUAD utilizando XL-Wiedemann.
El estudio de Yang et al. destacó el hecho de que los teoremas de seguridad a menudo se basan en reducciones con un factor de holgura, y cuando esto se tiene en cuenta, ninguno de los conjuntos de parámetros de las versiones sugeridas es suficiente para la prueba de seguridad. Una instancia que será probadamente segura sería QUAD (2,320,320), es decir, el doble de ancho de lo propuesto originalmente.
También se puede demostrar un teorema de seguridad para GF (q), aunque con un factor de holgura mayor; esto y extensiones de QUAD para implementaciones más eficientes es propuesto por Liu et al. (consulte la referencia "Proteger los PRNG de mapas polinomiales especializados sobre cualquier F q ").
Referencias
- "QUAD: un cifrado de flujo práctico con seguridad demostrable" (PDF) . Consultado el 18 de marzo de 2008 .
- "Implementaciones eficientes de sistemas cuadráticos multivariados" (PDF) . Consultado el 18 de marzo de 2008 .
- "Sobre la seguridad de cifrados de flujo dependientes IV" (PDF) . Consultado el 18 de marzo de 2008 .
- "Análisis de QUAD" (formato Adobe Acrobat) . 2007-03-03 . Consultado el 5 de febrero de 2008 .
- "Análisis de funciones hash multivariantes" (PDF) .
- "Proteja los PRNG de mapas polinomiales especializados sobre cualquier $ F_q $" (PDF) .