El criptoanálisis (del griego kryptós , «oculto», y analýein , «analizar») se refiere al proceso de analizar sistemas de información con el fin de comprender aspectos ocultos de los sistemas. [1] El criptoanálisis se utiliza para violar los sistemas de seguridad criptográfica y obtener acceso al contenido de mensajes cifrados , incluso si se desconoce la clave criptográfica .
Además del análisis matemático de los 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, pasando por máquinas como las computadoras británicas Bombes y Colossus en Bletchley Park en la Segunda Guerra Mundial , hasta los esquemas computarizados matemáticamente avanzados del presente. Los métodos para descifrar criptosistemas modernos a menudo implican la resolución de 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 (denominada " texto simple " ) se envía de forma segura a un destinatario mediante el remitente convirtiéndola primero en 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 simple. Para descifrar el texto cifrado, el destinatario requiere un conocimiento secreto del remitente, normalmente una cadena de letras, números o bits , llamada 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 volver a convertirlo en texto simple.
El cifrado se ha utilizado a lo largo de la historia para enviar mensajes militares, diplomáticos y comerciales importantes, y hoy en día se usa 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 simple " ), intentando "romper" el cifrado para leer el texto cifrado y conocer la clave secreta para que los mensajes futuros puedan descifrarse y leerse. [2] Una técnica matemática para hacer esto se llama ataque criptográfico . Los ataques criptográficos se pueden caracterizar de varias formas:
Los ataques criptoanalíticos pueden clasificarse en función del tipo de información que tenga disponible el atacante. Como punto de partida básico, normalmente se supone que, a efectos de análisis, se conoce el algoritmo general; se trata de 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, existen innumerables ejemplos de algoritmos secretos que caen en manos de un conocimiento más amplio, ya sea a través del espionaje , la traición o 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. Entre estos recursos se incluyen: [6]
A veces es difícil predecir estas cantidades con precisión, especialmente cuando el ataque no es práctico para implementarlo en la práctica 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 que no son prácticos desde el punto de vista computacional pueden considerarse como una ruptura: "Romper un código significa simplemente encontrar una debilidad en el código que pueda ser explotada con una complejidad menor que la fuerza bruta. No importa que la fuerza bruta pueda requerir 2 128 cifrados; 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 código no funciona como se anuncia". [8]
Los resultados del criptoanálisis también pueden variar en cuanto a su utilidad. El criptógrafo Lars Knudsen (1998) clasificó varios tipos de ataques a los cifrados en bloque según la cantidad y calidad de la información secreta descubierta:
Los ataques académicos suelen dirigirse contra versiones debilitadas de un criptosistema, como un cifrado de bloques 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 el criptosistema completo sea fuerte aunque las variantes con rondas reducidas sean débiles. No obstante, las rupturas parciales que se acercan a romper el criptosistema original pueden significar que seguirá una ruptura completa; los ataques exitosos a DES , MD5 y SHA-1 fueron todos precedidos por ataques a versiones debilitadas.
En criptografía académica, una debilidad o una ruptura en un sistema se define generalmente de manera bastante conservadora: puede requerir cantidades imprácticas de tiempo, memoria o textos simples conocidos. También puede 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 simples particulares para cifrar o incluso solicitar que los textos simples se cifren utilizando varias claves relacionadas con la clave secreta . Además, puede revelar solo una pequeña cantidad de información, suficiente para demostrar que el criptosistema es imperfecto pero demasiado poco para ser útil para los atacantes del mundo real. Finalmente, un ataque solo puede aplicarse a una versión debilitada de herramientas criptográficas, como un cifrado de bloque de ronda reducida, como un paso hacia la ruptura del sistema completo. [8]
El criptoanálisis ha evolucionado junto con la criptografía, y la contienda se puede rastrear a lo largo de la historia de la criptografía : se diseñaron nuevos sistemas de cifrado para reemplazar los viejos diseños defectuosos y se inventaron nuevas técnicas criptoanalíticas para descifrar los esquemas mejorados. En la práctica, se consideran como dos caras de la misma moneda: la criptografía segura requiere un diseño que evite el posible criptoanálisis. [ cita requerida ]
Aunque la palabra criptoanálisis es relativamente reciente (fue acuñada por William Friedman en 1920), los métodos para descifrar códigos y cifras son mucho más antiguos. David Kahn señala en The Codebreakers que los eruditos árabes fueron los primeros en documentar sistemáticamente los métodos criptoanalíticos. [10]
La primera explicación registrada conocida del criptoanálisis fue dada por 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, se considera a Al-Kindi como el primer descifrador de códigos de la historia. [14] Su trabajo innovador estuvo 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 posibles palabras árabes 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 los lenguajes naturales, ciertas letras del alfabeto aparecen con más frecuencia que otras; en inglés , es probable que " E " sea la letra más común en cualquier muestra de texto simple . 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 simplemente se reemplaza por otra), la letra más frecuente en el texto cifrado sería una candidata probable para "E". El análisis de frecuencia de un cifrado de este tipo es, por lo tanto, 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. [16]
La invención de Al-Kindi de la técnica de análisis de frecuencia para descifrar cifras de sustitución monoalfabética [17] [18] fue el avance criptoanalítico más significativo hasta la Segunda Guerra Mundial. La Risalah fi Istikhraj al-Mu'amma de Al-Kindi describió las primeras técnicas criptoanalíticas, incluidas algunas para cifras polialfabéticas , clasificación de cifras, fonética y sintaxis árabes y, lo más importante, dio las primeras descripciones sobre análisis de frecuencia. [19] También abordó métodos de cifrados, criptoanálisis de ciertos cifrados y análisis estadístico de letras y combinaciones de letras en árabe. [20] [13] Una importante contribución de Ibn Adlan (1187-1268) fue sobre 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]
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, 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 otros 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 repetitiva 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 de varios países desarrollaron máquinas de cifrado de rotor como Enigma de Arthur Scherbius , en un intento de minimizar la repetición que se había explotado para descifrar el sistema de Vigenère. [24]
En la Primera Guerra Mundial , el desciframiento del Telegrama Zimmermann fue decisivo para que Estados Unidos entrara en la guerra. En la Segunda Guerra Mundial , los Aliados se beneficiaron enormemente de su éxito conjunto en el criptoanálisis de los sistemas de cifrado alemanes (incluida la máquina Enigma y el sistema de cifrado Lorenz ) y los sistemas de cifrado japoneses, en particular el «Púrpura» y el JN-25 . A la inteligencia «Ultra» se le atribuyen todo, desde acortar el final de la guerra europea en hasta dos años hasta determinar el resultado final. La guerra en el Pacífico también recibió ayuda de la inteligencia «Mágica» . [25]
El criptoanálisis de los mensajes enemigos jugó un papel importante en la victoria aliada en la Segunda Guerra Mundial. F. W. Winterbotham citó al Comandante Supremo Aliado occidental, Dwight D. Eisenhower , al final de la guerra, quien describió la inteligencia Ultra 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 frecuencias depende tanto del conocimiento lingüístico como de la estadística, pero a medida que los cifrados se volvieron más complejos, las matemáticas cobraron mayor importancia en el criptoanálisis. Este cambio fue particularmente evidente antes y durante la Segunda Guerra Mundial , cuando los esfuerzos por descifrar los cifrados del Eje exigieron 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]
En los sistemas de cifrado recíproco, como el cifrado de Lorenz y la máquina Enigma que utilizó la Alemania nazi durante la Segunda Guerra Mundial , cada mensaje tenía su propia clave. Normalmente, el operador transmisor informaba al operador receptor de esta clave del mensaje transmitiendo algún texto simple o 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 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 indicadores similares permitieron a los británicos identificar las profundidades que llevaron al diagnóstico del sistema de cifrado Lorenz SZ40/42 y al descifrado completo de sus mensajes sin que los criptoanalistas vieran la máquina de cifrado. [33]
El envío de dos o más mensajes con la misma clave es un proceso inseguro. Para un criptoanalista, los mensajes se consideran "en profundidad". [34] [35] Esto se puede detectar si los mensajes tienen el mismo indicador mediante el cual el operador que envía informa al operador que recibe sobre la configuración inicial del generador de claves para el mensaje. [36]
En general, el criptoanalista puede beneficiarse de alinear operaciones de cifrado idénticas entre un conjunto de mensajes. Por ejemplo, el cifrado Vernam cifra mediante la combinación bit a bit de texto simple con una clave larga utilizando el operador " o exclusivo ", que también se conoce como " suma módulo 2 " (simbolizado por ⊕):
El descifrado combina los mismos bits clave con el texto cifrado para reconstruir el texto simple:
(En aritmética módulo 2, la suma es lo mismo que la resta). Cuando dos de estos textos cifrados están alineados en profundidad, al combinarlos se elimina la clave común y queda solo una combinación de los dos textos simples:
Luego, es posible resolver lingüísticamente los textos simples individuales probando palabras (o frases) probables, también conocidas como "cribs", en varias ubicaciones; una suposición correcta, cuando se combina con el flujo de texto simple fusionado, produce un texto inteligible a partir del otro componente de texto simple:
El fragmento recuperado del segundo texto simple a menudo se puede ampliar en una o ambas direcciones, y los caracteres adicionales se pueden combinar con el flujo de texto simple fusionado para ampliar el primer texto simple. Al trabajar de ida y vuelta entre los dos textos simples, utilizando el criterio de inteligibilidad para comprobar las suposiciones, el analista puede recuperar gran parte o la totalidad de los textos simples originales. (Con solo dos textos simples en profundidad, el analista puede no saber cuál corresponde a qué texto cifrado, pero en la práctica esto no es un gran problema). Cuando un texto simple recuperado se combina con su texto cifrado, se revela la clave:
El conocimiento de una clave permite entonces 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 construirlas. [33]
Los gobiernos han reconocido desde hace mucho tiempo los beneficios potenciales del criptoanálisis para la inteligencia , tanto militar como diplomática, y han establecido organizaciones dedicadas a descifrar los códigos y cifras de otras naciones, por ejemplo, GCHQ y la NSA , organizaciones que todavía son 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 hizo posibles nuevos métodos de criptografía órdenes de magnitud más complejos que nunca. En 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 la ventaja sobre el criptoanálisis puro. [ cita requerida ] El historiador David Kahn señala: [37]
Muchos de los criptosistemas que ofrecen los cientos de proveedores comerciales actuales no pueden ser descifrados por ningún método conocido de criptoanálisis. De hecho, en tales sistemas ni siquiera un ataque de texto simple elegido , en el que se compara un texto simple seleccionado con su texto cifrado, puede proporcionar la clave que desbloquee otros mensajes. En cierto sentido, entonces, 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, escuchas ilegales , ataques de canal lateral 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 análisis posterior al criptoanálisis puede ser prematuro. Si bien la eficacia 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 muchos ataques graves contra primitivos criptográficos, tanto académicos como prácticos: [39]
Por lo tanto, 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 siendo bastante activos. [40]
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 (relacionadas matemáticamente): una privada y otra pública. Estos sistemas de cifrado 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 clave única generalmente no lo hace y, a la inversa, vincula el criptoanálisis a una investigación matemática más amplia de una manera nueva. [ cita requerida ]
Los esquemas asimétricos están diseñados en torno a la (supuesta) dificultad de resolver varios 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 forma 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. [41]
En 1980, se podía factorizar un número difícil de 50 dígitos con un coste de 10 12 operaciones informáticas elementales. 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 podían realizarse mucho más rápido. La ley de Moore predice que la velocidad de las computadoras seguirá aumentando. Las técnicas de factorización también pueden seguir 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 se usaba en RSA. El esfuerzo fue mayor que el anterior, pero no era irrazonable en las rápidas computadoras modernas. 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. En 2005, los números con varios cientos de dígitos todavía se consideraban demasiado difíciles de factorizar, aunque es probable que los métodos sigan mejorando con el tiempo, lo que requerirá que el tamaño de la clave siga el ritmo o que se utilicen otros métodos como la criptografía de curva elíptica . [ cita requerida ]
Otra característica distintiva de los esquemas asimétricos es que, a diferencia de los ataques a los criptosistemas simétricos, cualquier criptoanálisis tiene la oportunidad de hacer uso del conocimiento obtenido de la clave pública . [42]
Las computadoras cuánticas , que todavía se encuentran en las primeras fases de investigación, tienen un uso potencial en el criptoanálisis. Por ejemplo, el algoritmo de Shor podría factorizar números grandes en tiempo polinomial , rompiendo así algunas formas de cifrado de clave pública comúnmente utilizadas. [43]
Si se utiliza el algoritmo de Grover en una computadora cuántica, la búsqueda de claves por fuerza bruta puede ser cuadráticamente más rápida. Sin embargo, esto podría contrarrestarse duplicando la longitud de la clave. [44]
Al-Kindi es considerado el primer descifrador de códigos
