Hack The Box: Weak RSA

This is the third in a series of write-ups of challenges from the Hack The Box Beginner Track.

The Challenge

The previous challenge, Find The Easy Pass, gave us a Windows executable to reverse engineer. In this sense it didn't align with my expectations of what a CTF involves.

This challenge, Weak RSA, is similar in the sense that we're given two files to download. This time though, neither of them are executable:

$ file key.pub
key.pub: ASCII text
$ file flag.enc 
flag.enc: data

Looking at the contents of key.pub, it looks like an RSA public key:

$ cat key.pub 
-----END PUBLIC KEY-----

We can confirm this with OpenSSL:

$ openssl rsa -pubin -in key.pub -text -noout
RSA Public-Key: (1026 bit)

So it's definitely an RSA key. At this point it's fairly clear what we need to do. flag.enc must contain the encrypted flag. We need to decrypt that by finding the private key that matches the public key we've been provided.


RSA is an asymmetric encryption algorithm. This means that there are two keys: one to encrypt, the public key, and one to decrypt, the private key. As their names suggest, the public key is intended to be shared, whilst the private key must be kept secret. Together they form a key pair.

Before we get into the nitty gritty, here's a little warning. The security of RSA involves quite a lot of maths. I've tried to keep this brief and relevant to the current problem, but a bit of maths is unavoidable, so apologies in advance if this isn't your jam.

An RSA key pair is defined by a modulus, $N$, a public key exponent, $e$, and a private key exponent, $d$. $N$ is the product of two large, prime numbers $p$ and $q$. The security of RSA is founded on the difficulty of determining $p$ and $q$, given only $N$ and $e$. If RSA is used correctly, factoring $N$ into $p$ and $q$ is essentially impossible. $e$ and $d$ are then related via

$$ e d \equiv 1 \quad \left(\text{mod} \space \varphi(N)\right) \tag{1} $$

where $\varphi$ is Euler's totient function. Within the realm of RSA, $\varphi(N) = (p-1)(q-1)$. $\text{mod}$ is short for modular arithmetic, which effective means that we require the remainder when we divide the product of $e$ and $d$ by $\varphi(N)$ is $1$. $d$ is said to be the modular multiplicative inverse of $e$, and vice versa. $e$ is normally picked, and $d$ is then calculated using something like the extended Euclidean algorithm or Euler's theorem.

Finding a Weakness

Our public key's modulus is 1026 bits long according to OpenSSL. Given that it took 2700 CPU-years of compute time on state-of-the-art hardware just to break a public key with an 829-bit modulus back in 2020, we can safely assume this approach won't work here.

The time required to encrypt a plaintext message or decrypt a ciphertext is a function of the size of the public and private key exponents, respectively. Implementations generally favour smaller values of $e$, and $2^{16} + 1 = 65537$, or 0x10001, is a common public key exponent. Smaller values weaken the security of the cryptosystem, whilst larger values result in longer encryption times without any further security benefit.

The public key above has an exponent that is far greater than 65537, which is a bit strange. Googling "rsa public key large exponent" produced results that suggest a large exponent like ours may be symptomatic of a correspondingly small private key exponent. When the private exponent is small relative to the modulus, the former can be recovered relatively easily using Wiener's attack.

Wiener's Attack

Wiener's attack uses Wiener's theorem to let us efficiently determine $d$. The theorem states that, given the following:

$$ \begin{gather} N = pq\\\\ q < p < 2q\\\\ e d \equiv 1 \space \left(\text{mod} \space \varphi(N)\right)\\\\ d < \frac{1}{3}N^\frac{1}{4}\\ \end{gather} $$

we can efficiently compute $d$ using approximations of $\frac{e}{N}$.

But how? What does it mean to approximate $\frac{e}{N}$?

Revisiting the relationship between the public and private exponents, $e$ and $d$, we can say that there must be some integer $k$ such that

$$ e d - k \varphi(N) = 1\tag{2} $$

Here $k$ is essentially the quotient we would obtain if we divided $ed$ by $\varphi(N)$. Using $\varphi(N) = (p - 1)(q - 1)$ allows us to write

$$ e d - k (p - 1)(q - 1) = 1 $$

With a bit of massaging this can be rewritten as

$$ \frac{e}{pq} = \frac{k}{d}(1 - \delta); \quad \delta = \frac{p + q - 1 - \frac{1}{k}}{pq}\tag{3} $$

So we expect $\frac{e}{pq}$ to be slightly smaller than $\frac{k}{d}$, up to some fraction $\delta$. We know $e$ and $pq$ as they define the public key, but how can we use (3) to determine $\frac{k}{d}$?

In the paper originally describing this attack, Wiener outlines how we can find $\frac{k}{d}$ using continued fractions. A continued fraction takes the form

$$ \frac{m}{n} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_n}}}} $$

The various values $a_i$ are known as the quotients. These can be calculated using an iterative process. We determine the quotient and remainder of $\frac{m}{n}$. The quotient is our $a_i$, and the reciprocal of the remainder becomes our new $\frac{m}{n}$. We repeat this process until the remainder is zero. $\frac{m}{n}$ is approximated by the convergents, $c_i$, of the continued fraction:

$$ c_i = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_i}}}} $$

Wiener's paper explains that, if the value of $d$ is sufficiently small relative to $N$, we can find $\frac{k}{d}$ amongst the convergents of $\frac{e}{pq}$.

Computing the convergents of $\frac{e}{pq}$ gives us some potential values of $\frac{k}{d}$, but we're not quite done yet. To complete the attack, we need a way of determining which of these convergents is indeed $\frac{k}{d}$. From (2), we can determine $\varphi(N)$ given some candidate values for $k$ and $d$. At the same time, we can use the relationship between $\varphi(N)$, $p$ and $q$ to derive a quadratic equation in $p$:

$$ \begin{align} \varphi(N) & = (p - 1)(p - 1) &\\ & = p q - p - q + 1 &\\ & = N - p - \frac{N}{p} + 1 &\\ \end{align} $$

Multiplying both sides by $p$ and collecting terms gives

$$ p^2 + (\varphi(N) - N - 1) p + N = 0 \;.\tag{4} $$

We know $N$, and we have a candidate value for $\varphi(N)$. Plugging these in, we can solve this equation for $p$. If the value of $\varphi(N)$ is correct, we should end up with two roots, $p_1$ and $p_2$, whose product is $N$. (Because $p_1$ and $p_2$ must be integers, it does not automatically hold that $p_1 p_2 = N$.)

Putting it All Together

With an understanding of Wiener's attack in hand, we can try to break the public key we've been provided with the following steps:

  1. Compute the quotients of $\frac{e}{N}$.
  2. Compute the convergents of $\frac{e}{N}$ from the quotients in step 1.
  3. For each convergent in step 3, use the numerator as a candidate for $k$ and the denominator as a candidate for $d$ and compute a candidate for $\varphi(N)$ using equation (2).
  4. Calculate the roots of equation (4) for each candidate $\varphi(N)$. For a given $\varphi(N)$, if the product of these roots is equal to $N$, the candidate $d$ from step 3 will satisfy equation (1).

I coded this up using Go. Unfortunately, Go's standard library doesn't support RSA public keys with large exponents, so I had to cook up a few custom types. Running my code against the provided public key gives the following:

$ cat key.pub | go run main.go

Pasting this into a file, we can use OpenSSL to decrypt the provided flag:

$ cat flag.enc | openssl rsautl -decrypt -inkey key

And that's it! We've recovered the flag.