Friday, June 10, 2011

Cómo romper RSA explícitamente con llaves OpenSSL

Todo el mundo habla de lo vulnerable que es RSA y de la importancia de los números primos envueltos en las llaves,
muchos saben que la seguridad radica en la dificultad de factorizar, hace poco en twitter a muchos les interesó el cómo se hace, ahora lo dejo aquí en mi blog para que lo hagan ustedes, vamos a romper una llave RSA de 256 bits la cual no es tan grande pero tampoco es tristemente pequeña en menos de 5 minutos, una razón mas para investigar más con otro tipo de esquemas de logaritmo discreto como los que ya he mencionado aquí y de los cuales me la paso dando charlas sobre Jacobianas con curvas algebraicas u otras variedades abelianas.

Dejo antes una reseña de ¿cómo funciona RSA? y después a romper RSA :)

Generación de llaves:

- Se generan dos números primos grandes (p,q) aleatorios
- Se computa n=pq el cual servirá como módulo
- Se computa phi(n)=(p-1)(q-1) (phi función de conteo de primos relativos con n, y es (p-1)(q-1) por ser primos p y q)
- Escoges un e tal que 1 menor que e menor que phi(n) y mcd(phi(n),e) = 1 (OpenSSL generalmente asigna algo cercano a 2^16 como 65537)
- Computas d = e^-1 mod phi(n)

(d,p,q) es la llave privada
(e,n) es la llave publica



Cifrado:

- a A le van a mandar M entonces A le manda a B (e,n)
- B computa c=M^e mod n y se lo manda a A

Descifrado:

- A computa m=c^d mod n que es lo mismo que m=(m^e)^d mod n que es m (es fácil demostrar que eso es m)

La seguridad radica en que si alguien obtiene la llave pública (e,n) como d = e^-1 mod phi(n) , o sea d = e^-1 mod (p-1)(q-1)

tendría que factorizar n=pq para obtener e^-1 mod (p-1)(q-1)



Como romper RSA dada una llave pública SSL


Primero generamos un ambiente de pruebas.


Generamos llave privada (o sea p,q) en privada.pem
openssl genrsa -out privada.pem 256

Generamos llave pública con la privada (o sea e,n) en pub.pem
openssl rsa -in privada.pem -pubout -out pub.pem

Extraemos módulo n y exponente e, o sea n , y e de la llave publica
openssl rsa -in pub.pem -pubin -text -modulus

Lo cual nos dará mucha info, y en esa info vendrá lo siguiente:

Exponent: 65537 (0x10001)
Modulus=9ABAAD5BBE954A26BDBB15568B7AEB3651D0605EA5687329F849DB1F9871865F


Exponent es "e" y Modulus es "n"

Convertimos a decimal esa cosa:
echo "ibase=16; 9ABAAD5BBE954A26BDBB15568B7AEB3651D0605EA5687329F849DB1F9871865F"|bc

69986008711415694391421268580269058232048146719704518153244714221529713444447


Lo factorizamos con msieve que está disponible aquí
el cual su funcionamiento, es con la criba numérica (GNFS) el cual es el algoritmo más rápido hasta ahora para factorizar, éste hay que compilarlo , solo requiere -lgmp (gnu multiprecision) y otras cosas estándar

Para factorizar ese número basta correr después de haber compilado , de la siguiente manera

msieve -v 69986008711415694391421268580269058232048146719704518153244714221529713444447

Tardará de 2 minutos en una computadora normal (esto es porque es de 256 bits, pero seguro en Kanbalam de la UNAM se puede romper 768 bits en cuestión de días,
ya que es paralelizable y soporta resumen.

Ya que termina te mostrará los factores.

prp39 factor: 258903250452187592132630852021175987089
prp39 factor: 270317226953240634960995990331891792623


Construimos la llave privada, para esto, hice un programa con libcrypto que te la genera en formato PEM y lo publiqué en mi sitio como un CGI
Sólo manda a llamar mi página con los parámetros de los números primos en la URL y el exponente 65537 que sacamos en otro paso atrás

http://math.co.ro/cgi-bin/genpriv?p=258903250452187592132630852021175987089&q=270317226953240634960995990331891792623&e=65537

y la página te sacará lo siguiente:

Llave privada de 258903250452187592132630852021175987089,270317226953240634960995990331891792623 y 65537 por Eduardo Ruiz Duarte (beck) toorandom@gmail.com

-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAmrqtW76VSia9uxVWi3rrNlHQYF6laHMp+EnbH5hxhl8CAwEAAQIh
AIb+e6Vhn6p0JnCE618BvRfp5+WyQWSxb7Fz8aTB5FTBAhEAy100RZ5hZCzjbv48
M2I67wIRAMLG88hDEnjIwaItDgCYK5ECEE4kDBfMGaQCU4msirk7v2UCEFDOY1MA

6Iftmc+ja3y5pNECEF2g5ukd6W4XRpU1d9AwY/4=
-----END RSA PRIVATE KEY-----


Y si comparas la llave inicial (privada.pem) con esta que sacamos la cual guardé en "llaverota.pem"
verás que son la misma y no utilizamos ninguna información de la llave privada generada originalmente para llegar a llaverota.pem

md5sum privada.pem llaverota.pem
9cd4b5a39be5717978b9035ddc5fc887 privada.pem
9cd4b5a39be5717978b9035ddc5fc887 llaverota.pem



Comentarios:
Eduardo Ruiz Duarte
toorandom at gmail d0t com
Twitter: @toorandom

3 comments:

R said...

Muy bonita explicación, pocas veces alguien se toma la molestia de hacer las cuentas. :-)

Debo mencionar que tu estimación respecto al tiempo para factorizar algo de 768 bits es muy optimista, porque en general el problema (o por lo menos los algoritmos conocidos) tienen complejidad exponencial en el número de bits. Específicamente, según wikipedia:

an effort concluded in 2009 by several researchers factored a 232-digit number (RSA-768) utilizing hundreds of machines over a span of 2 years.

Anonymous said...

Gracias por el comment, pero dice "hundreds of machines"
ahora imagina "decenas de 10 miles" de cores como kanbalam en la unam, 2^15=32768
y si es exponencial o más bien "subexponencial" si consideras miller-rabin

Anonymous said...

31337