Sobre la probabilidad de romper cifrados de flujo utilizando el método de superposición .
Sobre la probabilidad de descifrar cifrados de flujo utilizando el método de superposición
Sea un aro o círculo cuya circunferencia sea L centímetros. Una tira de papel de longitud l1 está pegada a este aro., centímetros. Después de esto, se gira el aro en un ángulo aleatorio y se pega otra tira de papel de l2 centímetros de largo. Determine la probabilidad de que las moscas superpongan tiras de papel unas sobre otras en más de s centímetros.
La solución a este problema, a primera vista “infantil”, contiene respuestas a preguntas serias que surgen al crear, piratear y evaluar la solidez de los cifrados de flujo.
Definiciones y planteamiento del problema
El principio del cifrado de flujo es aplicar un código cifrado a datos simples. Se entiende por gamma de un cifrado una secuencia de bits aleatorios {Гi} generados por el generador R(k) según algún algoritmo (en este caso no importa si el generador funciona de forma verdaderamente aleatoria o pseudoaleatoria R(k)). El parámetro del generador k se llama clave; determina el valor inicial del generador y se selecciona aleatoriamente de un conjunto de claves suficientemente grande K. Conociendo el algoritmo del generador y su estado inicial (clave), puede calcular fácilmente la gamma de cifrado.
Si la profundidad de bits es R(k)es n bits, entonces el período máximo de la secuencia generada por dicho generador es 2n-1 bits, después del cual se repite la secuencia de bits gamma [ 1 ].
Denotemos por L = 2n-1 la duración del ciclo de dicha secuencia.
Es inaceptable que cualquier cifrado de flujo utilice la misma clave dos veces, ya que no es difícil extraer información cifrada de dos textos cifrados utilizando la misma gamma, incluso sin conocer la clave de cifrado. El método de descifrado correspondiente se denomina método de superposición. Sin embargo, incluso si se utilizan dos claves diferentes (aleatorias) para el cifrado, no se excluye la superposición (intersección) de los segmentos de la gama, lo que también implica la posibilidad de leer la información cifrada.
Obviamente, para garantizar un alto grado de seguridad de un cifrado, es necesario que la probabilidad de intersección de dos textos cifrados sea extremadamente pequeña, por lo que el estudio de la solidez de los cifrados de flujo incluye el estudio de la probabilidad de superposición de los segmentos gamma obtenidos; con claves aleatorias.
Descifrado de mensajes mediante el método de superposición
Describamos brevemente el principio de descifrado de información mediante el método de superposición.
Que haya dos criptogramas (texto cifrado 1 y texto cifrado 2), cifrados en la computadora.
1. Supongamos que en este criptograma se cifró alguna Palabra 1 desde la primera posición. De la relación texto cifrado = texto plano + gamma, dada la codificación ASCII, calculamos la gamma probable Probablemente. Eliminamos el segmento calculado de la gama Probablemente del texto cifrado 2 de la primera posición y verificamos el texto resultante en el diccionario para ver si corresponde a alguna palabra o parte de una palabra. Si no tiene éxito, elimine la gamma Probablemente de la segunda posición del texto cifrado 2, luego de la tercera, etc. hasta el final del texto cifrado 2.
2. Si el paso anterior falla, asumimos la aparición de la Palabra 1desde la segunda posición del texto cifrado 1 y ejecutamos el procedimiento descrito en el párrafo 1. Si no tiene éxito, asumimos la aparición de la Palabra 1 desde la tercera posición del texto cifrado 1, etc. hasta el final del texto cifrado 1.
3. Si no se obtuvo un resultado semántico en la etapa anterior, seleccione Palabra 2 del diccionario.y repetimos los pasos 1 y 2. Repetimos este proceso hasta que nos quedemos sin palabras posibles (se acaba el diccionario). Evidentemente, para optimizar la velocidad del algoritmo de descifrado, es aconsejable ordenar las palabras del diccionario no alfabéticamente, sino por frecuencia de uso en los textos de correspondencia: las más utilizadas se encuentran al principio, las menos utilizadas al final. fin. Para ello, el criptoanalista debe estudiar primero las características de la correspondencia cifrada de su oponente.
4. Si como resultado del proceso descrito no salió nada que valiera la pena, es decir, como resultado de ejecutar los pasos 1, 2,3, no se puede extraer el texto semántico, entonces estos criptogramas no tienen intersecciones. En este caso, puede detener el criptoanálisis o seleccionar el siguiente par de criptogramas (textos cifrados). Para n criptogramas, el número de muestras emparejadas posibles se expresa mediante el «número de combinaciones»; Si aparece un texto semántico en cualquier etapa del criptoanálisis, puede continuar con el criptoanálisis de la parte restante del texto de la manera descrita anteriormente. Por lo general, el conocimiento de las palabras descifradas ayuda a adivinar la siguiente palabra que tiene un significado adecuado, así como a seleccionar palabras, parte de una palabra y espacio, frase o grupo de palabras incluidas en la parte no descifrada del texto. También puede intentar analizar un segmento de la gamma resultante Probablemente para descubrir el algoritmo de funcionamiento del generador R(k) — determinar analíticamente la ley de formación de pseudo -bits aleatorios y así descifrar el resto del mensaje. p>
Probabilidad
Dado que las sesiones de comunicación suelen tener aproximadamente la misma duración (día, semana, mes), todos los segmentos gamma tienen la misma duración, lo que denotamos con l. Denotaremos por s la cantidad máxima permitida de superposición entre dos segmentos de la gama, es decir, ese volumen de texto cifrado, cuyo descifrado no implica la revelación de secretos.
Por ejemplo, dicho valor en un idioma de correspondencia puede sugerir la longitud promedio de una palabra, varias palabras o la longitud promedio de una frase.
En ruso, la longitud media de una palabra es de 7 a 8 caracteres, normalmente seguidos de un espacio. Entonces s es ~ 8 o 9 bits. Obviamente, establecer el valor de este parámetro requiere una investigación lingüística especial para cada idioma en el que se realiza la correspondencia cifrada.
En el código ASCII, un carácter de mensaje está codificado en 8 bits, por lo tanto, la superposición permitida entre dos textos cifrados en una computadora es de 64 a 72 bits. En el código MTK-2, un signo de mensaje está codificado con cinco bits, por lo que el valor de superposición permitido para mensajes telegráficos será de 40 a 45 bits. Incluso puedes aumentar ligeramente este valor en el primer caso en 7 y en el segundo en 4 bits, de modo que el último símbolo quede incompleto.
En la notación indicada, la probabilidad de que dos copias de la gamma formada por dos claves aleatorias, se cruzarán en más de s bits, es: El número máximo de gammas de sesión para el criptosistema en estudio es L/(l — 2s). Para lograr un alto grado de seguridad de un cifrado de flujo, el número L/(l — 2s) debe ser lo suficientemente grande.
La fórmula (1) no refleja dos puntos importantes. En primer lugar, al derivar esta fórmula, debemos tener en cuenta que normalmente el enemigo no intercepta todos los mensajes cifrados. Por lo tanto, al calcular la probabilidad de descifrado, es necesario tener en cuenta la probabilidad de que el enemigo intercepte los mensajes р. En segundo lugar, la fórmula (1) es correcta para calcular la probabilidad de superposición de sólo dos mensajes. Sin embargo, es lógico suponer que durante el uso de este cifrado (llamémoslo m) se cifrarán más de dos mensajes.
Teniendo en cuenta lo anterior, la probabilidad requerida debe calcularse de acuerdo con la siguiente fórmula: Puede calcular la cantidad aproximada de mensajes cifrados durante la «vida útil» del cifrado de la siguiente manera. Supongamos que se producen N copias de herramientas de cifrado, cuya “vida útil” es de M años. Entonces, si designamos el periodo de validez de la clave de sesión (en segundos) como Tk, durante la vida útil del equipo en las claves de sesión, m = N*M*(C0/Tk ) se generarán piezas de la gama, donde C0=31.558.153 es el número de segundos en un año. El parámetro m es inversamente proporcional al período de validez de la clave. La duración de la escala de la sesión l también depende de Tk. Si se denota por Vla tasa de generación de gamma por el equipo de cifrado, entonces l = Va*Tk
Por lo tanto, la fórmula (2) se puede reescribir de la siguiente manera: De la expresión (3) puede derivar la fórmula para el período de validez de la clave de sesión Tk si configura el resto parámetros del criptosistema (P, N, M , L, s, Va, p). En particular, para ello es necesario establecer el valor numérico de la probabilidad P, garantizando que la fuerza de los cifrados de flujo supera la capacidad del enemigo para descifrarlos.
En este caso, son posibles dos enfoques:
A. La fuerza de la cadena está determinada por la fuerza del eslabón más débil, por lo tanto, la probabilidad P no debe exceder la probabilidad de encontrar una clave aleatoria para ella, que idealmente es 1/K, donde K — el poder del conjunto de claves.
B. Puede utilizar otros tipos de cifrados como base de comparación. Si requerimos que la fuerza de los cifrados de flujo no sea inferior a la fuerza de los cifrados de bloque, entonces desde aquí podemos obtener valores numéricos de probabilidad P: P = 10-17 (DES), P = 10-38 (RC4) , P = 10-77 (GOST).
Obviamente, a medida que el enemigo acumule textos cifrados, aumentará la probabilidad de superposición. Este proceso de acumulación de segmentos de criptograma refleja el proceso de «envejecimiento» de la herramienta de cifrado, y al alcanzar un cierto valor crítico, aparentemente es necesario planear cambiar el cifrado o realizar cambios significativos en el algoritmo de su funcionamiento. Es necesario tener en cuenta los recursos informáticos del enemigo, que puede destinar a descifrar cifrados.
Recomendaciones
La fórmula (2) te permite analizar los parámetros del algoritmo de cifrado L , l (Tk, Va), s, m (N, M, Tk), p, del cual depende la solidez del cifrado de flujo, y dar recomendaciones para aumentar la solidez de los sistemas de cifrado de este tipo.
Por lo tanto, para aumentar la solidez de un cifrado de flujo, están disponibles las siguientes opciones.
Disminuya el parámetro р. Reducir este parámetro significa que es necesario hacer más difícil para el enemigo interceptar información cifrada. A pesar de que la información está cifrada y, como podría pensarse, segura, su interceptación por parte del enemigo es peligrosa con una probabilidad p y debe evitarse.
Agrandar L. Dado que L = 2n, para aumentar L es necesario aumentar el ancho de bits del generador R(k), lo cual es similar a reemplazar el cifrado.
Para aumentar la seguridad criptográfica del cifrado, puede, por ejemplo, utilizar una combinación de varios generadores diferentes (R = R1+R2+R3+…) con diferentes períodos. En este caso, la duración total del período es igual al producto de la duración de los períodos de los generadores individuales. Para complicar el trabajo del criptoanalista, no está de más idear una combinación más compleja de diferentes generadores.
Dado que Tk suele ser un día, una semana, un mes y la velocidad del equipo es fijo, entonces a partir de la relación L/(l-2s)puede determinar el valor mínimo de L, lo que dará el valor mínimo de la profundidad de bits R(k). En la práctica, esta relación para aumentar la fuerza del cifrado prescribe aumentar L, en igualdad de condiciones.
Disminuir l. Dado que l = Tk*Va, entonces disminuye lsignifica reducir el período de validez de la clave de sesión o reducir la velocidad de salida gamma en el canal de comunicación. Sin embargo, reducir el período de validez de la clave de sesión conduce a un aumento en el número de sesiones de comunicación m, lo que conduce a un aumento en la probabilidad de superposiciones. Por lo tanto, usar este parámetro es inútil.
Disminuye m. Dado que m = N*M*(C0/Tk), esto significa reducir la cantidad de dispositivos que implementan este cifrado (N), o reducir la vida útil de esta herramienta de cifrado (M).
La relación (3) también significa que la seguridad de la información de uno de los usuarios del cifrado está determinada por el número de otros suscriptores que utilizan un cifrado similar y la intensidad de su correspondencia cifrada.
Por lo tanto, el fabricante de cifrado debe calcular el límite en la cantidad de copias de herramientas criptográficas que puede vender a sus clientes sin comprometer la solidez, así como el límite en la cantidad de clientes que utilizan un cifrado determinado. El fabricante está obligado a advertir al consumidor con antelación sobre la vida útil máxima de este tipo de cifrado, tras la cual deberá ser sustituido. El consumidor debe estar seguro de que el fabricante, por motivos de beneficio comercial, en ningún caso violará estas restricciones. Es razonable exigir garantías escritas y cálculos teóricos al respecto.
Esta observación confirma una vez más el hecho de que una gran cantidad de claves de un cifrado no garantiza su solidez. Por ejemplo, la potencia de un cifrado de flujo con cualquier longitud de clave se puede reducir tanto como se desee aumentando el número de superposiciones. Por supuesto, este caso es bastante hipotético, ya que la potencia informática del enemigo puede no permitirle procesar una gran cantidad de mensajes en un tiempo aceptable.
Literatura
1. Zhelnikov V. Criptografía del papiro a la computadora.
2. Kuzminov T. V. Métodos criptográficos de protección de la información. Novosibirsk Instituto de Sistemas Informáticos SB RAS, 1998.
3. Gnedenko B.V. Fundamentos de la teoría de la probabilidad. M., 1989.
4. Barichev S. Fundamentos de criptografía.
5. Sapegin, Wegner. Protección del software de ordenadores personales.