Breaking RSA

Hop in and break poorly implemented RSA using Fermat’s factorization algorithm.

RSA- Room

A brief overview of RSA

Introduction

In a recent analysis, it is found that an organization named JackFruit is using a deprecated cryptography library to generate their RSA keys. This library is known to implement RSA poorly. The two randomly selected prime numbers (p and q) are very close to one another, making it possible for an attacker to generate the private key from the public key using Fermat's Factorization method.

TryHackMe Breaking RSA — Enumeration

System vulnerability exploration is vital in cybersecurity. Using Nmap, we can unveil open ports on a target system, potentially accessing it via SSH.

Execute nmap <target_ip> to scan all ports. Results highlight open ports, including SSH (port 22).

nmap scan….

Web server

Given the limited number of open ports, we initiate our investigation by inspecting the web server for any vulnerabilities or pertinent details.

The subsequent step involves examining hidden files and directories. Gobuster is an excellent tool for uncovering such hidden elements within the web server.

gobuster dir -u http://10.10.126.156/ -w /usr/share/wordlists/dirbuster/directory-list-2.3-medium.txt

web and gobuster scan….

After some time, only one hidden directory is discovered. Below is the output of the scan:

/development  (Status: 301) [Size: 178] [--> http://10.10.126.156/development/]

Browsing to `10.10.126.156/development` reveals the following downloadable files:

/development….

Breaking RSA | Acquiring the private key

To extract the value of the public key from id_rsa.pub, which is Base64-encoded, we'll utilize Python with the pycryptodome library. Begin by installing pycryptodome using the following commands:

pip install pycryptodome

pip install gmpy2

To address the factorization questions, you can use the following Python code after installing the necessary libraries:

For this code i used ChatGPT for reference while creating code. with Below is an implementation of Fermat’s factorization algorithm in Python.

#!/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.")

This code reads the id_rsa.pub file, decodes the Base64-encoded key, extracts the modulus (n) and public exponent (e), and then performs the necessary calculations to answer each of the factorization questions. Finally, it generates the private key using the obtained factors and the provided public exponent.

Set Appropriate Permissions: Ensure the private key file (id_rsa) has the correct permissions set for security purposes. You can do this by running the following command:

chmod 400 id_rsa

SSH Login: Next, initiate the SSH login process using the private key by running the following command:

ssh root@10.10.126.156 -i id_rsa

After adjusting the permissions of the private key to ensure it’s only readable by the owner, proceed to log in to the server. Once logged in, obtain the flag by running the following command:

cat flag

FLAG

This command will display the contents of the flag file, allowing you to retrieve it. Congratulations on successfully accessing the server!!

Breaking RSA | Conclusion

The TryHackMe Breaking RSA box provides a compelling exploration of RSA security, emphasizing the criticality of safeguarding the modulus (n) from factorization into its prime factors (p and q). Possessing these factors grants access to the private key, jeopardizing encryption integrity. Fortunately, contemporary cryptographic libraries implement advanced methods, mitigating the risk of such factorization attacks. As a result, RSA remains a robust encryption scheme, bolstering confidence in its continued use for secure communication and data protection in modern computing environments.

Happy Hacking!
“#HackWithJoy: Unleash your coding prowess and dive into exhilarating hacking adventures!”