从DDCTF中看区块链安全之51%攻击

author: Homaebic
team: Syclover

mini blockchain

DDCTF2018出了一道区块链题目，对于区块链的web安全网上还没有很多的教程，这道题目给了一个很好的入门机会，我也将学习到的知识分享出来。

DD自己创造了一个自己的区块链货币用于商店，但它并不是真正的区块链，因为链只保存在服务器的session中，不过这不影响我们理解和做题。

来看一张交易模型

关于UTXO的详解看http://8btc.com/article-4381-1.html

区块链就是区块和链。在这道题目中，看上面的图片，一个方框就是一个区块（block）。一个区块包含了一次交易（tx），一个交易包含了交易的输入（input）和交易的输出（output），其中输出又称为UTXO。每一次交易的输入和输出必须相同，如果输入10块钱花了2块给便利店，那么2块输出给便利店，8块输出给自己。也可以把UTXO理解为余额，因为每次能花多少，都是要取决于之前的UTXO向自己输出了多少。

这道题目的背景是银行在某天发行了100w个DDB（对应上图第一个方块），这时黑客出现了，他在第一个block后面append了一个区块，把银行的99w9999转给了自己，把1转给银行。这样银行就只剩下一块钱了，黑客还得意的喊：second_block = create_block(genesis_block['hash'], 'HAHA, I AM THE BANK NOW!', [transferred]) 题目的要求是获得两个钻石，获得钻石的方法是商店有100w元。一个钻石的价格是100w，就是说我们得有200w才可以得到两个钻石，可银行只发行了100w，该怎么办？

双花攻击

双花攻击是同一笔UTXO在不同交易中的花费，双花不会产生新的货币，只能把自己花出去的钱重新拿回来。

这个攻击方法给了我灵感，实际上这道题就是使用双花攻击中的51% attack。51% attack指的是攻击者如果可以拥有超过全网50%的算力，就可以创造一条高度大于原始链的链，攻击者可以发送一个新的块到这条链上。（如果有对比特币进行51% attack成功的案例，最大的危害在于人们对比特币的信心受损导致的比特币大跌而不是51% attack本身带来的危害）

如何进行51% attack攻击？在这道题中，就是创造一条超过原始链的长度。为了在后续讲解中方便，先写出题目给出的几个块，主链上块前有*

*块1（创世区块）：银行发行100w币
*块2(1)：黑客转走99w9999，银行留1
*块3(1)：空块（什么都没操作）

具体操作就是从块1之后append一个块，把银行的100w转到shop中

*块1（创世区块）：银行发行100w币
*块2(1)：黑客转走99w9999，银行留1 块2(2)--shop转走100w
*块3(1)：空块（什么都没操作）

（还可以随意转钱？就是有这种操作23333）

下一步，在自己append的块后append一个空块

*块1（创世区块）：银行发行100w币
*块2(1)：黑客转走99w9999，银行留1 块2(2)--shop转走100w
*块3(1)：空块（什么都不发生） 块3(2)--空块（什么都不发生）

再来一次同样的操作

*块1（创世区块）：银行发行100w币
块2(1)：黑客转走99w9999，银行留1 *块2(2)--shop转走100w
块3(1)：空块（什么都没操作） *块3(2)--空块（什么都不发生）
*块4(1)--空块（什么都不发生）

此时最长的链为块1-块2(2)-块3(1)-块4(1)。这样，我们就构造了一个比题目给我们还要长的链，区块链这套逻辑会把最长的链当做主链，主链从块2(2)处分叉，块2(1)失效了，shop账户中多了100w，我们获得一个钻石。接下来系统在购买钻石的块3(2)块后添加一个块，转走商店中的100w到商店钱包。

*块1（创世区块）：银行发行100w币
块2(1)：黑客转走99w9999，银行留1 *块2(2)--shop转走100w
*块3(2)--空块（什么都不发生）
*块4(1)--空块（什么都不发生）
*块5(1)--把100w转到shop_wallet_address

那么另一个钻石该怎么获得呢？继续利用50% attack攻击，从块4(1)分叉，添加空块

*块1（创世区块）：银行发行100w币
块2(1)：黑客转走99w9999，银行留1 *块2(2)--shop转走100w
*块3(2)--空块（什么都不发生）
*块4(1)--空块（什么都不发生）
*块5(1)--把100w转到shop_wallet_address 块5(2)--空块（什么都不发生）

再append一个空块

*块1（创世区块）：银行发行100w币
块2(1)：黑客转走99w9999，银行留1 *块2(2)--shop转走100w
*块3(2)--空块（什么都不发生）
*块4(1)--空块（什么都不发生）
块5(1)--把100w转到shop_wallet_address *块5(2)--空块（什么都不发生）
*块6(1)--空块（什么都不发生）

主链变为块1-块2(2)-块3(1)-块4(1)-块5(2)-块6(1)，块5(1)失效，shop拥有100w，钻石+1，得到flag。

为何可以直接append？

在这道题目中，给了一个append块的方法，可以将post请求当做块append到某个块后面，这个是一个正常的功能。在生成sign的时候没有将使用签名的交易hash计算进去，导致在验证的时候没有验证sign和交易hash的对应，所以只要有一个sign，就可以不断的利用这个sign append区块。

如果可以任意append，为什么不直接给shop转200w？

首先，所有的append都必须在创世block后。其次，系统会验证append块中的sign。还会验证prev值，是否为某个已存在的block的hash。（block的hash是将block的每个参数打包后进行hash）无法知道某个block的hash就无法在block后append一个block。最后，转出的钱，必须是之前的UTXO，题目中UTXO总量为100w，无法创造200w的UTXO。

51% attack和算力有什么关系？

append的块除了以上要求，还有一个复杂性要求。也就是工作量证明（https://baike.baidu.com/item/%E5%B7%A5%E4%BD%9C%E9%87%8F%E8%AF%81%E6%98%8E/22448498?fr=aladdin）。任意添加一个块的要求是

DIFFICULTY = int('00000' + 'f' * 59, 16)
......
if block_hash > difficulty: raise Exception('Please provide a valid Proof-of-Work')

block的hash要小于系统定义的difficulty。为了使得可以控制hash的大小，一个block中还有一个可以随意定义的nonce，我们可以控制nonce来控制block_hash达到目的。为了满足复杂度要求，必须穷举nonce。init()中的几个块可以使用有语义的nonce是因为在那个阶段DIFFICULTY要求极低。

如果世界上有100个用户在使用这个系统，100个用户都在计算nonce以append自己的block。如果其中一个人计算nonce的速度要超过其余99个的速度，那么他添加新块的速度就会超过其他99个人添加新块的速度，他就可以在随意的一个块开始添加自己的块，使得自己构造的链长度大于其余99个构造的链，成为主链，达成51%攻击。这道题没人和我们比算力，生成一个比最长链长度大一的链即可。

一个block结构是怎样的？块2(1)

{
'nonce': 'HAHA, I AM THE BANK NOW!', 
'prev': 'dd04faf20c550cf63ae07504884e1fb673cfefaaac2979dde1ae3cbf95961569', 
'hash': '5217b7fa9c1e2296e66202997df0a51b20e58fe921011069535a62cd53518e55', 
'transactions': [{
    'input': ['9d65e5db-8671-4323-b279-af56963f2565'], 
    'output': [{
        'amount': 999999, 
        'hash': 
        'da32c8155ebbec8df888653d4d243698e29c4ea43cc0fa1bff14649e8511416b', 
        'id': '9dcb9e47-5816-4451-b99e-eb6d729f64b7', 
        'addr': 'b2a6484625db7305ea7bb1c8a484832ec32686c0f3a3dac5cfe63779ede94494d841f8117fe1dd55c57e23aa61953391'
        }, 
        {
        'amount': 1, 
        'hash': '19fa5198bc172d6525976b7f0fb5f0647b96ab6b55bd4eb9033ab158faebb0ad', 
        'id': '592e27c6-b111-40a7-8b2d-ccefa333e616', 
        'addr': '99a13a3a21051c8f93c5a87f7f92151b4acfaf01f2e596696e8922e3801278470592cdbc8920f289a1829f726c43a1e9'
        }],

        'hash': '5815cc2ccf6327396ce5490c39e7c6381f15250fa0ab043eae8096d1a1c44704', 
        'signature': ['9455298609f042b631f99cb33f3f683f6b3361962df5f1c6f698e03b23d72c7ea42c939999913424e4c424f6b7024514']
        }
]}

参数解释，括号内为生成函数

nonce：自定义字符串

prev：上一个块的hash

hash：本个块的hash（hashhash，hash_reducer，hash_block）

transactions：交易（tx）

​ input：之前utxo的id

​ output：UTXO

​ amount：数量

​ hash：UTXO的hash（hash，hash_reducer，hash_utxo）

​ id：这个UTXO的id

​ addr：目标地址

​ hash：交易的hash（hash，hash_reducer，hash_tx）

​ signature：交易签名（sign_input_utxo）

题目代码：

# -*- encoding: utf-8 -*-
# written in python 2.7

import hashlib, json, rsa, uuid, os
from flask import Flask, session, redirect, url_for, escape, request

app = Flask(__name__)
app.secret_key = '*********************'
url_prefix = '/b9af31f66147e'

def FLAG():
    return 'Here is your flag: DDCTF{******************}'

def hash(x):
    return hashlib.sha256(hashlib.md5(x).digest()).hexdigest()

def hash_reducer(x, y):
    return hash(hash(x)+hash(y))

def has_attrs(d, attrs):
    if type(d) != type({}): raise Exception("Input should be a dict/JSON")
    for attr in attrs:
        if attr not in d:
            raise Exception("{} should be presented in the input".format(attr))

EMPTY_HASH = '0'*64

def addr_to_pubkey(address):
    return rsa.PublicKey(int(address, 16), 65537)

def pubkey_to_address(pubkey):
    assert pubkey.e == 65537
    hexed = hex(pubkey.n)
    if hexed.endswith('L'): hexed = hexed[:-1]
    if hexed.startswith('0x'): hexed = hexed[2:]
    return hexed

def gen_addr_key_pair():
    pubkey, privkey = rsa.newkeys(384)
    return pubkey_to_address(pubkey), privkey

bank_address, bank_privkey = gen_addr_key_pair()
hacker_address, hacker_privkey = gen_addr_key_pair()
shop_address, shop_privkey = gen_addr_key_pair()
shop_wallet_address, shop_wallet_privkey = gen_addr_key_pair()

def sign_input_utxo(input_utxo_id, privkey):
    return rsa.sign(input_utxo_id, privkey, 'SHA-1').encode('hex')

def hash_utxo(utxo):
    return reduce(hash_reducer, [utxo['id'], utxo['addr'], str(utxo['amount'])])

def create_output_utxo(addr_to, amount):
    utxo = {'id': str(uuid.uuid4()), 'addr': addr_to, 'amount': amount}
    utxo['hash'] = hash_utxo(utxo)
    return utxo

def hash_tx(tx):
    return reduce(hash_reducer, [
        reduce(hash_reducer, tx['input'], EMPTY_HASH),
        reduce(hash_reducer, [utxo['hash'] for utxo in tx['output']], EMPTY_HASH)
    ])

def create_tx(input_utxo_ids, output_utxo, privkey_from=None):
    tx = {'input': input_utxo_ids, 'signature': [sign_input_utxo(id, privkey_from) for id in input_utxo_ids], 'output': output_utxo}
    tx['hash'] = hash_tx(tx)
    return tx

def hash_block(block):
    return reduce(hash_reducer, [block['prev'], block['nonce'], reduce(hash_reducer, [tx['hash'] for tx in block['transactions']], EMPTY_HASH)])

def create_block(prev_block_hash, nonce_str, transactions):
    if type(prev_block_hash) != type(''): raise Exception('prev_block_hash should be hex-encoded hash value')
    nonce = str(nonce_str)
    if len(nonce) > 128: raise Exception('the nonce is too long')
    block = {'prev': prev_block_hash, 'nonce': nonce, 'transactions': transactions}
    block['hash'] = hash_block(block)
    return block

def find_blockchain_tail():
    return max(session['blocks'].values(), key=lambda block: block['height'])

def calculate_utxo(blockchain_tail):
    curr_block = blockchain_tail
    blockchain = [curr_block]
    while curr_block['hash'] != session['genesis_block_hash']:
        curr_block = session['blocks'][curr_block['prev']]
        blockchain.append(curr_block)
    blockchain = blockchain[::-1]
    utxos = {}
    for block in blockchain:
        for tx in block['transactions']:
            for input_utxo_id in tx['input']:
                del utxos[input_utxo_id]
            for utxo in tx['output']:
                utxos[utxo['id']] = utxo
    return utxos

def calculate_balance(utxos):
    balance = {bank_address: 0, hacker_address: 0, shop_address: 0}
    for utxo in utxos.values():
        if utxo['addr'] not in balance:
            balance[utxo['addr']] = 0
        balance[utxo['addr']] += utxo['amount']
    return balance

def verify_utxo_signature(address, utxo_id, signature):
    try:
        return rsa.verify(utxo_id, signature.decode('hex'), addr_to_pubkey(address))
    except:
        return False

def append_block(block, difficulty=int('f'*64, 16)):
    has_attrs(block, ['prev', 'nonce', 'transactions'])

    if type(block['prev']) == type(u''): block['prev'] = str(block['prev'])
    if type(block['nonce']) == type(u''): block['nonce'] = str(block['nonce'])
    if block['prev'] not in session['blocks']: raise Exception("unknown parent block")
    tail = session['blocks'][block['prev']]
    utxos = calculate_utxo(tail)

    if type(block['transactions']) != type([]): raise Exception('Please put a transaction array in the block')
    new_utxo_ids = set()
    for tx in block['transactions']:
        has_attrs(tx, ['input', 'output', 'signature'])

        for utxo in tx['output']:
            has_attrs(utxo, ['amount', 'addr', 'id'])
            if type(utxo['id']) == type(u''): utxo['id'] = str(utxo['id'])
            if type(utxo['addr']) == type(u''): utxo['addr'] = str(utxo['addr'])
            if type(utxo['id']) != type(''): raise Exception("unknown type of id of output utxo")
            if utxo['id'] in new_utxo_ids: raise Exception("output utxo of same id({}) already exists.".format(utxo['id']))
            new_utxo_ids.add(utxo['id'])
            if type(utxo['amount']) != type(1): raise Exception("unknown type of amount of output utxo")
            if utxo['amount'] <= 0: raise Exception("invalid amount of output utxo")
            if type(utxo['addr']) != type(''): raise Exception("unknown type of address of output utxo")
            try:
                addr_to_pubkey(utxo['addr'])
            except:
                raise Exception("invalid type of address({})".format(utxo['addr']))
            utxo['hash'] = hash_utxo(utxo)
        tot_output = sum([utxo['amount'] for utxo in tx['output']])

        if type(tx['input']) != type([]): raise Exception("type of input utxo ids in tx should be array")
        if type(tx['signature']) != type([]): raise Exception("type of input utxo signatures in tx should be array")
        if len(tx['input']) != len(tx['signature']): raise Exception("lengths of arrays of ids and signatures of input utxos should be the same")
        tot_input = 0
        tx['input'] = [str(i) if type(i) == type(u'') else i for i in tx['input']]
        tx['signature'] = [str(i) if type(i) == type(u'') else i for i in tx['signature']]
        for utxo_id, signature in zip(tx['input'], tx['signature']):
            if type(utxo_id) != type(''): raise Exception("unknown type of id of input utxo")
            if utxo_id not in utxos: raise Exception("invalid id of input utxo. Input utxo({}) does not exist or it has been consumed.".format(utxo_id))
            utxo = utxos[utxo_id]
            if type(signature) != type(''): raise Exception("unknown type of signature of input utxo")
            if not verify_utxo_signature(utxo['addr'], utxo_id, signature):
                raise Exception("Signature of input utxo is not valid. You are not the owner of this input utxo({})!".format(utxo_id))
            tot_input += utxo['amount']
            del utxos[utxo_id]
        if tot_output > tot_input:
            raise Exception("You don't have enough amount of DDCoins in the input utxo! {}/{}".format(tot_input, tot_output))
        tx['hash'] = hash_tx(tx)

    block = create_block(block['prev'], block['nonce'], block['transactions'])
    block_hash = int(block['hash'], 16)
    if block_hash > difficulty: raise Exception('Please provide a valid Proof-of-Work')
    block['height'] = tail['height']+1
    if len(session['blocks']) > 50: raise Exception('The blockchain is too long. Use ./reset to reset the blockchain')
    if block['hash'] in session['blocks']: raise Exception('A same block is already in the blockchain')
    session['blocks'][block['hash']] = block
    session.modified = True

def init():
    if 'blocks' not in session:
        session['blocks'] = {}
        session['your_diamonds'] = 0

        # First, the bank issued some DDCoins ...
        total_currency_issued = create_output_utxo(bank_address, 1000000)
        genesis_transaction = create_tx([], [total_currency_issued]) # create DDCoins from nothing
        genesis_block = create_block(EMPTY_HASH, 'The Times 03/Jan/2009 Chancellor on brink of second bailout for bank', [genesis_transaction])
        session['genesis_block_hash'] = genesis_block['hash']
        genesis_block['height'] = 0
        session['blocks'][genesis_block['hash']] = genesis_block

        # Then, the bank was hacked by the hacker ...
        handout = create_output_utxo(hacker_address, 999999)
        reserved = create_output_utxo(bank_address, 1)
        transferred = create_tx([total_currency_issued['id']], [handout, reserved], bank_privkey)
        second_block = create_block(genesis_block['hash'], 'HAHA, I AM THE BANK NOW!', [transferred])
        append_block(second_block)

        # Can you buy 2 diamonds using all DDCoins?
        third_block = create_block(second_block['hash'], 'a empty block', [])
        append_block(third_block)

def get_balance_of_all():
    init()
    tail = find_blockchain_tail()
    utxos = calculate_utxo(tail)
    return calculate_balance(utxos), utxos, tail

@app.route(url_prefix+'/')
def homepage():
    announcement = 'Announcement: The server has been restarted at 21:45 04/17. All blockchain have been reset. '
    balance, utxos, _ = get_balance_of_all()
    genesis_block_info = 'hash of genesis block: ' + session['genesis_block_hash']
    addr_info = 'the bank\'s addr: ' + bank_address + ', the hacker\'s addr: ' + hacker_address + ', the shop\'s addr: ' + shop_address
    balance_info = 'Balance of all addresses: ' + json.dumps(balance)
    utxo_info = 'All utxos: ' + json.dumps(utxos)
    blockchain_info = 'Blockchain Explorer: ' + json.dumps(session['blocks'])
    view_source_code_link = "<a href='source_code'>View source code</a>"
    return announcement+('<br /><br />\r\n\r\n'.join([view_source_code_link, genesis_block_info, addr_info, balance_info, utxo_info, blockchain_info]))


@app.route(url_prefix+'/flag')
def getFlag():
    init()
    if session['your_diamonds'] >= 2: return FLAG()
    return 'To get the flag, you should buy 2 diamonds from the shop. You have {} diamonds now. To buy a diamond, transfer 1000000 DDCoins to '.format(session['your_diamonds']) + shop_address

def find_enough_utxos(utxos, addr_from, amount):
    collected = []
    for utxo in utxos.values():
        if utxo['addr'] == addr_from:
            amount -= utxo['amount']
            collected.append(utxo['id'])
        if amount <= 0: return collected, -amount
    raise Exception('no enough DDCoins in ' + addr_from)

def transfer(utxos, <
源链接

Hacking more

...