Cryptography CTF Walkthroughs | HackTheBox Brevi Moduli Writeup

Introduction

HackTheBox Brevi Moduli is a relatively simple challenge. The player needs to complete five rounds to obtain the flag. In each round, they must provide the prime factors ppp and qqq of a 220-bit RSA modulus. Due to the small size of the modulus, it can be easily factored using common tools like SageMath.

HackTheBox CPTS Study Notes

HackTheBox CDSA Study Notes

HackTheBox Brevi Moduli Description

On a cold Halloween night, five adventurers gathered at the entrance of an ancient crypt. The Cryptkeeper appeared from the shadows, his voice a chilling whisper: “Five locks guard the treasure inside. Crack them, and the crypt is yours.” One by one, they unlocked the crypt’s secrets, but as the final door creaked open, the Cryptkeeper’s eerie laughter filled the air. “Beware, for not all who enter leave unchanged.”

Enumeration

In this challenge, only one file is provided:

server.py: This Python script is executed when we connect to the challenge instance.

To obtain the flag, we must successfully complete 5 rounds. In each round, an RSA public key is given, and the task is to find and submit the prime factors ppp and qqq of the modulus NNN. The public exponent eee is consistently set to the standard value of 65537.

The given source code:

rounds = 5
e = 65537

for i in range(rounds):
    print('*'*10, f'Round {i+1}/{rounds}', '*'*10)

    p = getPrime(110)
    q = getPrime(110)
    n = p * q
    pubkey = RSA.construct((n, e)).exportKey()
    print(f'\nCan you crack this RSA public key?\n{pubkey.decode()}\n')

    assert isPrime(_p := int(input('enter p = '))), exit()
    assert isPrime(_q := int(input('enter q = '))), exit()

    if n != _p * _q:
        print('wrong! bye...')
        exit()

    print()

print(open('flag.txt').read())

---

The Vulnerability

The security of the RSA cryptosystem is entirely based on the difficulty of solving the Integer Factorization Problem. Simply put, this problem can be described as:

Given p=10412581p = 10412581p=10412581 and q=15559549q = 15559549q=15559549, it is straightforward and quick to compute their product:
10412581×15559549=162015064285969=N10412581 \times 15559549 = 162015064285969 = N10412581×15559549=162015064285969=N
However, if only N=162015064285969N = 162015064285969N=162015064285969 is provided, determining the original factors ppp and qqq becomes significantly harder.

For much larger values, factoring becomes practically impossible for modern computers.

In this challenge, each prime number is 110 bits long, resulting in their product NNN being 220 bits. A 220-bit RSA modulus is completely insecure for cryptographic use because modern computers can factor it very quickly. Numerous tools and libraries exist for integer factorization, but in CTF challenges, SageMath is the most commonly used.

Let’s explore an example with some dummy numbers to understand how this works.

# Generate two random prime numbers, each less than 2^110
prime1 = random_prime(2^110)
prime2 = random_prime(2^110)

# Compute their product
product = prime1 * prime2

# Measure the time taken to factor the product
%time factor(product)

# Display the first prime
prime1

# Display the second prime
prime2

prime1 and prime2 are large random prime numbers.

product is the result of multiplying these two primes.

%time measures how long it takes to factor product back into its prime components.

Finally, both primes are printed.

It took only 6.5 seconds for SageMath to factor nnn, making our task straightforward:

1. Connect to the server.
2. Retrieve the RSA modulus at each round.
3. Factor the modulus to find its prime factors ppp and qqq.
4. Send the factors back to the server.

However, the RSA public key is provided in PEM format, so we need to extract the modulus NNN from this format before factoring.

pem_pubkey = RSA.construct((n, e)).exportKey()
print(f'\nCan you crack this RSA public key?\n{pubkey.decode()}\n')

The PEM format:

-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcBEwL/SBkcv+AmVwzDWtY80vQ4ALwjtUt
RgeXuwIDAQAB
-----END PUBLIC KEY-----

One might wonder why RSA public keys are shared in such a complex format like PEM. The reason is that RSA is heavily used in applications like TLS, where consistency in key formatting is crucial to avoid parsing errors. The PEM format is a standardized and widely accepted format for this purpose. Without it, there would be confusion over how to represent key parameters, such as:

• (n=value_of_n,e=value_of_e)(n = \text{value\_of\_n}, e = \text{value\_of\_e})(n=value_of_n,e=value_of_e)
• (n=value_of_n,e=value_of_e)(n=\text{value\_of\_n}, e=\text{value\_of\_e})(n=value_of_n,e=value_of_e)
• [n=value_of_n,e=value_of_e][n=\text{value\_of\_n}, e=\text{value\_of\_e}][n=value_of_n,e=value_of_e]

…and so on.

To extract the actual RSA parameters from a PEM-formatted key, we use the inverse of exportKey, which is importKey. This allows us to parse the PEM key correctly and retrieve the modulus NNN and the public exponent eee.

>>> from Crypto.PublicKey import RSA
>>> n = 452533018482816403250499886919603981486991592917670642633077659579
>>> e = 65537
>>> pem_pubkey = RSA.construct((n, e)).exportKey()
>>> pem_pubkey
b'-----BEGIN PUBLIC KEY-----\nMDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcBEwL/SBkcv+AmVwzDWtY80vQ4ALwjtUt\nRgeXuwIDAQAB\n-----END PUBLIC KEY-----'
>>> key = RSA.importKey(pem_pubkey)
>>> key
RsaKey(n=452533018482816403250499886919603981486991592917670642633077659579, e=65537)

We can now proceed to create a function that extracts and factors the five moduli.

Exploit Code

from pwn import *
from Crypto.PublicKey import RSA
from sage.all import *

def retrieve_flag():
    exponent = 65537  # Common RSA public exponent
    for _ in range(5):
        io.recvuntil(b'key?\n')
        public_key_data = io.recvuntil(b'-----END PUBLIC KEY-----\n')
        rsa_key = RSA.importKey(public_key_data)
        modulus, exponent = rsa_key.n, rsa_key.e

        # Factor the modulus into its prime factors p and q
        prime_factors = list(factor(modulus))
        p, q = prime_factors[0], prime_factors[1]

        io.sendlineafter(b'p = ', str(p).encode())
        io.sendlineafter(b'q = ', str(q).encode())
        io.recvline()

    # Receive and return the flag
    flag = io.recvline().strip().decode()
    return flag

---

The given RSA public keys are intentionally small, making them easy to factor using SageMath.
For each round, extract the public key, factor it, and return the prime factors.
Repeat this process five times to obtain the flag.

This process can be implemented in the pwn() function.

def exploit():
    flag = retrieve_flag()
    print(flag)

if __name__ == '__main__':
    if args.REMOTE:
        host, port = sys.argv[1].split(':')
        io = remote(host, port, level='error')
    else:
        import os
        os.chdir('../challenge')
        io = process(['python3', 'server.py'], level='error')

    exploit()

You can also watch: