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.
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.
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:
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 , el iésimo bit de la clave es computado con el bit menos significativo de cada registro usando un XOR:.
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.
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..
En 1997, Golic presentó un ataque basado en resolver conjuntos de ecuaciones lineales de complejidad computacional de 240.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 248 pasos para computar alrededor de 300Gb de datos.
Ese mismo año, Eli Biham y Orr Dunkelman publicaron un ataque con una complejidad de 239.91 desplazamientos del A5/1 dando 220.8 bits de texto en claro conocido. El ataque necesita 32Gb de datos almacenados despueś de una etapa previa de computación de 238.
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.
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. '
La Agencia de Seguridad Nacional Americana es capaz de craquear A5/1 de acuerdo a documentos internos que han sido publicados.