Los ataques de correlación son una clase de ataques criptográficos de texto plano 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 ataques de correlación, los cifrados de flujo generados mediante dichas funciones no son inherentemente inseguros.
Los ataques de correlación se vuelven 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 un 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 aplicar fuerza bruta a 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, es posible aplicar fuerza bruta primero, seguido de los tres LFSR restantes. Como resultado, la complejidad total del ataque pasa a ser 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 se redujo 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. Denotemos estos registros como: , y , respectivamente. Luego, la función booleana que combina los tres registros para proporcionar la salida del generador viene dada por (es decir ( Y ) XOR (NOT Y )). Hay 2 3 = 8 valores posibles para las salidas de los tres registros, y el valor de esta función combinadora 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 tanto, LFSR-3 está "correlacionado" con el generador. Esta es una debilidad que puede explotarse de la siguiente manera:
Se puede realizar una interceptación del texto cifrado de un texto sin formato que ha sido cifrado mediante un cifrado de flujo utilizando un generador Geffe como generador de flujo de claves, es decir, for , dónde está la salida de LFSR-1 en el momento , etc. También es posible que parte del texto sin formato, por ejemplo , los primeros 32 bits del texto sin formato (correspondientes a 4 caracteres ASCII de texto). Esto no es del todo improbable considerando que el texto sin formato es un archivo XML válido; por ejemplo, los primeros 4 caracteres ASCII deben ser "<xml". De manera similar, muchos formatos de archivos o protocolos de red tienen encabezados o pies de página muy estándar. Dado lo interceptado y lo conocido/adivinado , podemos encontrarlo fácilmente aplicando XOR a 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 por fuerza bruta del espacio de posibles claves (valores iniciales) para LFSR-3 (asumiendo que conocemos los bits intervenidos de LFSR-3, una suposición que está en línea con el principio de Kerckhoffs ). 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 completa del generador. Debido a que hemos establecido anteriormente que existe 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 coinciden. con los bits correspondientes de la salida del generador. Si hemos adivinado incorrectamente, deberíamos esperar que aproximadamente la mitad, o 16, de los primeros 32 bits de estas dos secuencias coincidan. Así podremos 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 duración 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 de cada 8 veces, 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 tanto esfuerzo como el necesario para forzar 3 LFSR completamente independientes. Esto significa que el generador Geffe es un generador muy débil y nunca debe usarse para generar secuencias de claves cifradas.
Observe en la tabla anterior que concuerda con la salida del generador 4 de 8 veces: una correlación del 50%. No podemos usar esto para forzar bruscamente LFSR-1 independientemente de los demás: la clave correcta producirá una salida que concuerda 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 acuerdo.
Si bien el ejemplo anterior ilustra bien los conceptos relativamente simples detrás de los ataques de correlación, quizás simplifique la explicación de cómo se produce precisamente la fuerza bruta de los LFSR individuales. Las claves adivinadas incorrectamente generarán una salida LFSR que concuerda con la salida del generador aproximadamente el 50% de las veces porque, dadas dos secuencias de bits aleatorias de una longitud determinada, la probabilidad de concordancia entre las secuencias en cualquier bit en particular es 0,5. Sin embargo, claves individuales incorrectas específicas pueden generar una salida LFSR que coincida con la salida del generador con más o menos frecuencia de exactamente el 50% de las veces. Esto es particularmente notable 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 de que una clave adivinada incorrectamente 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 de ese LFSR. Sin embargo, es posible identificar varias claves potenciales, lo que sigue siendo una violación importante de la seguridad del cifrado. Además, dado un megabyte de texto plano conocido, la situación sería sustancialmente diferente. Una clave incorrecta puede generar una salida LFSR que concuerde con más de 512 kilobytes de la salida del generador, pero no es probable que genere una salida que concuerde hasta con 768 kilobytes de la salida del generador como lo haría una clave adivinada correctamente. Como regla general, cuanto más débil sea la correlación entre un registro individual y la salida del generador, más texto plano conocido se necesitará para encontrar la clave de ese registro con un alto grado de confianza. Las estimaciones de la longitud del texto plano conocido necesaria para una correlación determinada se pueden calcular utilizando la distribución binomial .
Las correlaciones que se explotaron en el ataque de ejemplo al generador Geoff son ejemplos de lo que se llaman correlaciones de primer orden : son correlaciones entre el valor de la salida del generador y un LFSR individual. Además de éstas, es posible definir correlaciones de orden superior. Por ejemplo, es posible que, si bien una función booleana determinada no tenga fuertes correlaciones 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 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 límite". La siguiente tabla muestra una medida del costo computacional de 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 clave para los generadores correlacionados, y el término más a la derecha representa el tamaño del espacio clave 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 lo hace 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 número entero m , si no existe una 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 sí 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 debe considerarse).
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 máxima inmunidad de correlación posible. Además, si la función está equilibrada, entonces . [1]
De ello se deduce 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 se puede escribir utilizando una base de Reed-Muller como una combinación de XOR de las funciones de entrada.
Dada la probable gravedad extrema 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 determinar 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 o aproximadamente tantos unos como ceros cuando se consideran todas las entradas posibles.
Se han realizado investigaciones sobre métodos para generar fácilmente funciones booleanas de un tamaño determinado que garanticen tener al menos algún orden particular de inmunidad de 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]
