Twin Oracles
10 minutos de lectura
Se nos proporciona el código fuente del servidor en Python que cifra la 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()
Análisis del código fuente
El servidor ofrece dos opciones:
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
'''
Sin embargo, tenemos un límite de 1500 consultas al servidor:
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
La primera opción simplemente cifra la flag y devuelve el texto cifrado. Usa un RSA básico con
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)
Por otro lado, en la opción 2 se nos da una salida de entre dos valores posibles, dependiendo de un 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
Las dos posibles respuestas usan sacred_decryption
sobre el mensaje dado, que representa un descifrado RSA básico: FateSeerWhisper
) o bien el bit más significativo (HighSeerVision
). Por lo tanto, teóricamente, no es posible saber si el bit que obtenemos es LSB o MSB.
Este bit que decide si se devuelve LSB o MSB proviene de 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
Este bit es el LSB del estado x
. Este estado se inicializa como un número primo
Sabemos que
Solución
Básicamente estamos tratando con un oráculo de descifrado LSB/MSB en RSA. Podemos obtener la flag cifrada, así que la idea es usar este valor para consultar al oráculo con algunas modificaciones para extraer información sobre la flag en texto claro.
Sin embargo, necesitamos saber si la salida que obtenemos es el LSB o el MSB. Por lo tanto, debemos encontrar una forma de saber si a_bit
es 0
ó 1
.
Para esto, podemos enviar 1
a la opción 2, de modo que FateSeerWhisper
devuelve True
(a_bit
es 0
) y HighSeerVision
devuelve False
(a_bit
es 1
). También podríamos haber enviado FateSeerWhisper
devuelve False
(a_bit
es 0
) y HighSeerVision
devuelve True
(a_bit
es 1
). Usaremos la primera opción, pero ambas son válidas.
Una vez que sepamos el valor de a_bit
en cada consulta, el objetivo es encontrar
Primero, tomamos
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')
Usaremos la siguiente función auxiliar para usar la opción 2 como un oráculo:
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())
La idea es tomar todos los números primos de 15 bits posibles y probarlos como si fueran el valor inicial
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 = }')
Una vez que sepamos la semilla, podemos predecir la función que se usará para el resultado, ya sea FateSeerWhisper
(LSB) o HighSeerVision
(MSB), para poder planear los siguientes pasos. Pero primero, usemos la misma implementación y avancemos el estado hasta el punto actual:
my_relic = ChaosRelic()
my_relic.M = M
my_relic.x = x0
for r in results:
assert r == my_relic.get_bit()
Dado que 0
o 1
), necesitaremos usar ambos oráculos para la solución porque uno solo no será suficiente para obtener la flag completa.
Antes de analizar los oráculos, debemos dar algo de contexto sobre cómo funcionan. La cuestión es que podemos realizar cálculos sobre datos cifrados (maleabilidad de RSA), ya que
Por lo tanto, si multiplicamos el texto cifrado
Oráculo MSB
Este oráculo nos dice si
Por lo tanto, si consultamos con
Luego, consultamos con
Después, consultamos con
Como resultado, podemos usar búsqueda binaria consultando con
Oráculo LSB
De manera similar, este oráculo devuelve el último bit de
Si consultamos con
Si consultamos con False
), pero si True
). Si reescribimos las ecuaciones, tenemos:
False
, entonces, lo cual es equivalente a que sea verdadero, por lo que es falso True
, entoncesy , lo cual es equivalente a que sea verdadero
¿Lo ves? Es exactamente el mismo oráculo que el MSB, pero comenzando desde
Implementación
Como resultado, podemos hacer búsqueda binaria para consultar al oráculo dependiendo de la función que se vaya a usar (prediciendo el bit aleatorio) y actualizar los intervalos en consecuencia:
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)))
Necesitamos ajustar la flag debido a algunos matices que realmente no sé cómo explicar. Pero como tenemos un intervalo corto de valores posibles para la flag, podemos simplemente probar desde el límite inferior hasta obtener la misma flag cifrada:
while c != pow(lb, e, n):
lb += 1
io.success(f'Flag: {long_to_bytes(lb).decode()}')
Con esto, podemos obtener la flag en local:
$ 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
Y también funciona en remoto (aunque puede tardar aproximadamente un minuto):
$ 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
El script completo se puede encontrar aquí: solve.py
.