HackTheBox Cyber Apocalypse 2025 — Twin Oracle CTF Writeup

Welcome back to my WriteUp! Today, I’m excited to take you through my journey of solving Twin Oracles, the most challenging cryptography challenge in HackTheBox’s Cyber Apocalypse CTF 2025. I’ll break down my thought process, the techniques I used, and the obstacles I overcame to crack this tough puzzle. Let’s dive in!

Description

A powerful artifact — meant to generate chaos yet uphold order — has revealed its flaw. A misplaced rune, an unintended pattern, an oversight in the design. The one who understands the rhythm of its magic may predict its every move and use it against its creators. Will you be the one to claim its secrets?

Let’s start analyzing the provided file

This is the provided server.py:

from Crypto.Util.number import *

FLAG = bytes_to_long(open('flag.txt', 'rb').read())

MENU = '''
The Seers await your command:

1. Request Knowledge from the Elders
2. Consult the Seers of the Obsidian Tower
3. Depart from the Sanctum
'''

class ChaosRelic:
    def __init__(self):
        self.p = getPrime(8)
        self.q = getPrime(8)
        self.M = self.p * self.q
        self.x0 = getPrime(15)
        self.x = self.x0
        print(f"The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = {self.M}")

    def next_state(self):
        self.x = pow(self.x, 2, self.M)

    def get_bit(self):
        self.next_state()
        return self.extract_bit_from_state()

    def extract_bit_from_state(self):
        return self.x % 2


class ObsidianSeers:
    def __init__(self, relic):
        self.relic = relic
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.n = self.p * self.q
        self.e = 65537
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)

    def sacred_encryption(self, m):
        return pow(m, self.e, self.n)

    def sacred_decryption(self, c):
        return pow(c, self.d, self.n)

    def HighSeerVision(self, c):
        return int(self.sacred_decryption(c) > self.n//2)

    def FateSeerWhisper(self, c):
        return self.sacred_decryption(c) % 2

    def divine_prophecy(self, a_bit, c):
        return self.FateSeerWhisper(c) if a_bit == 0 else self.HighSeerVision(c)

    def consult_seers(self, c):
        next_bit = self.relic.get_bit()
        response = self.divine_prophecy(next_bit, c)
        return response



def main():
    print("You stand before the Seers of the Obsidian Tower. They alone hold the knowledge you seek.")
    print("But be warned—no force in Eldoria can break their will, and their wisdom is safeguarded by the power of the Chaos Relic.")
    my_relic = ChaosRelic()
    my_seers = ObsidianSeers(my_relic)
    counter = 0

    while counter <= 1500:
        print(MENU)
        option = input('> ')

        if option == '1':
            print(f"The Elders grant you insight: n = {my_seers.n}")
            print(f"The ancient script has been sealed: {my_seers.sacred_encryption(FLAG)}")
        elif option == '2':
            ciphertext = int(input("Submit your encrypted scripture for the Seers' judgement: "), 16)
            print(f'The Seers whisper their answer: {my_seers.consult_seers(ciphertext)}')
        elif option == '3':
            print("The doors of the Sanctum close behind you. The Seers watch in silence as you depart.")
            break
        else:
            print("The Seers do not acknowledge your request.")
            continue

        counter += 1

    print("The stars fade, and the Seers retreat into silence. They shall speak no more tonight.")

if __name__ == '__main__':
    main()

Analyzation between the 2 classes

ChaosRelic Class

class ChaosRelic:
    def __init__(self):
        self.p = getPrime(8)
        self.q = getPrime(8)
        self.M = self.p * self.q
        self.x0 = getPrime(15)
        self.x = self.x0
        print(f"The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = {self.M}")

    def next_state(self):
        self.x = pow(self.x, 2, self.M)

    def get_bit(self):
        self.next_state()
        return self.extract_bit_from_state()

    def extract_bit_from_state(self):
        return self.x % 2

The ChaosRelic class functions as a pseudo-random bit generator (PRNG) using a Blum-Blum-Shub (BBS)-like method. It initializes with two randomly chosen 8-bit prime numbers (p and q), computing M = p * q, and selects a 15-bit prime (x0) as the initial state. The generator updates its state iteratively by squaring the previous value modulo M, ensuring a level of unpredictability. The least significant bit (LSB) of x is extracted at each step to produce a sequence of random bits, which are later used to control oracle selection. This method relies on quadratic residues and modular arithmetic, fundamental to cryptographic PRNGs.

ObsidianSeers Class

class ObsidianSeers:
    def __init__(self, relic):
        self.relic = relic
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.n = self.p * self.q
        self.e = 65537
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)

    def sacred_encryption(self, m):
        return pow(m, self.e, self.n)

    def sacred_decryption(self, c):
        return pow(c, self.d, self.n)

    def HighSeerVision(self, c):
        return int(self.sacred_decryption(c) > self.n//2)

    def FateSeerWhisper(self, c):
        return self.sacred_decryption(c) % 2

    def divine_prophecy(self, a_bit, c):
        return self.FateSeerWhisper(c) if a_bit == 0 else self.HighSeerVision(c)

    def consult_seers(self, c):
        next_bit = self.relic.get_bit()
        response = self.divine_prophecy(next_bit, c)
        return response

The ObsidianSeers class implements a 1024-bit RSA encryption system, generating two 512-bit primes (p, q) to compute n = p * q. Using the standard public exponent 65537, it derives the private exponent via modular inversion. Messages are encrypted using the RSA formula c=memod nc = m^e \mod nc=memodn and decrypted with m=cdmod nm = c^d \mod nm=cdmodn. The class also provides two distinct oracle functions. The parity oracle (FateSeerWhisper) reveals whether the decrypted plaintext is even or odd, which can be exploited in an LSB Oracle Attack. The location oracle (HighSeerVision) determines whether the plaintext is in the lower or upper half of [0, n-1], aiding in a binary search attack. These two oracles are combined within the twin_Oracles function, which dynamically selects an oracle based on an input bit—querying the parity oracle when the bit is 0 and the location oracle when the bit is 1.

To add complexity, the Ask_twins function integrates the BBS PRNG, using its output bits to decide which oracle will be queried at each step, making the decryption process non-deterministic. Additionally, to prevent excessive interaction, the challenge imposes a query limit, if the player exceeds 1500 queries, the program automatically terminates.

Solution

What is the vulnerability here??? There’s 2, let me explain.

1. It is well known that RSA becomes vulnerable when a location oracle is available.

2. The security of BBS relies on the difficulty of factoring MM, but in this case, factoring MM is trivial.

How to solve it? Here’s our plan

1. We will factor M.

2. We will determine the cycle length of the BBS generator.

3. We will construct an oracle distinguisher to recover all bits within the BBS cycle.

4. We will design a method to convert the parity oracle into a location oracle.

5. We will apply this conversion strategically, guided by predicted BBS outputs.

6. We will utilize the location oracle to conduct a binary search and uncover the plaintext.

This is the decode script that I’ve made to automate the process and crack this challenge

from Crypto.Util.number import *
import sympy
from math import lcm
from pwn import *

# Remote connection details
HOST = ""
PORT = 
io = remote(HOST, PORT)

# Retrieve the value of M from the server
io.recvuntil(b'power: ')
M = int(io.recvline().decode().split()[-1])
print(f'[+] Value of M: {M}')

# Request public key details
io.sendlineafter(b'> ', b'1')
n = int(io.recvline().decode().split()[-1])  # RSA modulus
print(f'[+] Modulus (n): {n}')
enc_flag = int(io.recvline().decode().split()[-1])  # Encrypted flag
print(f'[+] Encrypted Flag: {enc_flag}')

e = 65537  # Public exponent (standard RSA value)

# Factorize M to extract its prime components
factor_list = [(key, value) for key, value in sympy.factorint(M).items()]
print(f'[+] M Factorized: {factor_list}')

# Compute the Carmichael function λ(M) using the least common multiple of (p-1)
factors_lambda = lcm(*[(fac[0] - 1) for fac in factor_list])
lambda_factors_list = [(key, value) for key, value in sympy.factorint(factors_lambda).items()]
print(f'[+] Carmichael Function: {factors_lambda}')

# Determine the BBS period length (LCM of λ factors)
period = lcm(*[(fac[0] - 1) for fac in lambda_factors_list])
print(f'[+] Period Length: {period}')

# Collect BBS-generated bits for the period length
period_bits = []
for i in range(period):
    io.sendlineafter(b'> ', b'2')
    io.recvuntil(b': ')
    io.sendline(b'1')  # Query the oracle
    response = int(io.recvline().decode().split()[-1])
    period_bits.append(0 if response == 1 else 1)  # Convert response into a bit

# Begin binary search attack on the plaintext
bit_index = 0
curr_ctxt = enc_flag
mul = pow(2, e, n)  # Precompute multiplication factor for RSA homomorphic property
m_space = [1, n - 1]  # Define search space for plaintext

while m_space[1] != m_space[0]:  # Continue until plaintext is fully narrowed down
    next_bit = period_bits[bit_index % len(period_bits)]
    io.sendlineafter(b'> ', b'2')
    io.recvuntil(b': ')
    
    # Choose ciphertext transformation based on BBS prediction
    io.sendline(hex(curr_ctxt * pow(2, e, n) % n)[2:].encode() if next_bit == 0 else hex(curr_ctxt)[2:].encode())
    response = int(io.recvline().decode().split()[-1])

    # Update plaintext search space using binary search logic
    if response:
        m_space[0] = (m_space[1] + m_space[0] + 1) // 2  # Adjust lower bound
    else:
        m_space[1] = (m_space[1] + m_space[0]) // 2  # Adjust upper bound

    # Update ciphertext for next iteration
    curr_ctxt = mul * curr_ctxt % n
    bit_index += 1

# Verify and extract the correct plaintext value
for i in range(-10, 10):  # Check a small range around computed plaintext
    plaintext = m_space[0] + i
    if pow(plaintext, e, n) == enc_flag:
        print(f'[+] Total Attempts: {bit_index + len(period_bits)}')
        print(f'[+] Flag: {long_to_bytes(plaintext).decode()}')
        break

When we run the script, this is the output (Take note that the cracking process takes a lot of time).

As you can see here, the wait is worth it! It gives me the flag!!!

Conclusion

This attack highlights critical vulnerabilities in RSA when combined with a weak PRNG like Blum-Blum-Shub (BBS). By factoring MM, we can determine the BBS period, allowing us to predict its future outputs. With access to both a parity oracle and a location oracle, we can progressively narrow down the possible plaintext values based on the oracle responses. By leveraging this information, we apply a binary search approach, systematically refining the search space until the plaintext is fully recovered. This demonstrates how even minor information leaks in cryptographic implementations can be exploited to completely break encryption. The challenge reinforces the importance of using cryptographically secure PRNGs and ensuring that no unintended information is leaked, as attackers can use even small hints to compromise an otherwise secure system.