GOAL
https://tryhackme.com/room/hfb1cryptosystem
Given a sample vulnerable RSA implementation, utilize cryptographic and mathematical concepts to break the encryption given the implementation, modulus (n), and ciphertext.
BACKGROUND
Kerckhoff’s Principle states that a cryptosystem should remain secure even if the implementation and system
details are public knowledge. A secure system should rely on the secrecy of the key, not on security through obscurity
or hidden implementation details.
TryHackMe’s “Cryptosystem” challenge covers this concept with an example of a vulnerable RSA implementation. We are given
the following information:
from Crypto.Util.number import *
from flag import FLAG
def primo(n):
n += 2 if n & 1 else 1
while not isPrime(n):
n += 2
return n
p = getPrime(1024)
q = primo(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(FLAG.encode()), e, n)
#c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
#n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
Given the implementation, modulus (n), and ciphertext, we can begin to analyze potential gaps in the cryptosystem.
TOOLS
To recover the plaintext, I utilized:
- Python to handle mathematics and streamline the solution
- Wikipedia’s pseudocode for Fermat’s factorization method
ANALYSIS
Initially, the first thing that jumped out at me when looking at the RSA implementation source code was the generation of the second prime number (q). Given a 1024-bit value,
there are way too many potential prime numbers to try to brute force the value of p. The second prime number, however, is generated by finding the next prime after the first prime p. Therefore, in a smaller example, if p is 3, q would be 5.
Pierre de Fermat created an algorithm that enables the (relatively) quick calculation of the prime factors of a large number when the two primes are close. This concept will allow us to determine the values of p and q, giving us the ability to decrypt the given ciphertext.
Implementing Fermat’s Factorization algorithm in Python looks roughly like this:
def fermat_factor(n: int):
a = math.isqrt(n)
if a**2 < n:
a += 1
b = a * a -n
while math.isqrt(b) ** 2 != b:
a += 1
b = a * a -n
return a - math.isqrt(b), a + math.isqrt(b)
Given a large number n, we take a to be the integer square root (essentially the ceiling of the floating point square root) of n. We will represent the second prime as b, which we will
assign to be a squared subtracted by n. When b is a perfect square, we know that we have found the prime number pair, a and b, that was combined to make n.
Extending this algorithm, we can reverse-engineer the cryptosystem and decrypt the given ciphertext: s
cryptosystem.py
from Crypto.Util.number import long_to_bytes
import math
def fermat_factor(n: int):
a = math.isqrt(n)
if a**2 < n:
a += 1
b = a * a -n
while math.isqrt(b) ** 2 != b:
a += 1
b = a * a -n
return a - math.isqrt(b), a + math.isqrt(b)
def decrypt(e, p, q, n, c):
phi = (p - 1)*(q - 1)
d = pow(e, -1, phi)
return pow(c, d, n)
n = 1595625016206... # input given modulus (n) here
c = 3591116664311... # input given ciphertext here
p, q = fermat_factor(n)
e = 65537 # given public exponent
plaintext_bytes = long_to_bytes(decrypt(e, p, q, n, c))
plaintext = plaintext_bytes.decode(errors="ignore")
print(plaintext)
Running the script with the given modulus, public exponent, and ciphertext will return the flag to complete the challenge.
CONCLUSION
In conclusion, custom RSA algorithms are dangerous (never roll your own crypto). While choosing the next prime after your first randomly generated one may seem like
a time-saving shortcut for an RSA implementation, Fermat’s factorization method can be used to derive the primes used in encryption, allowing attackers to decrypt and re-encrypt
data using your private key.
Just 3 years ago, a similiar vulnerability in the Rambus SafeZone Basic Crypto Module was found, affecting various companies including Canon and Fujifilm (CVE-2022-26320). Security
Researcher Hanno Böck has a great breakdown of the vulnerability and how Fermat Factorization works here.
SOURCES
https://en.wikipedia.org/wiki/Fermat%27s_factorization_method