ふるつき

v(*'='*)v かに

BambooFox CTF 2019 Oracle writeup

We're given the server.py and the nc information.

#!/usr/bin/env python3
from Crypto.Util.number import *

with open("flag", "rb") as f:
    flag = int.from_bytes(f.read(), "big")


def genkeys():
    e = 65537
    while True:
        p, q = getPrime(512), getPrime(512)
        n, phi = p * q, (p - 1) * (q - 1)
        if GCD(e, phi) == 1:
            d = inverse(e, phi)
            return n, e, d


def menu():
    print("1) Info")
    print("2) Decrypt")
    print("3) Exit")


def main():
    n, e, d = genkeys()

    while True:
        menu()
        option = input("> ")
        if option == "1":
            c = pow(flag, e, n)
            print(f"c = {c}")
            print(f"n = {n}")
        elif option == "2":
            c = int(input("c = "))
            m = pow(c, d, n)
            print(f"m = {m % 3}")
        else:
            return


main()

At first glance, we could notice that the LSB Oracle Attack is available. However, the oracle is the modulo of 3, though generally modulo of 2.

So we need to think that how to get the oracle that  2m is larger than  n or else, like when the modulo is 2. I tried to find the low of the modulo 3. Then it was found easily.

Assume we have the x as modulo 3 oracle of m. If y which is a modulo 3 oracle of 2m, equals to  2x \mod 3 then this means that  n > 2m, otherwise means  2m > n. You can confirm this fact by your example and can proof by yourself (however, I don't XP. please tell me if you did it).

The thing remaining it just write the code and get the flag. Just do it!

from ptrlib import *
from Crypto.Util.number import long_to_bytes

e = 65537

sock = Socket("34.82.101.212", 20001)

sock.recvuntil("> ")
sock.sendline("1")
sock.recvuntil("c = ")
c = int(sock.recvline().strip())
sock.recvuntil("n = ")
n = int(sock.recvline().strip())

sock.recvuntil("> ")
sock.sendline(b"2")
sock.recvuntil("c = ")
sock.sendline(str(c).encode())
sock.recvuntil("m = ")
last = int(sock.recvline().strip())


def oracle(c):
    global last
    sock.recvuntil("> ")
    sock.sendline(b"2")
    sock.recvuntil("c = ")
    sock.sendline(str(c).encode())
    sock.recvuntil("m = ")
    m = int(sock.recvline().strip())
    if m != (last * 2) % 3:
        ret = 1
    else:
        ret = 0
    last = m
    return ret


m = lsb_leak_attack(oracle, n, e, c)
print(long_to_bytes(m))

This code is a modified version of yoshiking's one. It uses the amazing library ptrlib and its function lsb_leak_attack. So the code is very short and essential.

After waiting some minutes, just get the flag: BAMBOOFOX{SimPlE0RACl3}