ångstromCTF 2019 | Powerball

#angstromCTF2019

https://ctftime.org/task/8344

Introducing ångstromCTF Powerball, where the Grand Prize is a flag! All you need to do is guess 6 ball values, ranging from 0 to 4095. But don't worry, we'll give one for free!

nc 54.159.113.26 19001

サーバが止まっていてprivate.txtが失われてしまっているのでnとdは新しく作り直すことにした。

n: 24714368843752022974341211877467549639498231894964810269117413322029642752633577038705218673687716926448339400096802361297693998979745765931534103202467338384642921856548086360244485671986927177008440715178336399465697444026353230451518999567214983427406178161356304710292306078130635844316053709563154657103495905205276956218906137150310994293077448766114520034675696741058748420135888856866161554417709555214430301224863490074059065870222171272131856991865315097313467644895025929047477332550027963804064961056274499899920572740781443106554154096194288807134535706752546520058150115125502989328782055006169368495301
e: 65537

import socketserver

from Crypto.Util.number import getRandomRange

from secret import flag

welcome = b'''\
************  ANGSTROMCTF POWERBALL  ************
Correctly guess all 6 ball values ranging from 0
to 4095 to win the jackpot! As a special deal,
we'll also let you secretly view a ball's value!
'''

with open('public.txt') as f:
    n = int(f.readline()[3:])
    e = int(f.readline()[3:])

with open('private.txt') as f:
    d = int(f.readline()[3:])

def handle(self):
    self.write(welcome)
    balls = [getRandomRange(0, 4096) for _ in range(6)]
    x = [getRandomRange(0, n) for _ in range(6)]
    self.write('x: {}\n'.format(x).encode())
    v = int(self.query(b'v: '))
    m = []
    for i in range(6):
        k = pow(v-x[i], d, n)
        m.append((balls[i]+k) % n)
    self.write('m: {}\n'.format(m).encode())
    guess = []
    for i in range(6):
        guess.append(int(self.query('Ball {}: '.format(i+1).encode())))
    if balls == guess:
        self.write(b'JACKPOT!!!')
        self.write(flag)
    else:
        self.write(b'Sorry, those were the wrong numbers.')

class RequestHandler(socketserver.BaseRequestHandler):

    handle = handle

    def read(self, until=b'\n'):
        out = b''
        while not out.endswith(until):
            out += self.request.recv(1)
        return out[:-len(until)]

    def query(self, string=b''):
        self.write(string, newline=False)
        return self.read()

    def write(self, string, newline=True):
        self.request.sendall(string)
        if newline:
            self.request.sendall(b'\n')

class Server(socketserver.ForkingTCPServer):

    allow_reuse_address = True

    def handle_error(self, request, client_address):
        pass

port = 3000
server = Server(('0.0.0.0', port), RequestHandler)
server.serve_forever()

0からnまでのが与えられて、こちらからはを与える。すると

与えられる。は0から4095まで。この状態ですべてのを当てよ、という問題。

各についてを全探索する。 がちゃんと成立するような を選べば良い

from ptrlib.pwn.sock import Socket

f = open("public.txt")
n = int(f.readline()[3:])
e = int(f.readline()[3:])

sock = Socket("localhost", 3000)
_ = sock.recvuntil("x: ")
xs = eval(sock.recvline().decode())
v = max(xs)
_ = sock.recvuntil("v: ")
sock.sendline(str(v))
_ = sock.recvuntil("m: ")
ms = eval(sock.recvline().decode())

balls = []
for i in range(6):
    for b in range(4096):
        if pow(ms[i] - b, e, n) == v - xs[i]:
            print("BALL {} found".format(i))
            balls.append(b)
            break
for i in range(6):
    _ = sock.recvuntil(": ")
    sock.sendline(str(balls[i]))
print(sock.recvline())
print(sock.recvline())

フラグは actf{no_more_free_oblivious_transfers}。oblivious transferは「紛失通信」のことらしい