Criptoanálisis

Los ataques criptoanalíticos pueden clasificarse según el tipo de información de la que dispone el atacante. Como punto de partida básico, se suele asumir que, a efectos de análisis, se conoce el algoritmo general ; esta es la máxima de Shannon : «el enemigo conoce el sistema» ^{[ 2 ]} , equivalente a su vez al principio de Kerckhoffs ^{[ 3 ]} . En la práctica, esta suposición es razonable: a lo largo de la historia, existen innumerables ejemplos de algoritmos secretos que se han hecho públicos, ya sea por espionaje , traición o ingeniería inversa . (Y en ocasiones, se han descifrado cifrados mediante deducción pura; por ejemplo, el cifrado alemán de Lorenz y el código púrpura japonés , así como diversos esquemas clásicos) ^{[ 4 ].}

• Solo texto cifrado : el criptoanalista solo tiene acceso a una colección de textos cifrados o textos codificados .
• Texto plano conocido : el atacante tiene un conjunto de textos cifrados para los que conoce el texto plano correspondiente .
• Texto plano elegido ( texto cifrado elegido ): el atacante puede obtener los textos cifrados (textos planos) correspondientes a un conjunto arbitrario de textos planos (textos cifrados) de su elección.
• Ataque adaptativo de texto plano elegido : similar a un ataque de texto plano elegido, excepto que el atacante puede elegir textos planos subsiguientes basándose en información aprendida de cifrados anteriores, de forma similar al ataque adaptativo de texto cifrado elegido .
• Ataque de clave relacionada : Similar a un ataque de texto plano elegido, con la diferencia de que el atacante puede obtener textos cifrados con dos claves diferentes. Las claves son desconocidas, pero se conoce la relación entre ellas; por ejemplo, dos claves que difieren en un bit.

Los ataques también pueden caracterizarse por los recursos que requieren. Estos recursos incluyen: ^{[ 5 ]}

• Tiempo: el número de pasos de cálculo (por ejemplo, cifrados de prueba) que deben realizarse.
• Memoria: la cantidad de almacenamiento necesaria para realizar el ataque.
• Datos: la cantidad y el tipo de textos planos y textos cifrados necesarios para un método específico.

A veces es difícil predecir estas cantidades con precisión, especialmente cuando el ataque no es práctico de implementar para realizar pruebas. Pero los criptoanalistas académicos suelen proporcionar al menos el orden de magnitud estimado de la dificultad de sus ataques, diciendo, por ejemplo, "Colisiones SHA-1 ahora 2 ⁵² ". ^{[ 6 ]}

Bruce Schneier señala que incluso los ataques computacionalmente impracticables pueden considerarse fallos de seguridad: «Romper un cifrado simplemente significa encontrar una debilidad en el cifrado que pueda explotarse con una complejidad menor que la fuerza bruta. No importa que la fuerza bruta pueda requerir 2¹²⁸ ^cifrados ; un ataque que requiera ^2¹¹⁰ cifrados se consideraría un fallo de seguridad... En pocas palabras, un fallo de seguridad puede ser simplemente una debilidad de certificación: evidencia de que el cifrado no funciona como se anuncia». ^{[ 7 ]}

Los resultados del criptoanálisis también pueden variar en utilidad. El criptógrafo Lars Knudsen (1998) clasificó varios tipos de ataques a cifrados de bloques según la cantidad y calidad de la información secreta descubierta:

• Ruptura total : el atacante deduce la clave secreta .
• Deducción global : el atacante descubre un algoritmo funcionalmente equivalente para el cifrado y el descifrado, pero sin conocer la clave.
• Deducción de instancia (local) : el atacante descubre textos planos (o textos cifrados) adicionales que no se conocían previamente.
• Deducción de información : el atacante obtiene información de Shannon sobre textos planos (o textos cifrados) que no se conocía previamente.
• Algoritmo distintivo : el atacante puede distinguir el cifrado de una permutación aleatoria .

Los ataques académicos suelen dirigirse contra versiones debilitadas de un criptosistema, como un cifrado por bloques o una función hash con algunas rondas eliminadas. Muchos ataques, aunque no todos, se vuelven exponencialmente más difíciles de ejecutar a medida que se añaden rondas a un criptosistema, ^{[ 8 ]} por lo que es posible que el criptosistema completo sea robusto incluso si las variantes con rondas reducidas son débiles. No obstante, las rupturas parciales que se aproximan a la ruptura del criptosistema original pueden significar que le seguirá una ruptura completa; los ataques exitosos contra DES , MD5 y SHA-1 fueron precedidos por ataques contra versiones debilitadas.

En criptografía académica, una debilidad o una brecha en un esquema se define generalmente de forma bastante conservadora: podría requerir cantidades impracticables de tiempo, memoria o textos planos conocidos. También podría requerir que el atacante sea capaz de hacer cosas que muchos atacantes del mundo real no pueden: por ejemplo, el atacante podría necesitar elegir textos planos específicos para cifrar o incluso solicitar que se cifren utilizando varias claves relacionadas con la clave secreta . Además, podría revelar solo una pequeña cantidad de información, suficiente para demostrar que el criptosistema es imperfecto, pero demasiado poca para ser útil a los atacantes del mundo real. Finalmente, un ataque podría aplicarse únicamente a una versión debilitada de las herramientas criptográficas, como un cifrado de bloques de rondas reducidas, como un paso hacia la ruptura del sistema completo. ^{[ 7 ]}

Aunque el término « criptoanálisis » es relativamente reciente (fue acuñado por William Friedman en 1920), los métodos para descifrar códigos y cifrados son mucho más antiguos. David Kahn señala en su libro Los descifradores de códigos que los eruditos árabes fueron los primeros en documentar sistemáticamente los métodos criptoanalíticos. ^{[ 9 ]}

La primera explicación conocida registrada de criptoanálisis fue dada por Al-Kindi (c. 801–873, también conocido como "Alkindus" en Europa), un polímata árabe del siglo IX , ^{[ 10 ] [ 11 ]} en Risalah fi Istikhraj al-Mu'amma ( Un manuscrito sobre el descifrado de mensajes criptográficos ). Este tratado contiene la primera descripción del método de análisis de frecuencia . ^{[ 12 ]} Por lo tanto, Al-Kindi es considerado el primer criptógrafo de la historia. ^{[ 13 ]} Su obra revolucionaria fue influenciada por Al-Khalil (717–786), quien escribió el Libro de los mensajes criptográficos , que contiene el primer uso de permutaciones y combinaciones para enumerar todas las posibles palabras árabes con y sin vocales. ^{[ 14 ]}

El análisis de frecuencia es la herramienta básica para descifrar la mayoría de los cifrados clásicos . En los lenguajes naturales, ciertas letras del alfabeto aparecen con más frecuencia que otras; en inglés , la " E " probablemente sea la letra más común en cualquier muestra de texto plano . De manera similar, el dígrafo "TH" es el par de letras más probable en inglés, y así sucesivamente. El análisis de frecuencia se basa en que un cifrado no oculte estas estadísticas . Por ejemplo, en un cifrado de sustitución simple (donde cada letra se reemplaza simplemente por otra), la letra más frecuente en el texto cifrado sería una candidata probable para la "E". Por lo tanto, el análisis de frecuencia de dicho cifrado es relativamente fácil, siempre que el texto cifrado sea lo suficientemente largo como para proporcionar un recuento razonablemente representativo de las letras del alfabeto que contiene. ^{[ 15 ]}

La invención de Al-Kindi de la técnica de análisis de frecuencia para descifrar cifrados de sustitución monoalfabéticos ^{[ 16 ] [ 17 ]} fue el avance criptoanalítico más significativo hasta la Segunda Guerra Mundial. El Risalah fi Istikhraj al-Mu'amma de Al-Kindi describió las primeras técnicas criptoanalíticas, incluyendo algunas para cifrados polialfabéticos , clasificación de cifrados, fonética y sintaxis árabes y, lo más importante, dio las primeras descripciones sobre análisis de frecuencia. ^{[ 18 ]} También abordó métodos de cifrado, criptoanálisis de ciertos cifrados y análisis estadístico de letras y combinaciones de letras en árabe. ^{[ 19 ] [ 12 ]} Una contribución importante de Ibn Adlan (1187–1268) fue sobre el tamaño de la muestra para el uso del análisis de frecuencia. ^{[ 14 ]}

En Europa, el erudito italiano Giambattista della Porta (1535-1615) fue el autor de una obra fundamental sobre criptoanálisis, De Furtivis Literarum Notis . ^{[ 20 ]}

El éxito del criptoanálisis ha influido sin duda en la historia; la capacidad de leer los pensamientos y planes supuestamente secretos de otros puede ser una ventaja decisiva. Por ejemplo, en Inglaterra, en 1587, María Estuardo, reina de Escocia, fue juzgada y ejecutada por traición a raíz de su participación en tres complots para asesinar a Isabel I de Inglaterra. Los planes salieron a la luz después de que Thomas Phelippes descifrara su correspondencia cifrada con otros conspiradores .

En Europa, durante los siglos XV y XVI, se desarrolló la idea de un cifrado de sustitución polialfabético , entre otros, por el diplomático francés Blaise de Vigenère (1523-1596). ^{[ 21 ]} Durante unos tres siglos, el cifrado de Vigenère , que utiliza una clave repetitiva para seleccionar diferentes alfabetos de cifrado de forma rotativa, se consideró completamente seguro ( le chiffre indéchiffrable —«el cifrado indescifrable»). Sin embargo, Charles Babbage (1791-1871) y, posteriormente, de forma independiente, Friedrich Kasiski (1805-1881) lograron descifrarlo. ^{[ 22 ]} Durante la Primera Guerra Mundial , inventores de varios países desarrollaron máquinas de cifrado de rotor , como la Enigma de Arthur Scherbius , en un intento por minimizar la repetición que se había explotado para romper el sistema de Vigenère. ^{[ 23 ]}

En la Primera Guerra Mundial , el desciframiento del Telegrama Zimmermann fue fundamental para la entrada de Estados Unidos en la guerra. En la Segunda Guerra Mundial , los Aliados se beneficiaron enormemente de su éxito conjunto en el criptoanálisis de los cifrados alemanes —incluida la máquina Enigma y el cifrado Lorenz— y los cifrados japoneses, en particular «Purple» y JN-25 . Se atribuye a la inteligencia «Ultra» el mérito de haber acortado la guerra europea hasta en dos años y de haber determinado su resultado final. La guerra en el Pacífico también se vio beneficiada por la inteligencia «Magic» . ^{[ 24 ]}

El criptoanálisis de los mensajes enemigos desempeñó un papel fundamental en la victoria aliada en la Segunda Guerra Mundial. F. W. Winterbotham citó al Comandante Supremo Aliado occidental, Dwight D. Eisenhower , quien al final de la guerra describió la inteligencia Ultra como "decisiva" para la victoria aliada. ^{[ 25 ]} Sir Harry Hinsley , historiador oficial de la inteligencia británica en la Segunda Guerra Mundial, hizo una valoración similar sobre Ultra, afirmando que acortó la guerra "en no menos de dos años y probablemente en cuatro"; además, dijo que, sin Ultra, es incierto cómo habría terminado la guerra. ^{[ 26 ]}

En la práctica, el análisis de frecuencias se basa tanto en el conocimiento lingüístico como en la estadística, pero a medida que los cifrados se volvieron más complejos, las matemáticas adquirieron mayor importancia en el criptoanálisis. Este cambio fue particularmente evidente antes y durante la Segunda Guerra Mundial , donde los esfuerzos por descifrar los cifrados del Eje requirieron nuevos niveles de sofisticación matemática. Además, la automatización se aplicó por primera vez al criptoanálisis en esa época con el dispositivo polaco Bomba , el británico Bombe , el uso de equipos de tarjetas perforadas y en las computadoras Colossus , las primeras computadoras digitales electrónicas controladas por un programa. ^{[ 27 ] [ 28 ]}

Los gobiernos han reconocido desde hace tiempo los beneficios potenciales del criptoanálisis para la inteligencia , tanto militar como diplomática, y han establecido organizaciones especializadas dedicadas a descifrar los códigos y cifrados de otras naciones, como por ejemplo el GCHQ y la NSA , organizaciones que siguen muy activas hoy en día.

Aunque la computación se utilizó con gran eficacia en el criptoanálisis del cifrado de Lorenz y otros sistemas durante la Segunda Guerra Mundial, también posibilitó nuevos métodos de criptografía mucho más complejos que nunca. En conjunto, la criptografía moderna se ha vuelto mucho más resistente al criptoanálisis que los sistemas de lápiz y papel del pasado, y ahora parece tener ventaja frente al criptoanálisis puro. El historiador David Kahn señala: ^{[ 36 ]}

Son muchos los criptosistemas que ofrecen hoy en día los cientos de proveedores comerciales que no pueden ser vulnerados por ningún método conocido de criptoanálisis. De hecho, en tales sistemas, ni siquiera un ataque de texto plano elegido , en el que se compara un texto plano seleccionado con su texto cifrado, puede proporcionar la clave que descifre otros mensajes. En cierto sentido, entonces, el criptoanálisis está muerto. Pero la historia no termina ahí. Puede que el criptoanálisis esté muerto, pero, parafraseando, hay más de una manera de hacer las cosas.

Kahn menciona además el aumento de las oportunidades de interceptación, espionaje , ataques de canal lateral y computadoras cuánticas como sustitutos de los métodos tradicionales de criptoanálisis. En 2010, el exdirector técnico de la NSA, Brian Snow, afirmó que tanto los criptógrafos académicos como los gubernamentales están "avanzando muy lentamente en un campo maduro". ^{[ 37 ]}

Sin embargo, cualquier análisis posterior a un ataque criptoanalítico podría ser prematuro. Si bien la efectividad de los métodos criptoanalíticos empleados por las agencias de inteligencia sigue siendo desconocida, en la era moderna de la criptografía informática se han publicado numerosos ataques serios contra primitivas criptográficas tanto académicas como prácticas: ^{[ 38 ]}

• En 1998 se descubrió que el cifrado por bloques Madryga , propuesto en 1984 pero poco utilizado, era susceptible a ataques que solo afectaban al texto cifrado .
• FEAL-4 , propuesto como sustituto del algoritmo de cifrado estándar DES pero poco utilizado, fue desmantelado por una serie de ataques de la comunidad académica, muchos de los cuales son totalmente prácticos.
• Los sistemas A5/1 , A5/2 , CMEA y DECT utilizados en la tecnología de telefonía móvil e inalámbrica pueden ser vulnerados en horas, minutos o incluso en tiempo real utilizando equipos informáticos ampliamente disponibles.
• La búsqueda por fuerza bruta en el espacio de claves ha roto algunos cifrados y aplicaciones del mundo real, incluyendo DES simple (ver el descifrador de DES de la EFF ), criptografía de 40 bits de "alta resistencia para exportación" y el sistema de codificación de contenido de DVD .
• En 2001, se demostró que el protocolo Wired Equivalent Privacy (WEP), utilizado para proteger las redes inalámbricas Wi-Fi , era vulnerable en la práctica debido a una debilidad en el cifrado RC4 y a aspectos de su diseño que hacían factibles los ataques de clave relacionada . Posteriormente, WEP fue reemplazado por Wi-Fi Protected Access .
• En 2008, investigadores realizaron una prueba de concepto para vulnerar SSL aprovechando las vulnerabilidades de la función hash MD5 y las prácticas de los emisores de certificados, lo que permitió explotar ataques de colisión en las funciones hash. Los emisores de certificados implicados modificaron sus prácticas para evitar que el ataque se repitiera.

Así, aunque los mejores cifrados modernos pueden ser mucho más resistentes al criptoanálisis que Enigma , el criptoanálisis y el campo más amplio de la seguridad de la información siguen estando bastante activos. ^{[ 39 ]}

• Conel Hugh O'Donel Alexander
• Charles Babbage
• Fredson Bowers
• Lambros D. Callimahos
• Joan Clarke
• Alastair Denniston
• Agnes Meyer Driscoll
• Elizabeth Friedman
• William F. Friedman
• Meredith Gardner
• Friedrich Kasiski
• Al-Kindi
• Dilly Knox
• Salomón Kullback
• Marian Rejewski
• Joseph Rochefort , cuyas contribuciones influyeron en el resultado de la Batalla de Midway.
• Frank Rowlett
• Abraham Sinkov
• Giovanni Soro , el primer criptoanalista destacado del Renacimiento.
• Juan Tiltman
• Alan Turing
• William T. Tutte
• John Wallis – matemático inglés del siglo XVII
• William Stone Weedon – trabajó con Fredson Bowers en la Segunda Guerra Mundial
• Herbert Yardley