MOOC El algoritmo RSA


Lección 9. Ataque por cifrado cíclico
Dr. Jorge Ramió Aguirre - 16/11/2012 

La lección 9, Ataque por cifrado cíclico, nos servirá para destruir una máxima en criptografía de clave pública, que nos decía que para descifrar un criptograma resultado de la cifra de un mensaje con una clave, por ejemplo la pública de destino, la única solución era utilizar el mismo algoritmo pero usando la clave inversa, en este caso la clave privada de destino. Veremos cómo es posible descifrar ese criptograma usando la misma clave de cifra, es decir la clave pública, mediante un ataque que utiliza sólo datos de la víctima que son públicos. Otro tema es que esto implique mucho tiempo de cómputo para claves de tamaños actuales sobre los mil bits. Con ello, no romperemos la clave privada del destino pero sí el secreto o confidencialidad que se esperaba lograr con esa cifra.

Si deseas descargar las diapositivas del curso en formato pptx animado o bien en pdf, puedes hacerlo desde esta dirección.

Este icono y el fondo de color amarillo te indican que entras en una zona de prácticas.

Este icono y el fondo de color azul te indican que entras en una zona de cuestiones para reflexionar e investigar.

El tiempo recomendado para el seguimiento de esta lección, la realización de sus prácticas y ejercicios, así como la búsqueda de información en la red sobre los temas abiertos planteados al final de cada apartado, es de dos semanas.

Temario

Objetivos

  • 1. Comprobar que en RSA es posible romper el secreto de una cifra sin conocer la clave privada del destinatario.
  • 2. Obtener conclusiones sobre la viabilidad de este tipo de ataque.

Software que vas a utilizar en esta lección


APARTADO 9.1. ATAQUE AL SECRETO MEDIANTE CIFRADO CICLICO

En la Lección 4 comprobamos que un mensaje secreto cifrado con la clave pública del destino, típica operación en el intercambio de clave, sólo podía descifrarse y recuperar ese secreto usando la clave privada de destino, es decir la inversa de la usada en el proceso de cifra, o bien con alguna clave privada pareja.

Ahora veremos que también será posible romper ese secreto usando nuevamente la misma clave pública, algo que estaría en contra de toda la lógica de los sistemas de cifra asimétrica o de clave pública.

El problema que se nos presenta es que entonces cualquiera que conozca las claves usadas en el proceso de cifra o intercambio de clave, podría en teoría recuperar el secreto. Y conocer las claves públicas de un destinatario es muy fácil, están expuestas en su certificado digital X.509 al alcance de todos por su carácter público como se observa en la siguiente figura, si bien como es lógico ataques a claves con números grandes son actualmente inviables.

Clave pública de una entidad bancaria

La cuestión es la siguiente:

Como C = Ne mod n, con N un valor secreto, vamos a realizar cifrados sucesivos de los criptogramas Ci resultantes con la misma clave pública e. Si en uno de estos cifrados obtenemos nuevamente el cifrado C original con el que se ha iniciado el ataque, resulta obvio que el valor del paso anterior será el secreto N buscado.

Esto se debe a que RSA es un grupo mutiplicativo. Para dificultar este tipo de ataques, es interesante usar primos seguros de forma que los subgrupos de trabajo sean lo suficientemente altos.

Por tanto, conocido o capturado el criptograma C, realizaremos los siguientes cifrados:

  Ci = Cei-1 mod n;   para i = 1, 2, ..., con C0 = C

Si en el cifrado iésimo se encuentra el criptograma C inicial, entonces el cifrado anterior (i-1) será el número secreto, como se muestra en el siguiente ejercicio.

Ejercicio 9.1.1

Capturas un criptograma C = 50 en el que sabes va enmascarada una clave secreta K que ha enviado Alicia a Bernardo, de quien sólo conoces sus claves públicas n = 187 y e = 7.
Aunque para este caso sería elemental encontrar los primos p y q factorizando el módulo 187 = 11 x 17, vamos a ver qué sucede haciendo un ataque por cifrado cíclico.
Para ello usaremos simplemente la calculadora de Windows.
Solución:
  1ra operación: Ce mod n = 507 mod 187 = 118
  2da operación: Ce mod n = 1187 mod 187= 101
  3ra operación: Ce mod n = 1017 mod 187= 84
  4ta operación: Ce mod n = 847 mod 187= 50
Como en la cuarta operación se ha llegado al valor 50 con el que partimos en el ataque, resulta claro que la clave secreta era K = 84.

En este ejemplo hemos realizado tan sólo 4 operaciones para romper el secreto. El número de operaciones necesarias hasta encontrar el secreto va a depender del valor con el que comencemos el ataque. ¿Qué sucedería si, por ejemplo, el valor del criptograma inicial fuese 100 en vez de 50?

Ejercicio 9.1.2

Usando la calculadora de Windows, inicia ahora el ataque con el criptograma capturado C = 100, siendo las claves públicas n = 187 y e = 7.
Solución:
  1ra operación: Ce mod n = 1007 mod 187 = 144
  2da operación: Ce mod n = 1447 mod 187= 100
En este otro caso sólo hemos necesitado 2 operaciones para romper el secreto K = 144.

Como has podido observar, el número de vueltas necesarias hasta romper el secreto va a depender del valor con el cual arranque el ataque, es decir, el criptograma que se ha capturado.

No obstante, el programa genRSA para mayor claridad no inicia el ataque introduciendo el criptograma C sino el mensaje en claro M, pero lógicamente en el fondo es lo mismo. En el siguiente apartado veremos cómo se comporta el ataque en función del valor de entrada.

Cuestiones para reflexionar e investigar:
1. ¿Por qué se dice que este ataque va en contra de los principios de la criptografía de clave pública?


APARTADO 9.2. INCIDENCIA DEL VALOR CAPTURADO EN EL ATAQUE

Para comprobar el papel que juega en el ataque por cifrado cíclico el valor con el que éste se inicia, vamos a realizar la siguiente práctica.

Práctica 9.2.1

Con el programa genRSA crea las siguientes claves y haz un ataque cíclico con los valores que se indican.
Anota el número de vueltas que debe realizar el programa hasta dar con el secreto.
  Clave 1) p = 367, q = 487, e = 713. Valores de ataque: 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 y 30. Número cifrados: 500
  Clave 2) p = 1949, q = 1889, e = 51. Valores de ataque: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 y 20. Número cifrados: 3.000

Solución:
La figura muestra uno de los ataques que debes realizar.

Ataque por cifrado cíclico a la clave con n = 178.729 y e = 713

Como has podido comprobar, en función del valor de la entrada, se rompe el secreto para valores distintos de vueltas. En este caso y dependiendo de la entrada, para la clave 1 encontrarás 90, 270 y 810, vueltas y 783, 1.566, 3.132 y 6.264 vueltas para la clave 2. Compruébalo y observa además que estos valores son múltiplos.

Para claves pequeñas como la anterior, si quieres puedes dejar seleccionada en genRSA la opción "Obtener todos los valores" que te servirá para hacer un seguimiento del documento html que genera el software. Para claves mayores, deja la opción marcada por defecto pues significaría una carga excesiva para tu ordenador y bajaría su rendimiento.

Algo más. Antes de realizar un ataque a claves grandes, ten en cuenta que dependiendo de la velocidad de tu ordenador, la tasa de operaciones en este tipo de ataque con el software genRSA oscilará entre los 400 y los 500 cifrados por segundo en una máquina Intel(R) Core(TM) i7-2600 con CPU de 3,40 GHz y Sistema Operativo de 64 bits.

Por lo tanto, si un ataque prospera en torno a las 300.000 vueltas, deberás esperar en el mejor de los casos al menos 10 minutos.

El problema de este tipo de ataque es que, además de necesitar como dato el criptograma, es decir que es necesario capturar previamente esa información, no resulta sencillo llevarlo a un escenario de ataque distribuido pues los subgrupos que se forman son muy grandes cuando aumenta el tamaño de la clave. Existe una proporcionalidad entre el tamaño del módulo n y el tamaño de la ventana de cifrados del ataque, con lo cual va a ser muchísimo más difícil atacar, por ejemplo, una clave de 100 bits que una de 80.

Por otra parte como ya hemos visto, existe también una gran dispersión en el número de cifrados necesarios para que prospere el ataque ante claves de iguales dimensiones. En las siguientes figuras se muestran dos tablas que muestran este efecto.

1) La primera con el número más repetido y común de vueltas necesarias para que prospere un ataque por cifrado cíclico ante diferentes claves, todas de 24 bits, con diferentes entradas aleatorias del valor M.

Vueltas necesarias en un ataque a claves de 24 bits

2) En la segunda, se ataca el mensaje en claro 123 también con claves de 24 bits, manteniendo ahora constantes el valor del primo p y de la clave pública e. Se varía el valor del primo q dentro del rango de la clave, en tres casos eligiendo q como primo seguro. Al final de esta segunda tabla ambos primos p y q se eligen como primos seguros.

Vueltas para romper el secreto M = 123 para diferentes claves de 24 bits

Para que las tablas anteriores estuviesen completas, debería realizarse un barrido automático de ataques a centenas o miles de claves del mismo tamaño y con centenas o miles de valores de entrada en cada caso, apuntando además todos los valores obtenidos de vueltas. Con todo lo interesante que ello pueda ser, se escapa del objetivo de este curso y es más que suficiente para este momento haber visto el comportamiento de este particular ataque al secreto de una cifra.

No obstante, de la primera tabla podría deducirse, siempre en una primera aproximación, que el factor suerte jugará un papel muy importante en este ataque, en tanto los valores de los primos p y q son aleatorios y en un escenario de ataque a una clave de 24 bits como el de la tabla anterior, bien podríamos haber necesitado solamente una centena de cálculos para romper el secreto en la primera clave, como más de medio millón en la última.

Por otra parte, siguiendo ahora la segunda tabla, al utilizar primos seguros en la generación de la clave, observamos una tendencia a que los espacios de colisión sea mayores que con primos no seguros, algo que analizaremos con más detalle en un próximo apartado.

Ataque por cifrado cíclico a clave de 22 bits que necesita más de medio millón de cifrados

Práctica 9.2.2

Usa el programa genRSA y realiza una tabla similar a la que acabas de ver para una docena de claves diferentes de 18 bits. En este caso realiza ataques a cada clave al menos con 25 valores distintos para encontrar la dispersión de vueltas necesarias que hemos visto al comienzo del apartado.
Puedes usar la tabla de primos que verás en el programa ExpoCrip.

Cuestiones para reflexionar e investigar:
1. ¿Tiene alguna relación el número de cifrados necesarios para que prospere el ataque con los valores de p y q?
2. ¿A qué conclusiones has llegado sobre las vueltas necesarias encontradas para una clave con distintos valores de ataque?
3. Deja tu ordenador trabajando muchas horas para realizar un ataque a una clave de 32 bits con genRSA. Aunque parezca que el programa no responde, ten paciencia, es normal. O bien, si puedes ver tu ordenador cada 10 minutos por ejemplo, pon un número de cifrados no demasiado alto para que compruebes que el programa te va dando la opción de continuar si el ataque no ha prosperado. ¿Qué ha sucedido?


APARTADO 9.3. INCIDENCIA DEL VALOR DE LA CLAVE PUBLICA e EN EL ATAQUE

Como este ataque se lleva a cabo realizando sucesivos cifrados con la clave pública e, es decir VALORe mod n, podríamos pensar que ese valor de la clave pública e -que está en el exponente de la operación- va a incidir en la tasa de cifrados y, por tanto, en el rendimiento del ataque.

Esto es cierto pero sólo en parte. No resultará significativo ese parámetro porque, como sabemos, la clave pública siempre será un valor relativamente bajo.

La tabla siguiente muestra la tasa de cifrados por segundo que alcanza el programa genRSA en este ataque, en función del tamaño de la clave pública e con valores desde dos hasta cinco dígitos, para una máquina Intel(R) Core(TM) i7-2600 con CPU de 3,40 GHz y Sistema Operativo de 64 bits. No es necesario aumentar más ese tamaño dado que la clave pública estándar es el número 4 de Fermat 65.537, de cinco dígitos.

Los valores utilizados en la tabla para la clave pública e son:
  e = 23 = 10111 (con 4 bits en 1)
  e = 421 = 110100101 (con 5 bits en 1)
  e = 6.941 = 1101100011101 (con 8 bits en 1)
  e = 37.867 = 1001001111101011 (con 10 bits en 1)
  e = 65.537 = 10000000000000001 (con 2 bits en 1)

Tasa de cifrados por segundo en función del tamaño clave pública

Si bien los valores de la clave pública tienen distintos tamaños y un número creciente de bits en 1, que deberían hacer algo más lenta la operación de cifra C = Me mod n, lo cierto es que esto no influye en la tasa de cifra de este ataque como se observa en la tabla anterior con un mínimo de 80.000 lecturas, debido a que son valores pequeños. Incluso para números grandes este dato de cambio en la tasa de cifrados no es significativo, al menos en este ataque, y puede además tener muchas oscilaciones en función del valor con el que comience el ataque y los valores de la clave, bien en decimal como en hexadecimal.

Con todo, no hay que perder de vista que el programa genRSA tiene un carácter educativo y, como tal, su objetivo se centra sólo en ser una herramienta de laboratorio para prácticas con el sistema de cifra RSA, sin otras pretensiones.

En la siguiente tabla se muestran algunos valores del número de vueltas necesarios para romper el secreto con el programa genRSA, para las mismas claves públicas del ejemplo anterior y para diferentes valores de inicio en el ataque, en este caso M = 12, M = 123, M = 1.234, M = 12.345 y M = 123.456.

Vueltas necesarias en función de la clave pública y del valor de ataque

Observa que los 8 números distintos de vueltas que hay en la tabla (39.507; 118.521; 302.887; 605.774; 1.817.322; 3.634.644; 5.451.966; 10.903.932) para esa clave, tienen como máximo común divisor el valor 13.169.

Máximo común divisor de los números de vueltas de la tabla   (http://easycalculation.com/hcf.php)

Aunque este resultado tiene importancia en cuanto a los subgrupos que se forman en RSA, no profundizaremos en ello.

Práctica 9.3.1

Termina de rellenar la tabla anterior incluyendo los 5 valores pendientes marcados con un signo de interrogación. Como la tasa del ataque con genRSA para claves de 32 bits se encuentra como máximo en unos 500 cifrados por segundo, en algunos casos deberás tener mucha paciencia y dejar a tu ordenador trabajar durante muchas horas. Te recomiendo lo hagas en horas muertas, estableciendo por ejemplo una ventana de 10 millones de cifrados para unas 8 horas de trabajo.

Cuestiones para reflexionar e investigar:
1. ¿Tiene alguna influencia el valor de la clave pública e en el rendimiento de este tipo de ataque?
2. ¿Significa algo que los números de vueltas de la tabla anterior tengan como máximo común divisor el valor 13.169?
3. ¿Crees que se podría paralelizar este tipo de ataque? ¿En ese caso, cómo lo harías?


APARTADO 9.4. ATAQUE POR CIFRADO CICLICO A CLAVES CON PRIMOS SEGUROS

Cuando usamos primos seguros en el apartado anterior, hemos podido observar un incremento en la dificultad para realizar este ataque. Vamos entonces a profundizar qué sucede con este ataque cuando ambos primos en la clave son seguros. En este caso analizaremos tres claves muy parecidas, de 16, 20, 24 28 y 32 bits, para poder sacar unas primeras conclusiones.

En cada una de las mediciones, en la clave intermedia los valores de p y q serán primos seguros, y en las otras claves p y q serán valores primos no seguros inmediatamente inferiores a esos primos seguros en el primer caso e inmediatamente superiores en el segundo. Usaremos la misma clave pública e y los mismos números de ataque para las tres claves.

Claves de 16 bits:
  K1: p = 173, q = 257, n =44.461, e = 23, ataque: 4748 y 12345 (p y q primos inferiores próximos de K2)
  K2: p = 179, q = 263, n = 47.077, e = 23, ataque: 4748 y 12345 (p y q primos seguros)
  K3: p = 181, q = 269, n = 48.689, e = 23, ataque: 4748 y 12345 (p y q primos superiores próximos de K2)

Claves de 20 bits:
  K4: p = 709, q = 859, n = 609.031, e = 41, ataque: 12345 y 70758 (p y q primos inferiores próximos de K5)
  K5: p = 719, q = 863, n = 620.497, e = 41, ataque: 12345 y 70758 (p y q primos seguros)
  K6: p = 727, q = 877, n = 637.579, e = 41, ataque: 12345 y 70758 (p y q primos superiores próximos de K5)

Claves de 24 bits:
  K7: p = 1483, q = 2029, n = 3.009.007, e = 421, ataque: 12345 y 70758 (p y q primos inferiores próximos de K8)
  K8: p = 1487, q = 2039, n = 3.031.993, e = 421, ataque: 12345 y 70758 (p y q primos seguros)
  K9: p = 1489, q = 2053, n = 3.056.917, e = 421, ataque: 12345 y 70758 (p y q primos superiores próximos de K8)

Claves de 28 bits:
  K10: p = 14419, q = 15761, n = 227.257.859, e = 131, ataque: 12345 y 70758 (p y q primos inferiores próximos de K11)
  K11: p = 14423, q = 15767, n = 227.407.441, e = 131, ataque: 12345 y 70758 (p y q primos seguros)
  K12: p = 14431, q = 15773, n = 227.620.163, e = 131, ataque: 12345 y 70758 (p y q primos superiores próximos de K11)

Claves de 32 bits:
  K13: p = 55609, q = 64303, n = 3.575.825.527, e = 2011, ataque: 12345 y 70758 (p y q primos inferiores próximos de K14)
  K14: p = 55619, q = 64319, n = 3.577.358.461, e = 2011, ataque: 12345 y 70758 (p y q primos seguros)
  K15: p = 55621, q = 64327, n = 3.577.932.067, e = 2011, ataque: 12345 y 70758 (p y q primos superiores próximos de K14)

Generamos las claves, realizamos ataques con los valores indicados y obtenemos las siguientes tablas. Si usamos además distintos números como comienzo del ataque, en la mayoría de los casos se obtienen estos mismos valores.

Ataque por cifrado cíclico a una clave K2 de 16 bits con primos seguros y a sus claves cercanas

Ataque por cifrado cíclico a una clave K5 de 20 bits con primos seguros y a sus claves cercanas

Ataque por cifrado cíclico a una clave K8 de 24 bits con primos seguros y a sus claves cercanas

Ataque por cifrado cíclico a una clave K11 de 28 bits con primos seguros y a sus claves cercanas

Ataque por cifrado cíclico a una clave K14 de 32 bits con primos seguros y a sus claves cercanas

Si tienes curiosidad por conocer el valor exacto de vueltas necesarias para romper el secreto en la última clave K14 de 32 bits con primos seguros, ármate de paciencia porque tu ordenador deberá trabajar una semana para conseguir el objetivo. Te recuerdo que el programa genRSA es un software educacional que no tiene como objetivo ser un programa para realizar ataques; es decir, estos tiempos pueden optimizarse con otro código si lo que se desea es realizar ataques.

A partir de este ejemplo y otros similares que te recomiendo hagas, podríamos concluir que es recomendable usar primos seguros pues dificulta también este ataque. Algo que iría en consonancia con el valor añadido que nos daba el uso de primos seguros en la generación de claves RSA, como ya hemos comprobado en lecciones anteriores.

No obstante, al igual que en el caso anterior sobre la diversidad de vueltas necesarias para los ataques a claves con módulos de igual tamaño, para llegar a una conclusión definitiva sobre la fortaleza que añade el uso de primos seguros en la clave ante este ataque, será necesario realizar un análisis matemático más profundo del tema, así como presentar una amplia batería de pruebas, que van más allá del objetivo de esta lección.

Práctica 9.4.1

Usando el programa genRSA repite el ejercicio anterior para claves de 18 y 20 bits y usa, además, otros valores similares de los primos p y q de forma que el módulo n sea lo más parecido posible en todas las claves.
Nuevamente puedes usar la tabla de primos que verás en el programa ExpoCrip.

Cuestiones para reflexionar e investigar:
1. ¿Por qué crees que se vuelve más difícil el ataque a una clave generada con primos seguros?
2. ¿Crees que este ataque podría convertirse una vulnerabilidad en claves de 1.024 bits?


APARTADO 9.5. TEST DE EVALUACION DE LA LECCION RSA09

En las siguientes 5 preguntas, elige la respuesta correcta.

1. El ataque por cifrado cíclico vulnera:

a) El secreto de la clave privada
b) El secreto del mensaje
c) El secreto de la trampa o Indicador de Euler

2. Para realizar un ataque por cifrado cíclico es necesario conocer:

a) El módulo público n de la víctima
b) La clave privada o una privada pareja de la víctima
c) Las claves públicas n y e de la víctima

3. Una particularidad del ataque por cifrado cíclico es que:

a) Independientemente de la entrada, ejecuta el mismo número de vueltas
b) En función de la entrada, puede tardar más o menos tiempo en prosperar
c) Se ejecuta más rápido si la entrada es un número primo

4. El uso de primos seguros en la generación de la clave RSA:

a) Dificulta el ataque por cifrado cíclico
b) No afecta al tiempo de ejecución del ataque por cifrado cíclico
c) Reduce a la mitad el tiempo de ejecución del ataque por cifrado cíclico

5. Para claves de 1.024 bits o mayores, podríamos asegurar que el ataque por cifrado cíclico:

a) Podría ser una amenaza al sistema RSA
b) Es una amenaza inminente al sistema RSA
c) No es una amenaza real al sistema RSA


Ir a: [Portada c4y]    [Lección 8] [Índice] [Lección 10]