AlexCTF - CR4 Poor RSA (200pts)

Os traemos fresquísimo el writeup del cuarto reto de reversing de AlexCTF. Espero que lo disfrutéis!

.0x00. Intro

En esta ocasión, se nos facilitaba un tarball y la siguiente descripción:

This time Fady decided to go for modern cryptography implementations, He is fascinated with choosing his own prime numbers, so he picked up RSA once more. Yet he was unlucky again!

El tarball contenía lo siguiente:

> tar tvzf ../cr4_poor_rsa.tar.gz
-rw-r--r--  0 oddcoder oddcoder   69 Dec 11 10:08 flag.b64
-rw-r--r--  0 oddcoder oddcoder  162 Dec 11 09:59 key.pub

El contenido de flag.b64 era tal que así:

Ni45iH4UnXSttNuf0Oy80+G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSi+w=

Y la clave pública era esta:

-----BEGIN PUBLIC KEY-----
ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8
bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ==
-----END PUBLIC KEY-----

Parecía el típico reto de factorización. La idea consiste en factorizar la clave pública para obtener la clave privada. Con la clave privada deberemos hacer algo, que se supone que es descifrar el fichero flag.b64.

.0x01. Obteniendo la clave privada

La primera pista que nos dan es que se han usado dos números primos no aleatorios para generar el par de claves, por lo que seguramente no tengamos ningún problema al factorizar. Lo primero que hacemos es obtener el modulo de la clave pública:

> openssl rsa -in key.pub -pubin -modulus -noout
Modulus=52A99E249EE7CF3C0CBF963A009661772BC9CDF6E1E3FBFC6E44A07A5E0F894457A9F81C3AE132AC5683D35B28BA5C324243

Con dicho módulo, nos dirigimos a factordb para factorizarlo y obtener los 2 números primos necesarios para generar la clave privada (p y q). Dichos números corresponden a:

p=863653476616376575308866344984576466644942572246900013156919 
q=965445304326998194798282228842484732438457170595999523426901

Para obtener la clave privada, usamos rsatool:

> python rsatool/rsatool.py -p 863653476616376575308866344984576466644942572246900013156919 -q 965445304326998194798282228842484732438457170595999523426901 -o out.key -v
Using (p, q) to initialise RSA instance

n = 52a99e249ee7cf3c0cbf963a009661772bc9cdf6e1e3fbfc6e44a07a5e0f894457a9f81c3ae132ac5683d35b28ba5c324243

e = 65537 (0x10001)

d = 33ad09ca06f50f9e90b1acae71f390d6b92f1d6d3b6614ff871181c4df08da4c5f5012457a64309405eaecd6341e43027931

p = 899683060c76b9c0de581a69e0ea9d91bed1071beb1d924a37

q = 99cde74aedee87adffdd684cbc478e759870b4f20692f65255

dP = 66644075cbe8bf2c2d4bdbbc57c9c221a8a3de6a847aa957d9

dQ = 5b3e128b9a115abe77bf02a41b421c1a593feba8750bf4432d

qInv = 39a5e9be4e06d6df309817cbfb8f49a3277d4d0bed2c2e6c79

Saving PEM as out.key

Lo que nos deja la siguiente clave privada:

-----BEGIN RSA PRIVATE KEY-----
MIH5AgEAAjJSqZ4knufPPAy/ljoAlmF3K8nN9uHj+/xuRKB6Xg+JRFep+Bw64TKsVoPTWyi6XDJC
QwIDAQABAjIzrQnKBvUPnpCxrK5x85DWuS8dbTtmFP+HEYHE3wjaTF9QEkV6ZDCUBers1jQeQwJ5
MQIaAImWgwYMdrnA3lgaaeDqnZG+0Qcb6x2SSjcCGgCZzedK7e6Hrf/daEy8R451mHC08gaS9lJV
AhlmZEB1y+i/LC1L27xXycIhqKPeaoR6qVfZAhlbPhKLmhFavne/AqQbQhwaWT/rqHUL9EMtAhk5
pem+TgbW3zCYF8v7j0mjJ31NC+0sLmx5
-----END RSA PRIVATE KEY-----

.0x02. Profit

Teniendo la clave privada, podemos utilizar openssl para descifrar el contenido del fichero flag.b64. Para ello, ejecutamos lo siguiente:

> base64 -D flag.b64 | openssl rsautl -decrypt -inkey out.key
ALEXCTF{SMALL_PRIMES_ARE_BAD}

:wq! srm

Made with lots of coffee and Hugo.