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 donde y son números primos de 512 bits, por lo que :

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: . Sin embargo, la salida es o bien el bit menos significativo (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 de 15 bits y se actualiza de la siguiente forma:

Sabemos que , donde estos y son números primos de 8 bits (distintos de los primos RSA anteriores). Aunque no se nos da el estado inicial , se nos da en su lugar.

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 , lo cual significa que FateSeerWhisper devuelve True (a_bit es 0) y HighSeerVision devuelve False (a_bit es 1). También podríamos haber enviado ya que , así que análogamente, 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 para poder predecir las salidas futuras. Probablemente hay mejores formas de resolver esto, pero usé la siguiente, que es bastante directa y fácil de entender.

Primero, tomamos y también la flag cifrado y la clave pública RSA:

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 . Eliminaremos aquellos números primos que tengan un resultado diferente al devuelto por el servidor hasta que quede solo uno:

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 es un número de 1024 bits, que se nos permite consultar al servidor hasta 1500 veces, y que la información que podemos obtener del servidor es binaria (ya sea 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 por y lo enviamos al servidor, será descifrado como .

Oráculo MSB

Este oráculo nos dice si es mayor que o no. La idea es comenzar con un intervalo , porque sabemos que la flag se encuentra dentro, y luego consultar al oráculo para actualizar los límites del intervalo, reduciendo los valores posibles de la flag hasta obtenerla.

Por lo tanto, si consultamos con , obtendremos el valor de . Es muy probable que esto sea falso, así que actualizamos .

Luego, consultamos con y obtendremos , lo cual es equivalente a . Por lo tanto, si esto es falso, actualizamos el intervalo a , mientras que si es verdadero, se actualiza a .

Después, consultamos con para obtener , o equivalentemente , y actualizamos el intervalo en consecuencia.

Como resultado, podemos usar búsqueda binaria consultando con , y obteniendo el resultado de , lo cual es equivalente a , y actualizamos el intervalo en consecuencia.

Oráculo LSB

De manera similar, este oráculo devuelve el último bit de en binario (o, equivalentemente, indica si el entero descifrado es par o impar).

Si consultamos con , obtendremos el valor de , pero esto no da ninguna información.

Si consultamos con , obtendremos el valor de . Esto es más revelador, porque si , entonces el resultado es siempre par (False), pero si , entonces , lo cual es un número par menos uno impar, que es impar (True). Si reescribimos las ecuaciones, tenemos:

False, entonces , lo cual es equivalente a que sea verdadero, por lo que es falso
True, entonces y , lo cual es equivalente a que sea verdadero

¿Lo ves? Es exactamente el mismo oráculo que el MSB, pero comenzando desde en lugar de .

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.