Hackthebox challenge writeup - Weak RSA

Hackthebox challenge writeup - Weak RSA

Wed 31 March 2021

A writeup of how I approached the HTB challenge Weak RSA. Hackthebox is a fun platform that lets you work on your enumeration, pentesting and hacking skills.

Introduction

The challenge start with the download of a .zip file, and inside that you find 2 files.

weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ file flag.enc 
flag.enc: data
weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ cat key.pub 
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQMwO3kPsUnaNAbUlaubn7ip
4pNEXjvUOxjvLwUhtybr6Ng4undLtSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy
23CZuOl3WIsLiRKSVYyqBc9d8rxjNMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3
RQP/6p5hv1PYcWmErEeDewKBgGEXxgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpD
qlqqOFD8JA5UFK0roQkOjhLWSVu8c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ
4gYo6Ax+U7q6TOWhQpiBHnC0ojE8kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8sr
lb/N
-----END PUBLIC KEY-----
weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$

My first though is that I should derive the private-key from the public-key. When I have the private-key I can decrypt the flag.enc file and find the answer.

First some definitions:

Public Key - (n, e)
Private Key - (n, d)
Public Exponent - e
Private Exponent - d
Modulus - n
    n = p * q , where p and q are primenumbers
Plaintext message - m
    The message, converted to a number, in our challenge this is probably the flag we need to submit our answer
Encrypted message - c
    The ciphertext, in our challenge this is probably flag.enc

Lets decode the public key (n,e):

weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ openssl pkey -pubin -in key.pub -text
-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQMwO3kPsUnaNAbUlaubn7ip
4pNEXjvUOxjvLwUhtybr6Ng4undLtSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy
23CZuOl3WIsLiRKSVYyqBc9d8rxjNMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3
RQP/6p5hv1PYcWmErEeDewKBgGEXxgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpD
qlqqOFD8JA5UFK0roQkOjhLWSVu8c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ
4gYo6Ax+U7q6TOWhQpiBHnC0ojE8kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8sr
lb/N
-----END PUBLIC KEY-----
RSA Public-Key: (1026 bit)
Modulus:
    03:30:3b:79:0f:b1:49:da:34:06:d4:95:ab:9b:9f:
    b8:a9:e2:93:44:5e:3b:d4:3b:18:ef:2f:05:21:b7:
    26:eb:e8:d8:38:ba:77:4b:b5:24:0f:08:f7:fb:ca:
    0a:14:2a:1d:4a:61:ea:97:32:94:e6:84:a8:d1:a2:
    cd:f1:8a:84:f2:db:70:99:b8:e9:77:58:8b:0b:89:
    12:92:55:8c:aa:05:cf:5d:f2:bc:63:34:c5:ee:50:
    83:a2:34:ed:fc:79:a9:5c:47:8a:78:e3:37:c7:23:
    ae:88:34:fb:8a:99:31:b7:45:03:ff:ea:9e:61:bf:
    53:d8:71:69:84:ac:47:83:7b
Exponent:
    61:17:c6:04:48:b1:39:45:1a:b5:b6:0b:62:57:a1:
    2b:da:90:c0:96:0f:ad:1e:00:7d:16:d8:fa:43:aa:
    5a:aa:38:50:fc:24:0e:54:14:ad:2b:a1:09:0e:8e:
    12:d6:49:5b:bc:73:a0:cb:a5:62:50:42:55:c7:3e:
    a3:fb:d3:6a:88:83:f8:31:da:8d:1b:9b:81:33:ac:
    21:09:e2:06:28:e8:0c:7e:53:ba:ba:4c:e5:a1:42:
    98:81:1e:70:b4:a2:31:3c:91:4a:2a:32:17:c0:2e:
    95:1a:ae:e4:c9:eb:39:a3:f0:80:35:7b:53:3a:6c:
    ca:95:17:cb:2b:95:bf:cd
weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$

Convert from hex -> decimal, modulus, n (p*q):

57317782457963091166846927271254786544355665408619010472279550975689167002325903127543350912148103033159856937938350592
83154954628887885936959453214176762984715252432541433756223655522969494139206792905357171723195620643089373425674836904
86592868352763021360051776130919666984258847567032959931761686072492923

Convert from hex -> decimal, public exponent, e:

681809286312841472128205071926057346320355241311399386180695753755918063152887753105036968745091308475295724626087280192
907101496613002461380365793420795804347773441112454951879278811321383579587449742433659622048350897539876673955116828293
91276714359582055290140617797814443530797154040685978229936907206605

We already assumed that the flag.enc is encrypted with the given public-key. This means that we need a matching private-key to decrypt the flag.enc.

c = m^e mod n
m = c^d mod n

The private-key is given by the format (n,d) where n is the already given modulus, giving us the task of finding the private exponent, d.

Attacking the problem

So, how do we attack this? Luckily there are multiple attack-vectors: https://ctf101.org/cryptography/what-is-rsa/

There is a also suite of tools that is dedicated to this type of challenges: https://github.com/Ganapati/RsaCtfTool

Follow the instructions on the github page to install the RsaCtfTool.

Lets run the tool:

weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA/RsaCtfTool$ python3 RsaCtfTool.py --publickey ../key.pub  --output ../key.priv --private

[*] Testing key ../key.pub.
[*] Performing pastctfprimes attack on ../key.pub.
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 113/113 [00:00<00:00, 125484.87it/s]
[*] Performing system_primes_gcd attack on ../key.pub.
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 2353/2353 [00:00<00:00, 107158.57it/s]
[*] Performing factordb attack on ../key.pub.
[*] Attack success with factordb method !

Results for ../key.pub:

Private key :
-----BEGIN RSA PRIVATE KEY-----
MIICOQIBAAKBgQMwO3kPsUnaNAbUlaubn7ip4pNEXjvUOxjvLwUhtybr6Ng4undL
tSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy23CZuOl3WIsLiRKSVYyqBc9d8rxj
NMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3RQP/6p5hv1PYcWmErEeDewKBgGEX
xgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpDqlqqOFD8JA5UFK0roQkOjhLWSVu8
c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ4gYo6Ax+U7q6TOWhQpiBHnC0ojE8
kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8srlb/NAiBhwngxi+Cbie3YBogNzGJV
h10vAgw+i7cQqiiwEiPFNQJBAYXzr5r2KkHVjGcZNCLRAoXrzJjVhb7knZE5oEYo
nEI+h2gQSt1bavv3YVxhcisTVuNrlgQo58eGb4c9dtY2blMCQQIX2W9IbtJ26KzZ
C/5HPsVqgxWtuP5hN8OLf3ohhojr1NigJwc6o68dtKScaEQ5A33vmNpuWqKucecT
0HEVxuE5AiBhwngxi+Cbie3YBogNzGJVh10vAgw+i7cQqiiwEiPFNQIgYcJ4MYvg
m4nt2AaIDcxiVYddLwIMPou3EKoosBIjxTUCQQCnqbJMPEQHpg5lI6MQi8ixFRqo
+KwoBrwYfZlGEwZxdK2Ms0jgeta5jFFS11Fwk5+GyimnRzVcEbADJno/8BKe
-----END RSA PRIVATE KEY-----

We now have a private-key, maybe it works?

weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ openssl rsautl -decrypt -inkey key.priv -in flag.enc -out flag.bin
weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ cat flag.bin 
HTB{s1mpl3_Wi3n3rs_4tt4ck}

Congratulations!

Wrap up

This challenge made me read up on RSA and public-key crypto. It could been solved in a few minutes by going directly to the toolsuite that we ended up using, but I wanted to learn a bit on the way.

Here are some of the resources I stumbled upon on the way:

https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/the-fundamental-theorem-of-arithmetic-1

https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/the-fundamental-theorem-of-arithmetic-2

https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/the-fundamental-theorem-of-arithmetic-3

https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/the-fundamental-theorem-of-arithmetic-4

https://stackoverflow.com/questions/4078902/cracking-short-rsa-keys

https://raymii.org/s/tutorials/Encrypt_and_decrypt_files_to_public_keys_via_the_OpenSSL_Command_Line.html#toc_5

For completeness we decode the private part of the key:

weakrsa@kali:/mnt/hgfs/kali_share/weakrsa/Weak RSA$ openssl pkey -in key.priv -text
-----BEGIN PRIVATE KEY-----
MIICUwIBADANBgkqhkiG9w0BAQEFAASCAj0wggI5AgEAAoGBAzA7eQ+xSdo0BtSV
q5ufuKnik0ReO9Q7GO8vBSG3Juvo2Di6d0u1JA8I9/vKChQqHUph6pcylOaEqNGi
zfGKhPLbcJm46XdYiwuJEpJVjKoFz13yvGM0xe5Qg6I07fx5qVxHinjjN8cjrog0
+4qZMbdFA//qnmG/U9hxaYSsR4N7AoGAYRfGBEixOUUatbYLYlehK9qQwJYPrR4A
fRbY+kOqWqo4UPwkDlQUrSuhCQ6OEtZJW7xzoMulYlBCVcc+o/vTaoiD+DHajRub
gTOsIQniBijoDH5TurpM5aFCmIEecLSiMTyRSioyF8AulRqu5MnrOaPwgDV7Uzps
ypUXyyuVv80CIGHCeDGL4JuJ7dgGiA3MYlWHXS8CDD6LtxCqKLASI8U1AkEBhfOv
mvYqQdWMZxk0ItEChevMmNWFvuSdkTmgRiicQj6HaBBK3Vtq+/dhXGFyKxNW42uW
BCjnx4Zvhz121jZuUwJBAhfZb0hu0nborNkL/kc+xWqDFa24/mE3w4t/eiGGiOvU
2KAnBzqjrx20pJxoRDkDfe+Y2m5aoq5x5xPQcRXG4TkCIGHCeDGL4JuJ7dgGiA3M
YlWHXS8CDD6LtxCqKLASI8U1AiBhwngxi+Cbie3YBogNzGJVh10vAgw+i7cQqiiw
EiPFNQJBAKepskw8RAemDmUjoxCLyLEVGqj4rCgGvBh9mUYTBnF0rYyzSOB61rmM
UVLXUXCTn4bKKadHNVwRsAMmej/wEp4=
-----END PRIVATE KEY-----
RSA Private-Key: (1026 bit, 2 primes)
modulus:
    03:30:3b:79:0f:b1:49:da:34:06:d4:95:ab:9b:9f:
    b8:a9:e2:93:44:5e:3b:d4:3b:18:ef:2f:05:21:b7:
    26:eb:e8:d8:38:ba:77:4b:b5:24:0f:08:f7:fb:ca:
    0a:14:2a:1d:4a:61:ea:97:32:94:e6:84:a8:d1:a2:
    cd:f1:8a:84:f2:db:70:99:b8:e9:77:58:8b:0b:89:
    12:92:55:8c:aa:05:cf:5d:f2:bc:63:34:c5:ee:50:
    83:a2:34:ed:fc:79:a9:5c:47:8a:78:e3:37:c7:23:
    ae:88:34:fb:8a:99:31:b7:45:03:ff:ea:9e:61:bf:
    53:d8:71:69:84:ac:47:83:7b
publicExponent:
    61:17:c6:04:48:b1:39:45:1a:b5:b6:0b:62:57:a1:
    2b:da:90:c0:96:0f:ad:1e:00:7d:16:d8:fa:43:aa:
    5a:aa:38:50:fc:24:0e:54:14:ad:2b:a1:09:0e:8e:
    12:d6:49:5b:bc:73:a0:cb:a5:62:50:42:55:c7:3e:
    a3:fb:d3:6a:88:83:f8:31:da:8d:1b:9b:81:33:ac:
    21:09:e2:06:28:e8:0c:7e:53:ba:ba:4c:e5:a1:42:
    98:81:1e:70:b4:a2:31:3c:91:4a:2a:32:17:c0:2e:
    95:1a:ae:e4:c9:eb:39:a3:f0:80:35:7b:53:3a:6c:
    ca:95:17:cb:2b:95:bf:cd
privateExponent:
    61:c2:78:31:8b:e0:9b:89:ed:d8:06:88:0d:cc:62:
    55:87:5d:2f:02:0c:3e:8b:b7:10:aa:28:b0:12:23:
    c5:35
prime1:
    01:85:f3:af:9a:f6:2a:41:d5:8c:67:19:34:22:d1:
    02:85:eb:cc:98:d5:85:be:e4:9d:91:39:a0:46:28:
    9c:42:3e:87:68:10:4a:dd:5b:6a:fb:f7:61:5c:61:
    72:2b:13:56:e3:6b:96:04:28:e7:c7:86:6f:87:3d:
    76:d6:36:6e:53
prime2:
    02:17:d9:6f:48:6e:d2:76:e8:ac:d9:0b:fe:47:3e:
    c5:6a:83:15:ad:b8:fe:61:37:c3:8b:7f:7a:21:86:
    88:eb:d4:d8:a0:27:07:3a:a3:af:1d:b4:a4:9c:68:
    44:39:03:7d:ef:98:da:6e:5a:a2:ae:71:e7:13:d0:
    71:15:c6:e1:39
exponent1:
    61:c2:78:31:8b:e0:9b:89:ed:d8:06:88:0d:cc:62:
    55:87:5d:2f:02:0c:3e:8b:b7:10:aa:28:b0:12:23:
    c5:35
exponent2:
    61:c2:78:31:8b:e0:9b:89:ed:d8:06:88:0d:cc:62:
    55:87:5d:2f:02:0c:3e:8b:b7:10:aa:28:b0:12:23:
    c5:35
coefficient:
    00:a7:a9:b2:4c:3c:44:07:a6:0e:65:23:a3:10:8b:
    c8:b1:15:1a:a8:f8:ac:28:06:bc:18:7d:99:46:13:
    06:71:74:ad:8c:b3:48:e0:7a:d6:b9:8c:51:52:d7:
    51:70:93:9f:86:ca:29:a7:47:35:5c:11:b0:03:26:
    7a:3f:f0:12:9e
Tagged as : htb hackthebox crypto weakrsa