Challenge Overview

Challenge Name: Hakari Domain Category: Crypto / Misc Points: 488 Flag Format: hack10{...} Service: nc 34.126.187.50 5500 Provided File: chall.py

The challenge provides a remote guessing game. The player must correctly predict numbers generated by the server. After achieving a streak of 3 correct guesses, the service unlocks “jackpot” mode and starts returning RSA encryption samples of the flag.

The goal is to abuse the predictable random number generator, unlock jackpot mode, collect RSA ciphertexts, and recover the flag.

Initial Analysis

The provided source code shows that the game uses Python’s random.getrandbits(32) to generate the target number:

target = random.getrandbits(32)

If the guess is wrong, the server reveals the generated number:

print(f"Wrong. The number was {target}.")

This is important because Python’s random module uses MT19937, also known as Mersenne Twister.

The jackpot is unlocked after 3 correct guesses in a row:

JACKPOT_STREAK = 3

Once jackpot mode is active, every correct prediction gives an RSA sample:

n, e, c = gen_rsa_sample(message, used_primes)

The RSA exponent is fixed:

E = 17

The plaintext is always the same flag:

message = bytes_to_long(flag)

Each RSA sample uses a different modulus n, but encrypts the same message with the same small exponent e = 17.

Vulnerability / Weakness Identification

There are two main weaknesses.

First, the server leaks raw outputs from Python’s MT19937 PRNG. Since every wrong guess reveals the actual generated number, we can collect enough outputs to reconstruct the PRNG state.

MT19937 requires 624 32-bit outputs to recover its internal state. After collecting 624 leaked numbers, future outputs can be predicted perfectly.

Second, the RSA encryption is vulnerable to Håstad’s broadcast attack. The same plaintext is encrypted multiple times using:

c = m^17 mod n

with different moduli. If enough ciphertexts are collected, Chinese Remainder Theorem can reconstruct m^17 over the integers. Then taking the exact 17th root recovers the original message.

Exploitation Strategy

The attack plan is:

1. Connect to the remote service.

2. Send a fixed wrong guess, such as 0.

3. Collect 624 leaked outputs from:

   Wrong. The number was X.

4. Use randcrack to reconstruct the MT19937 state.

5. Predict the next 3 numbers correctly to unlock jackpot.

6. Continue predicting future numbers to collect RSA samples.

7. Use CRT to combine the ciphertexts.

8. Take the exact 17th root.

9. Convert the recovered integer back into bytes.

10. Print the flag.

Proof of Concept

A normal wrong guess leaks the generated number:

nc 34.126.187.50 5500

Example:

Guess the next number: 123
Wrong. The number was 1234623462.
Attempts used: 1/700

This leak allows PRNG state recovery.

After 624 outputs, the exploit predicts future values:

[+] Recovered MT19937 state
Correct. Current streak: 1
Correct. Current streak: 2
Correct. Current streak: 3
Jackpot unlocked.

Then the server returns RSA samples:

Sample 1
n = ...
e = 17
c = ...

After enough samples are collected, the flag is recovered using Håstad’s broadcast attack.

Full Python Solver

#!/usr/bin/env python3
from pwn import *
from randcrack import RandCrack
from Crypto.Util.number import long_to_bytes
import gmpy2
import re

HOST = "34.126.187.50"
PORT = 5500

context.log_level = "info"

NORMAL_PROMPT = b"Guess the next number: "
JACKPOT_PROMPT = b"Predict the next number or type 'exit': "

rc = RandCrack()
samples = []


def recv_menu(io, jackpot=False):
    """
    Receive server output until the correct prompt appears.
    This avoids stopping early on other ':' characters.
    """
    prompt = JACKPOT_PROMPT if jackpot else NORMAL_PROMPT
    data = io.recvuntil(prompt, drop=False)
    return data.decode(errors="ignore")


def parse_target(text):
    m = re.search(r"Wrong\. The number was (\d+)\.", text)
    return int(m.group(1)) if m else None


def parse_n(text):
    m = re.search(r"n = (\d+)", text)
    return int(m.group(1)) if m else None


def parse_e(text):
    m = re.search(r"e = (\d+)", text)
    return int(m.group(1)) if m else None


def parse_c(text):
    m = re.search(r"c = (\d+)", text)
    return int(m.group(1)) if m else None


def crt(items):
    """
    Chinese Remainder Theorem.

    items format:
        [(c1, n1), (c2, n2), ...]

    Returns:
        x where x ≡ c_i mod n_i
    """
    N = 1
    for _, n in items:
        N *= n

    x = 0

    for c, n in items:
        m = N // n
        inv = pow(m, -1, n)
        x += c * m * inv

    return x % N


def recover_message(rsa_samples, e=17):
    """
    Recover plaintext using Håstad's broadcast attack.
    """
    items = [(c, n) for n, ee, c in rsa_samples if ee == e]

    x = crt(items)

    root, exact = gmpy2.iroot(x, e)

    if not exact:
        raise ValueError("e-th root is not exact yet. Need more RSA samples.")

    return long_to_bytes(int(root))


def main():
    io = remote(HOST, PORT)

    # Read banner and first prompt
    banner = recv_menu(io, jackpot=False)
    print(banner, end="")

    # Phase 1: Collect 624 leaked MT19937 outputs
    for i in range(624):
        io.sendline(b"0")
        block = recv_menu(io, jackpot=False)

        if "Wrong. The number was" in block:
            leaked = parse_target(block)

            if leaked is None:
                raise RuntimeError(f"Failed to parse leaked number:\n{block}")

            rc.submit(leaked)

        elif "Correct. Current streak:" in block:
            # Rare case: target was actually 0
            rc.submit(0)

        else:
            raise RuntimeError(f"Unexpected response:\n{block}")

        if (i + 1) % 50 == 0:
            log.info(f"Collected {i + 1}/624 outputs")

    log.success("Recovered MT19937 state")

    # Phase 2: Predict 3 correct numbers to unlock jackpot
    for i in range(3):
        prediction = rc.predict_getrandbits(32)
        io.sendline(str(prediction).encode())

        if i < 2:
            block = recv_menu(io, jackpot=False)
        else:
            block = recv_menu(io, jackpot=True)

        print(block, end="")

        if "Correct. Current streak:" not in block:
            raise RuntimeError(f"Prediction failed:\n{block}")

    log.success("Jackpot unlocked")

    # Phase 3: Collect RSA samples
    # 10 samples are enough in practice for this challenge.
    for i in range(10):
        prediction = rc.predict_getrandbits(32)
        io.sendline(str(prediction).encode())

        block = recv_menu(io, jackpot=True)
        print(block, end="")

        n = parse_n(block)
        e = parse_e(block)
        c = parse_c(block)

        if n is None or e is None or c is None:
            raise RuntimeError(f"Failed to parse RSA sample:\n{block}")

        samples.append((n, e, c))
        log.success(f"Collected RSA sample {i + 1}")

    io.sendline(b"exit")
    io.close()

    # Phase 4: Try Håstad broadcast attack
    for k in range(3, len(samples) + 1):
        try:
            flag = recover_message(samples[:k], e=17)
            log.success(f"Recovered plaintext using {k} samples")

            print("\n[+] Flag / plaintext:")
            print(flag.decode(errors="replace"))
            return

        except Exception as ex:
            log.warning(f"{k} samples not enough: {ex}")

    raise RuntimeError("Failed to recover plaintext. Try collecting more samples.")


if __name__ == "__main__":
    main()

Walkthrough

Create and activate a Python virtual environment:

python3 -m venv venv
source venv/bin/activate

Install dependencies:

pip install pwntools randcrack gmpy2 pycryptodome

Run the solver:

python solve.py

Expected progress:

[+] Opening connection to 34.126.187.50 on port 5500: Done
[*] Collected 50/624 outputs
[*] Collected 100/624 outputs
...
[*] Collected 600/624 outputs
[+] Recovered MT19937 state
Correct. Current streak: 1
Correct. Current streak: 2
Correct. Current streak: 3
Jackpot unlocked.
[+] Collected RSA sample 1
[+] Collected RSA sample 2
...
[+] Recovered plaintext using 6 samples

If the solver says:

e-th root is not exact yet. Need more RSA samples.

increase this value:

for i in range(10):

to:

for i in range(15):

This gives more RSA samples and increases the chance that the CRT product is large enough.

Flag

The recovered flag is:

hack10{ab3a61603241b0638804acdc5f905cd4}

Conclusion

The challenge is solved by chaining two weaknesses.

The first weakness is the use of Python’s non-cryptographic PRNG, MT19937, for a security-critical prediction game. Since the server leaks the generated number after every wrong guess, the attacker can collect 624 outputs and fully recover the PRNG state.

The second weakness is the repeated RSA encryption of the same plaintext using a small public exponent, e = 17, across different moduli. This allows Håstad’s broadcast attack to recover the plaintext without factoring any RSA modulus.

The key lesson is clear: predictable randomness must never be used for security decisions, and RSA must always use secure padding such as OAEP instead of raw textbook encryption.