PDF de programación - RSA cumple 36 años y se le ha caducado el carné joven

Rooted CON 2014

RSA cumple 36 años y se le ha caducado el carné joven

Dr. Jorge Ramió - UPM - Criptored
Madrid, viernes 7 de marzo de 2014


RESUMEN

Se repasa la historia de este longevo algoritmo estándar de clave pública, que a pesar del paso
del tiempo sigue resistiéndose ante ataques de todo tipo; desde aquellos con tintes muy
académicos como la factorización entera o el ataque con un divide y vencerás mediante la
paradoja del cumpleaños, que a fecha de hoy se muestran impracticables para claves grandes,
hasta los más sofisticados y recientes ataques basados en el concepto de canal lateral, que en
este caso sí son preocupantes. A pesar de ello y tras 36 años de vida, parece no vislumbrarse
un cambio en el estándar, al menos a corto plazo. Y para cuando ello ocurra, que eso algún día
va a ocurrir, ¿estaremos preparados o nos encontraremos ante otro Y2K o caso MD5?

I. INTRODUCCIÓN

Me preguntaba hace unos días un amigo de Palencia, de Villamuriel del Cerrato para ser más
precisos donde por cierto vienen realizando unas espléndidas Jornadas de Seguridad desde
hace tres años, que por qué le tengo tanto cariño a este algoritmo: mis apuntes de clases y en
especial el capítulo de criptografía asimétrica del libro electrónico de 2006 [1], el curso El
algoritmo RSA publicado en Crypt4you [2], el libro Cifrado de las comunicaciones digitales de la
cifra clásica al algoritmo RSA [3] de 0xWord escrito con mi colega el Dr. Alfonso Muñoz,
desarrollo de software para prácticas de laboratorio con dicho algoritmo a partir de trabajos
fin de carrera de algunos alumnos [4], varias conferencias impartidas sobre este tema, etc.

Una buena pregunta. La respuesta es muy sencilla y puede resumirse en tan sólo dos razones.

La primera, que RSA es un sistema de cifra muy simple, cuya seguridad está basada en un
principio matemático también muy simple y que todo el mundo es capaz de comprender:
multiplicar dos números primos, aunque éstos sean de muchos dígitos, es una tarea fácil, que
lógicamente nos va a requerir más tiempo si dichos números son cada vez más grandes pero,
por el contrario, conocido ese número producto de dos primos, encontrar esos dos valores
primos se transforma en una tarea muy difícil a medida que vamos haciendo ese número más
grande. En otras palabras, que si en el primer caso se va duplicando el tamaño de la entrada se
debe trabajar el doble en cada caso para hacer esos cálculos pero, en el segundo, este tiempo
de cómputo va a aumentar más del doble, y cada vez más, convirtiéndose así en una operación
de muy difícil resolución.

El concepto difícil se aquí asocia tanto a la necesidad de tiempo requerido para resolver el
problema como por los recursos de cómputo que son necesarios para tal fin, de manera que si
hablamos de productos de dos primos del mismo o similar tamaño cuyo resultado esté por
sobre los mil bits, esto es unos 300 dígitos decimales, dicho problema se vuelve literalmente
intratable. Es lo que en matemática se denominan problemas de tipo NP o No Polinomial. Con

RSA cumple 36 años - Madrid, marzo de 2014 - Rooted CON © Jorge Ramió

1

un par de ejemplos básicos y unos números no tan grandes será más que suficiente para todo
el mundo entienda a qué tipo de problema se están enfrentando; no hay que ser muy listos
para ello.

Y la segunda razón es que las matemáticas discretas que deben conocerse para comprender el
funcionamiento de RSA son conceptos extremadamente básicos. Si te dicen que “un cuerpo”
no es sólo el de Angelina Jolie o el de Brat Pitt, que sí lo son, sino que hay otros cuerpos
compuestos en este caso por muchos ceros y muchos unos, y que cuando llegas al final de ese
cuerpo ... no el de nuestros queridos amigos claro... no te caes al precipicio sino que vuelves al
punto de origen donde habías comenzado tu recorrido, como sucede con un reloj cuando una
aguja da toda una vuelta a la circunferencia, y comprendes de esta manera el concepto de un
cuerpo finito o módulo n de cifra, pues ya tenemos mucho avanzado.

Hay algún concepto más dentro de las matemáticas discretas conocido como inverso en un
cuerpo (que no invertido… esto daría juego para varias interpretaciones y comentarios fuera
de lugar) pero también de muy fácil comprensión. Si un número es el inverso de otro dentro de
un cuerpo, entonces la operación de cifra que realizo con mi clave privada (firma digital) la
pueden deshacer todos quienes conozcan mi clave pública (verificación de una firma), y la
operación de cifra que realizo con la clave pública de un destinatario (envío de un número
secreto, una clave de sesión por ejemplo) sólo la puede deshacer ese destinatario (intercambio
de clave) usando su clave privada. Estos son los principios básicos de la criptografía de clave
pública o criptografía asimétrica, simple como cualquier invento que se precie.

Las ecuaciones que rigen a RSA para generar claves y cifrar o firmar no las veremos en este
documento. Se pueden encontrar en infinidad de sitios en Internet, sin ir más lejos en el curso
y libros comentados al comienzo. Lo importante es que, pese a su simpleza y con más de 36
años a sus espaldas, RSA sigue aguantando el paso del tiempo. De hecho, aunque Rivest,
Shamir y Adleman lo inventan en 1977, el algoritmo se publica un mes de febrero de 1978 y
por tanto en febrero de 2014 (coincidiendo con la Rooted CON 2014) ha cumplido ya 36 años.

La idea de que si es algo es muy simple no va a funcionar ni se va a vender, o bien que debe
tener algún truco escondido o debilidad y que tarde o temprano se descubrirá, con RSA no ha
funcionado pues 36 años son muchos años, y en criptografía moderna eso es casi toda una
eternidad. Ni el glorioso y controvertido DES puede presumir de esos datos en su currículum.

Siendo un estándar ampliamente utilizado, RSA ha soportado todo tipo de ataques durante
más tres décadas y media, logrando sortear tempestades, aunque eso sí haciendo uso de un
procedimiento al que podríamos catalogar de algorítmicamente poco elegante pero efectivo,
como es aumentar el tamaño de la clave o, mejor dicho, del módulo o cuerpo en el que se
cifra. Es una solución, qué duda cabe, pero no podemos aumentar de forma indefinida el
tamaño del módulo de trabajo porque la velocidad y las prestaciones del sistema se resentirían
al ser estos sistemas de cifra asimétricos muy lentos.

Si bien siempre han existido nubarrones en su entorno, lo cierto es que últimamente ya no
sólo llueve sobre el algoritmo RSA sino que se avecina un verdadero diluvio al publicarse en


2

RSA cumple 36 años - Madrid, marzo de 2014 - Rooted CON © Jorge Ramió

diciembre de 2013 un interesante artículo, RSA Key Extraction via Low-Bandwidth Acoustic
Cryptanalysis [5], en el que los autores demuestran cómo es posible extraer, sin demasiadas
complicaciones todo hay que decirlo, una clave privada nada menos que de 4.096 bits
simplemente escuchando el sonido que éstos emiten en nuestro ordenador al hacer una
operación de descifrado o de firma digital, que es cuando se usa dicha clave. Destacar que
entre esos autores se encuentra Adi Shamir, uno de los inventores de RSA, y que ha sido
patrocinado por importante organismos. Podemos leer en el artículo: This work was sponsored
by the Check Point Institute for Information Security; by the Israeli Ministry of Science and
Technology; by the Israeli Centers of Research Excellence I-CORE program (center 4/11); and by
NATO’s Public Diplomacy Division in the Framework of "Science for Peace". [5].

Por último, es menester indicar que se ha elegido a RSA en este artículo por la novedad y el
impacto del trabajo anteriormente presentado, pero que este tipo de ataque por canal lateral
también funciona con otros algoritmos que realizan operaciones de exponenciación modular
como, por ejemplo, Difiie y Hellman o Elgamal. Es verdad que puede parecer una imagen
dantesca que con tan poco esfuerzo se rompa una clave de 4.096 bits, pero afortunadamente
hay también algunas contramedidas que pueden establecerse en la implementación de tales
algoritmos para que no se vean afectados por este tipo ataques, pero ello conlleva inversión
de dinero, esfuerzo tecnológico, adaptación de los protocolos, actualización de los estándares,
etc., algo que el tiempo ya nos ha demostrado infinidad de veces que no es inmediato. En esta
misma línea, debe mencionarse que el trabajo [5] se centra en el ataque a RSA en su
implementación en el programa de correo seguro GnuGP de la serie 1.x, y que nuevas
versiones de este programa ya cuentan con las contramedidas [6], propuestas además por los
propios autores de la investigación.

Analizaremos en este documento cosas interesantes y sorprendentes de este algoritmo,
porqué los ataques más tradicionales y que podríamos calificar incluso de ortodoxos no han
prosperado, ni creo lo harán en el futuro, y qué peligro tienen los ataques basados en canal
lateral.

II. UN POCO DE HISTORIA

Quince meses después de que dos investigadores de Stanford University, Whitfield Diffie y
Martin Hellman, con alguna ayuda de Ralph Merkle eso sí, cambiasen definitivamente los
conceptos y la historia de la criptografía tras su invento del intercambio de claves en la fecha
mítica de noviembre de 1976, que a la postre significa el nacimiento de la criptografía de clave
pública, en febrero de 1978 otros tres investigadores, ahora del Massachussets Institute of
Technology MIT, Ron Rivest, Adi Shamir y Leonard Adleman, dan