Criptoanálisis

La teoría de la información proporciona herramientas para evaluar la seguridad de los sistemas criptográficos. Por ejemplo, en los sistemas de cifrado se estudia la entropía de la clave, de los criptogramas y de los mensajes en claro. Como el mensaje en claro suele estar expresado en idiomas humanos, también es interesante el estudio de su entropía y en especial su ratio de entropía.

Los criptoanalistas también estudian el secreto de los sistemas criptográficos. Por ejemplo, en los sistemas de cifrado estudian el grado de secreto caracterizando aquellos sistemas que tienen secreto perfecto a nivel teórico. De su estudio se concluye que el secreto perfecto requiere que el número de claves sea al menos tan grande como el número de mensajes. Esto es impracticable excepto para los llamados cifradores de libreta de un solo uso. En la práctica la mayor parte de los sistemas tienen claves finitas. Para caracterizar la seguridad de estos sistemas los criptoanalistas han desarrollado el concepto de distancia de unicidad que es el valor mínimo de caracteres cifrados que hacen que solo haya una clave posible que haya sido utilizada para obtener este criptograma. Para ello se aprovecha el concepto de la entropía condicional del conocimiento de la clave una vez conocido el texto cifrado.

Para un sistema de cifrado hay dos entropías condicionales interesantes[1] desde el punto de vista del criptoanalista:

Para un sistema de cifrado hay una serie de entropías condicionales interesantes:[2][3]

Supongamos

• Un mensaje M₁ es sometido a un proceso de cifrado usando la clave K₁ obteniendo E(K₁,M₁)=C₁.
• ${\displaystyle P_{C}(K)}$ representan la probabilidad condicional de la clave K dado el criptograma recibido C. A veces también se denota por ${\displaystyle P(K|C)}$
• ${\displaystyle P_{C}(M)}$ representan la probabilidad condicional del mensaje M dado el criptograma recibido C. A veces también se denota por ${\displaystyle P(M|C)}$

Entonces:

• Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado, y por tanto medir la equivocación del mensaje (en inglés message equivocation), ${\displaystyle H_{C}(K)}$, también denotada por ${\displaystyle H(K|C)}$, mediante la fórmula:

${\displaystyle H_{C}(K)=-\sum _{E,K}P(E,K)\log _{P_{E}}(K)=-\sum _{E}P(E)\sum _{K}P_{E}(K)\log _{P_{E}}(K)}$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

Observar que si ${\displaystyle H_{C}(K)=0}$ significa que se podrá romper el cifrado pues ya no hay incertidumbre. Esta anulación nos introduce en el concepto de distancia de unicidad.

• Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado, y por tanto medir la equivocación de la clave (en inglés key equivocation), ${\displaystyle H_{C}(M)}$, también denotada por ${\displaystyle H(M|C)}$, mediante la fórmula:

${\displaystyle H_{C}(M)=-\sum _{E,M}P(E,M)\log _{P_{E}}(M)=-\sum _{E}P(E)\sum _{M}P_{E}(M)\log _{P_{E}}(M)}$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

• Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado y el mensaje en claro, y por tanto medir la equivocación del aspecto de la clave (en inglés key appearance equivocation), ${\displaystyle H_{C,M}(K)}$, también denotada por ${\displaystyle H(K|M,C)}$, mediante la fórmula:

${\displaystyle H_{C,M}(K)=-\sum _{E,M,C}P(E,K,M)\log _{P_{E,M}}(K)}$

• Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado y la clave, denotado por ${\displaystyle H_{C,K}(M)}$ o por ${\displaystyle H(M|K,C)}$. Dada una clave la relación entre texto cifrado y texto en claro es uno-a-uno y por tanto ${\displaystyle H_{C,K}(M)=0}$

Se ha demostrado[3] que se cumple la siguiente relación entre las distintas entropías:

${\displaystyle H_{C,M}(K)=H_{C}(K)-H_{C}(M)}$

De esta relación podemos sacar una conclusión:[3]

El objetivo de cualquiera que use un cifrador es tener un valor de ${\displaystyle H_{C,M}(K)}$ alto para que el sistema tenga la máxima fortaleza posible para el caso de que el atacante disponga tanto del texto cifrado como del texto claro (ataque con texto claro conocido). Sin embargo, por la expresión de la ecuación, para ello es necesario que ${\displaystyle H_{C}(M)}$ sea pequeño. Sin embargo, tener un valor pequeño de ${\displaystyle H_{C}(M)}$ implica que haya poca incertidumbre respecto al texto claro una vez conocido el texto cifrado (ataque con sólo texto cifrado disponible), lo cual contrario a los intereses de cualquiera que cifre un mensaje. Por tanto es necesario una solución de compromiso para que el sistema tenga una fortaleza aceptable para ambos tipos de ataque

Por ejemplo, la criptografía asimétrica emplea problemas matemáticos "duros" como base para su seguridad, así que un punto obvio de ataque es desarrollar métodos para resolver el problema. Los algoritmos asimétricos se diseñan en torno a la conjeturada dificultad de resolver ciertos problemas matemáticos. Si se encuentra un algoritmo mejorado que puede resolver el problema, el criptosistema se ve debilitado. Ejemplos:

• La seguridad del protocolo Diffie-Hellman depende de la dificultad de calcular un logaritmo discreto. En 1983, Don Coppersmith encontró una manera más rápida de calcular logaritmos discretos (dentro de ciertos grupos), y por tanto obligó a los criptógrafos a utilizar grupos más grandes, o diferentes tipos de grupos.
• La seguridad del protocolo RSA depende parcialmente de la dificultad en la factorización de enteros. Por tanto un avance en la factorización tendría un impacto claro en la seguridad de RSA. En 1980, se podía factorizar un número de 50 dígitos con un coste de 10¹² operaciones elementales de computación. Para 1984 la tecnología en algoritmos de factorización había avanzado hasta el punto de que se podía factorizar un número de 75 dígitos con las mismas 10¹² operaciones. Los avances en la tecnología de computación también han provocado que estas operaciones se puedan realizar en un tiempo mucho menor. La Ley de Moore predice empíricamente que las velocidades de computación continuarán aumentando. Las técnicas de factorización podrían mostrar un desarrollo parecido, pero con gran probabilidad dependerán de la capacidad y la creatividad de los matemáticos, ninguna de las cuales ha sido nunca satisfactoriamente predecible. Números de 150 cifras, como los utilizados en RSA, han sido factorizados. El esfuerzo fue mayor que el mencionado anteriormente, pero no estaba fuera de los límites razonables para un ordenador moderno. Al comienzo del siglo XXI, los números de 150 cifras ya no se consideran suficientemente grandes como clave para RSA. Números de varios cientos de dígitos se seguían considerando demasiado difíciles de factorizar en 2005, aunque los métodos probablemente continuarán mejorando con el tiempo, obligando a los tamaños de clave a mantener el ritmo de crecimiento o a desarrollar nuevos algoritmos.

Otra característica distintiva de los algoritmos asimétricos es que, a diferencia de los ataques sobre criptosistemas simétricos, cualquier criptoanálisis tiene la oportunidad de usar el conocimiento obtenido de la clave pública.

Los ataques criptoanalíticos se puede clasificar en función de sus características.

Los ataques se pueden clasificar según la forma de actuar del atacante

En los ataques pasivos el atacante no altera la comunicación, solo la escucha o monitoriza, para obtener información. Por tanto este tipo de ataques suelen usar técnicas de escucha de paquetes(sniffing) y de análisis de tráfico. Son difíciles de detectar ya que no implican alteración de los datos. En algunos casos este tipo de ataques se pueden dificultar cifrando la información posible objetivo de escuchas.

Suponen alguna modificación del flujo de datos o la creación de flujos falsos. Hay muchas técnicas que se usan en este tipo de ataques. Ejemplos:

1. Suplantación
2. Modificación de mensajes:Capturar paquetes para luego ser borrados (dropping attacks), manipulados, modificados (tagging attack) o reordenados
3. Reactuación:Captura de paquetes y retransmisiones
4. Degradación: Técnicas para que el servicio se degrade

El criptoanálisis puede realizarse bajo una serie de supuestos sobre cuánto puede observarse o descubrirse sobre el sistema en cuestión antes de realizar el ataque. Como un punto de comienzo básico se supone que, para los propósitos del análisis, el algoritmo general es conocido; esta es la Máxima de Shannon, "el enemigo conoce el sistema". Este es un supuesto razonable en la práctica - a lo largo de la Historia, hay incontables ejemplos de algoritmos secretos que fueron conocidos mediante el espionaje, la traición y la ingeniería inversa. (En algunas ocasiones, algunos códigos han sido reconstruidos mediante la pura deducción, por ejemplo, el código Lorenz y el código PURPLE, así como una cierta cantidad de códigos clásicos.)

Otros supuestos se pueden categorizar como sigue:

• Ataque con sólo texto cifrado disponible: el criptoanalista solo tiene acceso a una colección de textos cifrados o codificados.
• Ataque con texto claro conocido: el atacante tiene un conjunto de textos cifrados de los que conoce el correspondiente texto claro o descifrado.
• Ataque con texto claro escogido (ataque con texto cifrado elegido): el atacante puede obtener los textos cifrados (claros) correspondientes a un conjunto arbitrario de textos claros (cifrados) de su propia elección.
• Ataque adaptativo de texto claro escogido: como un ataque de texto claro escogido, pero el atacante puede elegir textos claros subsiguientes basándose en la información obtenida de los descifrados anteriormente. Similarmente, existe el ataque adaptativo de texto cifrado escogido.
• Ataque de clave relacionada: como un ataque de texto claro escogido, pero el atacante puede obtener texto cifrado utilizando dos claves diferentes. Las claves son desconocidas, pero la relación entre ambas es conocida; por ejemplo, dos claves que difieren en un bit.

Estos tipos de ataque difieren evidentemente en la plausibilidad de que ocurran en la práctica. Aunque algunos son más probables que otros, los criptógrafos suelen adoptar un enfoque conservador y asumir el peor caso imaginable cuando diseñan algoritmos, razonando que si un sistema es seguro incluso contra amenazas tan poco realistas, entonces debería resistir también al criptoanálisis en el mundo real.

Los supuestos en los que se basan estos ataques son a menudo más realistas de lo que podría parecer a primera vista. Para obtener un ataque con texto claro conocido, el criptoanalista podría muy bien conocer o ser capaz de inferir una parte que probablemente forma parte del texto claro, como por ejemplo el encabezamiento de una carta cifrada ("Estimado Sr."), o que el inicio de una sesión de ordenador contenga las letras "LOGIN". Un ataque de texto claro escogido es menos probable, pero en algunos casos puede ser plausible: por ejemplo, si convences a alguien para reenviar un mensaje que tú mismo le has mandado antes, pero en forma cifrada. Los ataques de clave relacionada son básicamente teóricos, aunque pueden ser realistas en ciertas situaciones, como por ejemplo al construir funciones hash criptográficas utilizando un cifrado por bloques.

Los resultados de un criptoanálisis también pueden variar en utilidad. Por ejemplo, el criptógrafo Lars Knudsen (Knudsen, 1998) clasificó varios tipos de ataque sobre cifrados por bloques de acuerdo con la cantidad y la calidad de la información secreta que pudiera ser descubierta:

• Ruptura total - el atacante deduce la clave secreta.
• Deducción global - el atacante descubre un algoritmo funcionalmente equivalente para el cifrado y descifrado de mensajes, pero no obtiene la clave.
• Deducción local (o de instancia) - el atacante descubre textos claros o cifrados adicionales a los conocidos previamente.
• Deducción de información - el atacante descubre alguna información en el sentido de Shannon que no era conocida previamente.
• Distinción del algoritmo - el atacante puede distinguir la información cifrada de una permutación al azar.

Se pueden aplicar estas categorías a los ataques sobre otros tipos de algoritmos.

Los ataques se pueden categorizar por la cantidad de recursos que requieren. Estos pueden tomar la forma de:

• Tiempo - el número de "operaciones primitivas" que deben ser realizadas. Esta categoría es bastante vaga; las operaciones primitivas podrían considerarse como instrucción básica de computación, como una suma, una operación XOR, un desplazamiento bit a bit, etc., o como métodos de cifrado enteros.
• Memoria - la cantidad de almacenamiento necesario para realizar el ataque.
• Datos - la cantidad de textos claros y cifrados necesaria.

En la criptografía académica, una debilidad o una ruptura en un algoritmo se definen de una manera bastante conservadora. Bruce Schneier resume esta posición de la siguiente manera: "Romper un cifrado simplemente significa encontrar una debilidad en el cifrado que puede ser explotada con una complejidad inferior a la de la fuerza bruta. No importa que la fuerza bruta pudiera requerir 2¹²⁸ cifrados; un ataque que requiera 2¹¹⁰ cifrados se consideraría una ruptura... puesto de una manera simple, una ruptura puede ser tan sólo una debilidad certificacional: una evidencia de que el código no es tan bueno como se publicita" (Schneier, 2000).

Hay multitud de métodos de ataque criptoanalíticos. Estos se pueden clasificar en a si están especializado en algún tipo de criptografía o si son más generales. Los principales son los siguientes:

• Especializados en cifrado clásico:
  • Análisis de frecuencias
  • Método Kasiski
  • Índice de coincidencia
  • Índice mutuo de coincidencia
• Especializados en criptografía simétrica:
  • Criptoanálisis diferencial
  • Criptoanálisis lineal
  • Criptoanálisis integral
  • Criptoanálisis estadístico
  • Criptoanálisis de módulo n
  • Ataque XSL (eXtended Sparse Linearisation)
  • Ataque de deslizamiento
• Generales (aplicados en distintos ámbitos):
  • Ataque de cumpleaños
  • Ataque Man-in-the-middle
  • Ataque Meet-in-the-middle
  • Ataque de fuerza bruta
  • Jardinería (criptoanálisis)
  • Análisis de energía

Primera página de Un manuscrito para el descifrado de mensajes criptográficos, de Al-Kindi.

Aunque la expresión criptoanálisis es relativamente reciente (fue acuñada por William F. Friedman en 1920), los métodos para romper códigos y cifrados son mucho más antiguos. La primera explicación conocida del criptoanálisis se debe al sabio árabe del siglo IX, Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi, en su Manuscrito para Descifrar Mensajes Criptográficos. Este tratado incluye una descripción del método de análisis de frecuencias (Ibraham, 1992).

El análisis de frecuencias es la herramienta básica para romper los cifrados clásicos. En todas las lenguas conocidas, ciertas letras del alfabeto aparecen más frecuentemente que otras; por ejemplo, en español, las vocales son muy frecuentes, ocupando alrededor del 45% del texto, siendo la E y la A las que aparecen en más ocasiones, mientras que la frecuencia sumada de F, Z, J, X, W y K no alcanza el 2%. Igualmente, se pueden reunir estadísticas de aparición de pares o tríos de letras. El análisis de frecuencias revelará el contenido original si el cifrado utilizado no es capaz de ocultar estas estadísticas. Por ejemplo, en un cifrado de substitución simple (en el que cada letra es simplemente substituida por otra), la letra más frecuente en el texto cifrado sería un candidato probable para representar la letra "E".

El análisis de frecuencias se basa tanto en el conocimiento lingüístico como en las estadísticas, pero al volverse cada vez más complicados los cifrados, las matemáticas se convirtieron gradualmente en el enfoque predominante en el criptoanálisis. Este cambio fue particularmente evidente durante la Segunda Guerra Mundial, cuando los esfuerzos para romper los códigos del Eje requirieron nuevos niveles de sofisticación matemática. Más aún, la automatización fue aplicada por primera vez en la Historia al criptoanálisis, bajo la forma de los dispositivos Bomba y Colossus, una de las primeras computadoras.

Réplica de un dispositivo Bombe.

Aunque la computación fue utilizada con gran éxito durante la Segunda Guerra Mundial, también hizo posible nuevos métodos criptográficos que eran órdenes de magnitud más complejos que los empleados hasta la fecha. Tomada como un todo, la criptografía moderna se ha vuelto mucho más impenetrable al criptoanalista que los métodos de pluma y papel del pasado, y parece que en la actualidad llevan ventaja sobre los métodos del puro criptoanálisis. El historiador David Kahn escribió: "Son muchos los criptosistemas en venta hoy por parte de cientos de compañías comerciales que no pueden ser rotos por ningún método conocido de criptoanálisis. De hecho, en ciertos sistemas incluso un ataque de texto claro escogido, en el que un fragmento de texto claro seleccionado es comparado con su versión cifrada, no permite conocer el código para romper otros mensajes. En cierto sentido, entonces, el criptoanálisis está muerto. Pero éste no es el final de la historia. El criptoanálisis puede estar muerto, pero, mezclando mis metáforas, hay más de un modo de desollar un gato." (Observaciones sobre el 50 Aniversario de la National Security Agency, 1 de noviembre de 2002). Kahn menciona a continuación las mayores posibilidades para la intercepción, la colocación de dispositivos grabadores ("bugging"), los ataques de canal lateral y la criptogtafía cuántica como sustitutos de los métodos tradicionales del criptoanálisis.

Kahn podría haberse apresurado demasiado al declarar al criptoanálisis muerto; aún no se han extinguido los cifrados débiles. En medios académicos, se presentan regularmente nuevos diseños, y también son rotos frecuentemente: el cifrado por bloques Madryga, de 1984, demostró ser vulnerable a un ataque con solo texto cifrado disponible en 1998; FEAL-4, propuesto como sustituto para el algoritmo estándar de cifrado de datos DES fue demolido por una avalancha de ataques de la comunidad académica, muchos de los cuales no eran enteramente realizables en condiciones prácticas. En la industria, igualmente, los cifrados no están exentos de fallos: por ejemplo, los algoritmos AS/1, AS/2 y CMEA, usados en la industria de teléfonos móviles, pueden ser rotos en horas, minutos o incluso en tiempo real por equipo informático ampliamente disponible. En 2001, se demostró que el algoritmo WEP, utilizado para proteger redes Wi-Fi, es susceptible de ser atacado mediante un ataque de clave relacionada.

El Telegrama Zimmerman, descifrado.

Los criptoanálisis exitosos han influido sin lugar a dudas en la Historia. La capacidad de leer los pensamientos, supuestamente secretos, o los planes de otros puede ser una ventaja decisiva, y nunca con mayor razón que en tiempos de guerra. Por ejemplo, durante la Primera Guerra Mundial, el descifrado del Telegrama Zimmermann fue capital para la entrada de los Estados Unidos en la guerra. En la Segunda Guerra Mundial, el criptoanálisis de los códigos alemanes, incluyendo la máquina Enigma y el código Lorenz, ha sido considerado desde un factor que apenas acortó la guerra en algunos meses en Europa, hasta un elemento crucial que determinó el resultado final (véase ULTRA). Los Estados Unidos también se beneficiaron del criptoanálisis del código japonés PURPLE durante la contienda (véase MAGIC).

Todos los gobiernos han sido conscientes desde antiguo de los potenciales beneficios del criptoanálisis para la inteligencia militar, tanto en lo puramente bélico como en lo diplomático, y han establecido con frecuencia organizaciones dedicadas en exclusiva al descifrado de códigos de otras naciones, por ejemplo GCHQ y NSA, organizaciones americanas todavía muy activas hoy en día. En 2004, surgió la noticia de que los Estados Unidos habían roto los códigos utilizados por Irán: ).