bank

[tiwanari]

You've earned a lot of cash from investing bitcoins! Why not try our coolest multi-signature bank?

nc tcp.realworldctf.com 20014

bank.zip

bank.zip

[tiwanari]

2 つはいっている

$ ll
total 16
-rw-r--r--@ 1 tatsuya  staff   3.3K Sep 13 22:19 multi-schnorr.py
-rw-r--r--@ 1 tatsuya  staff   2.8K Sep 13 22:21 schnorr.py

[tiwanari]

nc の結果

$ nc tcp.realworldctf.com 20014
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 dMq0hA2EHAyEqZ17
1
Check failed%

$ nc tcp.realworldctf.com 20014
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 6DSlsATAxTDrSjZm
2
Check failed%

starting with 以降が違うのでこれを見て正しい結果を返す必要あり

• dMq0hA2EHAyEqZ17
• 6DSlsATAxTDrSjZm

[tiwanari]

multi-schnorr.py

import os
import SocketServer
import base64 as b64
import hashlib
from Crypto.Util import number
from Crypto import Random
from Crypto.PublicKey.pubkey import *
import datetime
import calendar

from schnorr import *

MSGLENGTH = 40000
HASHLENGTH = 16
FLAG = open("flag","r").read()
PORT_NUM = 20014

def digitalize(m):
    return int(m.encode('hex'), 16)

class HandleCheckin(SocketServer.StreamRequestHandler):
    def handle(self):
        Random.atfork()
        req = self.request
        proof = b64.b64encode(os.urandom(12))

        req.sendall(
            "Please provide your proof of work, a sha1 sum ending in 16 bit's set to 0, it must be of length %d bytes, starting with %s\n" % (
            len(proof) + 5, proof))

        test = req.recv(21)
        ha = hashlib.sha1()
        ha.update(test)

        if (test[0:16] != proof or ord(ha.digest()[-1]) != 0 or ord(ha.digest()[-2]) != 0): # or ord(ha.digest()[-3]) != 0 or ord(ha.digest()[-4]) != 0):
            req.sendall("Check failed")
            req.close()
            return

        req.sendall("Generating keys...\n")
        sk, pk = generate_keys()
        balance = 0
        while True:
                req.sendall("Please tell us your public key:")
                msg = self.rfile.readline().strip().decode('base64')
                if len(msg) < 6 or len(msg) > MSGLENGTH:
                    req.sendall("what are you doing?")
                    req.close()
                    return
                userPk = (int(msg.split(',')[0]), int(msg.split(',')[1]))
                req.sendall('''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 %s!
    Thank you for being our loyal customer and your satisfaction is our first priority!
    ''' % calendar.day_name[(datetime.datetime.today() + datetime.timedelta(days=1)).weekday()])
                msg = self.rfile.readline().strip().decode('base64')
                if msg[0] == '1':
                    req.sendall("Please send us your signature")
                    msg = self.rfile.readline().strip().decode('base64')
                    if schnorr_verify('DEPOSIT', userPk, msg):
                        balance += 1
                    req.sendall("Coin deposited.\n")
                elif msg[0] == '2':
                    req.sendall("Please send us your signature")
                    msg = self.rfile.readline().strip().decode('base64')
                    if schnorr_verify('WITHDRAW', point_add(userPk, pk), msg) and balance > 0:
                        req.sendall("Here is your coin: %s\n" % FLAG)
                elif msg[0] == '3':
                    req.sendall("The custom service is offline now.\n\nBut here is our public key just in case a random guy claims himself as one of us: %s\n" % repr(pk))

class ThreadedServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", int(PORT_NUM)
    server = ThreadedServer((HOST, PORT), HandleCheckin)
    server.allow_reuse_address = True
    server.serve_forever()

[tiwanari]

schnorr.py

import hashlib
import binascii
import unittest

from Crypto.Random import random

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

# back-ports for python2 from https://stackoverflow.com/questions/16022556/has-python-3-to-bytes-been-back-ported-to-python-2-7
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_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 on_curve(point):
    return (pow(point[1], 2, p) - pow(point[0], 3, p)) % p == 7

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 schnorr_verify(msg, pubkey, sig):
    if (not on_curve(pubkey)):
        return False
    r = from_bytes(sig[0:32], byteorder="big")
    s = from_bytes(sig[32:64], byteorder="big")
    if r >= p or s >= n:
        return False
    e = sha256(sig[0:32] + bytes_point(pubkey) + msg)
    R = point_add(point_mul(G, s), point_mul(pubkey, n - e))
    if R is None or jacobi(R[1]) != 1 or R[0] != r:
        return False
    return True

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

def create_input(private_key, public_key, message, signature):
    return dict(
            private_key=private_key,
            public_key=public_key,
            message=bytearray.fromhex(message),
            signature=bytearray.fromhex(signature))

[tiwanari]

概要

大きく分けると2つの段階がある

sha1 した結果の最後の4バイト（コードでは2バイト）が0になるように文字列を返す

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 xxxx_xxxx_xxxx_xxxx (16 文字)

xxxx_xxxx_xxxx_xxxx に5バイト追加して sha1 をかけた結果の、最後の16ビットが0になるように適当な5バイトを選ぶ

        test = req.recv(21)  # 16 (xxxx_xxxx_xxxx_xxxx + 5バイト)
        ha = hashlib.sha1()
        ha.update(test)

        if (test[0:16] != proof or ord(ha.digest()[-1]) != 0 or ord(ha.digest()[-2]) != 0): # or ord(ha.digest()[-3]) != 0 or ord(ha.digest()[-4]) != 0):
            req.sendall("Check failed")
            req.close()
            return

Question: これ順列列挙以外に良い方法あるだろうか....

コインバンクにログインしてコインの振り込みと引き出しをする

1. まずこちらの public key を渡す
   • key は base64 で書かれた 6 文字以上4000文字以下の文字列
   • , で区切られていて前半後半に分かれる
2. 以下が表示される

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 %s!
    Thank you for being our loyal customer and your satisfaction is our first priority!

3 Support

なぜか向こうの public key を返してくれるので、これを2で活用する

"The custom service is offline now.\n\nBut here is our public key just in case a random guy claims himself as one of us: %s\n" % repr(pk)

1 DEPOSIT

• schnorr.py に書いてある署名の方法を使って deposite する

                    req.sendall("Please send us your signature")
                    msg = self.rfile.readline().strip().decode('base64')
                    if schnorr_verify('DEPOSIT', userPk, msg):
                        balance += 1
                    req.sendall("Coin deposited.\n")

2 WITHDRAW

• deposit をして balance があるうえで署名ができていると flag を返してくれる

            req.sendall("Please send us your signature")
            msg = self.rfile.readline().strip().decode('base64')
            if schnorr_verify('WITHDRAW', point_add(userPk, pk), msg) and balance > 0:
                req.sendall("Here is your coin: %s\n" % FLAG)

これは勉強をしないと・・・ Schnorr署名 ―― 30年の時を超えて注目を集める電子署名 – びりあるの研究ノート

[tiwanari]

第2段階で、public key を最初に聞かれるけどこれは2つの数字を,で区切ったものをbase64でencodeしたもの

例: 111111,222222 => MTExMTExLDIyMjIyMg== を送る

メニューの数字も base64 で受け取るので 1: MQ== 2: Mg== 3: Mw== をそれぞれ送る

menu2base64 = {1:"MQ==", 2:"Mg==", 3:"Mw=="}

[tiwanari]

毎回変わるけどこういうのが menu:3 では帰ってくる

The custom service is offline now.

But here is our public key just in case a random guy claims himself as one of us: (6500994360092417621017321812861573212506017208954801667147905054670460750512L, 98096092765526403371019955548832969809822231416882040578539145822846521789341L)

[tiwanari]

Schnorr Signatures（楕円曲線：EC） - Qiita

[hnoson]

def schnorr_sign(msg, seckey):
  ...
  return to_bytes(R[0], 32, byteorder="big") + to_bytes(((k + e * seckey) % n), 32, byteorder="big")

でseckeyがわからないから後半32bytesが作れないけどこれを適当に1とかにしてしまって、RとuserPkを操作してverifyを通るようにすればいける？

[hnoson]

3. Find one ...で聞いた鍵をpkとしてpk + GをuserPkとすればpk + userPk = Gになるからこれが使えそう

[hnoson]

rwctf{P1Ain_SChNorr_n33Ds_m0re_5ecur1ty!}