Twin Oracles

10 minutes to read

We are given the Python source code of the server that encrypts the flag:

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

Source code analysis

The server offers two options:

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
'''

However, we have a limit of 1500 queries to the server:

    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

The first option simply encrypts the flag and returns the ciphertext. It uses a textbook RSA with where and are 512-bit prime numbers, so :

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)

On the other hand, in option 2 we are given an output out of two possible values, depending on a bit:

    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 two possible answers use sacred_decryption on the given message, which stands for textbook RSA decryption: . However, the output is either the least significant bit (FateSeerWhisper) or the most significant bit (HighSeerVision). Therefore, theoretically, it is not possible to tell if the output bit we get is LSB or MSB.

This bit that decides whether to output LSB or MSB comes from get_bit:

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

This bit is the LSB of the state x. This state is initialized as a 15-bit prime number an updated as follows:

We know that , where these and are 8-bit prime numbers (different from the RSA primes from before). Although we are not given the initial state , we are given instead.

Solution

We are basically dealing with an LSB/MSB decryption oracle in RSA. We can get the encrypted flag, so the idea is to use this value to query the oracle with some modifications to extract information about the plaintext flag.

However, we need to know whether the output we get is the LSB or the MSB. Therefore, we need to find a way to tell if a_bit is 0 or 1.

For this, we can send 1 to option 2, so that , which means that FateSeerWhisper returns True (a_bit is 0) and HighSeerVision returns False (a_bit is 1). We could’ve also sent since , so analogously, FateSeerWhisper returns False (a_bit is 0) and HighSeerVision returns True (a_bit is 1). We will use the first option, but both are valid.

Once we know the value of a_bit on each query, the objective is to find out so that we can predict future outputs. There are probably better ways to solve this, but I used the following, which is kind of straight-forward and easy to understand.

First of all, we take and also the encrypted flag and the RSA public key:

io = get_process()

io.recvuntil(b"The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = ")
M = int(io.recvline().decode())

io.sendlineafter(b'> ', b'1')
io.recvuntil(b'The Elders grant you insight: n = ')
n = int(io.recvline().decode())
io.recvuntil(b'The ancient script has been sealed: ')
c = int(io.recvline().decode())

results = []
queries = 0

queries_prog = io.progress('Queries')

We will use the following helper function to use option 2 as an oracle:

def query(x: int) -> int:
    io.sendlineafter(b'> ', b'2')
    io.sendlineafter(b"Submit your encrypted scripture for the Seers' judgement: ", hex(x).encode())
    io.recvuntil(b'The Seers whisper their answer: ')
    return int(io.recvline().decode())

The idea is to take all possible 15-bit prime numbers and test all of them as if they were the initial value . We will remove those prime numbers that get a mismatch with the output returned by the server until there is only one remaining:

primes_15 = {x for x in range(2 ** 14, 2 ** 15) if isPrime(x)}

while len(primes_15) != 1:
    queries += 1
    queries_prog.status(f'{queries} / 1500')
    res = 1 - query(1)

    for t in list(primes_15):
        if res != pow(t, 2 ** queries, M) % 2:
            primes_15.remove(t)

    results.append(res)


x0 = list(primes_15)[0]
io.info(f'{x0 = }')

Once we know the seed, we can predict the function that will be used for the result, either FateSeerWhisper (LSB) or HighSeerVision (MSB), so we can plan the next steps. But first, let’s use the same implementation and advance the state to the current point:

my_relic = ChaosRelic()
my_relic.M = M
my_relic.x = x0

for r in results:
    assert r == my_relic.get_bit()

Given the fact that is a 1024-bit number, that we are allowed to query the server up to 1500 times, and that the information we can get from the server is binary (either 0 or 1), we will need to use both oracles for the solution because one of them alone will not be enough to get the full flag.

Before analyzing the oracles, we must give some background on how they work. The thing is that we can perform computations on encrypted data (RSA malleability), since

Therefore, if we multiply the ciphertext by and send it to the server, it will be decrypted to .

MSB oracle

This oracle tells us whether is greater than or not. The idea is to start with an interval , because we know that the flag lies inside, and then query the oracle to update the interval limits, narrowing down the possible values of the flag until we get it.

Therefore, if we query for , we will get the value of . It is very likely that this is false, so we can update .

Next, we query for and we will get , which is equivalent to . Therefore, in case this is false, we update the interval to , whereas in case this is true, it is updated to .

Then, we query to get , or equivalently , and update the interval accordingly.

As a result, we can use binary search by querying for , and getting the result of , which is equivalent to , and update the interval accordingly.

LSB oracle

Similarly, this oracle returns the last bit of the in binary (or equivalently, tells whether the decrypted integer is even or odd).

If we query for , we will get the value of , but this doesn’t give any information.

If we query for , we will get the value of . This is more insightful, because if , then the result is always even (False), but if , then , which is an even number minus an odd number, which is odd (True). If we rewrite the equations, we have:

False, then , which is equivalent to being true, so that is false
True, then and , which is equivalent to being true

Do you see it? It is exactly the same oracle as the MSB one, but starting from instead of .

Implementation

As a result, we can do binary search to query the oracle depending on the function that’s going to be used (predicting the random bit) and update the intervals accordingly:

lb, ub = 0, n

e = 65537
b = 1

flag_prog = io.progress('Flag')

while lb < ub:
    queries += 1
    flag_prog.status(str(long_to_bytes(lb)))
    queries_prog.status(f'{queries} / 1500')
    bit = my_relic.get_bit()

    if bit == 0:
        x = (pow(2 ** b, e, n) * c) % n
    else:
        x = (pow(2 ** (b - 1), e, n) * c) % n

    if query(x) == 0:
        ub = (ub + lb) // 2
    else:
        lb = (ub + lb) // 2

    b += 1

flag_prog.success(str(long_to_bytes(lb)))

We need to adjust the flag because of some nuances I don’t really know how to explain. But since we have a short interval of possible values of the flag, we can just test from the lower bound until we get the expected encrypted flag:

while c != pow(lb, e, n):
    lb += 1

io.success(f'Flag: {long_to_bytes(lb).decode()}')

With this, we can get the flag locally:

$ python3 solve.py
[+] Starting local process 'python3': pid 28794
[◤] Queries: 1038 / 1500
[*] x0 = 25667
The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = 45173
[+] Flag: b'HTB{f4k3_fl4g_f0r_t3st1ng|\xf0'
[+] Flag: HTB{f4k3_fl4g_f0r_t3st1ng}
[*] Stopped process '/opt/homebrew/bin/python3' (pid 28794)

Flag

And it also works remotely (although it might take about one minute):

$ python3 solve.py 83.136.249.246:43938
[+] Opening connection to 83.136.249.246 on port 43938: Done
[.] Queries: 1037 / 1500
[*] x0 = 32117
The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = 39913
[+] Flag: b'HTB{1_l0v3_us1ng_RS4_0r4cl3s___3v3n_4_s1ngl3_b1t_1s_3n0ugh_t0_g3t_m3_t0_3ld0r14!4'
[+] Flag: HTB{1_l0v3_us1ng_RS4_0r4cl3s___3v3n_4_s1ngl3_b1t_1s_3n0ugh_t0_g3t_m3_t0_3ld0r14!}
[*] Closed connection to 83.136.249.246 port 43938

The full script can be found in here: solve.py.