Breaking RSA Algorithm — Fermat’s Surprise (2024)

Recently I was doing a CTF challenge wherein the objective was to compromise the integrity of the RSA algorithm. Central to the challenge was Fermat’s Factorization Method and its deadly application to bring down a modern cryptographic system. I would like to point out that the compromise of RSA happens only when it is not properly implemented. Specifically, when the prime numbers (p, q) that make up the RSA keys are not sufficiently spaced apart. In this limiting scenario, Fermat’s Factorization Method can completely compromise the integrity of RSA.

In this article I wanted to take the readers on a cryptographic journey into the workings of RSA and watch for themselves how it can be broken with this 300 year old factorization method! I have structured this article into 3 broad sections.

1. The Background — In a Nutshell
2. Breaking RSA
3. References

In The Background we will cover some of the very basic mathematics that goes with RSA and also understand specifically what this vulnerability is. This is a theoretical section and in case if people want to get in on the action they can move to the second section directly.

In Breaking RSA we will have a look at a deliberately vulnerable application that I have designed for this tutorial. We will go over the vulnerability and exploit it to gain a reverse shell on the containerized application.

Finally, in the References section, I will give all the supporting material for this article. In fact, this vulnerability has been documented as CVE-2022–26320 and is chiefly the work of a gentleman by the name Hanno Bock. I did uncover some great resources while working on this article and links to all of those will be shared here in this section.

RSA is an asymmetric cryptographic system that consists of a Public Key and a Private Key. Encryption is done via the public key while decryption is achieved through the private key. The security resilience in RSA is achieved because of the inherent difficulty in factorizing very large numbers into their constituent prime factors. As an example, consider n=77, which can be easily factorized into p=11 and q=7. This factorization is easy because of the small magnitudes involved.

But let us consider an n = 106,109,701. Factorizing this would not be so simple! The prime numbers that give this product are p=10,331 and q=10,271. While this example is a little tough, but it is still within the bounds of possibility to factorize n. And in fact you very easily can do this programmatically.

For an industry standard cryptosystem like RSA that has been entrusted with safeguarding the integrity of data, the standards are quite high. NIST recommends key size of 2048 bits to 4096 bits for modern systems. This means that for the lower boundary of 2048 bit key size, the value of n would be 4096 bits long! The work function or in other words the time & effort required to brute force modern crptographic systems would be in hundreds of years with those kind of key sizes.

It will not be feasible to explain RSA at length, but we will touch upon some of its salient components that would faciliate our discussion going forward. For the purpose of this article, let us lay out all the components involved in RSA cryptography.

Let us go over these components in brief.

1. p & q are very large prime numbers that are used in the public as well as private key
2. Modulus or n is the product of p & q and is available inside the Public key that is shared with everyone
3. Totient Function Φ(n) is derived from the value of p & q and is utilized in generating the Private key
4. Integer e satisfies 2 conditions generally. Condition one is that 2 < e < Φ(n) and condition two is gcd(e,Φ(n)) = 1 or e and Φ(n) are co-prime. It is worth noting that the value of e is declared inside the public key.
5. Private Key Exponent, d which is d ≡ e^(-1)(mod Φ(n)). The value of d is kept a secret and is used in decrypting cipher text received.

At this point it is not very important to understand all of the math that comes with the above elements. What is important however, is to understand the distinct components involved and which components go where i.e. which cryptographic elements are revealed in the public key and the ones that are not.

As one can see the value of n and e are revealed inside the Public Key that is shared with everyone. The other components p, q, d and Φ(n) are not shared. But a careful examination tells us that only the values of p & q are critical. If we know p & q, we can compute the values of d & Φ(n). And this is extremely important because it tells us that if we can factorize n or in other words figure out p & q, all other components can be calculated.

And hence the damage that a factorization method like Fermat’s can do becomes disinctly severe in case if it is able to crack open the factors of n. Because then all other cryptographic elements can be calculated and a private key can then be trivially generated at the attacker’s end. Keep in mind, the values of n & e are publicly available e.g., inside Public Certificates. The stage is set now for Fermat’s Theorem.

Fermat’s factorization method aims to quickly identify factors for n. And Fermat’s method is such that in case if the prime numbers (p & q) are not very far apart or the difference between them is not very high then the method can quickly identify the factors or in this case the value of p & q. The associated math for Fermat’s method can be looked at separately. I have provided the link to it in references section.

So to summarize, the security resilience of RSA depends on the difficulty in factoring large numbers. That central notion of security is challenged by Fermat’s Factorization Method for factors that are not very far apart in magnitude. Fermat’s method in such situations can effectively find factors even for very large values of n as mandated by Industry Standards like NIST. And this leads to a complete compromise of the keys because once n, e, p and q are available, all other parameters can be calculated and keys can be generated too.

Let us now shift our focus to a deliberately vulnerable web application developed for this demo. I have containerized this application and anyone reading this article can build an image on cloud or locally and work alongisde. The repository to the vulnerable web application is here.

For the sake of this writeup, I have setup the application on an AWS EC2 instance (which I will take down once my article is done). The application in itself is not the center of focus. In fact we are more interested in the certificate (TLS) that is being used in the web app.

The Certificate contains the public key, from which an attacker can trivially obtain the value of n & e. As a next step, we use Fermat’s Factorization method and try to find the prime numbers p & q that are factors of n. Since, this application is vulnerable we are able to obtain values for p & q by using the Fermat’s method.

Next, we leverage our understanding of RSA to derive remaining cryptographic elements d & Φ(n) or Totient Function. Armed with these we generate the Private Key of the certificate successfully!

Because this is a demo of the severity of this vulnerability, I thought let us take it up a notch. This private key is also the private key that is used to SSH into the container that is running this application. And as is to be expected we are running as ROOT inside the container!

One can say that it would have been more fun if the private key was used to get SSH access to the host (or EC2 in this case). And I agree, but I didn’t want to leave EC2 instances open to SSH with a method to get to their private keys even in a tutorial! Enough said, let us get to action.

When we get to the web app we can see that our browser complains because the certificate is self-signed. We will “Accept” the risk and continue.

Once we do that we can see that the web app has a very basic home page.

There is one more page, in the web application that contains a small note indicating the potential vulnerability that might be present.

As part of reconnaissance we can also look at the certificate that is present on the website.

We can see certificate and its associated details. In the Public Key info section we can see the algorithm being used along with the key size and the exponent or e value and also the modulus. As discussed earlier, these are shared as part of the public key.

As a next step, I will share the repository that contains the exploit for this vulnerability. This exploit automates the process of extracting public key information (n, e) and then it attempts to use Fermat’s Factorization method to break the algorithm.

We can provide the domain name and the script will connect with the domain and then download the certificate and public key. Post that it can attempt to use Fermat’s Factorization method to crack open the prime numbers (p & q). Let us see this in action.

In our case, we don’t have a domain and hence we can provide the IP address and there is no need to define the port because it takes 443 by default. Let us run and see what happens.

At this point the exploit asks whether we would like to proceed with Fermat’s Factorization Method to identify p & q. We will say “YES” to proceed with the exploit.

The moment we said yes, a few things happened.

1. It successfully factorized the modulus (n) into its prime numbers (p & q) in very quick time. Note, this happened in less than a second for a 2048 bit long key size!
2. We see the difference between the 2 prime numbers p & q is a mere 214. This is the real culprit why Fermat’s Factorization method was able to factorize n so quickly.
3. Remaining cryptographic components such as d & Φ(n) are computed (only d is shown here). These components help is generating the private key
4. Finally, we also have the private key available to us. The exploit stores the key in a separate PEM file while displaying it on the STDOUT.

In a nutshell, what we saw above is a complete breakdown & compromise of the RSA implementation. Because we were able to arrive at the Private Key from publicly declared elements in extremely quick time!

The key obtained can be leveraged to SSH inside the container that is running this application. So, let us first log inside the EC2 instance or the host and then we will use the retrieved key to show that final step as well.

We will use this key to log in into the container that is running at 172.17.0.2

And indeed, we were able to SSH into the container from the key that we retrieved by leveraging the exploit. This completes the attack chain that we had laid out before in this section. We began by navigating to the web application and had a look at its certificate. We then used our exploit to leverage Fermat’s Factorization Method to factorize the modulus (n) and retrieve p & q. Post that, we generated the private key because we had all the cryptographic primitives required to generate the Private Key. And finally we used this private key to get (SSH) inside the container running the application.

At this point it would be worth discussing how the exploit works at a high level. There is one main component (rsaBreak.py) and it is supported by 4 other python modules that perform various tasks. One module extracts the public certificate from the domain provided and its public key components (n, e). Another module, uses the Fermat method for factorizing n into its prime numbers. There is another module that computes the private key exponent (d). And finally there is a module that uses all of the cryptographic primitives to generate the Private Key. I must confess that I have taken the logic for Fermat’s factorization & Modulo Inverse from generous donors in the GitHub community!

All of these modules tie together inside the main component from where we launch the exploit. This exploit can be used to test a key individually as well for its susceptibility to this vulnerability.