Post

HackTheBox Challenge Baby Time Capsule (Crypto)

Writeup for HackTheBox Challenge Baby Time Capsule

Posted Updated
By Edwin Tok
6 min read
HackTheBox Challenge Baby Time Capsule (Crypto)

Challenge Synopsis

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? (Source)

Enumeration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

❯ cat server.py
from Crypto.Util.number import bytes_to_long, getPrime
import socketserver
import json

FLAG = b'HTB{--REDACTED--}'


class TimeCapsule():

    def __init__(self, msg):
        self.msg = msg
        self.bit_size = 1024
        self.e = 5

    def _get_new_pubkey(self):
        while True:
            p = getPrime(self.bit_size // 2)
            q = getPrime(self.bit_size // 2)
            n = p * q
            phi = (p - 1) * (q - 1)
            try:
                pow(self.e, -1, phi)
                break
            except ValueError:
                pass

        return n, self.e

    def get_new_time_capsule(self):
        n, e = self._get_new_pubkey()
        m = bytes_to_long(self.msg)
        m = pow(m, e, n)

        return {"time_capsule": f"{m:X}", "pubkey": [f"{n:X}", f"{e:X}"]}


def challenge(req):
    time_capsule = TimeCapsule(FLAG)
    while True:
        try:
            req.sendall(
                b'Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) '
            )
            msg = req.recv(4096).decode().strip().upper()
            if msg == 'Y' or msg == 'YES':
                capsule = time_capsule.get_new_time_capsule()
                req.sendall(json.dumps(capsule).encode() + b'\n')
            elif msg == 'N' or msg == "NO":
                req.sendall(b'Thank you, take care\n')
                break
            else:
                req.sendall(b'I\'m sorry I don\'t understand\n')
        except:
            # Socket closed, bail
            return


class MyTCPRequestHandler(socketserver.BaseRequestHandler):

    def handle(self):
        req = self.request
        challenge(req)


class ThreadingTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


def main():
    socketserver.TCPServer.allow_reuse_address = True
    server = ThreadingTCPServer(("0.0.0.0", 1337), MyTCPRequestHandler)
    server.serve_forever()


if __name__ == '__main__':
    main()

1
2
3
4
5

❯ nc 83.136.250.212 32847
Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) y
{"time_capsule": "AC1FFB2814638ADBEF3B663B5C60BC2E1B14914A960BC58B8FBFD45B9C524945BE4B00197559B531DC65D9D232E88D1AB33A9858E8F2AA64A8E5ECAE1109D2D48E62C01F714806246C3219ED60B46AEC3F9749044B9189B294DF45E5ED1B439BA80121F455EA3CBB09BC5A1931C4D145BEFA8EF310740232E16EBB9F88F3939F", "pubkey": ["D4349F5588880D15CAA5D3B66357CDD42E21E0ED2674689DBA77AC37896DF2E5ACE2B90248702A5196CD836D7F27DC0B486E85057DF9982AF70CDAE4B61B0B612DF530E13FEDF3493621B410D64C368C44F935AF4AD4D99D35953AA14E8F3E28E36C2DB145F5D045B6F1BAFA3FA5DB50181AEC1E90731DD6B51257232C9D1379", "5"]}
Welcome to Qubit Enterprises. Would you like your own time capsule? (Y/n) n
Thank you, take care

The vulnerability in this challenge lies in the repeated use of the same exponent e = 5 with different modulus n. This allows for a broadcast attack (or “Hastad’s Broadcast Attack”) if we collect enough ciphertexts for the same plaintext (the FLAG in this case).

Here’s how the attack works:

  1. When the same plaintext is encrypted using the same e but with different moduli (n_1, n_2, … , n_k), the ciphertexts c_i will be: \(c_i = m^e mod  n_i\)

  2. By collecting enough c_i such that k ≥ e (in this case, e = 5), you can use the Chinese Remainder Theorem (CRT) to solve for \(m^e mod  (n_1 ⋅ n_2 ⋅ … ⋅ n_k)\)

  3. Once m^e^ is determined, take the e-th root to recover m, which is the FLAG.

Exploitation

Steps to Solve

  1. Collect at least 5 ciphertexts with their corresponding public keys (n).
  2. Use CRT to combine the equations and recover m^e^.
  3. Compute the e-th root of m^e^ to get m, which can be converted back to bytes to reveal the FLAG.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

import json
import socket
from sympy import Integer
from sympy.ntheory.residue_ntheory import crt
from gmpy2 import iroot

# Server connection details
HOST = "83.136.250.212"
PORT = 32847

def get_time_capsule():
    """Connect to the server and fetch a new time capsule."""
    with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
        s.connect((HOST, PORT))
        print("[*] Connected to server. Requesting time capsule...")
        s.recv(4096)  # Welcome message
        s.sendall(b"y\n")
        response = s.recv(4096).decode()
        capsule = json.loads(response)
        c = int(capsule["time_capsule"], 16)
        n = int(capsule["pubkey"][0], 16)
        e = int(capsule["pubkey"][1], 16)
        print(f"[+] Received data: ciphertext (c)={hex(c)}, modulus (n)={hex(n)}, exponent (e)={e}")
        return c, n, e

def recover_message(ciphertexts, moduli, e):
    """Recover the plaintext using CRT and root extraction."""
    print("[*] Combining ciphertexts using Chinese Remainder Theorem (CRT)...")
    combined_c, combined_n = crt(moduli, ciphertexts)
    print(f"[+] Combined value (m^e): {combined_c}")
    
    print(f"[*] Extracting the {e}-th root to recover the original message...")
    root, exact = iroot(combined_c, e)
    if not exact:
        raise ValueError("Failed to compute the exact root. The data might be incomplete or incorrect.")
    print("[+] Successfully recovered the original message!")
    return Integer(root)

def main():
    # Fixed parameters
    e = 5  # Public exponent
    num_samples = 5  # Number of ciphertexts to collect

    # Containers for ciphertexts and moduli
    ciphertexts = []
    moduli = []

    print("[*] Starting data collection from the server...")
    for i in range(num_samples):
        print(f"[*] Requesting time capsule {i + 1}/{num_samples}...")
        c, n, e_server = get_time_capsule()
        assert e_server == e, "Public exponent mismatch detected!"
        ciphertexts.append(c)
        moduli.append(n)

    print("[*] Data collection complete.")
    print("[*] Ciphertexts and moduli received:")
    for i, (c, n) in enumerate(zip(ciphertexts, moduli)):
        print(f"  - Time Capsule {i + 1}: c={hex(c)}, n={hex(n)}")

    print("[*] Recovering the message...")
    m = recover_message(ciphertexts, moduli, e)

    # Convert the recovered number to bytes and decode as a string
    flag = bytes.fromhex(hex(m)[2:]).decode()
    print(f"[+] Recovered FLAG: {flag}")

if __name__ == "__main__":
    main()


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

❯ python3 solve.py
[*] Starting data collection from the server...
[*] Requesting time capsule 1/5...
[*] Connected to server. Requesting time capsule...
[+] Received data: ciphertext (c)=0x1a9f9adb759a6e07e780ef91cf85a976f1faff493fb3daf88c724ed9cacab99d93ad74a4cbba4907af099930b875c04915fe182562188b569eb4e74573cdc39063fe9edee19e6c58e43e612be8b09d5d4294a5a83827d2769a0abf95a6ff45f5cabdbca3872c450adc5360bea5c7794f64dfc0e0f5b72970dffbf328798eb779, modulus (n)=0x7506bc266464a6ee734d0397f1b22058214d349f263722b47e6686b739c091c24a1cbf3fce249ae1152317243a18f78437d05cd2df6083af0092535a66790903cef529611994936b2195c873877959c871aa5203ddba23bda3f1747d572eed83b0e41984fcb121b3ff748106da6da9f8dc4c4c2063a56f265cd018d06a0ef135, exponent (e)=5
[*] Requesting time capsule 2/5...
[*] Connected to server. Requesting time capsule...
[+] Received data: ciphertext (c)=0x98a0cadf43443ca5d3cc35d6a6dd32b12900d1213532b139450187df5834c2cd1757ffa8c63c619db6bd60c80a5d3586242dd15ad8c3f0f4f76e61666d63b5505f84a2a941d4fd275ca0364c9b9520f26e463806b5ea862d9701fc413a96c7ee49de263f0a6e803f455b918ec1c6290ae90e5e22dee5bbf6c7a706704674b705, modulus (n)=0x9ab3a67cf2d34bc66dc26ad04ccdd88fd4fee289edd637c9021d71600db23fdc368d4ab412ed54ef7d5232b3a61377730d367e9017a7103f884b8924a6a57a6a4c082051d79f0828b85c06a365f62cd2c4de9fb73ae91f68a70d9e624f7c8ab79e0392746e93ff442cfea6146d15fdc351c1db560d54a80eebf3bb2cd2fefecb, exponent (e)=5
[*] Requesting time capsule 3/5...
[*] Connected to server. Requesting time capsule...
[+] Received data: ciphertext (c)=0x621f7ab63f367cafccae65c4a8556c4765a2e9828faa08bd3550bd671ecd514bfbebd2ba6e1a812a04771de2da5610bf002c27ea32e6d9b8351ca2eb97d41822136e40b729ab3e1aebd88857b2aba9fda5dabdb7d5a30b5eefa28085531d6b853d30c9875c45c56abf794d9779d0794e9c8e1f2d1624efdda82a2cfe32ea4d80, modulus (n)=0xad3c40965abbc454e31a2f6a80d41737fe45d07c4e82de79ca95ddc93385b89f2b9f69194af62e8d607024cc4985832c47e0b784b9bf6cf4b088193d692bf741012ab2860acbffa488c8bbdeea2abbd63db2ebaebfc1099e21e3e12008c2e95d8b1799606407448383f87f01e31e328d2875af5ae20f9fd84391d4e41f020f61, exponent (e)=5
[*] Requesting time capsule 4/5...
[*] Connected to server. Requesting time capsule...
[+] Received data: ciphertext (c)=0x82c4038f5ba7bee71074ccdce778daeda9dd2f7f5024fd4fa769edea756e1f56e9dc10da53b8fc43b0b663cb5e54b663f5383f9c9ecfa587ad24f0f5db6e593afae1fd55deca438cd9942896788c4c110d7f8ca5ea99cd27bd8a0234f5a377e51564e5854effe25a5edba67a5411a608826cf95f0fb5ada467cbcdc2820e06ac, modulus (n)=0xb3726dd7c8cee065a6287d16d53533e1bb560a4e31ee7be643bdfbabc62dfa1bb10ec1f025537fc03123504a62ce1f04d8df4f842bf0efb8aeb1fbdc3daa944de4fbf9f8b9630d64f8e154f4a72b92a3aae2c76ca246c5c50ca91afb483aab32d1800d4c502bc63aad1abb7178c1685f344d0c87a28f758cdf65a3c2cde74491, exponent (e)=5
[*] Requesting time capsule 5/5...
[*] Connected to server. Requesting time capsule...
[+] Received data: ciphertext (c)=0x16c7abfce39aefbe88cfbc959905615aa24a780393b4f24419e4215d310fcb146faa59cfbcd5c63ee59325b13aaf8aadedc49072007d83593651bf6d76bff13eece2dffa0dbff60405ab3ca113114e87676df9656b70bbfb161783a912725cfddd04b747afc22b86de274fa95ee2622d30f2e83f083ad0d462c2bfbd8ee107cc, modulus (n)=0x834df7723f73ee9e6d40a74d920141f09b6513266c2b74f8bb5dea2332f16aba8f1285501c410fd2dc48f63c61a1a1f50dde007cdb44a9c8d2669b28e28a2a24aae4a777f0b863ea8a7f31750eab36096148da28d3cca4fe323e9f131ea7e853d593733f584841a7ffc26cedf541ca67442edaae3abc327f45f25e78ef17636b, exponent (e)=5
[*] Data collection complete.
[*] Ciphertexts and moduli received:
  - Time Capsule 1: c=0x1a9f9adb759a6e07e780ef91cf85a976f1faff493fb3daf88c724ed9cacab99d93ad74a4cbba4907af099930b875c04915fe182562188b569eb4e74573cdc39063fe9edee19e6c58e43e612be8b09d5d4294a5a83827d2769a0abf95a6ff45f5cabdbca3872c450adc5360bea5c7794f64dfc0e0f5b72970dffbf328798eb779, n=0x7506bc266464a6ee734d0397f1b22058214d349f263722b47e6686b739c091c24a1cbf3fce249ae1152317243a18f78437d05cd2df6083af0092535a66790903cef529611994936b2195c873877959c871aa5203ddba23bda3f1747d572eed83b0e41984fcb121b3ff748106da6da9f8dc4c4c2063a56f265cd018d06a0ef135
  - Time Capsule 2: c=0x98a0cadf43443ca5d3cc35d6a6dd32b12900d1213532b139450187df5834c2cd1757ffa8c63c619db6bd60c80a5d3586242dd15ad8c3f0f4f76e61666d63b5505f84a2a941d4fd275ca0364c9b9520f26e463806b5ea862d9701fc413a96c7ee49de263f0a6e803f455b918ec1c6290ae90e5e22dee5bbf6c7a706704674b705, n=0x9ab3a67cf2d34bc66dc26ad04ccdd88fd4fee289edd637c9021d71600db23fdc368d4ab412ed54ef7d5232b3a61377730d367e9017a7103f884b8924a6a57a6a4c082051d79f0828b85c06a365f62cd2c4de9fb73ae91f68a70d9e624f7c8ab79e0392746e93ff442cfea6146d15fdc351c1db560d54a80eebf3bb2cd2fefecb
  - Time Capsule 3: c=0x621f7ab63f367cafccae65c4a8556c4765a2e9828faa08bd3550bd671ecd514bfbebd2ba6e1a812a04771de2da5610bf002c27ea32e6d9b8351ca2eb97d41822136e40b729ab3e1aebd88857b2aba9fda5dabdb7d5a30b5eefa28085531d6b853d30c9875c45c56abf794d9779d0794e9c8e1f2d1624efdda82a2cfe32ea4d80, n=0xad3c40965abbc454e31a2f6a80d41737fe45d07c4e82de79ca95ddc93385b89f2b9f69194af62e8d607024cc4985832c47e0b784b9bf6cf4b088193d692bf741012ab2860acbffa488c8bbdeea2abbd63db2ebaebfc1099e21e3e12008c2e95d8b1799606407448383f87f01e31e328d2875af5ae20f9fd84391d4e41f020f61
  - Time Capsule 4: c=0x82c4038f5ba7bee71074ccdce778daeda9dd2f7f5024fd4fa769edea756e1f56e9dc10da53b8fc43b0b663cb5e54b663f5383f9c9ecfa587ad24f0f5db6e593afae1fd55deca438cd9942896788c4c110d7f8ca5ea99cd27bd8a0234f5a377e51564e5854effe25a5edba67a5411a608826cf95f0fb5ada467cbcdc2820e06ac, n=0xb3726dd7c8cee065a6287d16d53533e1bb560a4e31ee7be643bdfbabc62dfa1bb10ec1f025537fc03123504a62ce1f04d8df4f842bf0efb8aeb1fbdc3daa944de4fbf9f8b9630d64f8e154f4a72b92a3aae2c76ca246c5c50ca91afb483aab32d1800d4c502bc63aad1abb7178c1685f344d0c87a28f758cdf65a3c2cde74491
  - Time Capsule 5: c=0x16c7abfce39aefbe88cfbc959905615aa24a780393b4f24419e4215d310fcb146faa59cfbcd5c63ee59325b13aaf8aadedc49072007d83593651bf6d76bff13eece2dffa0dbff60405ab3ca113114e87676df9656b70bbfb161783a912725cfddd04b747afc22b86de274fa95ee2622d30f2e83f083ad0d462c2bfbd8ee107cc, n=0x834df7723f73ee9e6d40a74d920141f09b6513266c2b74f8bb5dea2332f16aba8f1285501c410fd2dc48f63c61a1a1f50dde007cdb44a9c8d2669b28e28a2a24aae4a777f0b863ea8a7f31750eab36096148da28d3cca4fe323e9f131ea7e853d593733f584841a7ffc26cedf541ca67442edaae3abc327f45f25e78ef17636b
[*] Recovering the message...
[*] Combining ciphertexts using Chinese Remainder Theorem (CRT)...
[+] Combined value (m^e): 302104571691219451000547227647557197445855114125921744047262527923520276152187471184832966608014451919142617860953230086917533522168064133137355753548962355447867442282906584458323915936137277507596293058392465365126790592874265661864579154941893845277455975439713980644628329104500897037217924047311695616563557449472670150603945836587107685344612354640130555992181295641626423601935816567492817060685162067844909767041552282405733189486468937545640856429651254664439803449355087566843968669235944005176224217529002030875479755108669584074186941282720628825725257969464166847058895324524666933811896184330396612204823938088064816976936712195178125
[*] Extracting the 5-th root to recover the original message...
[+] Successfully recovered the original message!
[+] Recovered FLAG: HTB{t3h_FuTUr3_15_bR1ghT_1_H0p3_y0uR3_W34r1nG_5h4d35!}

Flag: HTB{t3h_FuTUr3_15_bR1ghT_1_H0p3_y0uR3_W34r1nG_5h4d35!}

HackTheBox Challenge
challenge ctf crypto
This post is licensed under CC BY 4.0 by the author.