Baby Time Capsule — HackTheBox

Description

Qubit Enterprises is a new company touting it's propriety method of qubit stabilization. They expect to be able to build a quantum computer that can factor a RSA-1024 number in the next 10 years. As a promotion they are giving out "time capsules" which contain a message for the future encrypted by 1024 bit RSA. They might be great engineers, but they certainly aren't cryptographers, can you find a way to read the message without having to wait for their futuristic machine?

Analysis

In this challenge, we are provided with a service that generates "time capsules". Each capsule contains the flag encrypted using RSA.

Upon analyzing the source code (or interacting with the server), we discover the following:

1. The public exponent $e$ is fixed and very small: $e = 5$.
2. For each new capsule, a new pair of primes $p$ and $q$ is generated, hence a new modulus $n$.
3. The message (flag) remains the same for all capsules.

This is a classic scenario for Håstad's Broadcast Attack.

Solution

Vulnerability

If the same message $m$ is encrypted $e$ times using different moduli $n_1, n_2, \dots, n_e$ and the same small exponent $e$, we get a system of equations: $c_1 \equiv m^e \pmod{n_1}$ $c_2 \equiv m^e \pmod{n_2}$ $\dots$ $c_e \equiv m^e \pmod{n_e}$

Using the Chinese Remainder Theorem (CRT), we can find a value $C$ such that: $C \equiv m^e \pmod{n_1 n_2 \dots n_e}$

Since $m < n_i$ for all $i$, then $m^e < n_1 n_2 \dots n_e$. This means the found value $C$ is exactly equal to $m^e$ in integers. To obtain $m$, we simply need to extract the $e$-th root of $C$.

Solution Script

...