Un ataque de compensación de tiempo / memoria / datos es un tipo de ataque criptográfico donde un atacante intenta lograr una situación similar a la compensación de espacio-tiempo pero con el parámetro adicional de datos , que representa la cantidad de datos disponibles para el atacante. Un atacante equilibra o reduce uno o dos de esos parámetros a favor del otro o dos. Este tipo de ataque es muy difícil, por lo que la mayoría de los sistemas de cifrado y cifrado en uso no fueron diseñados para resistirlo. [ cita requerida ]
Historia
Los ataques de compensación en criptosistemas simétricos se remontan a 1980, cuando Martin Hellman sugirió un método de compensación de tiempo / memoria para romper los cifrados de bloque con posibles claves en el tiempo y memoria relacionado por la curva de compensación dónde . [1] Más tarde, en 1995, Babbage y Golic idearon un ataque de compensación diferente para cifrados de flujo con un nuevo límite tal que por dónde son los datos de salida disponibles para el criptoanalista en tiempo real. [2] [3]
Mecánica de ataque
Este ataque es una versión especial del ataque de compensación de tiempo / memoria criptoanalítico general, que tiene dos fases principales:
- Procesamiento previo:
durante esta fase, el atacante explora la estructura del criptosistema y se le permite registrar sus hallazgos en tablas grandes. Esto puede llevar mucho tiempo. - Tiempo real:
en esta fase, al criptoanalista se le otorgan datos reales obtenidos de una clave desconocida específica. Luego intentan usar estos datos con la tabla precalculada de la fase de preprocesamiento para encontrar la clave particular en el menor tiempo posible.
Cualquier ataque de compensación de tiempo / memoria / datos tiene los siguientes parámetros:
- tamaño del espacio de búsqueda
- tiempo necesario para la fase de preprocesamiento
- tiempo requerido para la fase de tiempo real
- cantidad de memoria disponible para el atacante
- cantidad de datos en tiempo real disponibles para el atacante
El ataque de Hellman a los cifrados de bloque
Para cifrados de bloque, deje ser el número total de claves posibles y también suponga que el número de textos en claro y cifrados posibles es . También permita que los datos proporcionados sean un solo bloque de texto cifrado de una contraparte de texto sin formato específico. Si consideramos el mapeo de la clave al texto cifrado como una función de permutación aleatoria sobre un espacio de puntos, y si esta función es invertible; necesitamos encontrar la inversa de esta función. La técnica de Hellman para invertir esta función:
- Durante la etapa de preprocesamiento
- Trate de cubrir el espacio de puntos por un matriz rectangular que se construye iterando la función en puntos de partida aleatorios en por veces. Los puntos de inicio son la columna más a la izquierda en la matriz y los puntos finales son la columna más a la derecha. Luego, almacene los pares de puntos de inicio y finalización en orden creciente de valores de puntos finales.
- Ahora, solo una matriz no podrá cubrir la totalidad espacio. Pero si agregamos más filas a la matriz, terminaremos con una matriz enorme que incluye puntos recuperados más de una vez. Entonces, encontramos el valor crítico de en el que la matriz contiene exactamente diferentes puntos. Considere el primero Las rutas desde los puntos de inicio a los puntos finales son todas disjuntas con puntos, de modo que la siguiente ruta que tiene al menos un punto en común con una de esas rutas anteriores e incluye exactamente puntos. Esos dos conjuntos de y los puntos están separados por la paradoja del cumpleaños si nos aseguramos de que . Logramos esto aplicando la regla de detención de la matriz : .
- Sin embargo, un matriz con cubre una porción de todo el espacio. Para generar para cubrir todo el espacio, usamos una variante de definido: y es una simple manipulación de salida, como el reordenamiento de bits de [1] (consulte el documento original para obtener más detalles). Y se puede ver que el tiempo total de preprocesamiento es . También ya que solo necesitamos almacenar los pares de puntos de inicio y finalización y tenemos matrices cada una de pares.
- Durante la fase de tiempo real
- El cálculo total requerido para encontrar es porque tenemos que hacer intentos de inversión, ya que es probable que esté cubierto por una matriz y cada uno de los intentos toma evaluaciones de algunos . La curva de compensación óptima se obtiene utilizando la regla de parada de la matriz. y obtenemos y elección de y depende del costo de cada recurso.
Según Hellman, si el cifrado de bloque en cuestión tiene la propiedad de que el mapeo de su clave al texto cifrado es una función de permutación aleatoria sobre un espacio de puntos, y si esto es invertible, la relación de compensación se vuelve mucho mejor: .
Ataque de Babbage y Golic en cifrados de flujo
Para cifrados de flujo, se especifica por el número de estados internos del generador de bits, probablemente diferente del número de claves. es el recuento de los primeros bits pseudoaleatorios producidos por el generador. Finalmente, el objetivo del atacante es encontrar uno de los estados internos reales del generador de bits para poder ejecutar el generador a partir de este punto para generar el resto de la clave. Asocia cada uno de los posibles estados internos del generador de bits con la cadena correspondiente que consta de la primera bits obtenidos al ejecutar el generador desde ese estado mediante el mapeo de los estados para generar prefijos . Este mapeo anterior se considera una función aleatoria sobre elpuntos de espacio común. Para invertir esta función, un atacante establece lo siguiente.
- Durante la fase de preprocesamiento, elija aleatorio estados y calcular sus correspondientes prefijos de salida.
- Almacenar los pares en orden creciente de en una mesa grande.
- Durante la fase de tiempo real, tienes bits generados. Calcular de todos ellos posibles combinaciones de de bits consecutivos con longitud .
- Buscar cada uno en la tabla generada que lleva el tiempo de registro.
- Si tienes un golpe, este corresponde a un estado interno del generador de bits desde el cual puede ejecutar el generador para obtener el resto de la clave.
- Por la paradoja del cumpleaños , se le garantiza que dos subconjuntos de un espacio con los puntos tienen una intersección si el producto de sus tamaños es mayor que .
Este resultado del ataque de cumpleaños da la condición con tiempo de ataque y tiempo de preprocesamiento que es solo un punto particular en la curva de compensación . Podemos generalizar esta relación si ignoramos algunos de los datos disponibles en tiempo real y somos capaces de reducir de a y la curva de compensación general eventualmente se convierte en con y .
El ataque de Shamir y Biryukov a los cifrados de flujo
Esta nueva idea introducida en 2000 combina los ataques de compensación de Hellman y Babbage-and-Golic para lograr una nueva curva de compensación con mejores límites para el criptoanálisis de cifrado de flujo. [4] La técnica de cifrado de bloques de Hellman se puede aplicar a un cifrado de flujo utilizando la misma idea de cubrir el espacio de puntos a través de matrices obtenidas a partir de múltiples variantes de la función que es el mapeo de estados internos a prefijos de salida. Recuerde que este ataque de compensación en el cifrado de flujo es exitoso si alguno de los Los prefijos de salida se encuentran en cualquiera de las matrices que cubren . Esto reduce el número de puntos cubiertos por las matrices de a puntos. Esto se hace reduciendo el número de matrices de a mientras se mantiene tan grande como sea posible (pero esto requiere tener al menos una mesa). Para este nuevo ataque, tenemos porque redujimos el número de matrices a y lo mismo para el tiempo de preprocesamiento . El tiempo real requerido para el ataque es que es el producto del número de matrices, la duración de cada iteración y el número de puntos de datos disponibles en el momento del ataque.
Finalmente, usamos nuevamente la regla de detención de la matriz para obtener la curva de compensación por (porque ).
Ataques a cifrados de flujo con baja resistencia al muestreo
Este ataque, inventado por Biryukov , Shamir y Wagner , se basa en una característica específica de algunos cifrados de flujo: que el generador de bits experimenta solo unos pocos cambios en su estado interno antes de producir el siguiente bit de salida. [5] Por lo tanto, podemos enumerar los estados especiales que generan bits cero para valores pequeños de a bajo costo. Pero al forzar un gran número de bits de salida a tomar valores específicos, este proceso de enumeración se vuelve muy costoso y difícil. Ahora, podemos definir la resistencia de muestreo de un cifrado de flujo como con el valor máximo que hace factible tal enumeración.
Deje que el cifrado de flujo sea de afirma que cada uno tiene un nombre completo debits y un nombre de salida correspondiente que es el primerobits en la secuencia de salida de bits. Si este cifrado de flujo tiene resistencia al muestreo, entonces una enumeración eficiente puede usar un nombre corto debits para definir los estados especiales del generador. Cada estado especial con nombre corto tiene un nombre de salida corto correspondiente de bits que es la secuencia de salida del estado especial después de eliminar el primer bits iniciales. Ahora, podemos definir un nuevo mapeo en un espacio reducido depuntos y este mapeo es equivalente al mapeo original. Si dejamos, se garantiza que los datos en tiempo real disponibles para el atacante tendrán al menos una salida de esos estados especiales. De lo contrario, relajamos la definición de estados especiales para incluir más puntos. Si sustituimos por por y por en el nuevo ataque de compensación de tiempo / memoria / datos de Shamir y Biryukov, obtenemos la misma curva de compensación pero con . En realidad, esto es una mejora, ya que podríamos relajar el límite inferior en desde puede ser pequeño hasta lo que significa que nuestro ataque se puede hacer más rápido. Esta técnica reduce el número de costosas operaciones de acceso al disco de a ya que accederemos solo al especial puntos, y acelera el ataque debido al número reducido de costosas operaciones de disco.
Referencias
- ^ a b Hellman, ME, "Un intercambio criptoanalítico entre tiempo y memoria" , Teoría de la información, Transacciones IEEE, vol.26, no.4, pp.401.406, julio de 1980
- ^ Babbage, SH, "Ataques de" búsqueda exhaustiva "mejorados en cifrados de flujo" , Seguridad y detección, 1995., Convención europea sobre, vol., No., Pp.161-166, 16-18 de mayo de 1995
- ^ Golic, J., "Criptoanálisis del supuesto cifrado de flujo A5" Notas de la conferencia en informática, Avances en criptología - EUROCRYPT '97, LNCS 1233, pp.239-255, Springer-Verlag 1997
- ^ Biryukov A., Shamir A., "Compensaciones de tiempo / memoria / datos criptoanalíticos para cifrados de flujo" Notas de la conferencia en informática, Avances en criptología - ASIACRYPT 2000, LNCS 1976, pp.1-13, Springer-Verlag Berlin Heidelberg 2000
- ^ Biryukov A., Shamir A., Wagner D., "Criptoanálisis en tiempo real de A5 / 1 en una PC" Cifrado de software rápido 2000, páginas 1 a 18, Springer-Verlag 2000