Análisis criptográfico de los LFSR

• Síntesis
• Síntesis
• Introducción
• Desarrollo
• Conclusiones
• Bibliografía

Síntesis

En el presente trabajo se analiza una de las
herramientas más utilizadas para la construcción de
criptosistemas de cifrado en flujo, los registros de
desplazamiento con retroalimentación lineal (LSFRs, siglas
en inglés), los cuales están basados en el principio
matemático de las sucesiones recurrentes lineales (SRL)
sobre los campos finitos binarios. Se brinda la
fundamentación teórica de estos mecanismos presentando
las definiciones y propiedades principales, que son necesarias
para comprender su funcionamiento. Además, se detallan
métodos teóricos y prácticos para la
obtención de los parámetros de los LSFRs.

Introducción

La teoría de los campos finitos es una rama del
Álgebra moderna que se ha convertido en muy actual desde la
última mitad del siglo pasado, teniendo sus múltiples
aplicaciones en la combinatoria, la teoría de códigos,
la teoría matemática de los esquemas de
conmutación, la teoría de números, la
geometría algebraica, la teoría de Galois y en
particular en Criptografía, donde se utilizan en la
construcción de la mayoría de los códigos
conocidos y su decodificación(Niederreiter,
1986).

Las sucesiones sobre campos finitos cuyos términos
dependerán de una manera sencilla de sus predecesores son de
importancia para una variedad de aplicaciones ejemplo en la
criptografía. Dichas sucesiones son fáciles de generar
mediante procedimientos recursivos, lo cual es sin duda una
característica ventajosa desde el punto de vista
computacional y también tienden a tener propiedades
estructurales útiles(Menezes, VanOorschot, & Vanstone,
1996).

En 1917, J. Mauborgne y G. Vernam inventaron un
criptosistema perfecto según el criterio de Shannon. Dicho
sistema consistía en emplear una sucesión aleatoria de
igual longitud que el mensaje, que se usaría una única
vez, combinándola mediante alguna función simple e
inversible (xor) con el texto en claro bit a bit.

En este trabajo analizaremos una herramienta para la
construcción de este tipo de criptosistema, denominado en la
criptografía moderna como algoritmo de cifrado en flujo,
sobre campos finitos específicos: los binarios, o sea, los
campos finitos de característica dos. Dichos criptosistemas
no son más que la especificación de un generador
pseudoaleatorio, que permiten cifrar mensajes de longitud
arbitraria, combinando el mensaje con la sucesión (conjunto
de elementos encadenados o sucesivos) mediante la operación
or exclusivo bit a bit. Los mismos no proporcionan seguridad
perfecta, ya que mientras en el cifrado de Vernam el número
de posibles claves es tan grande como el de posibles mensajes,
cuando empleamos un generador tenemos, como mucho, tantas
sucesiones distintas como posibles valores del estado inicial del
registro.Una herramienta a emplear para la construcción de
estos criptosistemas la constituye los registros de
desplazamiento con retroalimentación lineal (LSFR, estos son
un tipo especial de circuitos electrónicos de
conmutación que procesan la información presentada de
una manera adecuada en forma de elementos del campo), los cuales
están basados en el principio matemático de las
sucesiones recurrentes lineales (SRL, ecuación que define
una sucesión recursiva donde cada término de la
sucesión es definido como una función de términos
anteriores).

Debido a que permiten generar sucesiones con
períodos muy grandes y con buenas propiedades
estadísticas, además de su bien conocida estructura
algebraica y su facilidad para ser implementados por hardware,
estos se encuentran presentes en muchos de los generadores de
sucesión propuestos en la literatura.

Actualmente existe una gran variedad de principios de
diseño para construir algoritmos de cifrado en flujo, pero
uno de los más utilizados desde hace décadas son los
registros de desplazamiento con retroalimentación lineal.
Hoy por hoy, se reportan algunas deficiencias de seguridad, lo
cual ha limitado su utilización y han impuesto
transformaciones en su estructura y funcionamiento. No obstante,
muchos de estos reportes no presentan información en detalle
e incluso en algunos se especula acerca de los resultados
planteados.

Desarrollo

1.1 Cifrado en flujo

El cifrado en flujo se realiza bit a bit,
mediante el texto claro y la sucesión aleatoria
generada.

Véase (López, 2009), (Schneier,
1) y (Bruen & Mollin, 2009)

Sealos bits de texto claro, texto cifrado y la
sucesión aleatoria generada, respectivamente. El cifrado y
descifrado en flujo consiste en:

Cifrado: i

Descifrado: i

Las función fueron denotadas de manera diferente
pero, como se puede observar existe una similitud entre estas. La
razón de la similitud de la función de cifrado y
descifrado se puede mostrar fácilmente. Debemos demostrar
que la función de descifrado realmente produce el bit de
texto en claroSe
sabe que el bit de
texto cifrado fue obtenido utilizando la función de cifrado

Los cifrados de flujo actuales utilizan una
sucesión de bits de clave generada por un generador de sucesiones
pseudoaleatorias que debe tener ciertas propiedades (Como los
postulados mencionados en el capítulo anterior). Una manera
sencilla de producir sucesiones pseudoaleatorias grandes es
utilizar los LFSRs. Los LFSRs se implementan fácilmente en
hardware y muchos, pero no todos, de los cifrados de flujo, hoy
por hoy, hacen uso de estos. Un ejemplo destacado es el sistema
de cifrado A5 / 1 (Biham & Dunkelman, 2000), que está
estandarizado para el cifrado de voz en las redes del Sistema
Global de la Comunicaciones Móviles (GSM)(Siegmund M. Redl,
1995). Como veremos en este capítulo, a pesar de que un LFSR
produce sucesiones con buenas propiedades estadísticas,
estos son criptográficamente débiles.

En la actualidad la mayoría de los algoritmos son
públicos, por lo que se pueden conocer las
características de los mismos y sus vulnerabilidades. Por
esta razón, es posible conocer la longitud de los registros
de desplazamiento con retroalimentación lineal.

No obstante, si el algoritmo es secreto es posible
conocer este dato, mediante la utilización de la
ingeniería inversa, si este está implementado en
hardware, lo cual es muy frecuente en la utilización de los
LFSRs. Tal es el caso del algoritmo mencionado, A5/1. Mientras
que, si está implementado en software es posible conocer
este parámetro teniendo en cuenta el almacenamiento
requerido.

Incluso los propios polinomios utilizados para
retroalimentación pueden ser públicos, pero es
recomendado que se mantenga como parámetros
secretos.

1.2 Ataques de texto claro
conocido

Como lo indica su nombre, los LFSRs son lineales. Los
sistemas lineales se rigen por relaciones lineales entre sus
entradas y salidas. Puesto que, las dependencias lineales pueden
ser relativamente fáciles de analizar, esto puede ser una
gran ventaja, por ejemplo, en sistemas de comunicación. Sin
embargo, un criptosistema donde los bits de la llave sólo
intervienen en relaciones lineales hace a un cifrado altamente
inseguro. Ahora vamos a investigar cómo el comportamiento
lineal de un LFSR conduce a un ataque poderoso (Guarino, 2010) y
(Kholosha, 2003).

Si utilizamos un LFSR para cifrado de flujo, la llave
secreta es el
estado inicial de registro, es decir, el vector Un ataque posible, es el
ataque de texto claro conocido donde un atacante conoce algunos
pares de texto claro y su texto cifrado correspondiente. Se puede
suponer, además, que el atacante conoce la longitud
del LFSR. El ataque
es tan eficiente que se puede tratar fácilmente un gran
número de valores posiblesde manera que esta suposición no es una
restricción importante. Sea el texto claro conocido y el texto cifrado
correspondiente. Con estos pares de bits de texto claro y texto cifrado, un
atacante puede reconstruir bits de la sucesión aleatoria generada
para el cifrado en flujo:

Para el desarrollo de este epígrafe nos
plantearemos la siguiente problemática, un criptoanalista
está trabajando para descifrar determinada información,
para ello realiza el ataque del texto claro conocido,
interceptando los caracteres que se pueden inferir
fácilmente de acuerdo al momento y las circunstancias en que
esta operación se realice.

Ejemplo 1.2

• a. Si el mensaje a cifrar posee referencia a
  direcciones web es muy común la presencia de los
  caracteres http:, ftp:, https:, u otras directivas de
  comunicación, lo cual puede ser utilizado para realizar
  estos ataques.

Para llegar al estado inicial necesitamos conocer
salidas sucesivas,
siendo la longitud
del registro de desplazamiento con retroalimentación lineal,
que se conoce por ser la mayoría de los algoritmos
públicos.

De esta manera, la sucesión obtenida mediante este
ataque, como subsucesiónde una SRL homogénea binaria
producida por un LFSR, la denotaremos por

siendoel
instante de tiempo en que se obtuvo dicha salida y el grado del polinomio de
conexión

del registro, que coincide con la longitud del mismo
(Golomb, 1982), que como se dijo al inicio del capítulo se
conoce por ser la mayoría de los algoritmos de llave
pública.A través de esta subsucesión se puede
obtener el estado inicial, obteniendo la llave secreta, y de esta
forma reconstruir la sucesión completa determinando todo el
texto claro.

1.3 Obtención del polinomio primitivo
de los LFSRs

En la búsqueda del estado inicial necesitamos obtener,
utilizando el ataque de texto claro conocido, el polinomio de
conexión del registro de desplazamiento con
retroalimentación lineal. Los coeficientes de dicho
polinomio coinciden con los de la sucesión recurrente lineal
que representa. Para hallarlo es necesario una parte de la
sucesión de salida de elementos consecutivos, siendo el grado del polinomio de
conexión. Para la aplicación de este método no es
necesario conocer el instante de tiempo donde comienza la
sucesión de elementos consecutivos, o sea,

Por la definición de recurrencia lineal (Panario,
2013) podemos obtener el siguiente sistema de ecuaciones
expresado en función de términos conocidos por el
epígrafe anterior, siendo las incógnitas:

Como podemos ver, siempre es posible expresar el estado
actual en función de los anteriores. Si la longitud del
registro no es muy grande, los cálculos se pueden hacer
fácilmente a mano, resolviendo un reducido sistema de
ecuaciones por alguno de los métodos clásicos
conocidos, como sustitución o reducción y en ocasiones
hasta por tanteo. Esto se complica a medida que la longitud
aumente. Cuando esto ocurre dicho sistema se puede resolver
fácilmente por el método de Gauss (véase
(Arachchige, 1991) y (Yoshiyasu Takefusi, 1983) ) el cual
está implementado en los anexos por el Laboratorio de
Criptografía académeica de la Universidad Central de
las Villas (LCA) (Ver anexo 1). Este nos elimina todo tipo de
complicación, se ponen ceros o unos en dependencia de si se
encuentran o no los términos de la sucesión recurrente
lineal homogénea que le anteceden a la subsucesión
obtenida, como ya hemos mencionado, por un ataque de texto claro
conocido y se aplica el método de Gauss. De esta forma se
obtienen los coeficientes del polinomio de conexión del registro de
desplazamiento con retroalimentación lineal y con esto el
polinomio característico asociado a la relación
recurrente lineal (Panario, 2013), que según lo planteado,,
donde es la matriz
identidad de orden sobre el campo y la matrizse puede considerar como la matriz
acompañante del polinomio mónico la cual se representa como
sigue:

Donde los por tanto son ceros y unos.

Ejemplo 1.3

Tenemos el siguiente registro de desplazamiento con
retroalimentación lineal

Para encontrar el polinomio de conexión, como
habíamos dicho, necesitamos una subsucesión de salida
de elementos
obtenidas por el ataque de texto claro conocido.

Sea dicha
subsucesión. Luego se tiene,

1 0 0 0 1 1 0 1 1 1

Planteando el sistema de ecuaciones dado en el
epígrafe anterior tendríamos:

Sustituyendo nos queda el reducido sistema:

Resolviendo el mismo se
obtiene

Siendo

y

Obtenemos el polinomio de conexión

1.4 Procedimientos para la
recuperación del estado inicial de los LFSR

Luego de haber obtenido el polinomio de conexión
podemos hacer uso la de matriz acompañante, la misma nos es
de gran utilidad para recuperar el estado inicial del registro de
desplazamiento con retroalimentación lineal.

Sea la matriz acompañante a la sucesión
recurrente lineal homogénea binaria.

Para todo vector de estado se verifica en la SRL
homogénea que (Panario, 2013), entonces despejando obtenemos

De esta manera obtenemos el vector de estado inicial,
siendo el instante
de tiempo que se obtuvo la sucesión,

Ejemplo 1.4

Utilizando el resultado del ejemplo anterior y
conociendo el instante de tiempo en que se comenzó a generar
dicha subsucesión () podemos recuperar el estado inicial
El registro de
deslazamiento con retroalimentación lineal que mostramos es no
singular. Cada uno de los posibles estados iniciales del registro
no singular produce una sucesión recurrente lineal
homogénea sobre el campo binario (sucesión de salida)
de posible período máximo (Golomb, 1982) ya que
es un polinomio
primitivo, por lo tanto su período sería:

Además 5 y 31 son primos de Mersenne, entonces la
sucesión recurrente lineal es de período
máximo.

Como todo vector de estado verifica que , entonces se cumple para el
estado inicial

Despejando la incógnita se obtiene

Luego necesitamos el cálculo de:

Y de su matriz inversa, la cual se puede obtener por el
método de Gauss o utilizando la traspuesta de la adjunta
dividida por el determinante de dicha matriz, o sea o también utilizando el
software El Matemática:

Realizando entonces el producto de matrices
obtenemos:

El cual podemos verificar que es el estado inicial a
partir del cual se generó la sucesión recurrente lineal
homogénea.

Sea el registro de desplazamiento con
retroalimentación lineal y el estado inicial a partir del cual se generó la
subsucesión

Las conexiones están dadas según (Golomb,
1982).

Aplicando un correcto funcionamiento del registro
obtenemos los 31 estados del registro y justo en el instante de
tiempo obtenemos el
estado a partir del cual se generó la sucesión de
salida obtenida por el ataque de texto claro conocido.

La sucesión de salida que se obtiene es:

Observación: El estado a partir del cual se
obtuvieron los elementos de dicha subsucesión y dichos
elementos coinciden (rojo subrayado).

Bajo el mismo supuesto y la misma hipótesis
plantearemos otro procedimiento para la recuperación del
estado inicial. Utilizaremos la definición de recurrencia
propuesta en el segundo epígrafe del primer
capítulo.

Sea el
polinomio de conexión del registro de desplazamiento
obtenido en el epígrafe anterior, la subsucesión de salida que se obtuvo
por el ataque de texto claro expuesto en el epígrafe 1.1.
Entonces por la definición de sucesión recurrente
lineal homogénea (Panario, 2013), siempre es posible
expresar cualquier término de la sucesión recurrente
lineal homogénea en función de los términos
anteriores. De esta manera, podemos representar la ecuación
de cualquier término de la recurrencia a partir de en función de los
estados anteriores y por consiguiente, del estado inicial
realizando la
recurrencia hacia atrás utilizando la suma

En función de las etapas iniciales
sería

Y así sucesivamente

donde.

Formaríamos entonces un sistema solo en
función de las etapas iniciales utilizando la suma

El sistema de ecuaciones anterior siempre se puede
resolver, solo que sería costoso computacionalmente en los
casos donde el instante de tiempo sea muy grande. La cantidad de ecuaciones a
formular es que es
la cantidad de etapas desconocidas del estado inicial y, como se
había mencionado, el grado del polinomio de conexión.
El planteamiento de las ecuaciones cesa cuando obtengamos las
primeras ecuaciones
a partir del instante de tiempo supuesto conocido. Con este
sistema recuperaría el estado inicial.

Ejemplo 1.5

Sea el
polinomio de conexión del registro de desplazamiento con
retroalimentación lineal encontrado en el Ejemplo 3.2,
la subsucesión
de salida obtenida por el ataque a partir del tiempo y constituyen las incógnitas.

El sistema se formularía

Sustituyendo los valores de en el sistema y realizando
la recurrencia hacia atrás se obtiene

Resolviendo este utilizando algún
método de los dichos anteriormente
obtendríamos

Mediante el análisis criptográfico de los
registros de desplazamiento con retroalimentación lineal
pudimos obtener, bajo ciertos supuestos, el polinomio de
conexión del registro y con este hallar, por dos vías,
el estado inicial a partir del cual se generó la SRL
homogénea binaria del primer capítulo. Esto no prueba
que los registros son vulnerables a ataques por lo que hay que
utilizar otros mecanismos para potenciarlos.

Conclusiones

• A través de este trabajo se pudo obtener un
  procedimiento práctico para la obtención de los
  polinomios de retroalimentación de los registros de
  desplazamiento lineales a partir del conocimiento de
  elementos
  consecutivos de una sucesión de salida, siendo la longitud del
  registro.

• Además, se expusieron métodos
  teóricos para la recuperación del estado inicial de
  los registros de desplazamiento, los cuales pueden constituir
  amenazas reales bajos entornos que soporten las suposiciones
  planteadas.

• A partir de estos resultados se puede llegar a la
  conclusión de que los LSFR no se pueden utilizar por si
  solos, hay que introducirles otros mecanismos para aumentar
  su fortaleza.

Bibliografía

• 1. Arachchige, C. K. (1991). A Fast Algorithm
  for Gaussian Elimination over GF (2) and Its Implementation
  on the GAPP.

• 2. Biham, E., & Dunkelman, O. ( 2000).
  Cryptanalysis of the A5/1 GSM Stream Cipher.
  43–51.

• 3. Bruen, A., & Mollin, R. (2009).
  Cryptography and Shift Registers.

• 4. Golomb, S. (1982). Shift register
  sequences.

• 5. Guarino, S. (2010). Ciphertext-only
  reconstruction of LFSR-based stream ciphers.

• 6. Kholosha, A. (2003). Investigations in the
  Design and Analysis of Key-Stream Generators.

• 7. López, M. J. (2009).
  CRIPTOGRAFÍA Y SEGURIDAD EN
  COMPUTADORES.

• 8. Menezes, A., VanOorschot, P., &
  Vanstone, S. (1996). Handbook of Applied
  Cryptography.

• 9. Niederreiter, R. L. (1986). Introduction
  to Finite fields.

• 10. Panario, G. L. (2013). Handbook of
  finite fields.

• 11. Schneier, B. (1996 de 1 de 1). Applied
  Cryptography. Recuperado el 25 de mayo de
  2014

• 12. Siegmund M. Redl, M. K. (1995). An
  Introduction to GSM.

• 13. Yoshiyasu Takefusi, T. K. (1983). Fast
  Matrix Solver in GF(2). Recuperado el 15 de 5 de
  2014

Anexo

Algoritmo para generar polinomio
primitivo sobre campos binarios (elaborado por el
LCA).

UNIVERSIDAD DE
CIENFUEGOS

"Carlos Rafael
Rodríguez"

Facultad de Ingeniería

Departamento de Matemática
Aplicada

ANÁLISIS CRIPTOGRÁFICO DE
LOS LFSR

Autores: Lic. Mayara Rosa Mier
Macías

MSc. Oristela Cuellar
Justiz

Esp. Evaristo José Madarro
Capó

2014-2015