TryHackMe Breaking RSA Write-up

This write-up will help you solve the Breaking RSA box on TryHackMe. Before we start tackling this box, please add this domain to your /etc/hosts file.

echo "<box_ip>   rsa.thm" >> /etc/hosts

TryHackMe Breaking RSA – Enumeration

At first, we need to find out what services are running and open to the world. We can find this out by running a port scan. We will use RustScan for port scanning. You can read more about RustScan here. Run the following command to scan all the ports:

rustscan -a rsa.thm -- -A -sC -sV

All flags after the — -A sequence are treated as nmap flags, flags that are used by the nmap port scanner as well. The sC(or –script=default) and sV flags indicate that basic vulnerability scripts are executed against the target and that the port scan tries to find version information. You can see the output of the port scan below:

PORT   STATE SERVICE REASON  VERSION
22/tcp open  ssh     syn-ack OpenSSH 8.2p1 Ubuntu 4ubuntu0.5 (Ubuntu Linux; protocol 2.0)
80/tcp open  http    syn-ack nginx 1.18.0 (Ubuntu)
| http-methods: 
|_  Supported Methods: GET HEAD
|_http-server-header: nginx/1.18.0 (Ubuntu)
|_http-title: Jack Of All Trades
Service Info: OS: Linux; CPE: cpe:/o:linux:linux_kernel

There are only 2 open ports.

Port 22 serves as an SSH-sever.
Port 80 serves as a web server.

Web server

Since there are only 2 open ports. We start by checking the web server. The web page at the document root shows the following message:

"A jack of all trades is a master of none but oftentimes better than a master of one"

Aside from this message, there is no hint at the HTML source code either. The next step is to check for hidden files and directories. An excellent tool to find such hidden files and directories is gobuster. Please note that we got our big.txt word list from this URL. Run the following command to find hidden directories and files.

gobuster -u http://10.10.161.155/ -w /usr/share/wordlists/Discovery/Web-Content/big.txt

After a while, you will find just one hidden directory. You can see the output of this scan below:

/development (Status: 301)

Browsing to rsa.thm/development shows us the following files that one can download.

id_rsa.pub                                         13-Aug-2022 09:27                 725
log.txt                                            13-Aug-2022 09:27                 321

The log.txt file might reveal some interesting information. Click the file to find the following message:

The library we are using to generate SSH keys implements RSA poorly. The two
randomly selected prime numbers (p and q) are very close to one another. Such
bad keys can easily be broken with Fermat's factorization method.

Also, SSH root login is enabled.

<https://github.com/murtaza-u/zet/tree/main/20220808171808>

As we can see in this log.txt file, root log-in is enabled. Furthermore, we find a public RSA key. The RSA keys are implemented poorly and the private RSA key can be acquired by Fermat’s factorization method.

TryHackMe Breaking RSA | Acquiring the private key

Now that we now what we have to do, start by downloading the public key:

wget http://rsa.thm/development/id_rsa.pub

The public key is a large number, but when we check the content of id_rsa.pub we can only see a key that consists of a Base64-encoded value. To read its value, we will use the Python programming language in combination with a library called pycryptodome. Start by installing pycryptodome by running the following commands:

pip install pycryptodome

Next, we create our script to get the information from the RSA key. To make things easier, we will make 1 single script to answer all the questions. In each step, we will extend the script created to include all necessary lines to answer the question at that time.

Key Length and last 10 digits

The first questions are about some generic properties of the public key. Thanks to the pycryptodome library we can answer these questions. Create the following Python script:

#!/usr/bin/env python3

from Crypto.PublicKey import RSA

with open('id_rsa.pub', 'r') as file:
    public_key = RSA.import_key(file.read())

bit_size = public_key.size_in_bits()
n = public_key.n
x = str(n)[-10:]

print(f"The size in bits of the public key is: {bit_size}")
print(f"The last 10 digits of the public key are: {x}")

We include the library to read and make computations on the public RSA key.
Now we open the id_rsa.pub file and store the computable key in a variable called public_key
We use the size_in_bits() function on our public key. As the name suggests, calling this function on the public key returns the size in bits.
The n variable is an attribute of the public key object. We also store its value in a variable called n and print the last 10 digits. This is done by first converting the number to a string object.

Factorizing n

Below is an updated code version that includes the answers to the factorization questions. We highlighted them in bold.

#!/usr/bin/env python3

from Crypto.PublicKey import RSA

from gmpy2 import isqrt

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will
    # always be 2
    if (n & 1) == 0:
        return (n/2, 2)

    # isqrt returns the integer square root of n
    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    while True:
        a = a + 1
        bsq = a * a - n
        b = isqrt(bsq)
        if b * b == bsq:
            break

    return a + b, a - b


with open('id_rsa.pub', 'r') as file:
    public_key = RSA.import_key(file.read())

bit_size = public_key.size_in_bits()
n = public_key.n
x = str(n)[-10:]

p, q = factorize(n)

print(f"The size in bits of the public key is: {bit_size}")
print(f"The last 10 digits of the public key are: {x}")
print(f"The difference between p and q is: {p - q}")

First, we include the gmpy2 library. The gmpy2 is a C-coded Python extension module that supports multiple-precision arithmetic. Thus, a library for computation with large numbers.
Next, we include the provided factorize function from the box into our code.
Last, by running the function on our n value, we can get the values:p and q. We print the difference between the primary to answer the next question.

Acquiring the private key

Now that we have obtained the usually unobtainable values of p and q, we can calculate the d value to obtain the private key. The formula to obtain d is: d = modinv(e, lcm(p - 1, q - 1))

. Since we know the values of e (given=65537),p, and q, we can calculate d. Let’s now plug this formula into our code.

#!/usr/bin/env python3

from Crypto.PublicKey import RSA

from gmpy2 import isqrt, invert, lcm

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will
    # always be 2
    if (n & 1) == 0:
        return (n/2, 2)

    # isqrt returns the integer square root of n
    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    while True:
        a = a + 1
        bsq = a * a - n
        b = isqrt(bsq)
        if b * b == bsq:
            break

    return a + b, a - b


def get_private_key(e, p, q):
    return invert(e, lcm(p - 1, q - 1))



with open('id_rsa.pub', 'r') as file:
    public_key = RSA.import_key(file.read())

bit_size = public_key.size_in_bits()
n = public_key.n
x = str(n)[-10:]

e = 65537
p, q = factorize(n)

d = get_private_key(e, p, q)

private_key = RSA.construct((n ,e , int(d)))

with open('id_rsa', 'wb') as file:
    file.write(private_key.export_key('PEM'))

print(f"The size in bits of the public key is: {bit_size}")
print(f"The last 10 digits of the public key are: {x}")
print(f"The difference between p and q is: {p - q}")


print(f"The value of the private key is {d}")
print("You can find your key in this directory.")

First, we will import the invert and lcm packages of the gmpy2 module as well since we need them both for computing d.
Next, we write the function to return the value for our private key d. This function only applies the mathematical function above as a function in Python.
We have to run our get_private_key function and return its value as d. After computing the numerical value of the private key, we have to create a new RSA object to contain the key. We can do so by running the RSA.construct function. This function requires 3 parameters: n, e and d.
After constructing our RSA private key, we can run the export_key function on this key, with the PEM parameter to encode this key as PEM. The output of this function is written to a file calledid_rsa, our new private key to log in to the server.

Now that we have generated the private key, let’s log in to the server. Do so by running the following commands:

chmod 400 id_rsa
ssh [email protected]

By default, a private key can only be read by the user onwing that key. After changing the permissions of the private key, log into the server.

Congratulations, you are in! Obtain the flag by running: cat flag.

TryHackMe Breaking RSA | Conclusion

The TryHackMe Breaking RSA box was a fun box to root! Its primary focus is the security of RSA and why no one must be able to factorize the value of n into p and q. Obtaining such values results in the user acquiring the private key. Luckily, modern-built libraries will not use such factorization methods nowadays, so RSA is still considered a safe encryption scheme.

TAGS:
CTF
RSA
TryHackMe

About Richard

Twitter | Facebook

TryHackMe Breaking RSA Write-up