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
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: 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
We know that
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 FateSeerWhisper
returns True
(a_bit
is 0
) and HighSeerVision
returns False
(a_bit
is 1
). We could’ve also sent 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
First of all, we take
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
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 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
MSB oracle
This oracle tells us whether
Therefore, if we query for
Next, we query for
Then, we query
As a result, we can use binary search by querying for
LSB oracle
Similarly, this oracle returns the last bit of the
If we query for
If we query for False
), but if True
). If we rewrite the equations, we have:
False
, then, which is equivalent to being true, so that is false True
, thenand , which is equivalent to being true
Do you see it? It is exactly the same oracle as the MSB one, but starting from
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 94.237.60.131:56566
[+] Opening connection to 94.237.60.131 on port 56566: Done
[◤] Queries: 1038 / 1500
[*] x0 = 24691
The Ancient Chaos Relic fuels the Seers' wisdom. Behold its power: M = 51067
[+] Flag: b'HTB{1_l0v3_us1ng_RS4_0r4cl3s___3v3n_4_s1ngl3_b1t_1s_3n0ugh_t0_g3t_m3_t0_3ld0r14!_d840b436853390615bbadb6e8fbf76cf\x11'
[+] Flag: HTB{1_l0v3_us1ng_RS4_0r4cl3s___3v3n_4_s1ngl3_b1t_1s_3n0ugh_t0_g3t_m3_t0_3ld0r14!_d840b436853390615bbadb6e8fbf76cf}
[*] Closed connection to 94.237.60.131 port 56566
The full script can be found in here: solve.py
.