A5 / 1 es un cifrado de flujo utilizado para proporcionar privacidad de comunicación por aire en el estándar de telefonía celular GSM . Es uno de los siete algoritmos que se especificaron para uso GSM. [1] Inicialmente se mantuvo en secreto, pero se convirtió en conocimiento público a través de filtraciones e ingeniería inversa . Se han identificado una serie de debilidades graves en el cifrado.A5 / 1 es un cifrado de flujo utilizado para proporcionar privacidad de comunicación por aire en el estándar de telefonía celular GSM . Es uno de los siete algoritmos que se especificaron para uso GSM. [1] Inicialmente se mantuvo en secreto, pero se convirtió en conocimiento público a través de filtraciones e ingeniería inversa . Se han identificado una serie de debilidades graves en el cifrado.
Historia y uso [ editar ]
A5 / 1 se utiliza en Europa y Estados Unidos. A5 / 2 fue un debilitamiento deliberado del algoritmo para ciertas regiones de exportación. [2] 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; para 2014, era de 7,2 mil millones. [3]
El investigador de seguridad Ross Anderson informó en 1994 que "a mediados de la década de 1980 hubo una disputa excelente entre las agencias de inteligencia de señales de la OTAN sobre si el cifrado GSM debería ser fuerte o no. Los alemanes dijeron que sí, ya que compartían una larga frontera con el Pacto de Varsovia , pero los otros países no se sentían así, y el algoritmo tal como se presenta ahora es un diseño francés ". [4]
Descripción [ editar ]
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 secuencia 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 de campo 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 resultó en una longitud de clave efectivade 54 bits. Esta debilidad se rectificó con la introducción de Comp128v3 que produce claves de 64 bits adecuadas. 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 A5 / 3 se usa 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 sincronización 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 registros se registran en una parada / marcha usando una regla de mayoría. Cada registro tiene un bit de reloj asociado. En cada ciclo, se examina el bit de sincronización de los tres registros y se determina el bit de mayoría. Se registra un registro si el bit de sincronización coincide con el bit de la mayoría. Por lo tanto, en cada paso se registran al menos dos o tres registros, y cada registro registra pasos con probabilidad 3/4.
Inicialmente, los registros se establecen en cero. Luego, durante 64 ciclos, la clave secreta de 64 bits se mezcla de acuerdo con el siguiente esquema: en ciclo, La i se añade ésimo bit clave para el bit menos significativo de cada registro usando XOR -
![R [0] = R [0] \ oplus K [i].](https://wikimedia.org/api/rest_v1/media/math/render/svg/756ea4bf1c69618bd865b725f0f8b99b79e4e701)
Cada registro se sincroniza.
Del mismo modo, los 22 bits del número de trama se suman en 22 ciclos. Luego, todo el sistema se sincroniza utilizando el mecanismo de sincronización mayoritaria 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 clave de salida, primero 114 para enlace descendente, último 114 para enlace ascendente.
Seguridad [ editar ]
Se han publicado varios ataques contra A5 / 1, y la Agencia de Seguridad Nacional de Estados Unidos puede descifrar rutinariamente los mensajes A5 / 1 de acuerdo con los documentos internos publicados. [5]
Algunos ataques requieren una etapa de preprocesamiento costosa después de la cual el cifrado se puede romper en minutos o segundos. Hasta hace poco, las debilidades habían sido los ataques pasivos utilizando el supuesto de texto sin formato conocido . En 2003, se identificaron debilidades más serias que pueden ser explotadas en el escenario de solo 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 aprovechar las 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 eran seguros durante al menos 15 años. Ahora se cree que 128 bits también serían 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 era para permitir que el servicio secreto británico escuchara 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 proteger contra el espionaje de Alemania Oriental, por lo que el compromiso se convirtió en una longitud de clave de 54 bits. [6]
Ataques de texto sin formato conocidos [ editar ]
Ross Anderson propuso el primer ataque contra el A5 / 1 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 manera, se determina la sincronización de los tres registros y se puede calcular la segunda mitad de R3. [4]
En 1997, Golic presentó un ataque basado en la resolución de conjuntos de ecuaciones lineales que tiene una complejidad temporal 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 utilizando un ataque de compensación de memoria de tiempo, [7] basado en el trabajo anterior de Jovan Golic. [8] Una compensación permite a un atacante reconstruir la clave en un segundo a partir de dos minutos de texto plano conocido o en varios minutos a partir de dos segundos de texto plano 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 contra A5 / 1 con una complejidad de trabajo total de 2 39.91 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 . [9]
Ekdahl y Johansson publicaron un ataque al procedimiento de inicialización que rompe A5 / 1 en unos minutos usando dos a cinco minutos de texto sin formato de conversación. [10] 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ómputos y unos pocos segundos de conversación conocida". El ataque fue mejorado por Elad Barkan y Eli Biham en 2005. [11]
Ataques en A5 / 1 como se usa en GSM [ editar ]
En 2003, Barkan et al. Publicó varios ataques al cifrado GSM. [12] El primero es un ataque activo. Se puede convencer a los teléfonos GSM de 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 texto cifrado que requiere una gran cantidad de precomputación.
En 2006, Elad Barkan , Eli Biham , Nathan Keller publicaron la versión completa de su artículo de 2003, con ataques contra los cifrados A5 / X. Los autores afirman: [13]
En 2007, las universidades de Bochum y Kiel comenzaron un proyecto de investigación para crear un acelerador criptográfico basado en FPGA masivamente paralelo COPACOBANA . COPACOBANA fue la primera solución disponible comercialmente [14] que utilizó técnicas rápidas de intercambio de memoria de tiempo que podrían usarse para atacar los algoritmos populares 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 contra A5 / 1. El ataque requiere la construcción de una gran tabla de búsqueda 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 encriptado con A5 / 1, y dentro de unos 3-5 minutos obtener la clave de encriptación y, por lo tanto, escuchar la llamada y lea el SMS en claro. Pero las mesas no fueron liberadas. [15]
Un esfuerzo similar, el A5 / 1 Cracking Project , fue anunciado en la conferencia de seguridad de Black Hat 2009 por los criptógrafos Karsten Nohl y Sascha Krißler. Creó las tablas de búsqueda utilizando GPUPU 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 cifra con un tamaño de clave de hasta 64 bits. [dieciséis]
En diciembre de 2009, Chris Paget y Karsten Nohl anunciaron las tablas de ataque del 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 distinguidos. Estas tablas constituyeron solo partes de la tabla completa de 1.7 TB y se calcularon durante tres meses utilizando 40 nodos CUDA distribuidos y luego se publicaron a través de BitTorrent y Google Drive que es proporcionado por el miembro de la comunidad Farid Nasiri [15] [16] [17] [18 ] [19] Más recientemente, el proyecto ha anunciado un cambio a un código ATI Evergreen más rápido , junto con un cambio en el formato de las tablas yFrank A. Stevenson anunció interrupciones de A5 / 1 utilizando las tablas generadas por ATI. [20]
Los documentos filtrados por Edward Snowden en 2013 afirman que la NSA "puede procesar A5 / 1 encriptado".
A5 / 2 es un cifrado de flujo utilizado para proporcionar privacidad de voz en el protocolo de telefonía celular GSM . Fue utilizado para la exportación en lugar del relativamente fuerte (pero aún débil) A5 / 1 . Es uno de los siete algoritmos de cifrado A5 que se han definido para uso GSM. [1]
El cifrado se basa en una combinación de cuatro registros de desplazamiento de retroalimentación lineal con sincronización irregular y un combinador no lineal .
En 1999, Ian Goldberg y David A. Wagner criptoanalizaron A5 / 2 en el mismo mes en que se publicó, y mostraron que era extremadamente débil, tanto que el equipo de gama baja probablemente pueda romperlo en tiempo real.
Desde el 1 de julio de 2006, la GSMA (Asociación GSM) ordenó que los teléfonos móviles GSM ya no admitan el cifrado A5 / 2, debido a su debilidad, y al hecho de que la asociación 3GPP considera que A5 / 1 es obligatorio . En julio de 2007, el 3GPP aprobó una solicitud de cambio para prohibir la implementación de A5 / 2 en cualquier teléfono móvil nuevo. Si la red no es compatible con A5 / 1, o cualquier otro algoritmo A5 implementado por el teléfono, entonces se puede utilizar una conexión no cifrada.
Abraham "Abe" Sinkov (22 de agosto de 1907 - 19 de enero de 1998) fue un criptoanalista estadounidense . Uno de los primeros empleados del Servicio de Inteligencia de Señales del Ejército de EE. UU . , Ocupó varios puestos de liderazgo durante la Segunda Guerra Mundial, haciendo la transición a la nueva Agencia de Seguridad Nacional después de la guerra, donde se convirtió en subdirector. Después de retirarse en 1962, enseñó matemáticas en la Universidad Estatal de Arizona .
Biografía [ editar ]
Sinkov era hijo de inmigrantes judíos Morris (Mordechai Eliezer) y Ethel (née Etel Constantinowsky) [1] de Alejandría, Rusia , que ahora es Oleksandriya , Óblast de Kirovohrad , Ucrania [2] . Sinkov nació en Filadelfia , pero creció en Brooklyn . Después de graduarse de Boys High School , obtuvo su licenciatura en matemáticas en el City College de Nueva York . (Por coincidencia, uno de sus amigos cercanos en Boys High y CCNY fue Solomon Kullback ). Sr. Sinkov enseñó en la ciudad de Nueva York escuelas, pero estaba descontento con las condiciones de trabajo y ansioso por usar su conocimiento matemático de manera práctica.
Carrera temprana [ editar ]
La oportunidad para un cambio de carrera llegó en 1930. Sinkov y Kullback tomaron el examen del Servicio Civil y se colocaron en alto. Ambos recibieron cartas misteriosas de Washington preguntando sobre su conocimiento de idiomas extranjeros. Sinkov sabía francés y kullback, español . Esto era aceptable para su posible empleador, y se les ofreció puestos como criptoanalistas junior. Aunque ninguno estaba seguro de lo que hacía un criptoanalista, aceptaron.
La pequeña organización del Servicio de Inteligencia de Señales (SIS) (Sinkov y Kullback eran el tercer y cuarto empleado allí) tenía la misión principal de compilar códigos y cifrados para uso del Ejército de los EE . UU . Su tarea secundaria era intentar resolver códigos y códigos extranjeros seleccionados; esto no se hizo necesariamente con fines de inteligencia, sino para mantener a los criptoanalistas al tanto de los nuevos desarrollos en el campo.
William Friedman sometió a sus nuevos empleados a un riguroso curso de estudio de su propio diseño en criptología, llevándolos a altos niveles de habilidad para crear y descifrar códigos y cifras. Friedman también alentó otros esfuerzos de superación personal: sus empleados entrenaron veranos en un campamento en Ft. Meade para ganar comisiones en las reservas militares. Tanto Sinkov como Kullback también recibieron doctorados en matemáticas. Sinkov recibió su doctorado en matemáticas en 1933 de la Universidad George Washington . En 1936, Sinkov fue asignado a la Zona del Canal de Panamá , donde estableció el primer sitio de intercepción permanente del Ejército de los EE. UU. Fuera de los Estados Unidos continentales .
Segunda Guerra Mundial [ editar ]
El SIS creció lentamente a principios de la década de 1930. Sin embargo, los éxitos contra los códigos diplomáticos japoneses que utilizan sistemas de máquinas después de 1935 proporcionaron al gobierno de los Estados Unidos información crítica durante una serie de crisis. Este éxito también tuvo consecuencias prácticas para el SIS. Por primera vez, el SIS comenzó a ganar el respeto de sus superiores militares. Una vez que los militares entendieron que esta pequeña organización podía leer mensajes sensibles de un adversario potencial, el Cuerpo de Señales aumentó el presupuesto del SIS y autorizó una mayor contratación de criptoanalistas.
En 1940, a pesar de que Estados Unidos no era oficialmente un combatiente, Estados Unidos y Gran Bretaña iniciaron intercambios de material técnico. En esto se incluyó un intercambio prudente de información criptológica: los británicos por etapas revelaron el alcance de su considerable éxito contra los sistemas alemanes de alto nivel, y los EE. UU. Su éxito equivalente contra los japoneses. Esto llevó a un nivel sin precedentes de cooperación en inteligencia de comunicación ( COMINT ) entre los dos países durante la guerra, lo que resultó en más personal, mayores presupuestos y una gama más amplia de actividades para la organización.
Misión Sinkov [ editar ]
En enero de 1941, mientras Gran Bretaña luchaba contra la Alemania nazi, pero casi un año antes de que Estados Unidos ingresara a la Segunda Guerra Mundial , el Capitán Sinkov fue seleccionado como miembro de una delegación en el Reino Unido para el intercambio inicial de información sobre los respectivos programas criptológicos de los dos países. . La delegación regresó en abril con resultados mixtos para informar. A Sinkov y sus colegas se les mostró Bletchley Park , la sede secreta de la criptología británica, e intercambiaron información sobre los sistemas alemanes y japoneses. Todavía no está claro cuánto le dijeron a la delegación estadounidense sobre el éxito británico contra la máquina alemana Enigma, pero Sinkov luego recordó que se les informó sobre el problema de Enigma poco tiempo antes de que la delegación se fuera, y que los detalles eran poco precisos. Sin embargo, la misión al Reino Unido fue un éxito en general y ayudó a dar a las relaciones criptológicas entre Estados Unidos y el Reino Unido una base práctica sólida.
Después del ataque japonés a Pearl Harbor el 7 de diciembre de 1941, los japoneses también atacaron las Islas Filipinas . Al general Douglas MacArthur se le ordenó abandonar Filipinas y restablecer el cuartel general del ejército de los Estados Unidos en Australia , desde donde podrían lanzarse contraataques. MacArthur reconoció la necesidad de apoyo criptológico, por lo tanto, el 15 de abril de 1942, estableció el Buró Central (CB), reuniéndolo de elementos refugiados de criptólogos estadounidenses evacuados de Filipinas, criptólogos australianos y otros contingentes aliados . CB comenzó en Melbourne , luego se mudó a Brisbane .
En julio de 1942, el comandante Sinkov llegó a Melbourne como comandante del destacamento estadounidense en la Oficina Central . El director de CB en papel era el general Spencer B. Akin , el jefe de señales de MacArthur, pero el general Akin en la práctica rara vez visitaba la organización. Había trabajado con Sinkov en Washington y en Panamá , y con confianza dejó las operaciones de CB bajo su control.
Sinkov, quien demostró fuertes cualidades organizativas y de liderazgo, además de sus habilidades matemáticas, reunió a este grupo de estadounidenses y australianos, que también representan diferentes servicios militares de sus países, en una unidad cohesiva. CB se convirtió rápidamente en un productor confiable de Signals Intelligence (SIGINT) para MacArthur y sus comandantes de alto rango. Este SIGINT permitió un éxito constante en la guerra aérea contra los japoneses y permitió a MacArthur ganar algunas victorias impresionantes en la campaña terrestre en Nueva Guinea y Filipinas.
Posguerra [ editar ]
Después de la guerra, Sinkov se reincorporó al SIS, ahora renombrado Agencia de Seguridad del Ejército y, en 1949, cuando se formó la Agencia de Seguridad de las Fuerzas Armadas (AFSA), la primera organización criptológica centralizada en los Estados Unidos, Sinkov se convirtió en jefe de Seguridad de Comunicaciones programa. Permaneció en este puesto cuando AFSA hizo la transición a la Agencia de Seguridad Nacional .
En 1954, Sinkov se convirtió en el segundo funcionario de la NSA en asistir al National War College (el primero fue Louis Tordella ). A su regreso, se convirtió en subdirector de producción, intercambiando efectivamente trabajos con su antiguo colega Frank Rowlett . Sinkov se retiró de la NSA en 1962.
En 1966, escribió Criptoanálisis elemental: un enfoque matemático , uno de los primeros libros sobre el tema, dirigido a estudiantes de secundaria y disponible para el público en general.
Retiro [ editar ]
Abraham Sinkov vivió retirado en Arizona después de dos carreras, 32 años en la NSA (y sus predecesores), seguido de un nombramiento como profesor de matemáticas en la Universidad Estatal de Arizona .
No hay comentarios:
Publicar un comentario