Los ataques de correlación son una clase de ataques criptográficos de texto simple conocido para romper cifrados de flujo cuyos flujos de claves se generan combinando la salida de varios registros de desplazamiento de retroalimentación lineal (LFSR) utilizando una función booleana . Los ataques de correlación explotan una debilidad estadística que surge de la función booleana específica elegida para el flujo de claves. Si bien algunas funciones booleanas son vulnerables a los ataques de correlación, los cifrados de flujo generados utilizando dichas funciones no son inherentemente inseguros.
Los ataques de correlación se hacen posibles cuando existe una correlación significativa entre el estado de salida de un LFSR individual en el generador de flujo de claves y la salida de la función booleana que combina los estados de salida de todos los LFSR. Estos ataques se emplean en combinación con el conocimiento parcial del flujo de claves, que se deriva del conocimiento parcial del texto sin formato. Luego, los dos se comparan utilizando una puerta lógica XOR . Esta vulnerabilidad permite a un atacante forzar la clave para el LFSR individual y el resto del sistema por separado. Por ejemplo, en un generador de flujo de claves donde se combinan cuatro LFSR de 8 bits para producir el flujo de claves, y si uno de los registros está correlacionado con la salida de la función booleana, se hace posible forzarlo primero, seguido de los tres LFSR restantes. Como resultado, la complejidad total del ataque se convierte en 2 8 + 2 24 .
En comparación con el costo de lanzar un ataque de fuerza bruta en todo el sistema, con una complejidad de 2,32 , esto representa un factor de ahorro de esfuerzo de ataque de poco menos de 256. Si se correlaciona un segundo registro con la función, el proceso puede repetirse y disminuir la complejidad del ataque a 2,8 + 2,8 + 2,16 para un factor de ahorro de esfuerzo de poco menos de 65028.
Un ejemplo es el generador Geffe, que consta de tres LFSR: LFSR-1, LFSR-2 y LFSR-3. Sean estos registros denotados como: , , y , respectivamente. Entonces, la función booleana que combina los tres registros para proporcionar la salida del generador está dada por (es decir, ( AND ) XOR (NOT AND )). Hay 2 3 = 8 valores posibles para las salidas de los tres registros, y el valor de esta función de combinación para cada uno de ellos se muestra en la siguiente tabla:
Considere la salida del tercer registro, . La tabla anterior muestra que de las 8 salidas posibles de , 6 son iguales al valor correspondiente de la salida del generador, . En el 75% de todos los casos posibles, . Por lo tanto, LFSR-3 está "correlacionada" con el generador. Esta es una debilidad que se puede explotar de la siguiente manera:
Se puede realizar una interceptación en el texto cifrado de un texto simple que ha sido cifrado por un cifrador de flujo utilizando un generador Geffe como su generador de flujo de claves, es decir , para , donde es la salida de LFSR-1 en el momento , etc. También es posible que parte del texto simple, por ejemplo , los primeros 32 bits del texto simple (que corresponden a 4 caracteres ASCII de texto). Esto no es completamente improbable considerando que el texto simple es un archivo XML válido, por ejemplo, los primeros 4 caracteres ASCII deben ser "<xml". De manera similar, muchos formatos de archivo o protocolos de red tienen encabezados o pies de página muy estándar. Dado el interceptado y nuestro conocido/adivino , podemos encontrar fácilmente para mediante XOR-ing los dos juntos. Esto hace que los 32 bits consecutivos de la salida del generador sean fáciles de determinar.
Esto permite una búsqueda de fuerza bruta del espacio de claves posibles (valores iniciales) para LFSR-3 (asumiendo que conocemos los bits utilizados de LFSR-3, una suposición que está en línea con el principio de Kerckhoff ). Para cualquier clave dada en el espacio de claves, podemos generar rápidamente los primeros 32 bits de la salida de LFSR-3 y compararlos con nuestros 32 bits recuperados de la salida de todo el generador. Debido a que hemos establecido anteriormente que hay una correlación del 75% entre la salida de LFSR-3 y el generador, sabemos que hemos adivinado correctamente la clave para LFSR-3 si aproximadamente 24 de los primeros 32 bits de la salida de LFSR-3 coincidirán con los bits correspondientes de la salida del generador. Si hemos adivinado incorrectamente, debemos esperar que coincidan aproximadamente la mitad, o 16, de los primeros 32 bits de estas dos secuencias. Por lo tanto, podemos recuperar la clave para LFSR-3 independientemente de las claves de LFSR-1 y LFSR-2. En esta etapa, hemos reducido el problema de forzar un sistema de 3 LFSR al problema de forzar un solo LFSR y luego un sistema de 2 LFSR. La cantidad de esfuerzo ahorrado aquí depende de la longitud de los LFSR. Para valores realistas, es un ahorro muy sustancial y puede hacer que los ataques de fuerza bruta sean muy prácticos.
Observe en la tabla anterior que también concuerda con la salida del generador 6 veces de 8, nuevamente una correlación del 75% entre y la salida del generador. Podemos comenzar un ataque de fuerza bruta contra LFSR-2 independientemente de las claves de LFSR-1 y LFSR-3, dejando solo LFSR-1 intacto. Por lo tanto, podemos romper el generador Geffe con todo el esfuerzo necesario para forzar brutamente 3 LFSR completamente independientes. Esto significa que el generador Geffe es un generador muy débil y nunca debe usarse para generar flujos de claves de cifrado de flujo.
Tenga en cuenta que la tabla anterior coincide con la salida del generador 4 veces de 8, lo que representa una correlación del 50 %. No podemos usar esto para forzar la ejecución de LFSR-1 independientemente de las demás: la clave correcta generará una salida que coincida con la salida del generador el 50 % de las veces, pero, en promedio, también lo hará una clave incorrecta. Esto representa la situación ideal desde una perspectiva de seguridad: la función de combinación debe elegirse de modo que la correlación entre cada variable y la salida de la función de combinación sea lo más cercana posible al 50 %. En la práctica, puede resultar difícil encontrar una función que logre esto sin sacrificar otros criterios de diseño, por ejemplo, la duración del período, por lo que puede ser necesario llegar a un compromiso.
Si bien el ejemplo anterior ilustra bien los conceptos relativamente simples detrás de los ataques de correlación, tal vez simplifique la explicación de cómo se lleva a cabo con precisión el ataque de fuerza bruta a los LFSR individuales. Las claves incorrectamente adivinadas generarán una salida LFSR que concuerde con la salida del generador aproximadamente el 50% del tiempo porque, dadas dos secuencias de bits aleatorias de una longitud dada, la probabilidad de concordancia entre las secuencias en cualquier bit en particular es 0,5. Sin embargo, es posible que claves incorrectas individuales específicas generen una salida LFSR que concuerde con la salida del generador con más o menos frecuencia que exactamente el 50% del tiempo. Esto es particularmente relevante en el caso de los LFSR cuya correlación con el generador no es especialmente fuerte; para correlaciones lo suficientemente pequeñas, ciertamente no está fuera del ámbito de la posibilidad que una clave incorrectamente adivinada también conduzca a una salida LFSR que concuerde con el número deseado de bits de la salida del generador. Por lo tanto, puede que no sea posible identificar la clave única para ese LFSR. Sin embargo, es posible identificar varias claves potenciales, lo que sigue siendo una importante violación de la seguridad del cifrado. Además, dado un megabyte de texto simple conocido, la situación sería sustancialmente diferente. Una clave incorrecta puede generar una salida LFSR que coincida con más de 512 kilobytes de la salida del generador, pero no es probable que genere una salida que coincida con hasta 768 kilobytes de la salida del generador como lo haría una clave adivinada correctamente. Como regla, cuanto más débil sea la correlación entre un registro individual y la salida del generador, más texto simple conocido se requiere para encontrar la clave de ese registro con un alto grado de confianza. Las estimaciones de la longitud del texto simple conocido requerida para una correlación dada se pueden calcular utilizando la distribución binomial .
Las correlaciones que se explotaron en el ataque de ejemplo al generador Geffe son ejemplos de lo que se denominan correlaciones de primer orden : son correlaciones entre el valor de la salida del generador y un LFSR individual. Es posible definir correlaciones de orden superior además de estas. Por ejemplo, puede ser posible que, si bien una función booleana dada no tenga correlaciones fuertes con ninguno de los registros individuales que combina, pueda existir una correlación significativa entre alguna función booleana de dos de los registros, por ejemplo, . Este sería un ejemplo de una correlación de segundo orden. Las correlaciones de tercer orden y superiores se pueden definir de esta manera.
Los ataques de correlación de orden superior pueden ser más poderosos que los ataques de correlación de orden único; sin embargo, este efecto está sujeto a una "ley de rendimientos limitantes". La tabla siguiente muestra una medida del costo computacional para varios ataques a un generador de flujo de claves que consta de ocho LFSR de 8 bits combinados por una única función booleana. Comprender el cálculo del costo es relativamente sencillo: el término más a la izquierda de la suma representa el tamaño del espacio de claves para los generadores correlacionados, y el término más a la derecha representa el tamaño del espacio de claves para los generadores restantes.
Si bien las correlaciones de orden superior conducen a ataques más poderosos, también son más difíciles de encontrar, ya que el espacio de funciones booleanas disponibles para correlacionar con la salida del generador aumenta a medida que aumenta el número de argumentos de la función.
Se dice que una función booleana de n variables es " inmune a la correlación de orden m ", o que tiene " inmunidad a la correlación de orden m " para algún entero m , si no existe correlación significativa entre la salida de la función y cualquier función booleana de m de sus entradas. Por ejemplo, una función booleana que no tiene correlaciones de primer o segundo orden, pero que tiene una correlación de tercer orden, exhibe inmunidad a la correlación de segundo orden. Obviamente, una mayor inmunidad a la correlación hace que una función sea más adecuada para su uso en un generador de flujo de claves (aunque esto no es lo único que se debe considerar).
Siegenthaler demostró que la inmunidad de correlación m de una función booleana de grado algebraico d de n variables satisface ; para un conjunto dado de variables de entrada, esto significa que un grado algebraico alto restringirá la inmunidad de correlación máxima posible. Además, si la función está balanceada entonces . [1]
De ello se desprende que es imposible que una función de n variables sea inmune a la correlación de orden n. Esto también se desprende del hecho de que cualquier función de este tipo puede escribirse utilizando una base Reed-Muller como una combinación de XOR de las funciones de entrada.
Dada la probable extrema gravedad del impacto de un ataque de correlación en la seguridad de un cifrado de flujo, debería ser esencial probar una función de combinación booleana candidata para la inmunidad a la correlación antes de decidir usarla en un cifrado de flujo. Sin embargo, es importante señalar que una alta inmunidad a la correlación es una condición necesaria, pero no suficiente , para que una función booleana sea apropiada para su uso en un generador de flujo de claves. Hay otras cuestiones a considerar, por ejemplo, si la función está equilibrada o no , si genera tantos 1 como 0 cuando se consideran todas las entradas posibles.
Se han llevado a cabo investigaciones sobre métodos para generar fácilmente funciones booleanas de un tamaño determinado que garanticen al menos un orden particular de inmunidad a la correlación. Esta investigación ha descubierto vínculos entre las funciones booleanas inmunes a la correlación y los códigos de corrección de errores . [2]
