HTB Write-Up: Weak RSA

This is a write-up on the Weak RSA crypto challenge from HTB.  For more information on challenges like these, check out my post on penetration testing.  Special thanks to HTB user tomtoump for creating the challenge.

Cryptography 101 - Notes Worth Recalling

RSA is an asymmetric cryptographic algorithm, which means that it uses two keys for encryption.  The two keys, or key pair, are commonly referred to as the public and private keys, and anything encrypted with one key can be decrypted with the other.    Although the two keys are mathematically related to each other, the arithmetic makes it generally unrealistic (think: practically impossible with most computer systems) to derive one key from the other.  This has made RSA the encryption gold standard for decades.

There are some weaknesses in RSA, however.  In particular, when small keys are used, it becomes possible to derive the private key from the public key.

Cracking the Code

Two files are provided for this challenge:

• flag.enc: encrypted file containing the text, or "flag," that is needed to solve the challenge
• key.pub the public encryption key that was used to encrypt the flag

Math lovers can extract the modulus from the public key and try to factorize it or see if it's made of known primes.  For everyone else, RsaCtfTool is a Python tool that can be leveraged to automate recovery of weak RSA keys.  The steps are below - easy, right?

1. Download and install RsaCtfTool. If using Kali Linux, Unbuntu or MacOS, make sure to install the prerequisistes as outlined in the Readme file
2. Run python RsaCtfTool.py --publickey ./key.pub --private to output the private key. Save the private key to a file called key.priv
3. Although RsaCtfTool.py has a flag (--uncipherfile) which will automatically decrypt the file, I prefer to use a different command which is available on most systems: openssl rsautl -in flag.enc -out flag.txt -decrypt -inkey key.priv
4. The file flag.txt should now contain the flag