Dándole "cera" al algoritmo RSA
Publicado por Pedro C. el 15-11-2012
Hay mucha gente que se entera por Microsoft© de los "fallos de seguridad" y en esta entrada, vamos a ver cómo romper una clave RSA en GNU/Linux o Windows aprovechando la factorización de los números y la potencia de cálculo actual que tenemos en los equipos caseros.
Ya anunció desde Junio de 2012 que las claves RSA con menos de 1024 bits son consideradas inseguras porque se puede deducir la clave "privada" a partir de la clave "pública" y publicó un boletín de seguridad. Actualmente la práctica es emplear 2048 bits. Sin embargo, en el mundillo, llevamos ya mucho tiempo diciendo y demostrando dicha afirmación. De hecho, l@s que habéis venido a los Cursos de Seguridad, lo hemos practicado "a mano" con números "pequeños".
Como consecuencias de la actualización, aparecerá un error cuando un Certificado SSL para un sitio web tenga una longitud de clave inferior a 1024 bits, al crear correos encriptados o firmados con S/MIME, al instalar controles ActiveX o incluso al instalar aplicaciones que se firmen con claves inferiores a dicha longitud. Aquí tenemos un "salvoconducto" ya que la excepción es que no son bloqueadas si fueron firmadas antes del 1 de Enero de 2010... jejeje...
Para ponerlo en práctica y a partir de la publicación de Daniel Lerch adaptándola a los tiempos actuales, lo primero que haremos es instalar OpenSSL en Windows o GNU/Linux y crearnos una clave "débil" de 512 bits para posteriormente romperla y obtener a partir de la clave pública su clave privada.
Lo primero, crear la clave privada con 256 bits:
openssl genrsa –out privada.pem 256 more privada.pem -----BEGIN RSA PRIVATE KEY----- MIGrAgEAAiEA3x7cFSnjgi7T5jgnFlW2lOYgxozmKj4zs80HaSf/Y78CAwEAAQIh ANwZyy2tdttTaoFu31AvGb4NhSPhQkVSdH9Bb+E7f+GBAhEA8EW6Td2GFkwi1TL2 dA/Y3wIRAO25t31L+qBy8aJz06IGcSECEQCIXVqWVLKENyPR0oGzb0cLAhAY63z2 n35YT3RRCT9IHtDBAhA0kHMpCgP+a7L+UzirjCp6 -----END RSA PRIVATE KEY-----
Ahora, crearemos la clave pública a partir de la privada:
openssl rsa –pubout < privada.pem > publica.pem more publica.pem -----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAN8e3BUp44Iu0+Y4JxZVtpTmIMaM5io+ M7PNB2kn/2O/AgMBAAE= -----END PUBLIC KEY-----
Por supuesto, recordareis gpg y "subir nuestra clave pública" a los servidores. En éste caso, no lo vamos a hacer, pero vamos a cifrar un mensaje y para ello, recordareis que se hace con la clave pública.
echo Hola Mundo! > mensaje.txt more mensaje.txt Hola Mundo! openssl rsautl –encrypt –pubin –inkey publica.pem –in mensaje.txt –out cifrado.txt
Si pusiéramos more cifrado.txt veríamos "chinos" ya que es un formato binario. Para poder verlo desencriptado, y puesto que disponemos de la clave privada para poder hacerlo, tendríamos que poner:
openssl rsautl –decrypt –inkey privada.pem –in cifrado.txt Hola Mundo!
Con toda la tranquilidad y seguridad del mundo, ese mensaje cifrado sería enviado a Guacheras que con nuestra clave pública y su clave privada sería capaz de desencriptarlo. Es decir, Guacheras tiene nuestra "débil clave pública". Se sienta un "ratico" y antes de que le entre más sueño que a unos gaticos al "lao" de la lumbre, extrae la información que le interesa de la clave pública:
openssl rsa –in publica.pem –pubin –text –modulus
Public-Key: (256 bit)
Modulus:
00:df:1e:dc:15:29:e3:82:2e:d3:e6:38:27:16:55:
b6:94:e6:20:c6:8c:e6:2a:3e:33:b3:cd:07:69:27:
ff:63:bf
Exponent: 65537 (0x10001)
Modulus=DF1EDC1529E3822ED3E638271655B694E620C68CE62A3E33B3CD076927FF63BF
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAN8e3BUp44Iu0+Y4JxZVtpTmIMaM5io+
M7PNB2kn/2O/AgMBAAE=
-----END PUBLIC KEY-----
Y se guarda el módulo en hexadecimal y el exponente (en decimal). Lo primero que hace, es convertir el módulo a decimal. Con bc para Windows o bc para GNU/Linux, a mano o con un pequeño programa en C de Daniel Lerch:
vi hex2dec.c
#include <stdio.h>
#include <openssl/bn.h>
int main (int argc, char **argv)
{
BIGNUM *n = BN_new();
if (argc!=2)
{
printf("%s <hex>\n", argv[0]);
return 0;
}
if (!BN_hex2bn(&n, argv[1]))
{
printf("error: BN_hex2bn()");
return 0;
}
printf("%s\n", BN_bn2dec(n));
BN_free(n);
}
gcc hex2dec.c –lssl
./a.out DF1EDC1529E3822ED3E638271655B694E620C68CE62A3E33B3CD076927FF63BF
Obtenemos el número mágico producto de los dos primos "p" y "q":
100920289600778325609262470154337840622994795853937388642916029430161685308351
Ese número es el que vamos a factorizar para encontrar "p" y "q" con lo cual, nos permitirá obtener su clave privada. No hay que asustarse con las cifras. Sólo son 78 dígitos... La actual fortaleza, está establecida en la resistencia a la factorización que ofrecen números con muchos más dígitos.
Para ello, vamos a emplear msieve que es una librería en C implementando algoritmos para trabajar con la factorización de números enteros "largos". Contiene los algoritmos SIQS (Self Initialized Quadratic Sieve) y GNFS (General Number Field Sieve) para poder trabajar con las últimas factorizaciones públicas conocidas. Como seguro que no queréis compilar nada desde GNU/Linux para Windows y probablemente queráis aprovechar vuestro i7 o el soporte de CUDA, teneis las versiones para Windows completamente preparadas para trabajar. En GNU/Linux hay que compilarlo. No fiaros de los binarios que "circulan" ya que lo mismo os "hacen clientes de cómputo" sin que os enteréis...
Por tanto, vamos a emplear la versión con soporte para x64 y CUDA de la sección MSIEVE. Descomprimimos el fichero y nos vamos a la carpeta donde se encuentre. A veces es necesario crear el fichero vacío "worktodo"
touch worktodo msieve –v 100920289600778325609262470154337840622994795853937388642916029430161685308351
El programa intentará factorizar el número pasado. Ya podemos ir a tomar un café... pero ojo, rápido que no tarda mucho!!! Cuando acabe, veremos tanto "p" como "q"
Msieve v. 1.50 (SVN Official Release)
Wed Nov 14 07:20:10 2012
radom seeds: 11414170 bc6ececd
factoring 1009202896007783256092624701543378406229947958539373886429160294301
61685308351 (78 digits)
searching for 15-digits factors
commencing quadratic sieve (78-digit input)
using multiplier of 1
using VC8 64kb sieve core
sieve internal: 6 blocks of size 65536
processing polynomials in batches of 17
using a sieve bound of 924083 (36404 primes)
using a large prime bound of 92408300 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors
sieving in progress (press Ctrl-C to pause)
36519 relations (18552 full + 17967 combined from 199596 partial), need 36500
begin with 218147 relations
reduce to 52183 relations in 2 passes
attempting to read 52183 relations
recovered 52183 relations
recovered 42620 polynomials
attempting to build 36519 cycles
found 36519 cycles in 1 passes
distribution of cycle lengths:
length 1 : 18552
length 2 : 17967
largest cycle: 2 relations
matrix is 36404 x 36519 (5.3 MB) with weight 1103122 (30.21/col)
sparse part has weight 1103122 (30.21/col)
filtering completed in 3 passes
matrix is 26164 x 26228 (4.2 MB) with weight 881311 (33.60/col)
sparse part has weight 881311 (33.60/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 26116 x 26228 (2.9 MB) with weight 668466 (25.49/col)
sparse part has weight 497517 (18.97/col)
commencing Lanczos iteration
memory use: 2.9 MB
lanczos halted after 414 iterations (dim = 26116)
recovered 18 nontrivial dependencies
prp39 factor: 315991331527846152418692424103646097697
prp39 factor: 319376766168931793939205909238749583583
elapsed time 00:03:22
Ya únicamente nos resta conocidos los dos números primos y el exponente empleado, obtener la "clave privada". Podemos emplear utilidades como la del artículo de Daniel Lerch, pero en éste caso, hemos optado por hacerlo online desde la página http://math.co.ro/cgi-bin/genpriv?p=PRIMO_P&q=PRIMO_Q&e=EXPONENTE
wget "http://math.co.ro/cgi-bin/genpriv?p=315991331527846152418692424103646097697 \
&q=319376766168931793939205909238749583583&e=65537"
Editamos el fichero para eliminar la cabecera y voilá:
Llave privada de 315991331527846152418692424103646097697, 319376766168931793939205909238749583583 y 65537 by Eduardo Ruiz Duarte (beck) toorandom@gmail.com -----BEGIN RSA PRIVATE KEY----- MIGrAgEAAiEA3x7cFSnjgi7T5jgnFlW2lOYgxozmKj4zs80HaSf/Y78CAwEAAQIh ANwZyy2tdttTaoFu31AvGb4NhSPhQkVSdH9Bb+E7f+GBAhEA8EW6Td2GFkwi1TL2 dA/Y3wIRAO25t31L+qBy8aJz06IGcSECEQCIXVqWVLKENyPR0oGzb0cLAhAY63z2 n35YT3RRCT9IHtDBAhA0kHMpCgP+a7L+UzirjCp6 -----END RSA PRIVATE KEY-----
Guacheras ha conseguido la clave privada a partir de la pública!!! ¿Qué hacer con una clave privada? La imaginación ya la ponéis vosotr@s...
Os ofrecemos una plaza GRATUITA en cualquier Curso Privado a elegir a quien primero obtenga la clave privada y la mande como prueba a ex-alumnos@madesyp.com de la siguiente clave pública:
-----BEGIN PUBLIC KEY----- MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANeYWuPr69WGKfHmQv7AveanAzghrIxg /xlKafTe29YytGCCQRkWH84cOs4FRU8QVgdgufJEs24C2Sm0Q1E7KdMCAwEAAQ== -----END PUBLIC KEY-----
Recordaros que en los Cursos especializados de Seguridad Informática y Administración de Sistemas que ofrecemos en Academia MADESYP realizamos y establecemos las contramedidas con todo esto y mucho más...
Ser buenos y no hagáis maldades!!!
