1. 威客安全首页
  2. 安全资讯

分析RealWorld CTF 2019中Crypto方向bank题目

分析RealWorld CTF 2019中Crypto方向bank题目

 

前言

bank是RealWorld CTF 2019中唯一的一道crypto题,题目涉及到了schnorr比特币签名算法,在此记录一下分析和解题过程以及针对schnorr的一些攻击技巧。

 

题目信息

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

 

初步分析

源码+服务器交互题,bypass掉POW后,服务器端首先打印如下信息:

Generating keys...
Please tell us your public key:

可以看到,服务器预期我们提供一个public key,那么我们直接使用题目当中给出的schnorr.py随机生成一个公钥,通过阅读源码可以发现本题中所有交互均是以base64编码后的结果来进行的,生成过程如下:

>>> from schnorr import *
>>> sk, pk = generate_keys()
>>> pk
(64646428988419328348098910455943469703858360262896251929535045073512200095812L, 8827897429209231856466904238695535359213319466247516611187411915515480433077L)
>>> from base64 import *
>>> strpk = "64646428988419328348098910455943469703858360262896251929535045073512200095812, 8827897429209231856466904238695535359213319466247516611187411915515480433077"
>>> b64encode(strpk)
'NjQ2NDY0Mjg5ODg0MTkzMjgzNDgwOTg5MTA0NTU5NDM0Njk3MDM4NTgzNjAyNjI4OTYyNTE5Mjk1MzUwNDUwNzM1MTIyMDAwOTU4MTIsIDg4Mjc4OTc0MjkyMDkyMzE4NTY0NjY5MDQyMzg2OTU1MzUzNTkyMTMzMTk0NjYyNDc1MTY2MTExODc0MTE5MTU1MTU0ODA0MzMwNzc='

将base64编码后的结果提交至服务器,进入到本题的主菜单界面:

Generating keys...
Please tell us your public key:NjQ2NDY0Mjg5ODg0MTkzMjgzNDgwOTg5MTA0NTU5NDM0Njk3MDM4NTgzNjAyNjI4OTYyNTE5Mjk1MzUwNDUwNzM1MTIyMDAwOTU4MTIsIDg4Mjc4OTc0MjkyMDkyMzE4NTY0NjY5MDQyMzg2OTU1MzUzNTkyMTMzMTk0NjYyNDc1MTY2MTExODc0MTE5MTU1MTU0ODA0MzMwNzc=
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 Saturday!
    Thank you for being our loyal customer and your satisfaction is our first priority!

根据源码和提示信息,我们可以得知以下信息:

1.要求用户给出"DEPOSIT"字符串的签名,并使用用户自己提供的`用户公钥`对签名结果进行校验,校验通过的话,比特币+1。
2.要求用户给出"WITHDRAW"字符串的签名,并使用`mul_add(用户公钥,系统公钥)`对签名结果进行校验,校验通过且比特币数量>0的话,打印flag。
3.打印`系统公钥`。

其中,每执行完一个选项,系统都会重新从要求用户提供公钥那一步开始,不停循环这些操作,而系统公钥是在这些循环操作之前生成的,也就是说在一次nc过程中,系统公钥是始终保持不变的。

那么接下来整理一下我们的任务,我们要想满足选项2的check,得到flag,基本上只有3种可能的思路:

1. 想办法**求出**系统私钥,然后直接用我们的私钥和系统私钥计算出"WITHDRAW"字符串的签名。
2. 想办法**泄露**系统私钥,然后直接用我们的私钥和系统私钥计算出"WITHDRAW"字符串的签名。
2. 想办法在不知道系统私钥的情况下,直接**伪造**出我们所需要的签名。

第一种思路需要我们解决一个ECDLP问题,根据on_curve函数可知:

#即y^2 - x^3 ≡ 7 (mod p),a = 0,b = 7
def on_curve(point):
    return (pow(point[1], 2, p) - pow(point[0], 3, p)) % p == 7

曲线参数已知,我们可以check一下是否可以应用Smart’s attack来求出私钥:

sage: a = 0
sage: b = 7
sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
sage: E = EllipticCurve(GF(p), [a, b])
sage: E.order() == p
False

可以看到这里E.order()p是不相同的,所以我们没有办法很好的展开Smart’s attack,那么我们接下来看一下第二种思路。

第二种思路需要我们泄露私钥,通过查阅资料&论文,我们可以找到《Simple Schnorr Multi-Signatures with Applications to Bitcoin》这篇论文,在这篇论文中介绍了一类攻击场景,当使用相同的k签名两个不同的msg的时候,我们可以按照如下思路恢复私钥:

分析RealWorld CTF 2019中Crypto方向bank题目

将其写成代码的形式,即:

# 随机生成一对私钥和公钥
secret_key = random.SystemRandom().randrange(1, n)
public_key = point_mul(G, secret_key)

# 用相同的k对两个不同的消息进行签名
signing_k = random.SystemRandom().randrange(1, n)
sig1_r, sig1_s = schnorr_sign('first_message', secret_key, signing_k)
sig2_r, sig2_s = schnorr_sign('second_message', secret_key, signing_k)
assert sig1_r == sig2_r
print('+ R used   = {:x}'.format(sig1_r))

# 根据签名和哈希重构私钥
e1 = sha256(sig1_r.to_bytes(32, byteorder="big") + bytes_point(public_key) + 'first_message'.encode())
e2 = sha256(sig2_r.to_bytes(32, byteorder="big") + bytes_point(public_key) + 'second_message'.encode())
d = ((sig1_s - sig2_s) * inv(e1 - e2, n)) % n

但是如果采用这种方法的话,我们的k应该是作为一个独立可控的参数出现的,这样我们才能传入相同的k实施这一攻击,即我们的schnorr_sign函数应该这么写:

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

但是我们本题中的schnorr_sign函数是这么写的:

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")

按照我们本题的这种写法,在生产k的时候本身就引入了msg,因此不可能在msg不同的情况下产生相同的k。所以说这一思路又行不通了,那么我们就只剩下第三种思路。

第三种思路需要我们在不知道私钥的情况下伪造出签名,我们分析一下不难发现,由于系统每次都允许用户先提交一次公钥再进行后续的操作,而且操作3还可以得到系统的公钥,那么如果我们提交(用户公钥 - 系统公钥)作为用户公钥来提交,系统再在操作2进行校验时,就会使用(用户公钥 - 系统公钥) + 系统公钥来进行校验,系统公钥被消去,即系统将使用用户公钥来进行校验,而用户公钥是我们自己生成的,显然我们知道其对应的用户私钥,那么我们很容易就可以计算出'WITHDRAW'的签名了。

整理一下上述思路,即我们的操作顺序为:

1. 随机生成一对usr_sk,usr_pk
2. 连接服务器,提交usr_pk
3. 使用usr_sk对'DEPOSIT'字符串进行签名,并将其提交至菜单选项1当中(这一步是为了比特币+1)。
4. 再次提交usr_pk
5. 选择菜单选项3,得到sys_pk
6. 计算point_sub(usr_pk,sys_pk)并提交
7. 使用usr_sk对'WITHDRAW'字符串进行签名,并将其提交至菜单选项2当中
8. 得到flag

将上述操作步骤写成exp如下:

import hashlib
import string
from base64 import *
from pwn import *
from schnorr import *

m1 = 'DEPOSIT'
m2 = 'WITHDRAW'
usr_pk = (114327674085560363590993327163840066309500593894278650456892267846105105547989, 109500385706600046295187892243946732955158496133501036041122596162143636261984)
usr_sk = 74314251512198093380740058910780830895178188526210019598065364316962239197930
str_usr_pk = str(usr_pk).replace("(",'').replace(")",'').replace("L",'')
str_usr_sk = str(usr_sk).replace("L",'')
str_m1_sig = schnorr_sign(m1,usr_sk)
str_m2_sig = schnorr_sign(m2,usr_sk)

r = remote('tcp.realworldctf.com',20014)
r.recvuntil('starting with ')
prefix = r.recvline().replace('n','')
dic = string.printable

def bypassPOW(prefix):
    for a in dic:
        for b in dic:
            for c in dic:
                for d in dic:
                    for e in dic:
                        x = prefix + a + b + c + d + e
                        assert len(x)==21
                        if hashlib.sha1(x).hexdigest()[::-1][:4]=='0000':
                            return x

payload = bypassPOW(prefix)
r.send(payload)       
r.recv()
r.recv()
r.sendline(b64encode(str_usr_pk))
r.recv()
r.sendline(b64encode('1'))
r.recv()
r.sendline(b64encode(str_m1_sig))
r.recv()
r.sendline(b64encode(str_usr_pk))
r.recv()
r.sendline(b64encode('3'))
r.recvuntil("us: ")
sys_pk = tuple(map(int,r.recvline().replace("(",'').replace(")",'').replace("L",'').replace("n",'').split(',')))
neg_sys_pk = tuple([sys_pk[0]] + [(-sys_pk[1])%p])
rogue_pk = point_add(usr_pk, neg_sys_pk)
str_rogue_pk = str(rogue_pk).replace("(",'').replace(")",'').replace("L",'')
r.recv()
r.sendline(b64encode(str_rogue_pk))
r.recv()
r.sendline(b64encode('2'))
r.recv()
r.sendline(b64encode(str_m2_sig))
r.interactive()

执行exp即可拿到flag:

rwctf{P1Ain_SChNorr_n33Ds_m0re_5ecur1ty!}

如果查阅资料&论文,我们也可以找到一篇名为《Key Aggregation for Schnorr Signatures》的关于密钥聚合的报告,在这份报告中介绍了一种名为rogue-key attack的攻击方式,和我们本题的攻击思路是一致的,说明了在本题中的这种针对key aggregation scheme的攻击方式是真实存在的,也和我们本次比赛的realworld的风格相契合:)。

 

参考

https://wstein.org/edu/2010/414/projects/novotney.pdf
https://eprint.iacr.org/2018/068.pdf
https://github.com/mvrcrypto/bitp0wn/blob/8431c7f8802ba60041385f20265be6d9c87f5525/signatures/r_exploit_schnorr.py
https://blockstream.com/2018/01/23/en-musig-key-aggregation-schnorr-signatures/

原文链接:https://www.anquanke.com/post/id/188174

本站声明:网站内容来源于安全客,如有侵权,请联系我们,我们将及时处理。

本文转为转载文章,本文观点不代表威客安全立场。

联系我们

15110186328

在线咨询:点击这里给我发消息

邮件:zhanglei@jinlongsec.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code
X