Contenido principal

Backdoor CTF 2015 - RSANNE

Abril 3, 2015

We are given with two files in this challenge: an encrypted file and a 4484 bit RSA public key. The challenge is to get the plaintext from the encrypted file.

The first step is to get the modulus from the PEM file:

# openssl rsa -inform PEM -pubin -text -modulus < id_rsa.pub
Public-Key: (4484 bit)
Modulus:
    0f:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:fd:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    f8:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
    00:00:00:00:00:01
Exponent: 65537 (0x10001)
Modulus=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDFFFFFFFFFFFFFFFFF
FF80000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000001
writing RSA key
-----BEGIN PUBLIC KEY-----
MIICUjANBgkqhkiG9w0BAQEFAAOCAj8AMIICOgKCAjEP////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////////////////3////////////4AAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAECAwEAAQ==
-----END PUBLIC KEY-----

N is the product of two Mersenne primer numbers, so the second step is to make a script which is used to find them:

#!/usr/bin/env python

mersenne = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689]

for n1 in mersenne:
    for n2 in mersenne:
        m1 = (2 ** n1)  - 1
        m2 = (2 ** n2) - 1
        if m1 * m2  == 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDFFFFFFFFFFFFFFFFFFF80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001:
            print "Match! ", m1, m2

The two prime numbers are: 22281 - 1 and 22203 - 1.

We use rsatool.py from ius to reconstruct the private key PEM file (which is used later to decrypt the content of the file using the OAEP padding scheme):

-----BEGIN RSA PRIVATE KEY-----
MIIKCAIBAAKCAjEP////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
//3////////////4AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAECAwEAAQKCAjEIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yge
d+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB53
4Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfh
iB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GI
HnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yged+GIHnfhiB534Yge
d9+AgH9/gIB/f4B4YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhh
B574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEH
nvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee
+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574
YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhhB574YQee+GEHnvhh
B6ECggEeAf//////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
/////////wKCARQH////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
//8CggEeAYCAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CA
f3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/
f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/
gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+A
gH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CAf3+AgH9/gIB/f4CA
f3+AgH9/fwKCARQGWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZ
aaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllp
ppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmm
lllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaW
WWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZaaaWWWmmlllpppZZ
aaUCggEeAKqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqq
qlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVU
qqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpV
VUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqq
pVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVSqqpVVUqqqlVVS
qqpVVUqqqQ==
-----END RSA PRIVATE KEY-----

Final step is to decrypt the file:

# openssl rsautl -decrypt -in flag_d.bin -out plaintext.txt -inkey private.pem -oaep
Loading 'screen' into random state - done

# cat plaintext.txt
the_flag_is_e4972e14...

Archivado en: Criptografía, Retos informáticos |

Deja un comentario

« B-Sides Vancouver CTF 2015 - garbage file VirtualBox Disk Image Encryption password cracker »