El criptoanálisis (del griego kryptós , "oculto", y analýein , "analizar") se refiere al proceso de analizar sistemas de información para comprender aspectos ocultos de los sistemas. [1] El criptoanálisis se utiliza para violar los sistemas de seguridad criptográficos y obtener acceso al contenido de mensajes cifrados , incluso si se desconoce la clave criptográfica .
Además del análisis matemático de algoritmos criptográficos, el criptoanálisis incluye el estudio de ataques de canal lateral que no apuntan a las debilidades de los algoritmos criptográficos en sí, sino que explotan las debilidades en su implementación.
Aunque el objetivo ha sido el mismo, los métodos y técnicas del criptoanálisis han cambiado drásticamente a lo largo de la historia de la criptografía, adaptándose a la creciente complejidad criptográfica, desde los métodos de lápiz y papel del pasado, hasta máquinas como las británicas Bombes y Computadoras colosos en Bletchley Park en la Segunda Guerra Mundial , hasta los esquemas computarizados matemáticamente avanzados del presente. Los métodos para romper los criptosistemas modernos a menudo implican resolver problemas cuidadosamente construidos en matemáticas puras , siendo el más conocido la factorización de números enteros .
En el cifrado , la información confidencial (llamada " texto sin formato " ) se envía de forma segura a un destinatario mediante el remitente, que primero la convierte a un formato ilegible ( " texto cifrado " ) mediante un algoritmo de cifrado . El texto cifrado se envía a través de un canal inseguro al destinatario. El destinatario descifra el texto cifrado aplicando un algoritmo de descifrado inverso , recuperando el texto sin formato. Para descifrar el texto cifrado, el destinatario requiere un conocimiento secreto del remitente, generalmente una cadena de letras, números o bits , llamado clave criptográfica . El concepto es que incluso si una persona no autorizada obtiene acceso al texto cifrado durante la transmisión, sin la clave secreta no puede convertirlo nuevamente a texto sin formato.
El cifrado se ha utilizado a lo largo de la historia para enviar importantes mensajes militares, diplomáticos y comerciales, y hoy en día se utiliza ampliamente en redes informáticas para proteger el correo electrónico y las comunicaciones por Internet.
El objetivo del criptoanálisis es que un tercero, un criptoanalista , obtenga la mayor cantidad de información posible sobre el original ( " texto sin formato " ), intentando "romper" el cifrado para leer el texto cifrado y aprender la clave secreta para que los mensajes futuros puedan ser descifrado y leído. [2] Una técnica matemática para hacer esto se llama ataque criptográfico . Los ataques criptográficos se pueden caracterizar de varias maneras:
Los ataques criptoanalíticos se pueden clasificar según el tipo de información que el atacante tiene disponible. Como punto de partida básico, normalmente se supone que, a efectos del análisis, se conoce el algoritmo general; Esta es la máxima de Shannon : "El enemigo conoce el sistema" [3] , equivalente a su vez al principio de Kerckhoff . [4] Esta es una suposición razonable en la práctica: a lo largo de la historia, hay innumerables ejemplos de algoritmos secretos que han alcanzado un conocimiento más amplio, a través del espionaje , la traición y la ingeniería inversa . (Y en ocasiones, los cifrados se han descifrado mediante pura deducción; por ejemplo, el cifrado alemán de Lorenz y el código púrpura japonés , y una variedad de esquemas clásicos): [5]
Los ataques también pueden caracterizarse por los recursos que requieren. Esos recursos incluyen: [6]
A veces es difícil predecir estas cantidades con precisión, especialmente cuando no es práctico implementar el ataque para realizar pruebas. Pero los criptoanalistas académicos tienden a proporcionar al menos el orden de magnitud estimado de la dificultad de sus ataques, diciendo, por ejemplo, "las colisiones SHA-1 ahora son 2,52 " . [7]
Bruce Schneier señala que incluso los ataques computacionalmente poco prácticos pueden considerarse rupturas: "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 128 cifrados; un Un ataque que requiera 2 110 cifrados se consideraría una ruptura... en pocas palabras, una ruptura puede ser simplemente una debilidad de certificación: evidencia de que el cifrado no funciona como se anuncia". [8]
Los resultados del criptoanálisis también pueden variar en utilidad. El criptógrafo Lars Knudsen (1998) clasificó varios tipos de ataques a cifrados en bloque según la cantidad y calidad de la información secreta descubierta:
Los ataques académicos suelen ser contra versiones debilitadas de un criptosistema, como un cifrado de bloque o una función hash con algunas rondas eliminadas. Muchos ataques, pero no todos, se vuelven exponencialmente más difíciles de ejecutar a medida que se agregan rondas a un criptosistema, [9] por lo que es posible que todo el criptosistema sea fuerte incluso aunque las variantes de ronda reducida sean débiles. No obstante, las rupturas parciales que están a punto de romper el criptosistema original pueden significar que seguirá una ruptura total; Los ataques exitosos a DES , MD5 y SHA-1 fueron precedidos por ataques a versiones debilitadas.
En criptografía académica, una debilidad o una ruptura en un esquema generalmente se define de manera bastante conservadora: puede requerir cantidades poco prácticas de tiempo, memoria o textos claros 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 puede necesitar elegir textos sin formato concretos para cifrarlos o incluso solicitar que los textos sin formato se cifren utilizando varias claves relacionadas con el secreto. llave. Además, podría revelar sólo una pequeña cantidad de información, suficiente para demostrar que el criptosistema es imperfecto, pero demasiado poca para ser útil para los atacantes del mundo real. Por último, un ataque podría aplicarse sólo a una versión debilitada de las herramientas criptográficas, como un cifrado de bloque de ronda reducida, como un paso para romper todo el sistema. [8]
El criptoanálisis ha coevolucionado junto con la criptografía, y la contienda se puede rastrear a través de la historia de la criptografía : se diseñan nuevos cifrados para reemplazar viejos diseños rotos y se inventan nuevas técnicas criptoanalíticas para descifrar los esquemas mejorados. En la práctica, se consideran dos caras de la misma moneda: la criptografía segura requiere un diseño frente a un posible criptoanálisis. [ cita necesaria ]
Aunque la palabra " criptoanálisis " es relativamente reciente (fue acuñada por William Friedman en 1920), los métodos para descifrar códigos y cifrados son mucho más antiguos. David Kahn señala en The Codebreakers que los eruditos árabes fueron los primeros en documentar sistemáticamente métodos criptoanalíticos. [10]
La primera explicación registrada conocida del criptoanálisis la dio Al-Kindi (c. 801–873, también conocido como "Alkindus" en Europa), un erudito árabe del siglo IX , [11] [12] 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 . [13] Por lo tanto, Al-Kindi es considerado como el primer descifrador de códigos de la historia. [14] Su innovador trabajo fue influenciado por Al-Khalil (717–786), quien escribió el Libro de mensajes criptográficos , que contiene el primer uso de permutaciones y combinaciones para enumerar todas las palabras árabes posibles con y sin vocales. [15]
El análisis de frecuencia es la herramienta básica para descifrar la mayoría de los cifrados clásicos . En las lenguas naturales, ciertas letras del alfabeto aparecen con más frecuencia que otras; En inglés , " E " probablemente sea la letra más común en cualquier muestra de texto sin formato . 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 un cifrado que no oculta estas estadísticas . Por ejemplo, en un cifrado de sustitución simple (donde cada letra simplemente se reemplaza por otra), la letra más frecuente en el texto cifrado sería una candidata probable para "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 dar un recuento razonablemente representativo de las letras del alfabeto que contiene. [dieciséis]
La invención de Al-Kindi de la técnica de análisis de frecuencia para descifrar cifrados de sustitución monoalfabética [17] [18] fue el avance criptoanalítico más significativo hasta la Segunda Guerra Mundial. Risalah fi Istikhraj al-Mu'amma de Al-Kindi describió las primeras técnicas criptoanalíticas, incluidas algunas para cifrados polialfabéticos , clasificación de cifrado, fonética y sintaxis árabe y, lo más importante, dio las primeras descripciones sobre análisis de frecuencia. [19] También cubrió métodos de cifrado, criptoanálisis de ciertos cifrados y análisis estadístico de letras y combinaciones de letras en árabe. [20] [13] Una contribución importante de Ibn Adlan (1187-1268) fue el tamaño de la muestra para el uso del análisis de frecuencia. [15]
En Europa, el erudito italiano Giambattista della Porta (1535-1615) fue el autor de una obra fundamental sobre criptoanálisis, De Furtivis Literarum Notis . [21]
Sin duda, el criptoanálisis exitoso ha influido en la historia; la capacidad de leer los pensamientos y planes presuntamente secretos de los demás puede ser una ventaja decisiva. Por ejemplo, en Inglaterra en 1587, María, reina de Escocia, fue juzgada y ejecutada por traición como resultado 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 codificada con sus compañeros conspiradores .
En Europa, durante los siglos XV y XVI, la idea de un cifrado de sustitución polialfabética fue desarrollada, entre otros, por el diplomático francés Blaise de Vigenère (1523-1596). [22] Durante unos tres siglos, el cifrado de Vigenère , que utiliza una clave repetida para seleccionar diferentes alfabetos de cifrado en rotación, se consideró completamente seguro ( le chiffre indéchiffrable - "el cifrado indescifrable"). Sin embargo, Charles Babbage (1791-1871) y más tarde, de forma independiente, Friedrich Kasiski (1805-1881) lograron descifrar este cifrado. [23] Durante la Primera Guerra Mundial , inventores en varios países desarrollaron máquinas de cifrado de rotor como la Enigma de Arthur Scherbius , en un intento de minimizar la repetición que había sido explotada para romper el sistema Vigenère. [24]
En la Primera Guerra Mundial , la ruptura del Telegrama Zimmermann fue fundamental para llevar a Estados Unidos a la guerra. En la Segunda Guerra Mundial , los aliados se beneficiaron enormemente del éxito conjunto del criptoanálisis de los cifrados alemanes (incluidas la máquina Enigma y el cifrado Lorenz ) y los cifrados japoneses, en particular 'Purple' y JN-25 . A la "ultra" inteligencia se le ha atribuido todo, desde acortar el final de la guerra europea hasta en dos años hasta determinar el resultado final. La guerra en el Pacífico también contó con la ayuda de la inteligencia "Magic" . [25]
El criptoanálisis de los mensajes enemigos jugó un papel importante en la victoria aliada en la Segunda Guerra Mundial. FW Winterbotham citó al Comandante Supremo Aliado occidental, Dwight D. Eisenhower , al final de la guerra describiendo la Ultrainteligencia como "decisiva" para la victoria aliada. [26] Sir Harry Hinsley , historiador oficial de la inteligencia británica en la Segunda Guerra Mundial, hizo una evaluación similar sobre Ultra, diciendo que acortó la guerra "en no menos de dos años y probablemente en cuatro años"; además, dijo que en ausencia de Ultra, no es seguro cómo habría terminado la guerra. [27]
En la práctica, el análisis de frecuencia 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 se volvieron más importantes en el criptoanálisis. Este cambio fue particularmente evidente antes y durante la Segunda Guerra Mundial , donde los esfuerzos para 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. [28] [29]
Con cifrados mecánicos recíprocos como el cifrado de Lorenz y la máquina Enigma utilizados por la Alemania nazi durante la Segunda Guerra Mundial , cada mensaje tenía su propia clave. Normalmente, el operador transmisor informa al operador receptor de esta clave de mensaje transmitiendo algún texto sin formato y/o texto cifrado antes del mensaje cifrado. Esto se denomina indicador , ya que indica al operador receptor cómo configurar su máquina para descifrar el mensaje. [30]
Los sistemas de indicadores mal diseñados e implementados permitieron primero a los criptógrafos polacos [31] y luego a los criptógrafos británicos de Bletchley Park [32] descifrar el sistema de cifrado Enigma. Sistemas de indicadores deficientes similares permitieron a los británicos identificar profundidades que llevaron al diagnóstico del sistema de cifrado Lorenz SZ40/42 y a la ruptura completa de sus mensajes sin que los criptoanalistas vieran la máquina de cifrado. [33]
Enviar dos o más mensajes con la misma clave es un proceso inseguro. Para un criptoanalista, se dice que los mensajes son "profundos". [34] [35] Esto puede detectarse mediante mensajes que tienen el mismo indicador mediante el cual el operador emisor informa al operador receptor sobre la configuración inicial del generador de claves para el mensaje. [36]
Generalmente, el criptoanalista puede beneficiarse de alinear operaciones de cifrado idénticas entre un conjunto de mensajes. Por ejemplo, el cifrado Vernam cifra bit a bit combinando texto sin formato con una clave larga utilizando el operador " exclusivo o ", que también se conoce como " suma de módulo 2 " (simbolizado por ⊕):
El descifrado combina los mismos bits clave con el texto cifrado para reconstruir el texto sin formato:
(En aritmética de módulo 2, la suma es lo mismo que la resta). Cuando dos de estos textos cifrados se alinean en profundidad, combinarlos elimina la clave común, dejando solo una combinación de los dos textos sin formato:
Los textos claros individuales pueden luego resolverse lingüísticamente probando palabras (o frases) probables, también conocidas como "cunas", en varios lugares; una suposición correcta, cuando se combina con la secuencia de texto sin formato fusionada, produce texto inteligible a partir del otro componente de texto sin formato:
El fragmento recuperado del segundo texto sin formato a menudo se puede extender en una o ambas direcciones, y los caracteres adicionales se pueden combinar con la secuencia de texto sin formato fusionada para extender el primer texto sin formato. Trabajando de un lado a otro entre los dos textos claros, utilizando el criterio de inteligibilidad para comprobar las conjeturas, el analista puede recuperar gran parte o todos los textos claros originales. (Con sólo dos textos claros en profundidad, el analista puede no saber cuál corresponde a cada texto cifrado, pero en la práctica esto no es un gran problema). Cuando un texto claro recuperado se combina con su texto cifrado, se revela la clave:
El conocimiento de una clave permite al analista leer otros mensajes cifrados con la misma clave, y el conocimiento de un conjunto de claves relacionadas puede permitir a los criptoanalistas diagnosticar el sistema utilizado para construirlos. [33]
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 dedicadas a descifrar códigos y cifras de otras naciones, por ejemplo, GCHQ y la NSA , organizaciones que todavía están muy activas en la actualidad.
Aunque la computación se utilizó con gran éxito en el criptoanálisis del cifrado de Lorenz y otros sistemas durante la Segunda Guerra Mundial, también hizo posibles nuevos métodos de criptografía de órdenes de magnitud más complejos que nunca. En su conjunto, la criptografía moderna se ha vuelto mucho más inmune al criptoanálisis que los sistemas de lápiz y papel del pasado, y ahora parece tener ventaja sobre el criptoanálisis puro. [ cita necesaria ] El historiador David Kahn señala: [37]
Muchos son los criptosistemas que ofrecen los cientos de proveedores comerciales en la actualidad y que no pueden descifrarse mediante ningún método conocido de criptoanálisis. De hecho, en tales sistemas, incluso un ataque de texto sin formato elegido , en el que un texto sin formato seleccionado se compara con su texto cifrado, no puede proporcionar la clave que desbloquea otros mensajes. Entonces, en cierto sentido, el criptoanálisis está muerto. Pero ese no es el final de la historia. Puede que el criptoanálisis esté muerto, pero hay –para mezclar mis metáforas– más de una forma de despellejar a un gato.
Kahn continúa mencionando mayores oportunidades de interceptación, micrófonos , ataques de canales laterales y computadoras cuánticas como reemplazos de los medios tradicionales de criptoanálisis. En 2010, el ex director técnico de la NSA, Brian Snow, dijo que tanto los criptógrafos académicos como los gubernamentales están "avanzando muy lentamente en un campo maduro". [38]
Sin embargo, cualquier autopsia para el criptoanálisis puede ser prematura. Si bien se desconoce la eficacia de los métodos criptoanalíticos empleados por las agencias de inteligencia, en la era moderna de la criptografía informática se han publicado muchos ataques graves contra primitivas criptográficas tanto académicas como prácticas: [ cita necesaria ]
Así, si bien los mejores cifrados modernos pueden ser mucho más resistentes al criptoanálisis que el Enigma , el criptoanálisis y el campo más amplio de la seguridad de la información siguen bastante activos. [39]
La criptografía asimétrica (o criptografía de clave pública ) es una criptografía que se basa en el uso de dos claves (matemáticamente relacionadas); uno privado y otro público. Estos cifrados invariablemente se basan en problemas matemáticos "difíciles" como base de su seguridad, por lo que un punto de ataque obvio es desarrollar métodos para resolver el problema. La seguridad de la criptografía de dos claves depende de cuestiones matemáticas de una manera que la criptografía de una sola clave generalmente no lo hace y, a la inversa, vincula el criptoanálisis con una investigación matemática más amplia de una manera nueva. [ cita necesaria ]
Los esquemas asimétricos están diseñados en torno a la dificultad (conjeturada) de resolver diversos problemas matemáticos. Si se puede encontrar un algoritmo mejorado para resolver el problema, entonces el sistema se debilita. Por ejemplo, la seguridad del esquema de intercambio de claves Diffie-Hellman depende de la dificultad de calcular el logaritmo discreto . En 1983, Don Coppersmith encontró una manera más rápida de encontrar logaritmos discretos (en ciertos grupos) y, por lo tanto, requirió que los criptógrafos usaran grupos más grandes (o diferentes tipos de grupos). La seguridad de RSA depende (en parte) de la dificultad de la factorización de números enteros : un avance en la factorización afectaría la seguridad de RSA. [ cita necesaria ]
En 1980, se podía factorizar un número difícil de 50 dígitos a expensas de 10 12 operaciones elementales de computadora. En 1984, el estado del arte en algoritmos de factorización había avanzado hasta un punto en el que un número de 75 dígitos podía factorizarse en 10 12 operaciones. Los avances en la tecnología informática también significaron que las operaciones podrían realizarse mucho más rápido. La ley de Moore predice que la velocidad de las computadoras seguirá aumentando. Es posible que las técnicas de factorización también sigan haciéndolo, pero lo más probable es que dependan de la perspicacia matemática y la creatividad, ninguna de las cuales ha sido nunca predecible con éxito. Se han factorizado números de 150 dígitos del tipo que alguna vez se usaron en RSA. El esfuerzo fue mayor que el anterior, pero no era descabellado en computadoras modernas y rápidas. A principios del siglo XXI, los números de 150 dígitos ya no se consideraban un tamaño de clave lo suficientemente grande para RSA. Los números con varios cientos de dígitos todavía se consideraban demasiado difíciles de factorizar en 2005, aunque los métodos probablemente seguirán mejorando con el tiempo, requiriendo que el tamaño de la clave mantenga el ritmo u otros métodos como la criptografía de curva elíptica . [ cita necesaria ]
Otra característica distintiva de los esquemas asimétricos es que, a diferencia de los ataques a criptosistemas simétricos, cualquier criptoanálisis tiene la oportunidad de utilizar el conocimiento obtenido de la clave pública . [40]
Las computadoras cuánticas , que aún se encuentran en las primeras fases de investigación, tienen un uso potencial en criptoanálisis. Por ejemplo, el algoritmo de Shor podría factorizar grandes números en tiempo polinómico , rompiendo de hecho algunas formas comúnmente utilizadas de cifrado de clave pública. [41]
Utilizando el algoritmo de Grover en una computadora cuántica, la búsqueda de claves por fuerza bruta se puede hacer cuadráticamente más rápido. Sin embargo, esto podría contrarrestarse duplicando la longitud de la clave. [42]
Al-Kindi es considerado el primer descifrador de códigos
