Real World CTF 2019 Quals Writeup

この大会は2019/9/14 11:00(JST)~2019/9/16 11:00(JST)に開催されました。
今回もチームで参戦。結果は254点で576チーム中42位でした。
自分で解けた問題をWriteupとして書いておきます。

Advertisement (check-in)

問題にはこう書いてある。

What is the powerful security assessment tool developed by Chaitin Tech? Flag is in standard format rwctf{}.

"Chaitin Tech" powerful security assessment toolで調べると、XRAYとわかる。

rwctf{xray}

bank (crypto)

PoWをクリアした後が、本論の問題。サーバの処理の概要は以下の通り。

ECC: H = x * G
sk = x
pk = H
balance = 0

userPk: public key入力

msg(Base64)入力

■msg[0] = '1'
・msg(Base64)入力
・schnorr_verify('DEPOSIT', userPk, msg) == True
 →balance += 1

■msg[0] = '2'
・msg(Base64)入力
・schnorr_verify('WITHDRAW', point_add(userPk, pk), msg) == True かつ balance > 0
 →フラグ表示

■msg[0] = '3'
・pk表示

まず'DEPOSIT'のverifyをクリアして、balanceの値を1にしておく必要がある。sign関数があるので、自分用の秘密鍵(myPriv)、公開鍵(myPub)を生成して、signしたものをverifyに使えばよい。
その後、'WITHDRAW'のverifyをクリアする必要がある。ここではサーバの公開鍵pkと自分の公開鍵userPkをaddして、verifyしている。このaddした公開鍵に対して、秘密鍵を算出する必要があるが、この和が先ほどの自分用の公開鍵(myPriv)になれば、自分用の秘密鍵(myPub)でsignすればクリアできる。

myPub2 + pk = myPub
myPub2 = myPub + (- pk)

これを利用して、スクリプトを作成する。

import socket
import re
import itertools
import hashlib
import string
import base64
from Crypto.Random import random

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def to_bytes(n, length, byteorder='big'):
    h = hex(n)[2:].rstrip('L')
    #print 'h', h
    s = ('0'*(len(h) % 2) + h).zfill(length*2).decode('hex')
    return s if byteorder == 'big' else s[::-1]

def from_bytes(s, byteorder='big'):
    return int(s.encode('hex'), 16)

def point_add(p1, p2):
    if (p1 is None):
        return p2
    if (p2 is None):
        return p1
    if (p1[0] == p2[0] and p1[1] != p2[1]):
        return None
    if (p1 == p2):
        lam = (3 * p1[0] * p1[0] * pow(2 * p1[1], p - 2, p)) % p
    else:
        lam = ((p2[1] - p1[1]) * pow(p2[0] - p1[0], p - 2, p)) % p
    x3 = (lam * lam - p1[0] - p2[0]) % p
    return (x3, (lam * (p1[0] - x3) - p1[1]) % p)

def point_neg(p):
    return (p[0], -p[1])

def point_mul(p, n):
    r = None
    for i in range(256):
        if ((n >> i) & 1):
            r = point_add(r, p)
        p = point_add(p, p)
    return r

def bytes_point(p):
    return (b'\x03' if p[1] & 1 else b'\x02') + to_bytes(p[0], 32, byteorder="big")

def sha256(b):
    return from_bytes(hashlib.sha256(b).digest(), byteorder="big")

def jacobi(x):
    return pow(x, (p - 1) // 2, p)

def schnorr_sign(msg, seckey):
    k = sha256(to_bytes(seckey, 32, byteorder="big") + msg)
    R = point_mul(G, k)
    if jacobi(R[1]) != 1:
        k = n - k
    e = sha256(to_bytes(R[0], 32, byteorder="big") + bytes_point(point_mul(G, seckey)) + msg)
    return to_bytes(R[0], 32, byteorder="big") + to_bytes(((k + e * seckey) % n), 32, byteorder="big")

def generate_keys():
    privKey = random.randint(5, p-1)
    pubKey = point_mul(G, privKey)
    return privKey, pubKey

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('tcp.realworldctf.com', 20014))

data = recvuntil(s, '\n').rstrip()
print data
text_head = data.split(' ')[-1]

for c in itertools.product(string.printable, repeat=5):
    text = text_head + ''.join(c)
    if hashlib.sha1(text).hexdigest()[-4:] == '0000':
        print text
        s.sendall(text)
        break

myPriv, myPub = generate_keys()
str_myPub = str(myPub)[1:-1].replace(', ', ',').replace('L', '')

data = recvuntil(s, '\n').rstrip()
print data

#### set balance to 1 ####
data = recvuntil(s, ':')
print data + base64.b64encode(str_myPub)
s.sendall(base64.b64encode(str_myPub) + '\n')

data = recvuntil(s, 'priority!\n').rstrip()
print data

print base64.b64encode('1')
s.sendall(base64.b64encode('1') + '\n')
data = recvuntil(s, 'signature')
print data
sig = schnorr_sign('DEPOSIT', myPriv)
print base64.b64encode(sig)
s.sendall(base64.b64encode(sig) + '\n')
data = recvuntil(s, '\n').rstrip()
print data

#### get pk ####
data = recvuntil(s, ':')
print data + base64.b64encode(str_myPub)
s.sendall(base64.b64encode(str_myPub) + '\n')

data = recvuntil(s, 'priority!\n').rstrip()
print data

print base64.b64encode('3')
s.sendall(base64.b64encode('3') + '\n')
data = recvuntil(s, '\n\n').rstrip()
print data
data = recvuntil(s, '\n').rstrip()
print data

pk = eval(data.split(': ')[1])

#### get flag ####
myPub2 = point_add(myPub, point_neg(pk))
print myPub2
str_myPub2 = str(myPub2)[1:-1].replace(', ', ',').replace('L', '')

data = recvuntil(s, ':')
print data + base64.b64encode(str_myPub2)
s.sendall(base64.b64encode(str_myPub2) + '\n')

data = recvuntil(s, 'priority!\n').rstrip()
print data

print base64.b64encode('2')
s.sendall(base64.b64encode('2') + '\n')
data = recvuntil(s, 'signature')
print data
sig = schnorr_sign('WITHDRAW', myPriv)
print base64.b64encode(sig)
s.sendall(base64.b64encode(sig) + '\n')
data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Please provide your proof of work, a sha1 sum ending in 16 bit's set to 0, it must be of length 21 bytes, starting with 34s/3IosJXBH7LnP
34s/3IosJXBH7LnP005_M
Generating keys...
Please tell us your public key:MTE1NDIzMTI1NTkyNjk0NTYzMzM0NzE4MzU0ODY5NzA0ODE0NjA4ODQ2NjQxNzEyMDAyMDg3MzEwNDIzOTcxMDcyODc4MjAyNzMzNjIxLDExMTUxODYzNTcwNTUxODc3Nzg3MjIzODA0MzYzNzQwMzM3ODQxMzg2MTMyNzEyMTYxOTY0NzUyMTcyNTU4NDM0ODc3MDA1NjQxOTI3NQ==
User logged in.

                [Beep]

    Please select your options:

    1. Deposit a coin into your account, you can sign a message 'DEPOSIT' and send us the signature.
    2. Withdraw a coin from your account, you need to provide us a message 'WITHDRAW' signed by both of you and our RESPECTED BANK MANAGER.
    3. Find one of our customer support representative to assist you.


    Our working hour is 9:00 am to 5:00 pm every Monday!
    Thank you for being our loyal customer and your satisfaction is our first priority!
MQ==
    Please send us your signature
gl+Z63474gYAsIWDX2fZcvl+GkGd6O5pXu6z3kjNX8DRPjOjzMW4KE/TMT9mr1FluV9FdHqq5zLCeKZM3VBX1w==
Coin deposited.
Please tell us your public key:MTE1NDIzMTI1NTkyNjk0NTYzMzM0NzE4MzU0ODY5NzA0ODE0NjA4ODQ2NjQxNzEyMDAyMDg3MzEwNDIzOTcxMDcyODc4MjAyNzMzNjIxLDExMTUxODYzNTcwNTUxODc3Nzg3MjIzODA0MzYzNzQwMzM3ODQxMzg2MTMyNzEyMTYxOTY0NzUyMTcyNTU4NDM0ODc3MDA1NjQxOTI3NQ==
User logged in.

                [Beep]

    Please select your options:

    1. Deposit a coin into your account, you can sign a message 'DEPOSIT' and send us the signature.
    2. Withdraw a coin from your account, you need to provide us a message 'WITHDRAW' signed by both of you and our RESPECTED BANK MANAGER.
    3. Find one of our customer support representative to assist you.


    Our working hour is 9:00 am to 5:00 pm every Monday!
    Thank you for being our loyal customer and your satisfaction is our first priority!
Mw==
    The custom service is offline now.
But here is our public key just in case a random guy claims himself as one of us: (82138465389729382118160275546904778101486660476302056228245598173171434755635L, 26724533442039675526168320154818882440734636103490204685431841952870824511084L)
(66916183750854159755222420223475084047348071859752286201549092886168965259335L, 98990119392094347776956125953891488242069699643235727354522726226383496978433L)
Please tell us your public key:NjY5MTYxODM3NTA4NTQxNTk3NTUyMjI0MjAyMjM0NzUwODQwNDczNDgwNzE4NTk3NTIyODYyMDE1NDkwOTI4ODYxNjg5NjUyNTkzMzUsOTg5OTAxMTkzOTIwOTQzNDc3NzY5NTYxMjU5NTM4OTE0ODgyNDIwNjk2OTk2NDMyMzU3MjczNTQ1MjI3MjYyMjYzODM0OTY5Nzg0MzM=
User logged in.

                [Beep]

    Please select your options:

    1. Deposit a coin into your account, you can sign a message 'DEPOSIT' and send us the signature.
    2. Withdraw a coin from your account, you need to provide us a message 'WITHDRAW' signed by both of you and our RESPECTED BANK MANAGER.
    3. Find one of our customer support representative to assist you.


    Our working hour is 9:00 am to 5:00 pm every Monday!
    Thank you for being our loyal customer and your satisfaction is our first priority!
Mg==
    Please send us your signature
rFjxOGjBVuVZsDqy7t0pz/oppu1yTnYv4ya2h80LFqLepSWGzPZP1+wfmelnLKFUJ2hB4/ewTChpO+PKDU9lWA==
Here is your coin: rwctf{P1Ain_SChNorr_n33Ds_m0re_5ecur1ty!}
rwctf{P1Ain_SChNorr_n33Ds_m0re_5ecur1ty!}