Siempre que se habla de criptografía de clave pública es obligado nombrar RSA como indiscutible rey. Otras cifras muy usadas son ElGamal y las basadas en curvas elípticas, a la que dedicaré un artículo en cuanto saque algo de tiempo. Después de más de 20 años de uso, que sepamos, RSA sigue siendo un criptosistema seguro. En cualquier caso, como ya os conté en otro artículo, si se usan valores pequeños para el módulo, éste es fácilmente factorizable en un tiempo razonable. Sin embargo, éste no es el único problema que puede presentar RSA. En este artículo vamos a hacer un repaso de algunas de las posibles debilidades de este criptosistema y, por lo tanto, posibles vectores de ataque.
Obviamente, encontrar un sistema de factorización eficiente, en tiempo polinómico, es el Santo Grial de todos los investigadores en criptografía. Actualmente, algunos de los algoritmos más eficientes que se conocen son la criba cuadrática, criba numérica o el algoritmo de factorización en curvas elípticas.
En cualquier caso, están muy lejos de poder romper una cifrado RSA de más de 1024 bits en un tiempo razonable, aunque para valores más pequeños, como ya vimos, es factible obtener la clave privada a partir de la clave pública en unas pocas horas.
Mejor lo vemos con un ejemplo: Si Alicia cifra un mensaje m para Bernardo, y el mismo mensaje m para Carlos, que comparten el módulo N en su clave RSA, tenemos el siguiente escenario.
\[c_{1}=m^{e_{1}} \mod{n}\]
\[c_{2}=m^{e_{2}} \mod{n}\]
Siendo c1 y c2 los mensajes cifrados por Alicia, e1 y e2 los exponentes de Bernardo y Carlos, respectivamente, y n el módulo común que ambos comparten. Si Eduardo intercepta estos dos mensajes c1 y c2, sabiendo que el texto en claro era el mismo, podrá obtener el mensaje original m sin necesidad de factorizar N. ¿cómo?
Eduardo conoce los exponentes de Bernardo y de Carlos, ya que forman parte de su clave pública. Si ambos exponentes son primos entre sí (lo cual es más que probable), podrá encontrar dos valores u y v tales que:
\[u\times e_{1} +v\times e_{2} =1\]
Se puede usar el algoritmo de Euclides extendido para obtener u y v fácilmente. Eduardo ya sólo tiene que hacer el sencillo cálculo siguiente para obtener el mensaje m.
\[m=c_{1}^u \times c_{2}^v mod(n)\]
¿Qué por qué funciona esto? Fácil. Como \(c_{1}=m^{e_{1}} \mod{n}\) y \(c_{2}=m^{e_{2}} \mod{n}\), y teniendo en cuenta que u o v van a ser negativos, podemos sustituir en la ecuación anterior:
\[c_{1}^u \times c_{2}^v \equiv (m ^{e_{1}})^u \times (m ^{e_{2}})^v \equiv m^{e_{1}\times u +e_{2}\times v} \equiv m \mod{n}\]
\[m^{e} \mod{n_{1}} = c_{1}\]
\[m^{e} \mod{n_{2}} = c_{2}\]
\[m^{e} \mod{n_{3}} = c_{3}\]
Usando el Teorema Chino del Resto es posible resolver el sistema.
Si Alicia cifra un mensaje para Bernardo haciendo \(c=m^{e} \mod{n}\), Eduardo puede volver a cifrar repetidamente c usando la clave pública de Bernardo. En algún momento obtendrá de nuevo el valor c, lo que querrá decir que el valor que cifró en el paso anterior era el mensaje m.
Este ataque es muy lento para claves grandes, e incluso menos eficiente que los métodos de factorización nombrados más arriba.
Una formulación más o menos formal es que si tengo una función matemática f(x) que puede generar n resultados diferentes, siendo n un número grande, probabilísticamente sólo necesitamos evaluar la función \(1,2\sqrt{n}\) veces hasta que seamos capaces de encontrar dos valores x1 y x2 tales que f(x1)=f(x2). Es lo que se conoce como una colisión.
Aunque no lo parezca, que sólo haya que probar \(1,2\sqrt{n}\) valores de f(x) es un resultado sorprendente y choca frontalmente contra nuestra intuición.
El nombre de paradoja del cumpleaños se usa ya que para mostrar de forma gráfica este resultado se suele poner el ejemplo siguiente:
Si escogemos al azar 23 personas, la probabilidad de que dos de ellas cumplan años el mismo día y el mismo mes es de 0,507. Es decir, esto se dará con una probabilidad del 50,7% con sólo 23 personas.
En definitiva, la idea es que si tenemos una función f(m,k)=c, siendo m el mensaje que se quiere cifrar, k la clave y c el mensaje cifrado, es posible encontrar un un k' tal que f(m,k')=c. Además, por la paradoja del cumpleaños sabemos que probando al azar hay una probabilidad superior a la que intuitivamente podríamos esperar de encontrar dicho k'. O lo que es lo mismo, encontrar una colisión.
De nuevo, la forma de protegerse de este ataque es usar número lo suficientemente grandes para generar las claves como para que no sea rentable computacionalmente usar este método.
Hay más posibles debilidades en RSA, algunas tan exóticas como analizar el tiempo que tarda el procesador en computar las claves, pero por hoy ya está bien. Si quieres más información te recomiendo leer el fantástico artículo de Dan Boneh de la Universidad de Stanford.
Factorizar el módulo
La clave pública RSA está compuesta por dos valores (N, E) que son conocidos como el módulo y el exponente, respectivamente. El módulo N es un valor calculado a partir del producto de dos números primos grandes (a los que llamaremos p y q). Baste saber que la clave privada se calcula a partir de estos dos valores para hacerse una idea del gran problema al que nos enfrentaríamos si fuéramos capaces de encontrar esos dos valores p y q que multiplicados dan el valor N. Puede parecer que no es un problema muy complejo, sin embargo, la factorización del producto de dos números primos grandes es un problema abierto que no es resoluble en un tiempo razonable (hablamos de miles de años según sea el tamaño de los números).Obviamente, encontrar un sistema de factorización eficiente, en tiempo polinómico, es el Santo Grial de todos los investigadores en criptografía. Actualmente, algunos de los algoritmos más eficientes que se conocen son la criba cuadrática, criba numérica o el algoritmo de factorización en curvas elípticas.
En cualquier caso, están muy lejos de poder romper una cifrado RSA de más de 1024 bits en un tiempo razonable, aunque para valores más pequeños, como ya vimos, es factible obtener la clave privada a partir de la clave pública en unas pocas horas.
Ataque por módulo común
Encontrar un buen par de valores p y q a partir de los que calcular el módulo N no es siempre sencillo. Hay que escoger bien los valores y se deben cumplir ciertos requisitos para que sean seguros. Ante esta dificultad, es común que, cuando se deben generar múltiples claves para varios usuarios, se use el mismo módulo para todos ellos, pero con distinto exponente E. En principio, si el exponente es diferente, la clave privada sigue estando a buen recaudo, pero si se cifra el mismo mensaje para dos usuarios diferentes (que comparten el módulo N), es posible recuperar el mensaje original sin necesidad de factorizar N.Mejor lo vemos con un ejemplo: Si Alicia cifra un mensaje m para Bernardo, y el mismo mensaje m para Carlos, que comparten el módulo N en su clave RSA, tenemos el siguiente escenario.
\[c_{1}=m^{e_{1}} \mod{n}\]
\[c_{2}=m^{e_{2}} \mod{n}\]
Siendo c1 y c2 los mensajes cifrados por Alicia, e1 y e2 los exponentes de Bernardo y Carlos, respectivamente, y n el módulo común que ambos comparten. Si Eduardo intercepta estos dos mensajes c1 y c2, sabiendo que el texto en claro era el mismo, podrá obtener el mensaje original m sin necesidad de factorizar N. ¿cómo?
Eduardo conoce los exponentes de Bernardo y de Carlos, ya que forman parte de su clave pública. Si ambos exponentes son primos entre sí (lo cual es más que probable), podrá encontrar dos valores u y v tales que:
\[u\times e_{1} +v\times e_{2} =1\]
Se puede usar el algoritmo de Euclides extendido para obtener u y v fácilmente. Eduardo ya sólo tiene que hacer el sencillo cálculo siguiente para obtener el mensaje m.
\[m=c_{1}^u \times c_{2}^v mod(n)\]
¿Qué por qué funciona esto? Fácil. Como \(c_{1}=m^{e_{1}} \mod{n}\) y \(c_{2}=m^{e_{2}} \mod{n}\), y teniendo en cuenta que u o v van a ser negativos, podemos sustituir en la ecuación anterior:
\[c_{1}^u \times c_{2}^v \equiv (m ^{e_{1}})^u \times (m ^{e_{2}})^v \equiv m^{e_{1}\times u +e_{2}\times v} \equiv m \mod{n}\]
Ataque por exponente pequeño
Es común elegir un exponente pequeño -por ejemplo, 3- para agilizar los cálculos. Esto tiene el problema de que si, por ejemplo, Alicia, Bernardo y Carlos eligieron todos el mismo exponente (mismo exponente y distinto módulo) podemos obtener el mensaje original\[m^{e} \mod{n_{1}} = c_{1}\]
\[m^{e} \mod{n_{2}} = c_{2}\]
\[m^{e} \mod{n_{3}} = c_{3}\]
Usando el Teorema Chino del Resto es posible resolver el sistema.
Ataque cíclico
Sin entrar en detalles matemáticos, al estar trabajando dentro de un cuerpo finito, cuando multiplicamos un valor por otro repetidamente, acabaremos obteniendo el resultado inicial.Si Alicia cifra un mensaje para Bernardo haciendo \(c=m^{e} \mod{n}\), Eduardo puede volver a cifrar repetidamente c usando la clave pública de Bernardo. En algún momento obtendrá de nuevo el valor c, lo que querrá decir que el valor que cifró en el paso anterior era el mensaje m.
Este ataque es muy lento para claves grandes, e incluso menos eficiente que los métodos de factorización nombrados más arriba.
Ataque por paradoja del cumpleaños
Este ataque no sólo es posible con RSA, sino con otros criptosistemas. Se usa especialmente para romper firmas generadas por una función hash.Una formulación más o menos formal es que si tengo una función matemática f(x) que puede generar n resultados diferentes, siendo n un número grande, probabilísticamente sólo necesitamos evaluar la función \(1,2\sqrt{n}\) veces hasta que seamos capaces de encontrar dos valores x1 y x2 tales que f(x1)=f(x2). Es lo que se conoce como una colisión.
Aunque no lo parezca, que sólo haya que probar \(1,2\sqrt{n}\) valores de f(x) es un resultado sorprendente y choca frontalmente contra nuestra intuición.
El nombre de paradoja del cumpleaños se usa ya que para mostrar de forma gráfica este resultado se suele poner el ejemplo siguiente:
Si escogemos al azar 23 personas, la probabilidad de que dos de ellas cumplan años el mismo día y el mismo mes es de 0,507. Es decir, esto se dará con una probabilidad del 50,7% con sólo 23 personas.
En definitiva, la idea es que si tenemos una función f(m,k)=c, siendo m el mensaje que se quiere cifrar, k la clave y c el mensaje cifrado, es posible encontrar un un k' tal que f(m,k')=c. Además, por la paradoja del cumpleaños sabemos que probando al azar hay una probabilidad superior a la que intuitivamente podríamos esperar de encontrar dicho k'. O lo que es lo mismo, encontrar una colisión.
De nuevo, la forma de protegerse de este ataque es usar número lo suficientemente grandes para generar las claves como para que no sea rentable computacionalmente usar este método.
Hay más posibles debilidades en RSA, algunas tan exóticas como analizar el tiempo que tarda el procesador en computar las claves, pero por hoy ya está bien. Si quieres más información te recomiendo leer el fantástico artículo de Dan Boneh de la Universidad de Stanford.
Comentarios
Publicar un comentario