domingo, 13 de mayo de 2007

Rompiendo claves RSA

Aunque hoy por hoy no es posible romper una clave RSA de más de 1024 bits ni con miles de computadoras trabajando en paralelo, los algoritmos de factorización no dejan de mejorar. A continuación voy a explicar cómo romper una clave RSA relativamente pequeña usando uno de estos algoritmos.

Primero crearemos un entorno de pruebas con el que cifrar y descifrar. Usaremos la herramienta openssl.

Generamos un par de claves RSA de 256 bits.
$ openssl genrsa -out privkey.pem 256

# Extraemos la clave publica
$ openssl rsa -in privkey.pem -pubout -out pubkey.pem
$ cat pubkey.pem
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

# Algo que cifrar
$ echo ";)" > msg.txt

# Ciframos (con la clave publica)
$ openssl rsautl -encrypt -pubin -inkey pubkey.pem -in msg.txt -out msg.enc

# Desciframos (con la clave privada)
$ openssl rsautl -decrypt -inkey privkey.pem -in msg.enc
;)


Ya tenemos nuestro entorno de pruebas con un par de claves que nos pemiten cifrar y descifrar mensajes. Como RSA es un criptosistema asimétrico se supone que deberíamos distribuir la clave pública, mientras que guardaríamos con recelo la clave privada.

Nuetro objetivo será obtener la clave privada partiendo únicamente de la clave pública. Una vez obtenida descifraremos el mensaje.

RSA basa su fuerza en el problema de factorización de números grandes. Un problema matemático para el que no se conoce un algoritmo que lo resuelva de forma eficiente. Entre los algoritmos más rápidos destacan QS y NFS. Ambos implementados por la genial herramienta msieve (Instalar).

Lo primero que necesitamos es el módulo n y el exponete de cifrado. Los dos se pueden obtener facilmente a partir de la clave pública.

$ openssl rsa -in pubkey.pem -pubin -text -modulus
Modulus (256 bit):
00:ad:7f:79:a1:e5:5b:af:0e:af:06:9e:4f:f5:fa:
57:d9:b1:e2:99:2f:13:c9:96:41:27:2b:23:6c:fc:
51:50:61
Exponent: 65537 (0x10001)
Modulus=AD7F79A1E55BAF0EAF069E4FF5FA57D9B1E2992F13C99641272B236CFC515061
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----


Observemos que el módulo está en hexadecimal. Para continuar será necesario pasarlo a decimal. A continuación, lo factorizamos con msieve:


$ msieve -v 78475351858145546395020889284272950035474797715255953445997961959441362407521

Obteniendo como resultado los factores:
262908038773065572592762474383232893183
298489738938272421513567914663780208287

Únicamente nos quedará recuperar la clave original a partir de los datos obtenidos. Usaremos el programa get_priv_key.


$ ./get_priv_key 262908038773065572592762474383232893183 298489738938272421513567914663780208287 \ 
65537
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEArX95oeVbrw6vBp5P9fpX2bHimS8TyZZBJysjbPxRUGECAwEAAQIg
L/uaWxEAq0iHVXBBMwk6dDC0mJubL4dVLLdiaA01NPUCEQDgjwhah0l/hqX+D3Xh
3s6fAhEAxco/F01rh+Uzf+LV2K6A/wIRANOCxcqHPRpKGFV5+H3cYF8CEEN8O0Sf
JNZsTMMQyXgyKk8CEQCRfomgf/LY71boM54D8a5C
-----END RSA PRIVATE KEY-----


Con la nueva clave privada ya podemos acceder al mensaje cifrado.


$ openssl rsautl -decrypt -inkey cracked_privkey.pem -in msg.enc
;)





Referencias:
- RSA Labs.
- Ataque de factorización a RSA (hakin9 nº19).
- On the cost of factoring RSA 1024.

10 comentarios:

flacman dijo...

hey hombre de casualidad tiene tiempos? pues maso cuanto puede demorarse en promedio esta operacion?

Daniel Lerch dijo...

Te refieres a la factorización?
En ese caso hay un documento en las
referencias que puede interesarte.

Saludos.

Vermin dijo...

hola,

Muy buen Post. Te hago una consulta.

El modulus de que forma lo transformas de HEX a Decimal.

gracias

dlerch dijo...

Pasar de hexdecimal a decimal es trivial, aunque pesado para números tan grandes. Yo, en su momento, me hice un programa en C que usaba las librería GMP. No se donde estará ... si no lo colgaría.

De todas formas, seguro que si buscas un poco en Google encuentras algo.

Saludos.

Ember dijo...

Hola,

hace poco perdi una llave privada pgp 2048 RSA, tengo aun la publica y recuerdo el password de creacion, con esa informacion es posible recuperar la privada? segun entiendo esta se forma de la publica+password.

Saludos y gracias por su orientacion.

dlerch dijo...

Hola,
no vas a poder :(

El password solo es para proteger la privada. Es decir, si tienes la privada, para usarla necesitas el password.

Si has perdido la privada (el archivo) no la puedes recuperar a partir de la pública. Al menos, no con una clave de 2048 y la tecnología actual.

Anónimo dijo...

Hola, dispongo de una clave pública:

3035022e01356ba923f56d30902d0b4e94ceb116d2dcb8f95129040a2838e33fa16fed668cc4b76f29c3131f80873d54272d0203010001

La convierto a formato PEM y sigo los pasos que se indican con openssl, pero cuando intento obtener el modulo n y el exponente, me da el error:

unable to load Public Key
5388:error:0D0680A8:asn1 encoding routines:ASN1_CHECK_TLEN:wrong tag:.\crypto\asn1\tasn_dec.c:1319:

5388:error:0D07803A:asn1 encoding routines:ASN1_ITEM_EX_D2I:nested asn1 error:.\crypto\asn1\tasn_dec.c:381:Type=X509_ALGOR

5388:error:0D08303A:asn1 encoding routines:ASN1_TEMPLATE_NOEXP_D2I:nested asn1 error:.\crypto\asn1\tasn_dec.c:751:Field=algor, Type=X509_PUBKEY

5388:error:0906700D:PEM routines:PEM_ASN1_read_bio:ASN1 lib:.\crypto\pem\pem_oth.c:83:
error in rsa

A alguien se le ocurre que puede ser?

Gracias.

Unknown dijo...

Buenas. he visto que con ssl podria romper claves rsa.
Hemos tenido un problema en la oficina y nos han encriptado los archivos con clave rsa 1024. Parece ser que es imposible de descifrar.
¿es esto verdad?
Muchas Gracias

Anónimo dijo...

Me pasa lo mismo que a jorge Gimenez. Alguin sabe el porque de esto?

Jorge dijo...

Hola, tengo un archivo ecriptado con Cobian, tengo la llave pública y la llave privada y tengo la frase clave pero Cobian, al descifrarlo me indica que la frase no es correcta o la llave está corrupta, y estoy seguro que no son ciertas ninguna de las dos cosas. Es más encripto un nuevo archivo usando esas llaves y al desencriptarlos me indica lo mismo.

¿alguien me puede ayudar a saber si la frase es correcta? Con una pequeña idea puedo saberlo, no hará falta descifrar toda la frase

La frase es:
Elsueñodeverano2011

Espero la ayuda de alguien porqu los de cobian pasan de mis mensajes de ayuda

Gracias