A5 (algoritmo de cifrado)

A5  es un algoritmo de cifrado de transmisión utilizado para garantizar la confidencialidad de los datos transmitidos entre el teléfono y la estación base en el sistema europeo de comunicaciones móviles digitales GSM ( Groupe Spécial Mobile ).

El cifrado se basa en el módulo dos de adición bit a bit (operación XOR booleana) de la secuencia pseudoaleatoria generada y la información que se cifrará. En A5, se implementa una secuencia pseudoaleatoria basada en tres registros de desplazamiento de retroalimentación lineal . Los registros tienen una longitud de 19, 22 y 23 bits, respectivamente. Los cambios están controlados por un circuito especial que organiza el cambio de al menos dos registros en cada paso, lo que conduce a su movimiento desigual. La secuencia está formada por la operación XOR en los bits de salida de los registros.

Historia de la creación y desarrollo

Inicialmente, los criptógrafos militares franceses desarrollaron un cifrado de flujo para ser utilizado exclusivamente con fines militares. A finales de los 80, el estándar GSM requirió la creación de un nuevo y moderno sistema de seguridad. Se basó en tres algoritmos secretos: autenticación - A3 , cifrado de flujo - A5, generación de clave de sesión - A8 . Se utilizó un desarrollo francés como algoritmo A5. Este cifrado proporcionó un flujo de seguridad bastante bueno y, por lo tanto, la confidencialidad de la conversación. Inicialmente, no se esperaba la exportación del estándar desde Europa, pero pronto surgió la necesidad. Por eso el A5 pasó a llamarse A5/1 y empezó a distribuirse tanto en Europa como en USA. Para otros países (incluida Rusia), se modificó el algoritmo, lo que redujo significativamente la fuerza criptográfica del cifrado. El A5/2 fue diseñado específicamente como una opción de exportación para países fuera de la UE. La fuerza criptográfica de A5/2 se redujo al agregar otro registro (17 bits) que controla los turnos del resto. En A5 / 0, no hay encriptación en absoluto. El algoritmo A5/3, basado en el algoritmo Kasumi , también ha sido desarrollado y aprobado para su uso en redes 3G. Estas modificaciones se conocen como A5/x.

Aparición en el dominio público

Oficialmente, este esquema criptográfico no se publicó y su estructura no se hizo pública. Esto se debió a que los desarrolladores confiaron en la seguridad a expensas de la oscuridad , lo que significa que los algoritmos son más difíciles de descifrar si sus descripciones no están disponibles públicamente. Los datos se proporcionaron a los operadores GSM solo cuando fue necesario. Sin embargo, en 1994 se conocieron los detalles del algoritmo A5: la compañía telefónica británica British Telecom envió toda la documentación relativa al estándar a la Universidad de Bradford para su análisis sin entrar en un acuerdo de confidencialidad . Además, aparecieron materiales sobre el estándar en una de las conferencias en China. Como resultado, su esquema se filtró gradualmente a amplios círculos. En el mismo año, los científicos de Cambridge Ross Anderson (Ross Anderson) y Michael Roe (Michael Roe) publicaron un esquema criptográfico restaurado a partir de estos datos y evaluaron su fuerza criptográfica [1] . El algoritmo final se presentó en el trabajo de Jovan Golic en la conferencia Eurocrypt'97.

Estructura A5

El algoritmo A5 es actualmente una familia completa de cifrados. Para la descripción, tomemos A5/1 como antepasado de esta familia. Los cambios en los algoritmos derivados se describirán por separado.

Cifrado de flujo

En este algoritmo, cada carácter de texto sin formato corresponde a un carácter de texto cifrado. El texto no se divide en bloques (como en el cifrado de bloques ) y no cambia de tamaño. Para simplificar la implementación del hardware y, por lo tanto, aumentar el rendimiento, solo se utilizan las operaciones más simples: adición de módulo 2 (XOR) y cambio de registro.

La secuencia de salida se forma agregando el flujo de texto fuente a la secuencia generada (gamma). La peculiaridad de la operación XOR es que aplicada un número par de veces, conduce al valor inicial. Por lo tanto, el mensaje se decodifica agregando el texto cifrado a una secuencia conocida.

Así, la seguridad del sistema depende enteramente de las propiedades de la secuencia. Idealmente, cada bit de gamma es una variable aleatoria independiente y la secuencia en sí es aleatoria. Tal esquema fue inventado por Vernam en 1917 y lleva su nombre. Como demostró Claude Shannon en 1949, esto proporciona una seguridad absoluta. Pero el uso de una secuencia aleatoria supone la transmisión por un canal seguro de un mensaje de igual volumen que el texto plano, lo que complica mucho la tarea y prácticamente no se utiliza en ninguna parte.

En los sistemas reales, se crea una clave de un tamaño determinado, que se transmite fácilmente a través de un canal privado. La secuencia se genera en base a ella y es pseudoaleatoria. Una gran clase de cifrados de flujo (incluido A5) son cifrados cuyo generador de secuencias pseudoaleatorias se basa en registros de desplazamiento de retroalimentación lineal.

RSLOS

Un registro de desplazamiento de retroalimentación lineal consta del propio registro (una secuencia de bits de una longitud determinada) y la retroalimentación. En cada ciclo, ocurren las siguientes acciones: se extrae el bit más a la izquierda (bit más alto), la secuencia se desplaza hacia la izquierda y el valor de la función de retroalimentación se escribe en la celda derecha vacía (bit menos significativo). Esta función es la suma módulo dos de ciertos bits del registro y se escribe como un polinomio, donde el exponente indica el número de bit. Los bits extraídos forman la secuencia de salida.

Para LFSR, el indicador principal es el período de la secuencia pseudoaleatoria. Será máximo (e igual a 2 n − 1) si el polinomio de realimentación es módulo primitivo 2 . La secuencia de salida en este caso se denomina secuencia M.

Sistema LFSR en A5

LFSR en sí mismo se presta fácilmente al criptoanálisis y no es lo suficientemente fuerte como para ser utilizado en el cifrado. Las aplicaciones prácticas son sistemas de registros de reloj variables con diferentes longitudes y funciones de retroalimentación.

La estructura del algoritmo A5 es la siguiente:

  • Tres registros (R1, R2, R3) tienen longitudes de 19, 22 y 23 bits,
  • Polinomios de retroalimentación:
    • X19 + X18 + X17 + X14 + 1 para R1,
    • X 22 + X 21 + 1 para R2 y
    • X 23 + X 22 + X 21 + X 8 + 1 para R3,
  • El reloj está controlado por un mecanismo especial:
    • cada registro tiene bits de sincronización: 8 (R1), 10 (R2), 10 (R3),
    • se calcula la función F = x&y|x&z|y&z, donde & es AND booleano, | - OR booleano, y x, y y z son los bits de sincronización R1, R2 y R3, respectivamente,
    • solo se desplazan aquellos registros que tienen el bit de sincronización igual a F,
    • de hecho, los registros cuyo bit de sincronización pertenece a la mayoría se desplazan,
  • El bit de salida del sistema es el resultado de la operación XOR sobre los bits de salida de los registros.

Funcionamiento del algoritmo A5

Consideremos las características del funcionamiento del algoritmo basado en el esquema conocido. La transmisión de datos se realiza de forma estructurada, dividida en tramas (114 bits). Antes de la inicialización, los registros se restablecen, la clave de sesión (K - 64 bits) formada por A8 y el número de cuadro (Fn - 22 bits) se ingresan al algoritmo . A continuación, se realizan secuencialmente los siguientes pasos:

  • Inicialización:
    • 64 ciclos, en los que el siguiente bit de la clave se XOR con el bit menos significativo de cada registro, mientras que los registros se desplazan en cada ciclo,
    • similar a 22 ciclos, solo se realiza la operación XOR con el número de trama,
    • 100 ciclos con control de cambio de registro, pero sin generación de secuencia,
  • 228 (114 + 114) ciclos están funcionando, la trama transmitida se cifra (los primeros 114 bits) y la trama recibida se descifra (los últimos 114 bits),
  • la inicialización adicional se realiza de nuevo, se utiliza un nuevo número de cuadro.

Diferencias en algoritmos derivados A5/x

Al algoritmo A5/2 se le ha añadido otro registro de 17 bits (R4) , que controla el movimiento del resto. Los cambios de estructura son los siguientes:

  • registro agregado R4 con una longitud de 17 bits,
  • polinomio de retroalimentación para R4: ,
  • el reloj es controlado por R4:
    • R4 tiene bits de sincronización 3, 7, 10,
    • la función de mayoría se calcula F = x&y|x&z|y&z (igual a la mayoría), donde & es AND booleano, | - OR booleano, y x, y y z son los bits de sincronización R4(3), R4(7) y R4(10) respectivamente,
    • R1 se desplaza si R4(10) = F,
    • R2 se desplaza si R4(3) = F,
    • R3 se desplaza si R4(7) = F,
  • el bit de salida del sistema es el resultado de la operación XOR sobre los bits altos de los registros y la mayoría funciona a partir de ciertos bits de los registros:
    • R1 - 12, 14, 15,
    • R2 - 9, 13, 16,
    • R3 - 13, 16, 18.

Los cambios en el funcionamiento no son tan significativos y se refieren solo a la inicialización:

  • 64+22 ciclos se llenan con la clave de sesión y el número de cuadro también R4,
  • 1 ciclo R4(3), R4(7) y R4(10) se llenan con 1,
  • 99 ciclos con control de cambio de registro, pero sin generación de secuencia.

Se puede ver que la inicialización toma el mismo tiempo (100 ciclos sin generación se dividen en dos partes).

El algoritmo A5/3 se desarrolló en 2001 y debería reemplazar al A5/1 en la tercera generación de sistemas móviles. También se le llama algoritmo de Kasumi . Cuando se creó, se tomó como base el cifrado MISTY de Mitsubishi Corporation. Actualmente se considera que A5/3 proporciona la resistencia requerida.

El algoritmo A5/0 no contiene cifrado.

Seguridad

El desarrollo del estándar GSM significó una poderosa máquina de encriptación que no podía ser pirateada (especialmente en tiempo real). Los desarrollos utilizados, con una implementación adecuada, proporcionaron un cifrado de alta calidad de los datos transmitidos. Este es el tipo de información que se puede obtener de las empresas que distribuyen este estándar. Pero vale la pena señalar un matiz importante: escuchar conversaciones es un atributo integral utilizado por los servicios especiales. Estaban interesados ​​en la posibilidad de realizar escuchas telefónicas para sus propios fines. Por lo tanto, se realizaron cambios en el algoritmo, lo que permitió descifrar en un tiempo aceptable. Además, se modificó A5 para exportar a A5/2. El MoU (Memorandum of Understand Group Special Mobile standard) reconoce que el propósito de desarrollar A5 / 2 fue reducir la fuerza criptográfica del cifrado, sin embargo, los resultados de las pruebas oficiales dicen que no hay deficiencias conocidas del algoritmo [2] .


Vulnerabilidades conocidas

Con la llegada de los datos en el estándar A5, comenzaron los intentos de descifrar el algoritmo, así como la búsqueda de vulnerabilidades. Las características del estándar jugaron un papel muy importante, lo que debilita drásticamente la protección, a saber:

  • 10 bits de la clave se fuerzan a cero,
  • falta de enlaces cruzados entre registros (excepto para el control de turnos),
  • cifrado de la información del servicio conocida por el criptoanalista,
  • más del 40% de las claves conduce a la longitud mínima del período de la secuencia generada, a saber [3]
  • al comienzo de la sesión, se intercambian mensajes nulos (un cuadro a la vez),
  • el mismo relleno para todos los paquetes,
  • en A5/2 el movimiento lo realiza un registro separado de 17 bits de longitud.

Sobre la base de estos "agujeros" en el algoritmo, se construyen esquemas de piratería.

Ataques notables

La clave es una clave de sesión de 64 bits, se supone que se conoce el número de trama. Por lo tanto, la complejidad de un ataque de fuerza bruta es 2 64 .

Las primeras revisiones del cifrado (el trabajo de Ross Anderson) revelaron de inmediato la vulnerabilidad del algoritmo: debido a una disminución en la longitud efectiva de la clave (reducción a cero de 10 bits), la complejidad se redujo a 2 45 (en 6 órdenes de magnitud a la vez ). ). El ataque de Anderson se basa en la suposición del llenado inicial de registros cortos y en la salida de obtener el llenado del tercero.

En 1997, Jovan Golic publicó los resultados del análisis A5. Propuso una forma de determinar el llenado inicial de registros a partir de un segmento conocido de la gamma, de solo 64 bits de longitud. Este segmento se obtiene a partir de cero mensajes. El ataque tiene una dificultad media de 2 40 .

En 1999, Wagner y Goldberg demostraron fácilmente que, para abrir el sistema, basta con determinar el llenado inicial R4 por enumeración. La comprobación se realiza a expensas de cero tramas. La complejidad de este ataque es 2 17 , por lo que lleva unos segundos descifrar el cifrado en una computadora moderna.

En diciembre de 1999, un grupo de científicos israelíes ( Adi Shamir , Alex Biryukov y más tarde el estadounidense Wagner método muy no trivial, pero teóricamente muy eficaz, para abrir A5/1:

Esta es una idea muy compleja, que atacamos en muchos frentes para acumular algunas pequeñas ventajas, pero juntas, hacen una gran diferencia.adi shamir

Notas

  1. ↑ Anderson, Ross A5 - El algoritmo de cifrado GSM  (ing.) (txt)  (enlace no disponible) . sci.crypt (7 de junio de 1994). Consultado el 24 de noviembre de 2009. Archivado desde el original el 21 de septiembre de 2011.
  2. ↑ Quirke, Jeremy Seguridad en el sistema GSM (enlace no disponible) . AusMobile (1 de mayo de 2004). Archivado desde el original el 12 de julio de 2004. 
  3. ↑ Preneel, Cifrado de software Bart Fast  ( libro de Google) (diciembre de 1994). — (página 26). Consultado: 24 de noviembre de 2009.

Enlaces


 Criptosistemas simétricos
Cifrados de flujo
Red Feistel
red SP
Otro