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

from pwn import *
from Crypto.Util.number import long_to_bytes
import gmpy2
import json

def crt(remainders, moduli):
    from functools import reduce
    def mul_inv(a, b):
        b0 = b
        x0, x1 = 0, 1
        if b == 1: return 1
        while a > 1:
            q = a // b
            a, b = b, a % b
            x0, x1 = x1 - q * x0, x0
        if x1 < 0: x1 += b0
        return x1

    total = reduce(lambda x, y: x * y, moduli)
    result = 0
    for r_i, n_i in zip(remainders, moduli):
        p = total // n_i
        result += r_i * mul_inv(p, n_i) * p
    return result % total

def solve():
    host = '94.237.120.74'
    port = 34096
    
    cs = []
    ns = []
    e = 5
    
    r = remote(host, port)
    
    for i in range(e):
        r.sendlineafter(b'(Y/n) ', b'Y')
        data = r.recvuntil(b'}')
        res = json.loads(data.decode())
        ns.append(int(res['n'], 16))
        cs.append(int(res['c'], 16))
        print(f"Collected {i+1}/{e}")

    r.close()
    
    m_e = crt(cs, ns)
    m, exact = gmpy2.iroot(m_e, e)
    if exact:
        print(f"Flag: {long_to_bytes(m).decode()}")
    else:
        print("Failed to find exact root")

if __name__ == "__main__":
    solve()

Key Indicators

Use this technique when:

• Small public exponent $e$ (usually 3, 5, or 7).
• Ability to obtain $e$ or more different ciphertexts of the same message with different moduli $n$.