Breaking RSA

Hop in and break poorly implemented RSA using Fermat's factorization algorithm. - by hackerinthehouse

TryHackMe | Breaking RSATryHackMe

The following post by 0xb0b is licensed under CC BY 4.0

---

We start with a Nmap scan and find two open ports. SSH on port 22 and a web server on port 80.

We enumerate the directories of the web server using Gobuster, but only find one directory: development.

Visiting the index page doesn't reveal anything of interest.

On the /development page, we find an RSA public key and a log.txt.

The log only repeats what we already know from the challenge description and indicates the source of the algorithm. Furthermore, we can assume that SSH is enabled for root. So we already have the user when we generate the private key later and try to access SSH.

We know from the challenge that we are dealing with a weak RSA implementation. Our task will probably be to extract N and e from the public key in order to factorize N, getting p and q, and finally calculate d. The value d is the private key. If we have the parameters N, e, and d, we can generate the private SSH key and thus access the machine. Check out https://en.wikipedia.org/wiki/RSA_(cryptosystem) for a brief overview of RSA.

We download the public key.

id_rsa.pub

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDrZh8oe8Q8j6kt26IZ906kZ7XyJ3sFCVczs1Gqe8w7ZgU+XGL2vpSD100andPQMwDi3wMX98EvEUbTtcoM4p863C3h23iUOpmZ3Mw8z51b9DEXjPLunPnwAYxhIxdP7czKlfgUCe2n49QHuTqtGE/Gs+avjPcPrZc3VrGAuhFM4P+e4CCbd9NzMtBXrO5HoSV6PEw7NSR7sWDcAQ47cd287U8h9hIf9Paj6hXJ8oters0CkgfbuG99SVVykoVkMfiRXIpu+Ir8Fu1103Nt/cv5nJX5h/KpdQ8iXVopmQNFzNFJjU2De9lohLlUZpM81fP1cDwwGF3X52FzgZ7Y67Je56Rz/fc8JMhqqR+N5P5IyBcSJlfyCSGTfDf+DNiioRGcPFIwH+8cIv9XUe9QFKo9tVI8ElE6U80sXxUYvSg5CPcggKJy68DET2TSxO/AGczxBjSft/BHQ+vwcbGtEnWgvZqyZ49usMAfgz0t6qFp4g1hKFCutdMMvPoHb1xGw9b1FhbLEw6j9s7lMrobaRu5eRiAcIrJtv+5hqX6r6loOXpd0Ip1hH/Ykle2fFfiUfNWCcFfre2AIQ1px9pL0tg8x1NHd55edAdNY3mbk3I66nthA5a0FrKrnEgDXLVLJKPEUMwY8JhAOizdOCpb2swPwvpzO32OjjNus7tKSRe87w==

To determine the length in bits of the public we can issue the following command:

The following source gives an example of how the parameters N and e can be taken from the public key using Python.

How do you extract N and E from a RSA public key in python?Stack Overflow

We just do it manually for now, but we will integrate it into the final script to answer all RSA-related questions.

>>>from Crypto.PublicKey import RSA
>>>f = open("id_rsa.pub", "r")
>>>key = RSA.importKey(f.read())
>>>print key.n #displays n
>>>print key.e #displays e

We can extract N and e, allowing us to answer the first RSA-related question: the last 10 digits of N. Now things are really taking off.

The challenge description gives us a direct indication of how we can calculate p and q in this case of this weak implementation. We have to use Fermat's Factorization method. If we have p and q, we can calculate the private key d via the inverse of e.

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.

A rough overview of Fermat's factorization can be found here.

Fermat's factorization methodWikipedia

Here is the snippet of pseudocode we have to implement:

To be able to calculate with the large values, we use gmpy2.

gmpy2 is an optimized, C-coded Python extension module that supports fast multiple-precision arithmetic. gmpy2 is based on the original gmpy module. gmpy2 adds support for correctly rounded multiple-precision real arithmetic (using the MPFR library) and complex arithmetic (using the MPC library).

gmpy2PyPI

Well, we now have almost everything together; we can calculate p and q using the Fermat factorization method. Using p, q, and e, we can calculate d. Also, we are able to get the difference between p and q. Now we just have to generate the private SSH key from our integer values of the parameters N, e, and d. The following source gives a short how-to:

RSA generate private key from data with pythonStack Overflow

Adding this snippet to our final script, for SSH key generation:

from Crypto.PublicKey import RSA

# assume d was correctly calculated
n = 1234....L
e = 65537L
d = 43434...L
private_key = RSA.construct((n, e, d))
dsmg = private_key.decrypt(msg)

And here is the final Python-script:

rsa-pwn.py

import gmpy2
from Crypto.PublicKey import RSA

def fermat_factorization(n):
    """Fermat's Factorization Method"""
    a = gmpy2.isqrt(n) + 1
    b2 = gmpy2.square(a) - n
    while not gmpy2.is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n
    p = a + gmpy2.isqrt(b2)
    q = a - gmpy2.isqrt(b2)
    return p, q

def calculate_private_key(p, q, e):
    """Calculate the private key 'd'"""
    phi = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi)
    return d

# Open the RSA key file
with open("id_rsa.pub", "r") as f:
    # Import the RSA key
    key = RSA.import_key(f.read())

# Retrieve the modulus (n) and public exponent (e)
n = key.n
e = key.e

# Print the modulus and public exponent
print("\033[96mModulus (n):\033[0m", n)
print("\033[96mPublic Exponent (e):\033[0m", e)

# Factorize n into p and q using Fermat's Factorization
p, q = fermat_factorization(n)

# Calculate private key 'd' using p, q, and public exponent 'e'
d = calculate_private_key(p, q, e)

difference = abs(p - q)
print("\033[93mp:\033[0m", p)
print("\033[93mq:\033[0m", q)
print("\033[93mDifference between q and p:\033[0m", difference)
print("\033[96mPrivate Key (d):\033[0m", d)

key_params = (n, e, d, p, q)
key = RSA.construct((n,e,int(d)))

# Export the private key to a file
with open('id_rsa', 'wb') as f:
    f.write(key.export_key('PEM'))

print("\033[92mPrivate key generated and saved as 'id_rsa'.\033[0m")

After running our finished script, we can answer the questions about the last 10 digits of N, the difference between p and q, and get the private SSH key.

Lastly, we have to add the correct permissions to the key to log on the machine as root. In the home directory of root, we find the flag.