A5 / 1 es un cifrado de flujo utilizado para proporcionar privacidad en las comunicaciones por aire en el estándar de telefonía celular GSM . Es una de varias implementaciones del protocolo de seguridad A5. Inicialmente se mantuvo en secreto, pero se hizo de conocimiento público a través de filtraciones e ingeniería inversa . Se han identificado varias deficiencias graves en el cifrado.
Historia y uso
A5 / 1 se utiliza en Europa y Estados Unidos. A5 / 2 fue un debilitamiento deliberado del algoritmo para ciertas regiones de exportación. [1] A5 / 1 se desarrolló en 1987, cuando GSM aún no se consideraba para su uso fuera de Europa, y A5 / 2 se desarrolló en 1989. Aunque inicialmente ambos se mantuvieron en secreto, el diseño general se filtró en 1994 y los algoritmos fueron completamente ingeniería inversa en 1999 por Marc Briceno desde un teléfono GSM. En 2000, alrededor de 130 millones de clientes GSM confiaron en A5 / 1 para proteger la confidencialidad de sus comunicaciones de voz; en 2014, fue de 7.200 millones. [2]
El investigador de seguridad Ross Anderson informó en 1994 que "hubo una tremenda disputa entre las agencias de inteligencia de señales de la OTAN a mediados de la década de 1980 sobre si el cifrado GSM debería ser fuerte o no. Los alemanes dijeron que debería serlo, ya que compartían una larga frontera con el Pacto de Varsovia , pero los otros países no se sintieron así, y el algoritmo que se utiliza ahora es un diseño francés ". [3]
Descripción
Una transmisión GSM se organiza como secuencias de ráfagas . En un canal típico y en una dirección, se envía una ráfaga cada 4.615 milisegundos y contiene 114 bits disponibles para información. A5 / 1 se utiliza para producir para cada ráfaga una secuencia de 114 bits de flujo de claves que se XOR con los 114 bits antes de la modulación. A5 / 1 se inicializa utilizando una clave de 64 bits junto con un número de trama de 22 bits conocido públicamente. Las implementaciones GSM más antiguas que usaban Comp128v1 para la generación de claves tenían 10 de los bits de clave fijos en cero, lo que resultaba en una longitud de clave efectiva de 54 bits. Esta debilidad se corrigió con la introducción de Comp128v3, que produce claves adecuadas de 64 bits. Cuando se opera en modo GPRS / EDGE, la modulación de radio de mayor ancho de banda permite tramas más grandes de 348 bits, y luego se usa A5 / 3 en un modo de cifrado de flujo para mantener la confidencialidad.
A5 / 1 se basa en una combinación de tres registros de desplazamiento de retroalimentación lineal (LFSR) con reloj irregular. Los tres registros de desplazamiento se especifican de la siguiente manera:
Número LFSR | Longitud en bits | Polinomio de retroalimentación | Bit de reloj | Bits roscados |
---|---|---|---|---|
1 | 19 | 8 | 13, 16, 17, 18 | |
2 | 22 | 10 | 20, 21 | |
3 | 23 | 10 | 7, 20, 21, 22 |
Los bits se indexan con el bit menos significativo (LSB) como 0.
Los registros se cronometran de forma intermitente utilizando una regla de mayoría. Cada registro tiene un bit de reloj asociado. En cada ciclo, se examina el bit de reloj de los tres registros y se determina el bit mayoritario. Un registro se sincroniza si el bit de sincronización concuerda con el bit mayoritario. Por lo tanto, en cada paso se sincronizan al menos dos o tres registros, y cada registro avanza con probabilidad 3/4.
Inicialmente, los registros se ponen a cero. Luego, durante 64 ciclos, la clave secreta K de 64 bits se mezcla de acuerdo con el siguiente esquema: en ciclo, el i- ésimo bit de clave se agrega al bit menos significativo de cada registro usando XOR -
A continuación, se sincroniza cada registro.
De manera similar, los 22 bits del número de trama se agregan en 22 ciclos. Luego, todo el sistema se sincroniza utilizando el mecanismo de reloj mayoritario normal durante 100 ciclos, con la salida descartada. Una vez completado esto, el cifrado está listo para producir dos secuencias de 114 bits de flujo de claves de salida, el primero 114 para el enlace descendente y el último 114 para el enlace ascendente.
Seguridad
Se han publicado varios ataques a A5 / 1, y la Agencia de Seguridad Nacional de Estados Unidos puede descifrar de forma rutinaria los mensajes A5 / 1 de acuerdo con los documentos internos publicados. [4]
Algunos ataques requieren una costosa etapa de preprocesamiento después de la cual el cifrado se puede romper en minutos o segundos. Originalmente, las debilidades eran ataques pasivos que utilizaban el supuesto de texto plano conocido . En 2003, se identificaron debilidades más graves que pueden ser explotadas en el escenario de sólo texto cifrado o por un atacante activo. En 2006, Elad Barkan, Eli Biham y Nathan Keller demostraron ataques contra A5 / 1, A5 / 3 o incluso GPRS que permiten a los atacantes acceder a conversaciones de teléfonos móviles GSM y descifrarlas en tiempo real o en cualquier momento posterior.
Según el profesor Jan Arild Audestad, en el proceso de estandarización que comenzó en 1982, se propuso originalmente que A5 / 1 tuviera una longitud de clave de 128 bits. En ese momento, se proyectaba que 128 bits serían seguros durante al menos 15 años. Ahora se cree que 128 bits de hecho también seguirían siendo seguros hasta el advenimiento de la computación cuántica . Audestad, Peter van der Arend y Thomas Haug dicen que los británicos insistieron en un cifrado más débil, y Haug dijo que el delegado británico le dijo que esto permitiría que el servicio secreto británico escuchara a escondidas más fácilmente. Los británicos propusieron una longitud de clave de 48 bits, mientras que los alemanes occidentales querían un cifrado más fuerte para protegerse contra el espionaje de Alemania Oriental, por lo que el compromiso se convirtió en una longitud de clave de 54 bits. [5]
Ataques de texto sin formato conocidos
El primer ataque al A5 / 1 fue propuesto por Ross Anderson en 1994. La idea básica de Anderson era adivinar el contenido completo de los registros R1 y R2 y aproximadamente la mitad del registro R3. De esta forma, se determina la sincronización de los tres registros y se puede calcular la segunda mitad de R3. [3]
En 1997, Golic presentó un ataque basado en la resolución de conjuntos de ecuaciones lineales que tiene una complejidad de tiempo de 2 40,16 (las unidades están en términos de número de soluciones de un sistema de ecuaciones lineales que se requieren).
En 2000, Alex Biryukov , Adi Shamir y David Wagner demostraron que A5 / 1 se puede criptoanalizar en tiempo real usando un ataque de compensación de tiempo-memoria, [6] basado en un trabajo anterior de Jovan Golic. [7] Una compensación permite a un atacante reconstruir la clave en un segundo a partir de dos minutos de texto sin formato conocido o en varios minutos a partir de dos segundos de texto sin formato conocido, pero primero debe completar una costosa etapa de preprocesamiento que requiere 2 48 pasos para calcular 300 GB de datos. Son posibles varias compensaciones entre el preprocesamiento, los requisitos de datos, el tiempo de ataque y la complejidad de la memoria.
El mismo año, Eli Biham y Orr Dunkelman también publicaron un ataque a A5 / 1 con una complejidad de trabajo total de 2 39,91 relojes A5 / 1 dados 2 20,8 bits de texto plano conocido . El ataque requiere 32 GB de almacenamiento de datos después de una etapa de precomputación de 2 38 . [8]
Ekdahl y Johansson publicaron un ataque al procedimiento de inicialización que rompe A5 / 1 en unos pocos minutos usando de dos a cinco minutos de texto plano de conversación. [9] Este ataque no requiere una etapa de preprocesamiento. En 2004, Maximov et al. mejoró este resultado a un ataque que requirió "menos de un minuto de cálculos y unos segundos de conversación conocida". El ataque fue mejorado aún más por Elad Barkan y Eli Biham en 2005. [10]
Ataques a A5 / 1 como se usa en GSM
En 2003, Barkan et al. publicó varios ataques al cifrado GSM. [11] El primero es un ataque activo. Se puede convencer a los teléfonos GSM para que utilicen brevemente el cifrado A5 / 2, mucho más débil . A5 / 2 se puede romper fácilmente y el teléfono usa la misma clave que para el algoritmo A5 / 1 más fuerte. Se describe un segundo ataque en A5 / 1, un ataque de compensación de memoria de tiempo de solo texto cifrado que requiere una gran cantidad de cálculo previo.
En 2006, Elad Barkan , Eli Biham , Nathan Keller publicaron la versión completa de su artículo de 2003, con ataques contra cifrados A5 / X. Los autores afirman: [12]
Presentamos un criptoanálisis muy práctico de solo texto cifrado de la comunicación encriptada GSM y varios ataques activos a los protocolos GSM. Estos ataques pueden incluso penetrar en redes GSM que utilizan cifrados "irrompibles". Primero describimos un ataque de solo texto cifrado en A5 / 2 que requiere unas pocas docenas de milisegundos de conversación celular encriptada fuera del aire y encuentra la clave correcta en menos de un segundo en una computadora personal. Extendemos este ataque a un ataque de solo texto cifrado (más complejo) en A5 / 1. Luego describimos nuevos ataques (activos) en los protocolos de redes que usan A5 / 1, A5 / 3 o incluso GPRS. Estos ataques aprovechan las fallas en los protocolos GSM y funcionan siempre que el teléfono móvil admita un cifrado débil como A5 / 2. Destacamos que estos ataques son a los protocolos, por lo que son aplicables siempre que el teléfono celular soporte un cifrado débil, por ejemplo, también son aplicables para atacar redes A5 / 3 utilizando el criptoanálisis de A5 / 1. A diferencia de los ataques anteriores a GSM que requieren información poco realista, como los largos períodos de texto plano conocidos, nuestros ataques son muy prácticos y no requieren ningún conocimiento del contenido de la conversación. Además, describimos cómo fortalecer los ataques para resistir errores de recepción. Como resultado, nuestros ataques permiten a los atacantes acceder a conversaciones y descifrarlas en tiempo real o en cualquier momento posterior.
En 2007, las universidades de Bochum y Kiel iniciaron un proyecto de investigación para crear un acelerador criptográfico COPACOBANA basado en FPGA masivamente paralelo . COPACOBANA fue la primera solución disponible comercialmente [13] que utilizó técnicas rápidas de compensación de tiempo-memoria que podrían usarse para atacar los populares algoritmos A5 / 1 y A5 / 2, utilizados en el cifrado de voz GSM, así como el Estándar de cifrado de datos ( DES). También permite ataques de fuerza bruta contra GSM eliminando la necesidad de grandes tablas de búsqueda precalculadas.
En 2008, el grupo The Hackers Choice lanzó un proyecto para desarrollar un ataque práctico en A5 / 1. El ataque requiere la construcción de una gran tabla de consulta de aproximadamente 3 terabytes. Junto con las capacidades de escaneo desarrolladas como parte del proyecto hermano, el grupo esperaba poder grabar cualquier llamada GSM o SMS cifrado con A5 / 1, y en unos 3-5 minutos obtener la clave de cifrado y, por lo tanto, escuchar la llamada y leer el SMS en claro. Pero las tablas no fueron liberadas. [14]
Los criptógrafos Karsten Nohl y Sascha Krißler anunciaron un esfuerzo similar, el Proyecto de craqueo A5 / 1 , en la conferencia de seguridad Black Hat de 2009 . Creó las tablas de búsqueda utilizando GPGPU de Nvidia a través de una arquitectura informática distribuida de igual a igual . A partir de mediados de septiembre de 2009, el proyecto ejecutó el equivalente a 12 Nvidia GeForce GTX 260. Según los autores, el enfoque se puede utilizar en cualquier cifrado con un tamaño de clave de hasta 64 bits. [15]
En diciembre de 2009, Chris Paget y Karsten Nohl anunciaron las tablas de ataque A5 / 1 Cracking Project para A5 / 1. Las tablas utilizan una combinación de técnicas de compresión, incluidas tablas de arco iris y cadenas de puntos distinguidas. Estas tablas constituían solo partes de la tabla completa de 1,7 TB y se habían calculado durante tres meses utilizando 40 nodos CUDA distribuidos y luego se habían publicado en BitTorrent . [14] [15] [16] [17] Más recientemente, el proyecto anunció un cambio a un código ATI Evergreen más rápido , junto con un cambio en el formato de las tablas y Frank A. Stevenson anunció rupturas de A5 / 1 usando el ATI tablas generadas. [18]
Los documentos filtrados por Edward Snowden en 2013 afirman que la NSA "puede procesar A5 / 1 cifrado". [19]
Ver también
- A5 / 2
- KASUMI , también conocido como A5 / 3
- Algoritmo de cifrado de mensajes móviles
Notas
- ^ Quirke, Jeremy (1 de mayo de 2004). "Seguridad en el sistema GSM" (PDF) . AusMobile. Archivado desde el original (PDF) el 12 de julio de 2004 . Consultado el 8 de septiembre de 2008 .
- ^ "Hay oficialmente más dispositivos móviles que personas en el mundo" . The Independent . 7 de octubre de 2014 . Consultado el 19 de diciembre de 2017 .
- ^ a b Ross Anderson (17 de junio de 1994). "A5 (Era: HACKING DE TELÉFONOS DIGITALES)" . Grupo de noticias : uk.telecom . Usenet: [email protected] .
- ^ NSA capaz de descifrar criptografía de teléfono móvil A5 / 1 - Slashdot
- ^ https://www.aftenposten.no/verden/i/Olkl/sources-we-were-pressured-to-weaken-the-mobile-security-in-the-80s
- ^ Biryukov, Alex ; Adi Shamir ; David Wagner . "Criptoanálisis en tiempo real de A5 / 1 en una PC" . Cifrado de software rápido — FSE 2000 : 1–18.
- ^ Golic, Jovan Dj. (1997). "Criptoanálisis del supuesto cifrado de secuencia A5" (PDF) . Eurocrypt 1997 : 239–55. Archivado desde el original (PDF) el 15 de julio de 2010 . Consultado el 13 de enero de 2016 .
- ^ Biham, Eli; Orr Dunkelman (2000). "Criptoanálisis del cifrado de flujo GSM A5 / 1". Indocrypt 2000 . Apuntes de conferencias en Ciencias de la Computación. 1977 : 43–51. doi : 10.1007 / 3-540-44495-5_5 . ISBN 978-3-540-41452-0.
- ^ Ekdahl, Patrik; Thomas Johansson (2003). "Otro ataque a A5 / 1" (PDF) . Transacciones IEEE sobre teoría de la información . 49 (1): 284–89. doi : 10.1109 / TIT.2002.806129 . Archivado desde el original (PDF) el 25 de mayo de 2005.
- ^ Barkan, Elad; Eli Biham (2005). "Estimadores condicionales: un ataque eficaz en A5 / 1". Áreas seleccionadas en criptografía 2005 : 1–19.
- ^ Barkan, Elad; Eli Biham ; Nathan Keller (2003). "Criptoanálisis instantáneo de solo texto cifrado de comunicación cifrada GSM" (PDF) . Cripto 2003 . Apuntes de conferencias en Ciencias de la Computación. 2729 : 600–16. doi : 10.1007 / 978-3-540-45146-4_35 . ISBN 978-3-540-40674-7.
- ^ Barkan, Elad; Eli Biham; Nathan Keller. "Criptoanálisis instantáneo de sólo texto cifrado de comunicación cifrada GSM por Barkan y Biham of Technion (versión completa)" (PDF) .
- ^ Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp (2008). "Criptoanálisis con COPACOBANA" (PDF) . Transacciones IEEE en computadoras . 57 (11): 1498-1513. doi : 10.1109 / TC.2008.80 . S2CID 8754598 .
- ^ a b Nohl, Karsten; Chris Paget (27 de diciembre de 2009). GSM: ¿SRSLY? . 26 ° Congreso de Comunicación del Caos (26C3). Archivado desde el original el 6 de enero de 2010 . Consultado el 30 de diciembre de 2009 .
- ^ a b "Copia archivada" (PDF) . Archivado desde el original (PDF) el 26 de julio de 2011 . Consultado el 29 de diciembre de 2009 .CS1 maint: copia archivada como título ( enlace )Subvirtiendo la base de seguridad de GSM. Karsten Nohl y Sascha Krißler
- ^ O'Brien, Kevin (28 de diciembre de 2009). "Se divulga el código de cifrado del teléfono móvil" . New York Times . Archivado desde el original el 29 de abril de 2011 . Consultado el 29 de diciembre de 2009 .
- ^ McMillan, Robert. "Los piratas informáticos muestran que es fácil fisgonear en una llamada GSM" . Servicio de noticias IDG .
- ^ Frank A. Stevenson (1 de mayo de 2010). "Grietas empiezan a aparecer en A5 / 1" . Archivado desde el original el 6 de marzo de 2012.
- ^ Timberg, Craig; Soltani, Ashkan (13 de diciembre de 2013). "Al descifrar el código del teléfono celular, la NSA tiene la capacidad de decodificar conversaciones privadas" . The Washington Post . Consultado el 28 de septiembre de 2016 .
Referencias
- Rose, Greg (10 de septiembre de 2003). "Un resumen de los nuevos ataques a la encriptación GSM" (PDF) . QUALCOMM Australia. Archivado desde el original (PDF) el 27 de septiembre de 2011 . Consultado el 17 de octubre de 2004 .
- Maximov, Alexander; Thomas Johansson; Steve Babbage (2004). "Un ataque de correlación mejorado en A5 / 1". Áreas seleccionadas en criptografía 2004 : 1–18.
enlaces externos
- Briceno, Marc; Ian Goldberg; David Wagner (23 de octubre de 1999). "Una implementación pedagógica de los algoritmos de encriptación de" privacidad de voz "GSM A5 / 1 y A5 / 2" . Archivado desde el original el 8 de octubre de 2018 . Consultado el 23 de enero de 2017 .
- "Gran falla GSM permite a los piratas informáticos escuchar llamadas de voz" . 25 de agosto de 2009. Archivado desde el original el 14 de octubre de 2009.
- Horesh, Hadar (3 de septiembre de 2003). "El equipo de Technion descifra el cifrado de teléfonos móviles GSM" (PDF) . Haaretz . Archivado desde el original (PDF) el 3 de marzo de 2016 . Consultado el 15 de septiembre de 2019 .
- Barkan, Elad; Eli Biham; Nathan Keller (julio de 2006). "Criptoanálisis instantáneo de sólo texto cifrado de comunicación cifrada GSM (Informe técnico CS-2006-07)" .
- "Página de inicio de Nathan Keller" . Archivado desde el original el 4 de junio de 2008.
- "SVG animado que muestra cifrado de flujo A5 / 1" . Archivado desde el original el 26 de marzo de 2012.