Cifrado de flujo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 1 de diciembre de 2020; las comprobaciones requieren 2 ediciones .

Un flujo [1] [2] o un cifrado de flujo [3] es un cifrado simétrico en el que cada carácter de texto sin formato se convierte en un carácter de texto cifrado, dependiendo no solo de la clave utilizada, sino también de su ubicación en el flujo de texto sin formato. Un cifrado de flujo implementa un enfoque diferente al cifrado simétrico que los cifrados de bloque .

Historia

Los cifrados de flujo basados en registros de desplazamiento se utilizaron activamente durante los años de la guerra, mucho antes de la llegada de la electrónica. Eran fáciles de diseñar e implementar.

En 1965, Ernst Selmer, el criptógrafo jefe del gobierno noruego, desarrolló la teoría de la secuencia del registro de desplazamiento . Más tarde, Solomon Golomb , un matemático de la Agencia de Seguridad Nacional de EE . UU. , escribió un libro llamado "Shift Register Sequences" en el que expuso sus principales logros en esta área, así como los de Selmer.

El trabajo de Claude Shannon , publicado en 1949, trajo gran popularidad a los cifrados de flujo , en el que Shannon demostró la seguridad absoluta del cifrado de Vernam (también conocido como el bloc de notas de un solo uso). En el cifrado de Vernam , la clave tiene una longitud igual a la longitud del propio mensaje transmitido. La clave se usa como gamma , y si cada bit de la clave se elige al azar, entonces es imposible descifrar el cifrado (ya que todos los textos sin formato posibles serán igualmente probables). Hasta la fecha, se han creado una gran cantidad de algoritmos de cifrado de flujo , como: A3 , A5 , A8 , MUGI , PIKE , RC4 , SEAL .

Modo gamma para cifrados de flujo

La implementación más simple del cifrado de flujo se muestra en la figura. El generador gamma produce un flujo clave (gamma): . Denotemos el flujo de bits de texto sin formato como . Luego, el flujo de bits del texto cifrado se obtiene aplicando la operación XOR : donde . $k_1,k_2,k_3,\puntos,k_L$ $m_1,m_2,m_3,\puntos,m_L$ $c_1,c_2,c_3,\puntos,c_L$ $c_i=m_i\oplus k_i$

El descifrado se realiza mediante la operación XOR entre la misma gamma y el texto cifrado: . $m_i=c_i\oplus k_i$

Obviamente, si la secuencia de bits gamma no tiene período y se elige al azar, entonces es imposible descifrar el cifrado. Pero este modo de cifrado también tiene características negativas. Por lo tanto, las claves que tienen una longitud comparable a los mensajes transmitidos son difíciles de usar en la práctica. Por lo tanto, se suele utilizar una longitud de clave más pequeña (por ejemplo, 128 bits). Utilizándolo, se genera una secuencia de juego pseudoaleatoria (debe satisfacer los postulados de Golomb ). Naturalmente, la pseudoaleatoriedad de gamma puede explotarse en un ataque a un cifrado de flujo.

Clasificación de cifrados de flujo

Suponga, por ejemplo, que en el modo gamma para cifrados de flujo, un carácter del texto cifrado se distorsiona durante la transmisión a través de un canal de comunicación . Obviamente, en este caso, todas las señales recibidas sin distorsión serán decodificadas correctamente. Sólo se perderá un carácter del texto. Y ahora imaginemos que uno de los caracteres del texto cifrado se perdió durante la transmisión por el canal de comunicación. Esto conducirá a una decodificación incorrecta de todo el texto que sigue al carácter perdido.
Prácticamente todos los canales de transmisión de datos para los sistemas de cifrado de transmisión contienen interferencias . Por lo tanto, para evitar la pérdida de información, se resuelve el problema de sincronizar el cifrado y descifrado del texto. De acuerdo con el método para resolver este problema, los sistemas de cifrado se dividen en sistemas sincrónicos y autosincronizantes.

Cifrados de flujo síncrono

Definición:

Los cifrados de flujo síncrono (SPC) son cifrados en los que se genera un flujo de claves independientemente del texto sin formato y el texto cifrado.

Cuando se cifra, el generador de flujo de claves produce bits de flujo de claves que son idénticos a los bits de flujo de claves cuando se descifran. La pérdida del signo del texto cifrado hará que los dos generadores no estén sincronizados, lo que imposibilitará descifrar el resto del mensaje. Obviamente, en esta situación, el emisor y el receptor deben resincronizarse para poder seguir trabajando.

La sincronización generalmente se realiza insertando marcadores especiales en el mensaje transmitido. Como resultado, un carácter perdido durante la transmisión conduce a un descifrado incorrecto solo hasta que se recibe uno de los tokens.

Tenga en cuenta que la sincronización debe realizarse de tal manera que no se repita ninguna parte del flujo de claves. Por lo tanto, no tiene sentido transferir el generador a un estado anterior.

Ventajas de SPS:

sin efecto de propagación de errores (solo un bit distorsionado se decodificará incorrectamente);
evitar cualquier inserción y eliminación del texto cifrado, ya que provocarían una pérdida de sincronización y serían detectados.

Contras de SPS:

vulnerable a cambiar bits individuales del texto cifrado. Si el atacante conoce el texto en claro , puede cambiar estos bits para que se descifren como él quiera.

Cifrados de flujo autosincronizados

La idea básica de la construcción fue patentada en 1946 en USA .

Definición:

Los cifrados de flujo de sincronización automática (cifrados de flujo asíncrono (ATS)) son cifrados en los que el flujo de clave se crea mediante una función de la clave y un número fijo de caracteres de texto cifrado.

Entonces, el estado interno del generador de flujo de claves es una función de los N bits anteriores del texto cifrado. Por lo tanto, el generador de flujo de claves de descifrado, habiendo recibido N bits, se sincroniza automáticamente con el generador de cifrado.

La implementación de este modo es la siguiente: cada mensaje comienza con un encabezado aleatorio de N bits de longitud; el encabezado se cifra, transmite y descifra; la decodificación es incorrecta, pero después de estos N bits, ambos generadores estarán sincronizados.

Ventajas de APS:

Agitando las estadísticas de texto sin formato. Dado que cada carácter del texto sin formato afecta al siguiente texto cifrado, las propiedades estadísticas del texto sin formato se extienden a todo el texto cifrado. Por lo tanto, PNW puede ser más resistente a los ataques de redundancia de texto sin formato que PNW.

Contras de APS:

propagación de errores (cada bit incorrecto del texto cifrado corresponde a N errores en el texto sin formato);
sensible a la apertura por retransmisión.

Cifrados de flujo basados en registros de desplazamiento con retroalimentación lineal (LFSR)

Base teórica

Hay varias razones para usar registros de desplazamiento lineal en criptografía:

algoritmos criptográficos de alto rendimiento
el uso de solo las operaciones más simples de suma y multiplicación, implementadas en hardware en casi todos los dispositivos informáticos
buenas propiedades criptográficas (las secuencias generadas tienen un período largo y buenas propiedades estadísticas)
facilidad de análisis usando métodos algebraicos debido a la estructura lineal

Definición: Un registro de desplazamiento de retroalimentación lineal de longitud L consta de L celdas numeradas , cada una de las cuales es capaz de almacenar 1 bit y tiene una entrada y una salida; y una señal de reloj , que controla el desplazamiento de los datos. Durante cada unidad de tiempo, se realizan las siguientes operaciones: $0,1,2,\puntos L-1$

el contenido de la celda forma parte de la secuencia de salida; $L-1$
el contenido de la -ésima celda se mueve a la celda para cualquier , . $i$ $yo+1$ $i$ ${\ estilo de visualización 0 \ leq i <L-1}$
el nuevo contenido de la celda está determinado por el bit de retroalimentación, que se calcula mediante la adición de módulo 2 con ciertos coeficientes de los bits de la celda . ${\ estilo de visualización 0}$ $0,1,2,\puntos L-1$

En el primer paso: En el segundo paso: La siguiente relación describe el funcionamiento de LFSR en términos generales: Si escribimos bits iguales a cero en todas las celdas, entonces el sistema generará una secuencia que consistirá en todos ceros. Si escribimos bits distintos de cero, obtenemos una secuencia semi-infinita. La secuencia está determinada por los coeficientes . Veamos cuál puede ser el período de dicho sistema: Número de rellenos distintos de cero: Por lo tanto, . Después de la ocurrencia de un relleno, que fue antes, el proceso comenzará a repetirse. El proceso de llenar el registro, como se muestra arriba, está representado por una ecuación de diferencia lineal. Transferimos todos los términos a una parte de la igualdad, obtenemos: . $S_L=c_1 \cdot S_{L-1}\oplus c_2 \cdot S_{L-2}\oplus \dots \oplus c_L \cdot S_0.$

$S_{L+1}=c_1 \cdot S_L\oplus c_2 \cdot S_{L-1}\oplus \dots \oplus c_L \cdot S_1.$

$S_j=c_1 \cdot S_{j-1}\oplus c_2 \cdot S_{j-2}\oplus \dots\oplus c_L \cdot S_{jL}.$
$c_1,c_2,\puntos,c_L.$
$T$
${\ estilo de visualización 2^{L}-1.}$ $T\leqslant 2^L-1$

$S_{j}\oplus c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus \dots \oplus c_{L}\cdot S_{jL }=0$

Designemos: . Después: ${\displaystyle S_{j}=D^{-j))$
$(1 \oplus c_1\cdot D \oplus c_2\cdot D^2 \oplus \dots \oplus c_L\cdot D^L )\cdot D^{-j}.$

$C(D) = 1 \oplus c_1\cdot D \oplus c_2 \cdot D^2 \oplus \dots \oplus c_L\cdot D^L.$

Una propiedad importante de este polinomio es la reducibilidad.
Definición: Se dice que un
polinomio es reducible si se puede representar como el producto de dos polinomios de menor grado con coeficientes de un campo dado (en nuestro caso, con coeficientes binarios). Si tal representación no tiene lugar, entonces se dice que el polinomio es irreducible .
Si el polinomio es irreducible y primitivo , entonces el período será igual al período máximo posible, igual a ${\ estilo de visualización C (D)}$ ${\ estilo de visualización 2^{L}-1.}$

Ejemplo: tome un polinomio primitivo irreducible. Este polinomio se puede escribir como - se escriben los grados en los que hay coeficientes distintos de cero. Escribimos en el estado inicial en las celdas y determinamos la duración del período del generador: $C(D)=D^{3}+D^{2}+1(c_{3}=1,c_{2}=1,c_{1}=0).$ ${\ estilo de visualización (3,2,0)}$
${\ estilo de visualización 001}$

Mesa. Determinación del período del generador.

Retroalimentación	Celda0	Celda1	celda2
una	0	0	una
0	una	0	0
una	0	una	0
una	una	0	una
una	una	una	0
0	una	una	una
0	0	una	una
una	0	0	una

El periodo del generador es La salida del generador será la secuencia: Demos ejemplos de algunos polinomios primitivos módulo 2: ${\ estilo de visualización 7 (2 ^ {3} -1 = 7).}$ $1001011 1001011 1001011\puntos$

$(1.0), (2.1.0), (3.1.0), (4.1.0), (5.2.0), (6.1.0), (7.1 ,0), (7,3,0), (8 ,4,3,2,0), (9,4,0)\puntos$

Complejidad lineal

La complejidad lineal de una secuencia binaria es una de las características más importantes de la operación LFSR. Por lo tanto, nos detenemos en este tema con más detalle.
Antes de definir la complejidad lineal, introducimos algo de notación. -una secuencia infinita con miembros -se dice que una secuencia finita de longitud , cuyos miembros son LFSR genera una secuencia si hay algún estado inicial en el que la secuencia de salida LFSR coincide con . De manera similar, se dice que el LFSR genera una secuencia final si hay algún estado inicial para el cual la secuencia de salida del LFSR tiene como primeros términos los miembros de la secuencia . Finalmente, damos una definición de la complejidad lineal de una secuencia binaria infinita. Definición: La complejidad lineal de una secuencia binaria infinita es el número , que se define de la siguiente manera:
$S$ $S1,S2,S3,\puntos$
$S_{n}$ $norte$ $S_1,S_2,S_3,\puntos,S_{n-1}.$
$S$ $S$ $S_{n}$ $norte$ $S_{n}$

$S$ $L(S)$

Si es la secuencia cero , entonces $S$ $S=0,0,0,0,\puntos,$ ${\ estilo de visualización L (S) = 0.}$
Si no hay LFSR que genere , entonces es igual a infinito . $S$ $L(S)$
De lo contrario, existe la longitud del LFSR más corto que genera . $L(S)$ $S$

Definición: La
complejidad lineal de una sucesión binaria finita es el número , que es igual a la longitud del LFSR más corto que genera una sucesión que tiene como primeros términos . Propiedades de complejidad lineal: Sean y sean sucesiones binarias. Entonces: 1. Para cualquier complejidad lineal de la subsucesión satisface las desigualdades 2. si y sólo si es una sucesión cero de longitud . 3. si y solo si . 4. Si es periódico con un período , entonces 5. Un algoritmo eficiente para determinar la complejidad lineal de una secuencia binaria finita es el algoritmo de Berlekamp-Massey . $S_{n}$ $L(S_n)$ $norte$ $S_{n}$
$S$ $k$
$n>0$ $S_{n}$ $0\leqslant L(S_n) \leqslant n.$
${\ estilo de visualización L (S_ {n}) = 0}$ $S_{n}$ $norte$
${\ estilo de visualización L (S_ {n}) = n}$ ${\ estilo de visualización S_ {n} = 0,0,0, \ puntos, 1}$
$S$ $norte$ $L(S_{n})\leqslant N.$
$L(S \oplus K)\leqslant L(S) + L(K).$

Cifrados de flujo basados en LFSR. Complicación

Desafortunadamente, la secuencia de salida del LFSR es fácilmente predecible. Entonces, conociendo 2L caracteres de la secuencia de salida, es fácil encontrar el llenado inicial del registro resolviendo un sistema de ecuaciones lineales (consulte el párrafo "Cifrados de flujo basados en registros de desplazamiento con retroalimentación lineal").

Se cree que para uso criptográfico, la secuencia de salida LFSR debe tener las siguientes propiedades:

gran período
alta complejidad lineal
buenas propiedades estadísticas

Hay varios métodos para diseñar generadores de flujo de claves que destruyen las propiedades lineales de LFSR y, por lo tanto, hacen que dichos sistemas sean criptográficamente más seguros:
1. usando una función no lineal que combina las salidas de varios LFSR
2. usando una función de filtrado no lineal para el contenido de cada celda de un solo LFSR
3. usar la salida de un LFSR para controlar la señal de reloj de uno (o varios) LFSR.

Combinación no lineal de generadores

Se sabe que cada función booleana se puede escribir como una suma módulo 2 de productos de órdenes de variables independientes , . Esta expresión se llama la forma normal algebraica de la función . El orden no lineal de una función es el orden máximo de términos en la notación de su forma algebraica normal. Por ejemplo, una función booleana tiene un orden no lineal de 3. El orden no lineal máximo posible de una función booleana es igual al número de variables. Supongamos ahora que tenemos registros de desplazamiento de retroalimentación lineal, sus longitudes son diferentes por pares y mayor que dos. Todos los registros se combinan con una función no lineal , como se muestra en la figura. La función se representa en forma algebraica normal. Entonces la complejidad lineal del flujo de claves es . Si son números coprimos por pares, entonces la longitud del período del flujo de claves es igual a: . Por ejemplo, si , entonces . Y la duración del período del flujo de claves es . ${\ estilo de visualización f (x_ {1}, x_ {2}, \ puntos, x_ {n})}$ $metro$ $0 \leqslant m \leqslant n$ $F$ $F$
$f(x_1,x_2,x_3,x_4 )=x_1 \oplus x_2 \oplus x_4 \oplus x_1 x_3 \oplus x_2 x_3 x_4$ $norte.$
$norte$ $L_1, L_2, L_3, \puntos, L_n$ $f(x_1,x_2,\puntos,x_n)$ $F$ $f(L_1,L_2,\puntos,L_n)$
$L_1, L_2,\puntos, L_n$ $(2^{L_1}-1)\cdot(2^{L_2}-1) \cdots (2^{L_n }-1)$ ${\ estilo de visualización L_ {i} = 10}$ $(2^{L_1}-1)\aprox. 10^3$ ${\ estilo de visualización (10 ^ {3}) ^ {n}}$

Ejemplo (generador Geff):
este generador utiliza tres LFSR combinados de forma no lineal. Las longitudes de estos registros son números primos por parejas. La función no lineal para un generador dado se puede escribir de la siguiente manera: ${\ estilo de visualización L_{1},L_{2},L_{3))$

$f(x_1, x_2, x_3 )=x_1 x_2 \oplus (1+x_2 ) x_3=x_1 x_2 \oplus x_2 x_3 \oplus x_3.$

Duración del período: $(2^{L_1}-1)\cdot(2^{L_2}-1)\cdot(2^{L_3}-1).$

Complejidad lineal: $L=L_{1}\cdot L_{2}+L_{2}\cdot L_{3}+L_{3}.$

El generador Geff es criptográficamente débil porque la información sobre los estados de los generadores LFSR 1 y LFSR 3 está contenida en su secuencia de salida. Para entender esto, denotemos los -ésimos bits de salida del LFSR 1,2,3 y el flujo de claves , respectivamente. Entonces la probabilidad de correlación de la secuencia con respecto a la secuencia : $x_{1}(t),x_{2}(t),x_{3}(t),z(t)$ $t$ $x_1(t)$ $z(t)$

$P(z(t)=x_{1}(t))=P(x_{2}(t)=1)+P(x_{2}(t)=0)\cdot P(x_{ 3}(t)=x_{1}(t))=1/2+1/2\cdot 1/2=3/4.$

De manera similar, por esta razón, a pesar del largo período y la complejidad lineal bastante alta, el generador Geff se presta a ataques de correlación. $P(z(t)=x_{3}(t))=3/4.$

Generadores sobre filtros no lineales

La salida de cada celda se alimenta a la entrada de alguna función de filtrado booleano no lineal . Suponga que la función de filtrado es de orden , entonces la complejidad lineal del flujo de clave es como máximo . $F$ $metro$ $L_m=\sum^{m}_{i=1} {L \elegir i}$

Osciladores basados en reloj

En combinaciones no lineales de osciladores y osciladores de filtro no lineal, el movimiento de datos en todos los LFSR está controlado por una sola señal de reloj.
La idea principal del funcionamiento del tipo de generadores que se está considerando es introducir la no linealidad en el funcionamiento de los generadores de flujo de claves basados en LFSR mediante el control de la señal de reloj de un registro por la secuencia de salida de otro.
Hay 2 tipos de osciladores basados en el control del reloj:
1. Oscilador de tono variable
2. Oscilador de compresión.

Generador de tono variable

Idea principal:
LFSR 1 se usa para controlar el movimiento de los bits de los otros dos LFSR 2 y 3.

Algoritmo de operación:
1. El registro LFSR 1 está sincronizado por una señal de reloj externa
2. Si la salida del registro LFSR 1 es uno , entonces el registro LFSR 2 recibe una señal de reloj y el LFSR 3 repite su bit de salida anterior (durante el tiempo inicial, el bit de salida LFSR 3 anterior se toma igual a 0)
3. Si la salida del registro LFSR 1 es cero , entonces se aplica una señal de reloj al registro LFSR 3, y LFSR 2 repite su salida anterior bit (para el tiempo inicial, el bit de salida anterior del LFSR 2 también se toma igual a 0)
4. La secuencia de bits de salida del generador con paso variable es el resultado de aplicar la operación bit a bit XOR a las secuencias de salida del LFSR 2 y registros LFSR 3.

Aumento de la seguridad de los generadores de paso variable:

las longitudes de los registros RLOS 1, RLLS 2, RLLS 3 deben elegirse a pares por números primos
las longitudes de estos registros deben ser números cercanos.

Generador compresivo

El registro de control LFSR 1 se utiliza para controlar la salida LFSR 2. Algoritmo:

Los registros RLOS 1 y RLLS 2 están sincronizados por una señal de reloj común ;
Si el bit de salida de LFSR 1 es igual a 1, la salida del generador está formada por el bit de salida del registro LFSR 2;
Si el bit de salida LFSR 1 es 0, el bit de salida LFSR 2 se descarta.

El generador de compresión es simple, escalable y tiene buenas propiedades de seguridad. Su desventaja es que la tasa de generación de claves no será constante a menos que se tomen algunas precauciones.

Para aumentar la seguridad del generador de compresión:

las longitudes de los registros LFSR 1 y LFSR 2 deben ser números coprimos ;
es deseable utilizar una conexión oculta entre los registros LFSR 1 y LFSR 2.

Las principales diferencias entre los cifrados de flujo y los cifrados de bloque

La mayoría de los cifrados de clave secreta existentes se pueden clasificar sin ambigüedades como cifrados de flujo o cifrados de bloque . Pero el límite teórico entre ellos es bastante borroso. Por ejemplo, los algoritmos de cifrado de bloques se utilizan en el modo de cifrado de flujo (ejemplo: para el algoritmo DES , modos CFB y OFB ).

Considere las principales diferencias entre los cifrados de flujo y de bloque, no solo en términos de su seguridad y conveniencia, sino también en términos de su estudio en el mundo:

La ventaja más importante de los cifrados de flujo sobre los cifrados de bloque es la alta velocidad de cifrado, acorde con la velocidad de la información de entrada; por lo tanto, se proporciona cifrado casi en tiempo real, independientemente del volumen y la profundidad de bits del flujo de datos convertido.
en los cifrados de flujo síncrono (a diferencia de los cifrados de bloque) no hay efecto de propagación de errores, es decir, la cantidad de elementos distorsionados en la secuencia descifrada es igual a la cantidad de elementos distorsionados de la secuencia cifrada que proviene del canal de comunicación .
la estructura de la clave de secuencia puede tener vulnerabilidades que permiten al criptoanalista obtener información adicional sobre la clave (por ejemplo, con un período de clave pequeño, el criptoanalista puede usar las partes encontradas de la clave de secuencia para descifrar el texto privado posterior).
Las PN, a diferencia de las PN, a menudo se pueden atacar con álgebra lineal (porque las salidas de los registros de desplazamiento de retroalimentación lineal individuales se pueden correlacionar con gamma). Además, el análisis lineal y diferencial se usa con mucho éxito para romper los cifrados de flujo .

Ahora sobre el estado del mundo:

la mayor parte del trabajo de análisis y descifrado de cifrados de bloques se ocupa de algoritmos de cifrado basados en el estándar DES ; para los cifrados de flujo, no hay un área de estudio dedicada; Los métodos de piratería son muy diversos.
para los cifrados de flujo, se establece un conjunto de requisitos que son criterios de confiabilidad (grandes períodos de secuencias de salida, postulados de Golomb , no linealidad); no existen criterios tan claros para BS .
la investigación y el desarrollo de cifrados de flujo se llevan a cabo principalmente en los centros criptográficos europeos, los cifrados en bloque, en los estadounidenses.
el estudio de los cifrados de flujo es más dinámico que el de los cifrados de bloque; no ha habido descubrimientos recientes notables en el campo de los algoritmos DES, mientras que en el campo de los cifrados de flujo ha habido muchos éxitos y fracasos (algunos esquemas que parecían estables, después de una mayor investigación, no estuvieron a la altura de las esperanzas de los inventores) .

Diseño de cifrados de flujo

Según Rainer Rueppel, existen cuatro enfoques principales para el diseño de cifrado de flujo:

El enfoque de la teoría del sistema se basa en la creación de un problema complejo e inexplorado previamente para el criptoanalista.
El enfoque teórico de la complejidad se basa en un problema complejo pero bien conocido (por ejemplo, factorización de números o logaritmo discreto ).
El enfoque de la tecnología de la información se basa en un intento de ocultar el texto sin formato al criptoanalista: no importa cuánto tiempo se dedique al descifrado, el criptoanalista no encontrará una solución inequívoca.
El enfoque aleatorio se basa en la creación de una gran tarea; el criptógrafo intenta así hacer físicamente imposible la solución del problema de descifrado. Por ejemplo, un criptógrafo puede encriptar un artículo y la clave será una indicación de qué partes del artículo se usaron en el encriptado. El criptoanalista tendrá que probar todas las combinaciones aleatorias de partes del artículo antes de tener suerte y determinar la clave.

Criterios teóricos de Reiner Rüppel para el diseño de sistemas en línea:

largos períodos de secuencias de salida;
gran complejidad lineal;
difusión : dispersión de la redundancia en las subestructuras, estadísticas "difuminadas" en todo el texto;
cada bit del flujo de claves debe ser una transformación compleja de la mayoría de los bits de la clave;
criterio de no linealidad para funciones lógicas.

Hasta el momento, no se ha demostrado que estos criterios sean necesarios o suficientes para la seguridad de un sistema de cifrado de transmisión. También vale la pena señalar que si el criptoanalista tiene tiempo y poder de cómputo ilimitados, entonces el único cifrado de flujo realizable que es seguro contra tal adversario es el bloc de notas de un solo uso.

Criptoanálisis. Ataques a cifrados de flujo

Todos los métodos de criptoanálisis de cifrados de flujo generalmente se dividen en poder (ataque "fuerza bruta"), estadísticos y analíticos.

Ataques de poder

Esta clase incluye ataques que realizan una enumeración completa de todas las opciones posibles. La complejidad de una búsqueda exhaustiva depende del número de todas las posibles soluciones al problema (en particular, el tamaño del espacio de claves o el espacio de texto sin formato). Esta clase de ataques es aplicable a todo tipo de sistemas de cifrado de flujo. Al desarrollar sistemas de encriptación, los desarrolladores se esfuerzan por hacer que este tipo de ataque sea el más efectivo en comparación con otros métodos de piratería existentes.

Ataques estadísticos

Los ataques estadísticos se dividen en dos subclases:

método de criptoanálisis de las propiedades estadísticas del rango de cifrado : destinado a estudiar la secuencia de salida del criptosistema; el criptoanalista intenta establecer el valor del siguiente bit en la secuencia con una probabilidad mayor que la de la selección aleatoria, utilizando varias pruebas estadísticas.
método de criptoanálisis de complejidad de secuencia : un criptoanalista intenta encontrar una manera de generar una secuencia similar a gamma pero de una manera más sencilla de implementar.

Ambos métodos utilizan el principio de complejidad lineal.

Ataques analíticos

Este tipo de ataque se considera bajo el supuesto de que el criptoanalista conoce la descripción del generador, el texto público y el texto privado correspondiente. La tarea del criptoanalista es determinar la clave utilizada (el llenado inicial de los registros). Tipos de ataques analíticos aplicados a cifrados de flujo síncrono:

correlación
compensación "tiempo-memoria"
inversión
"sugerir y determinar"
para carga y reinicialización de llaves
Ataque XSL

Ataques de correlación

Son los ataques más comunes para romper cifrados de flujo.

Se sabe que el trabajo para abrir el criptosistema puede reducirse significativamente si la función no lineal pasa información sobre los componentes internos del generador a la salida. Por lo tanto, para restaurar el llenado inicial de los registros, los ataques de correlación examinan la correlación de la secuencia de salida del sistema de cifrado con la secuencia de salida de los registros.

Existen las siguientes subclases de ataques de correlación:

Ataques de correlación básica
Ataques basados en controles de paridad de bajo peso
Ataques basados en el uso de códigos convolucionales
Ataques mediante la técnica del código turbo
Ataques basados en la recuperación de polinomios lineales
Ataques de correlación rápida.

Ataques de correlación básica

Consideremos el ejemplo del ataque de correlación básico de Siegenthaler ("dividir y abrir"), que se basa en el concepto de la distancia de Hamming entre dos secuencias binarias de la misma longitud. Aplicable a generadores combinados.

Para revelar la influencia del j-ésimo registro de desplazamiento lineal (con la secuencia de salida {x (j) } en el cifrado gamma {g} , una parte del generador se modela como un canal simétrico binario (BSC). El algoritmo de ataque consta de dos etapas (a veces llamadas fases ):

calcular la probabilidad de correlación basada en la función de combinación y la segunda etapa. $p_{j}=P(g={x^{(j))))$ $F$
enumeración de los llenados iniciales del registro. En esta etapa, la presencia de una correlación de un fragmento gamma dado con el fragmento correspondiente de se determina calculando la función de correlación cruzada y comparando este valor con un cierto número . $gramo$ ${\ Displaystyle x_ {d}^{(j)))$ $C_{x^{j},{g}}(d)={\frac {1}{n}}\cdot \sum_{i=1}^{n}(-1)^{g_ {i}}\cdot (-1)^{x_{i+d}^{(j)}}$ $T$

Si la comparación tiene éxito, la fase se llama verdadera y se produce la transición al siguiente registro . De lo contrario, la fase se llama inválida y pasa a . Los valores de salida de este algoritmo son los estados que aportan información a la gamma. $j+1$ $d=d+1,d=1,2,\dots,2^{L_{j))$ ${\ estilo de visualización {x_{0}^{j))}$

Ahora un poco sobre la selección del valor de umbral y la cantidad de bits gamma necesarios para un criptoanálisis exitoso : $T$ $norte$ $P_{f}=P(C_{x^{j},{g}}(d)\geq T|Fase incorrecta)$ $P_{m}=P(C_{x^{j},{g}}(d)<T|FaseDerecha)$

Por ejemplo, elegimos , donde es la longitud del registro. Y luego de estas condiciones encontramos y . $P_{m}=0.01,P_{f}=2^{-L}$ $L$ $T$ $norte$

Ataques basados en controles de paridad de bajo peso

Un ejemplo de esta subclase de ataques es el ataque de correlación rápida de Mayer y Staffelbach. Es aplicable tanto a generadores de filtros como a generadores combinados y es la base para todos los demás ataques de correlación rápida de este tipo. La idea del ataque se basa en el uso de ecuaciones de verificación de paridad para un polinomio de retroalimentación de registro lineal .

Ataques de correlación rápida

Los ataques de correlación rápida se entienden como ataques cuya complejidad computacional es mucho menor que la complejidad computacional de los ataques de potencia.
Este tipo de ataque reduce el problema de la decodificación en un canal simétrico binario a un problema de criptoanálisis y se modela como la decodificación de un código lineal aleatorio. Similar a los ataques de correlación básicos, esta subclase usa la noción de distancia de Hamming . ${\ estilo de visualización (N, l)}$

La compensación de tiempo-memoria

El propósito de este ataque es restaurar el estado inicial del registro de desplazamiento (encontrar la clave) utilizando un esquema de dispositivo conocido y un fragmento de la secuencia de cifrado. La complejidad del ataque depende del tamaño del cifrado y la longitud de la gamma interceptada.

Consta de dos etapas:

construcción de un gran diccionario en el que se registran todos los posibles pares estado-salida;
adivinar el llenado inicial del registro de desplazamiento, generar la salida, observar la secuencia de salida capturada y buscar una coincidencia con la salida generada. Si hay una coincidencia, entonces este llenado estimado con alta probabilidad es el inicial.

Ejemplos de esta clase de ataques son el ataque de Steve Babbage y el ataque de Biryukov-Shamir.

"Asumir y Determinar"

El ataque se basa en la suposición de que el criptoanalista conoce la gamma, el polinomio de retroalimentación, el número de cambios de registro entre las salidas del circuito y la función de filtrado. Consta de tres etapas:

suposición sobre el llenado de algunas celdas del registro;
determinar el llenado completo del registro basado en el supuesto de conocimiento del criptoanalista;
generación de secuencias de salida; si coincide con gamma, entonces la suposición en la primera etapa era correcta; si no coincide, vuelva al paso 1.

La complejidad del algoritmo depende del dispositivo del generador y del número de suposiciones.

Notas

↑ Fuente . Fecha de acceso: 16 de enero de 2016. Archivado desde el original el 15 de febrero de 2017. (indefinido)
↑ Fuente . Consultado el 16 de enero de 2016. Archivado desde el original el 14 de febrero de 2017. (indefinido)
↑ Schneier B. Capítulo 16. Generadores de secuencias pseudoaleatorias y cifrados de flujo // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .

Literatura

Ryabko B. Ya., Fionov AN Métodos criptográficos de protección de la información. - Moscú. - Editorial Goryach Line-Telecom, 2005. - ISBN 5-93517-265-8 .

Bruce Schneier . Criptografía aplicada, segunda edición: protocolos, algoritmos y código fuente en C (tela). — John Wiley & Sons, Inc. - Editorial de Literatura Extranjera, 1996. - ISBN 0471128457 .

A. Menezes, P. van Oorschot, S. Vanstone. Manual de Criptografía Aplicada. — CRC Press, Inc. — 1997.

Conferencias de E. M. Gabidulin , Instituto de Física y Tecnología de Moscú, 2009

Enlaces

Matt JB Robshaw. Informe técnico de Stream Ciphers TR-701 (inglés) , versión 2.0, RSA Laboratories, 1995.
Cifrados de flujo. Resultados de la criptología abierta extranjera. . La compilación y traducción más completa de investigaciones extranjeras modernas (hasta 1997) en el campo de la creación y el criptoanálisis de cifrados de flujo.
BC Anashin , A.Yu. Bogdanov, I. S. Kizhvetov. eSTREAM: cifrados de flujo rápidos y fuertes .
JA Reeds y NJA Sloane. Síntesis de desplazamiento-registro .
AV. Yakovlev, A.A. Bezbogov, V. V. Rodin, V. N. Shamkin. Protección criptográfica de la información .
Métodos y medios de protección de la información informática . Tutorial.
Esquema general de un sistema de cifrado de flujo probabilístico
eSTREAM: Hijo del Monstruo del Lago Ness
A. A. Menyashev, V. A. Monarev, B. Ya. Ryabko, A. N. Fionov. Ataque estadístico .
S. Doroshenko, A. Fionov, A. Lubkin, V. Monarev, B. Ryabko, Yu. Yo Shokin. Ataques estadísticos experimentales en cifrados de bloque y flujo (enlace no disponible) .
Yu. V. Stasev, A. V. Potii, Yu. A. Izbenko. Un estudio de métodos de criptoanálisis para cifrados de flujo .

Criptosistemas simétricos
Cifrados de flujo	A3 A5 A8 decimal F-FCSR Grano HC-256 KCipher-2 MICKEY MUGI LUCIO Félix RC4 Conejo SELLO NIEVE SOSEMANES Salsa20 STRUMOK trivium VMPC
Red Feistel	GOST 28147-89 (Magma) pez globo Camelia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFÍA Cobra ACUERDO DES DESX DFC E2 en RUPT FEAL HPC OCURRENCIA KASUMI Khafre Keops LOKI97 MacGuffin MARTE MALLA MISTY1 NuevoDES NDS RC5 RC6 SEMILLA Simón sinople listado SM4 Partícula TÉ XTEA XXTEA Raiden RTEA DES triple Dos peces
red SP	Saltamontes 3 vías A B C ARIA AES (Rijndael) Akelarre Anubis BaseRey bajo omático Cinturón CRIPTON diamante2 grand cru Hierocripta-3 Hierocripta-L1 KHAZAD Kalyna Lucifer presente Arcoíris MÁS SEGURO TIBURÓN CUADRADO Serpiente tres peces
Otro	RANA NUSH REDOC SC2000 SHACAL Cifrado CS