Breaking RSA

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

Breaking RSATryHackMe

Let's start with a simple nmap scan.

┌──(kali㉿kali)-[~]
└─$ nmap -sT -p- 10.10.251.239 -T4          
Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-02-19 00:51 EST
Warning: 10.10.251.239 giving up on port because retransmission cap hit (6).
Stats: 0:18:56 elapsed; 0 hosts completed (1 up), 1 undergoing Connect Scan
Connect Scan Timing: About 92.68% done; ETC: 01:12 (0:01:30 remaining)
Nmap scan report for 10.10.251.239
Host is up (0.15s latency).
Not shown: 65530 closed tcp ports (conn-refused)
PORT      STATE    SERVICE
22/tcp    open     ssh
80/tcp    open     http
27567/tcp filtered unknown
31710/tcp filtered unknown
36144/tcp filtered unknown

Nmap done: 1 IP address (1 host up) scanned in 1247.83 seconds

We can see there are 2 open ports, SSH on port 22 and a web server on port 80.

Let's enumerate the directories now. We are using Gobuster.

We have found only one directory i.e: /development.

Let's visit the web server now.

Nothing to go one here. Let's visit /development.

There are two files as we can see.

• id_rsa.pub

• log.txt

The log.txt re iterates what is already mentioned in the description of the room.

We know from the challenge that we are dealing with a weak RSA implementation. We will most likely 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 N, e, and d, we can generate the private SSH key and then access the machine.

Let's download the public key.

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

We can use the ssh-keygen utility to find the length of the discovered RSA key.

┌──(kali㉿kali)-[~/Downloads]
└─$ ssh-keygen -l -f id_rsa.pub
**** SHA256:DIqTDIhboydTh2QU6i58JP+5aDRnLBPT8GwVun1n0Co no comment (RSA)

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

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

┌──(kali㉿kali)-[~/Downloads]
└─$ python               
Python 3.11.6 (main, Oct  8 2023, 05:06:43) [GCC 13.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from Crypto.PublicKey import RSA
>>> f = open("id_rsa.pub", "r")
>>> key = RSA.importKey(f.read())
>>> key.n
[REDACTED]
>>> key.e
[REDACTED]

The challenge gives us a direct indication of how to calculate p and q in this case of 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. The challenge room also gives us an implementation of Fermat's Factorization algorithm in python.

Now we have to generate the private SSH key from our values of the parameters N, e, and d. With the help of the followig source:

RSA generate private key from data with pythonStack Overflow

After being held at this point for quite some time. I eventually reffered to other write ups and this one helped the most with implementing the code of fermat factorization. I recommend giving it a read for a much more detailed understanding.

Breaking RSA | Writeups0xb0b.gitbook.io

rsa.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")

We use gmpy2 to calculate with large values.

It is now time to run our finished script.

┌──(kali㉿kali)-[~/Downloads]
└─$ python rsa.py    
Modulus (n): 960343778775549488806716229688022562692463185460664314559819511657255292180827209174624059690060629715513180527734160798185034958883650709727032190772084959116259664047922715427522089353727952666824433207585440395813418471678775572995422248008108462980790558476993362919639516120538362516927622315187274971734081435230079153205750751020642956757117030852053008146976560531583447003355135460359928857010196241497604249151374353653491684214813678136396641706949128453526566651123162138806898116027920918258136713427376775618725136451984896300788465604914741872970173868541940675400325006679662030787570986695243903017923121105483935334289783830664260722704673471688470355268898058414366742781725580377180144541978809005281731232604162936015554289274471523038666760994260315829982230640668811250447030003462317740603204577123985618718687833015332554488836087898084147236609893032121172292368637672349405254772581742883431648376052937332995630141793928654990078967475194724151821689117026010445305375748604757116271353498403318409547515058838447618537811182917198454172161072247021099572638700461507432831248944781465511414308770376182766366160748136532693805002316728842876519091399408672222673058844554058431161474308624683491225222383
Public Exponent (e): 65537
p: [REDACTED]
q: [REDACTED]
Difference between q and p: [REDACTED]
Private Key (d): [REDACTED]
Private key generated and saved as 'id_rsa'.

After running the script we answer question 4 and 6. ie

What are the last 10 digits of n? (where 'n' is the modulus for the public-private key pair)

What is the numerical difference between p and q?

We can SSH in as root and we get our flag.

┌──(kali㉿kali)-[~/Downloads]
└─$ ssh -i id_rsa root@10.10.73.144       
The authenticity of host '10.10.73.144 (10.10.73.144)' can't be established.
ED25519 key fingerprint is SHA256:p8ToZTCl6UDL9y+eR4LyuFIrGt62U3kJ+oLKS6Iua84.
This key is not known by any other names.
Are you sure you want to continue connecting (yes/no/[fingerprint])? yes
Warning: Permanently added '10.10.73.144' (ED25519) to the list of known hosts.
Welcome to Ubuntu 20.04.4 LTS (GNU/Linux 5.4.0-124-generic x86_64)

 * Documentation:  https://help.ubuntu.com
 * Management:     https://landscape.canonical.com
 * Support:        https://ubuntu.com/advantage

 System information disabled due to load higher than 1.0


0 updates can be applied immediately.


The list of available updates is more than a week old.
To check for new updates run: sudo apt update


The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.

Last login: Sat Aug 13 09:35:51 2022 from 10.0.0.11
root@thm:~# ls
flag  snap
root@thm:~# cat flag
[REDACTED]
root@thm:~#