A5/1

A5/1 es un algoritmo cifrador de flujo usado para proporcionar privacidad en la comunicación al aire libre en el estándar GSM, es decir, el algoritmo que cifra la conversación entre 2 terminales GSM cuando el mensaje viaja por el aire. Inicialmente fue mantenido en secreto pero llegó al dominio público debido a sus debilidades y a la ingeniería inversa. Varias debilidades serias han sido identificadas en el algoritmo.

Historia y uso

A5/1 es usado en Europa y los Estados Unidos; un algoritmo de cifrado más débil, A5/2 es usado en países que no son considerados de confianza para tener un cifrado fuerte. A5/1 fue desarrollado en 1987, cuando GSM no era considerado aún para su uso en Europa, por su parte A5/2 fue desarrollado en 1989.

Un ingeniero en computación alemán publicó detalles de los códigos secretos utilizados en la telefonía celular para proteger las conversaciones de más de cuatro mil millones de usuarios.

Karsten Nohl, en conjunto con otros expertos, dedicó los últimos cinco meses a descifrar el algoritmo utilizado para codificar las llamadas que utilizan el Sistema Móvil Global (GSM, por sus siglas en francés).

GSM es la tecnología de mayor uso en las redes celulares alrededor del mundo.

El resultado del trabajo permitiría a cualquiera -inclusive a los delincuentes- poder interceptar llamadas telefónicas privadas.

Durante el Congreso de Comunicación Caos en Berlín, Nohl afirmó que su trabajo demostraba que la seguridad GSM era "inadecuada".

"Intentamos informar a la gente sobre esta vulnerabilidad generalizada", expresó a la BBC.

La Asociación GSM, que elaboró el algoritmo y supervisa el desarrollo de la tecnología, señaló que lo hecho por Nohl sería considerado "altamente ilegal" en el Reino Unido y muchos otros países.

"Esto no es algo que podamos tomar a la ligera", dijo una portavoz.

Nohl le comentó a la BBC que había consultado con abogados antes de la publicación y que creía que su trabajo era "legal".

Después de trabajar con unas "cuantas docenas" de personas, Nohl afirma que el material publicado podría descifrar el algoritmo A5/1, un código que los proveedores de telefonía celular vienen utilizando durante 22 años.

El código está diseñado para prevenir la interceptación de llamadas telefónicas al forzar a los móviles y estaciones de base a cambiar rápidamente de frecuencias de radio a lo ancho de 80 canales.

Es conocido que el sistema tiene una serie de debilidades, la primera seria falla fue expuesta en 1994.

Descripción

El algoritmo A5/1 usa 3 registros lineales de desplazamiento con retroalimentación (LFSR). Un registro es desplazado si su bit de reloj coincide con el bit mayoritario de los 3 bits de reloj de los registros.

La transmisión en GSM está organizada como secuencias de ráfagas. En un canal y en una dirección una ráfaga es enviada cada 4.615 milisegundos y contiene 114 bits disponibles para información. A5/1 es usado para producir por cada ráfaga una secuencia de 114 bits de flujo de clave que es utilizado para hacer un XOR junto con los 114 bits del mensaje para su modulación. A5/1 es inicializado usando una clave de 64 bits junto con un número de frame o secuencia públicamente conocido de 22 bits. Una de las debilidades del A5/1 quizás intencionada es que 10 de los 64 bits de la clave son siempre cero, con lo que la clave efectiva resultante es de 54 bits.

A5/1 está basado en una combinación de 3 registros lineales de desplazamiento con retroalimentación (LFSR) con 3 relojes desiguales. Los 3 registros se especifican como sigue:

LFSR número	Longitud en bits	Polinomio característico	Bit de reloj	Bits de tapón
1	19	x19 + x18 + x17 + x14 + 1	8	13, 16, 17, 18
2	22	x22 + x21 + 1	10	20, 21
3	23	x23 + x22 + x21 + x8 + 1	10	7, 20, 21, 22

Los bits son indizados o indexados con el bit menos significativo (LSB) a 0.

Los registros son iniciados/parados siguiendo una regla mayoritaria. Cada registro tiene asociado un bit de reloj. En cada ciclo, el bit de reloj de los 3 registros es examinado y se determina el bit mayoritario. Un registro es desplazado si el bit de reloj concuerda con el bit mayoritario. Por tanto a cada paso 2 o 3 registros son desplazados, y cada registro avanza con probabilidad 3/4.

Inicialmente, los registros son inicializados a 0, luego para 64 ciclos, los 64 bits de la clave son mezclados acorde al siguiente esquema: en un ciclo $0\leq{i}<64$, el iésimo bit de la clave es computado con el bit menos significativo de cada registro usando un XOR:.

$R[0] = R[0] \oplus K[i].$

Cada registro es entonces desplazado.

De manera similar, los 22 bits del número de secuencia o frame son añadidos en 22 ciclos. Luego el sistema entero se avanza usando el mecanismo de desplazamiento normal durante 100 ciclos, descartando la salida. Después de terminar esto, el algoritmo está listo para producir 2 secuencias de 114 bits de clave de flujo, una para cada dirección de la comunicación.

Seguridad

Se han publicado varios ataques sobre A5/1. Algunos necesitan una etapa cara de preprocesado después de la cual el código puede ser atacado en minutos o segundos. Hasta hace poco la debilidad del algoritmo han sido ataques pasivos usando la suposición de conocerse el mensaje en claro. En 2003, se identificaron debilidades más serias que podían ser explotadas en un ataque con conocimiento sólo del texto cifrado, o ataque activo. En 2006, Eli Biham y Nathan Keller hicieron demostraciones de ataques contra A5/1, A5/3 e incluso GPRS que permiten al atacante pinchar un teléfono GSM y descifrar la conversación en tiempo real, o apenas con un poco de retraso..

Ataques con conocimiento de texto claro

En 1997, Golic presentó un ataque basado en resolver conjuntos de ecuaciones lineales de complejidad computacional de 2^40.16 (las unidades están en términos del número de soluciones del sistema de ecuaciones lineales que se requiere)

En el año 2000, Alex Biryukov, Adi Shamir y David Wagner mostraron que el A5/1 puede ser criptoanalizado en tiempo real usando un ataque de sacrificio tiempo-memoria, basado en los trabajos previos de Golic (1997). Este ataque permite al atacante reconstruir la clave en 1 segundo a partir de 2 minutos de texto en plano conocido o en algunos minutos a partir de 2 segundos de conversación, pero al principio se debe completar una cara etapa de preprocesado que requiere 2⁴⁸ pasos para computar alrededor de 300Gb de datos.

Ese mismo año, Eli Biham y Orr Dunkelman publicaron un ataque con una complejidad de 2^39.91 desplazamientos del A5/1 dando 2^20.8 bits de texto en claro conocido. El ataque necesita 32Gb de datos almacenados despueś de una etapa previa de computación de 2³⁸.

Ekdahl y Johannson (2003) publicaron un ataque en el proceso de inicialización del algoritmo que rompe el A5/1 en unos pocos minutos usando 2–5 minutos de conversación de texto en claro. Este ataque no necesita etapa de preprocesado. En 2004, Maximov mejoró este resultado consiguiendo un ataque que requiere menos de un 1 minuto de computación y unos pocos segundos de conversación conocida. El ataque fue posteriormente mejorado en 2005 por Elad Barkan y Eli Biham.

Ataques en A5/1 cuando es usado en GSM

En 2003, Barkan publicó varios ataques sobre el cifrado en GSM. El primero es un ataque activo, a los teléfonos GSM se les puede obligar a usar el cifrado A5/2, mucho más débil fácilmente. A5/2 se rompe fácilmente, teniendo la ventaja de que el teléfono usa la misma clave que para el algoritmo A5/1. Un segundo ataque está esbozado, se trata de un ataque con conocimiento sólo de texto cifrado pero de sacrificio tiempo-memoria lo que requiere una gran cantidad de computación previa.

En 2006, Elad Barkan, Eli Biham y Nathan Keller publicaron la versión completa del esbozo del 2003, con ataques contra los cifradores A5/X. Los autores reivindicaban: 'Presentamos un criptoanálisis práctico sobre texto cifrado en las comunicaciones cifradas GSM, y varios ataques activos sobre los protocolos GSM. Estos ataques funcionan incluso en redes GSM que usan cifrado "irrompible". Primero describimos un ataque de sólo texto cifrado en A5/2 que requiere unas pocas docenas de milisegundos de conversación cifrada que viaja por el aire entre los celulares y hallar la clave en menos de 1 segundo con un PC convencional. Extendemos este ataque a otro algo más complejo también sobre sólo texto cifrado en A5/1. Describimos luego nuevos ataques activos sobre los protocolos de las redes que usan A5/1, A5/3, o incluso GPRS. Estos ataques explotan defectos en los protocolos usados en GSM, funcionando siempre que el teléfono móvil soporte un cifrado más débil como el A5/2. Incidimos que estos ataques son sobre los protocolos, y que son aplicables siempre que el celular soporte un cifrado más débil, por ejemplo, se pueden aplicar para atacar redes que usen A5/3 usando el criptoanálisis del A5/1. A diferencia de ataques previos sobre GSM que requieren información no realista, como texto en claro conocido, nuestro ataque es práctico y no requiere ningún conocimiento del contenido de la conversación. Además, describimos como fortalecer el ataque frente a errores. Como resultado, nuestro ataque permite a los atacantes pinchar conversaciones y descifrarlas en tiempo real, o apenas con un poco de retraso. '

Referencias

• Elad Barkan, Eli Biham and Nathan Keller, Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication, CRYPTO 2003, pp600–616 (PDF).
• Eli Biham and Orr Dunkelman, Cryptanalysis of the A5/1 GSM Stream Cipher. INDOCRYPT 2000, pp43–51.
• Alex Biryukov, Adi Shamir and David Wagner, Real Time Cryptanalysis of A5/1 on a PC, Fast Software Encryption - FSE 2000, pp1–18 (HTML).
• Patrik Ekdahl and Thomas Johansson: Another attack on A5/1. IEEE Transactions on Information Theory 49(1), pp284–289, 2003 (PDF).
• Jovan Dj. Golic, Cryptanalysis of Alleged A5 Stream Cipher, EUROCRYPT 1997, pp239–255 (HTML).
• Greg Rose, A precis of the new attacks on GSM encryption, QUALCOMM Australia, 10 September 2003, (PDF).
• Alexander Maximov, Thomas Johansson and Steve Babbage, An Improved Correlation Attack on A5/1, Selected Areas in Cryptography 2004, pp1–18.
• Elad Barkan, Eli Biham, Conditional Estimators: An Effective Attack on A5/1, Selected Areas in Cryptography 2005, pp1–19.

Enlaces externos

• A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms
• Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Versión)
• Technion team cracks GSM cellular phone encryption(Haaretz September 2003)
• Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication, by Elad Barkan, Eli Biham and Nathan Keller, julio de 2006