2024西湖论剑

发表于 更新于

很巧地，DSA在比赛前一天刚好学习了，然后第二天就是ECDSA。挺费力，最后是解出了一题。其他的看不了，根本没啥时间。

Or1cle

题目描述

给了一个交互，源码啥的都没给，然后就猜呗。有签名，sign，和gift这些功能。
gift没发现有什么用，但是出题人说这是有用的，增加增加签名次数，但不懂，等别人wp吧。签名功能上也没发现有什么问题。
但sign这个就有问题了，只能输入定长的数据，输入别的内容会爆源码，从这里才发现签名里面的nonce由异或做的，可以找到maple写的有个类似的题目TSJ CTF 2022 WriteUps | 廢文集中區 (maple3142.net)。

但我不是用的maple的办法，在后面发现了一个用格的师傅写了从TSJCTF & Codegate的两道crypto题中学习新姿势 - 跳跳糖 (tttang.com)，用格还是很方便修改脚本的。
然后就跟xenny有关，在签名那里试着用’xenny’这个字符串做签名居然不行，于是就猜测题目的意思是找到私钥，然后制作一个’xenny’的签名进而得到flag。

解题思路

第一部分是交互拿5次数据，（为什么5次，因为爆到第六次居然出了部分源码了，没了就。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# %%
from pwn import *
import hashlib
from fastecdsa.curve import secp256k1 as CURVE
from fastecdsa.curve import secp256k1


r = remote("xxxxxx","xxxxxx")
# context.log_level="debug"
# r.interactive()


def inter(x):
    r.recvuntil(b'exit\n')
    r.sendline(b'1')
    r.sendline(str(x).encode())
    z = int(hashlib.sha256(str(x).encode()).hexdigest(),16)
    digs = str(r.recvline()).split(": ")[1].replace("\\n'","").replace(" ","")
    t,s = int(digs[:64],16),int(digs[64:],16)
    return (z,t,s)

# print(inter(1))

lis = []
for i in range(5):
    lis.append(inter(i))
# print(lis)

第二部分用了格攻击，也是幸运吧，5次交互的数据居然够用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def attack(lis):
    m = 5
    n = 257
    
    UL = matrix.identity(m) * CURVE.q
    UR = matrix.zero(m, n)
    DR = matrix.identity(n)

    main_mat = []
    for i in range(5):
        z, r, s = lis[i]
        vec = [-(s-1)*z]
        zbin = bin(z)[2:].zfill(256)
        assert len(zbin) == 256
        zbin = zbin[::-1]
        for i in range(256):
            tmp = (2^i) * (r + (2*int(zbin[i])-1) * s) % (CURVE.q)
            vec.append(tmp)
        main_mat.append(vec)
    mat = matrix(ZZ, main_mat).T

    M = block_matrix(ZZ, [[UL, UR], [mat, DR]])
    M = M.LLL()
    # print(M)
    for row in M:
        if row[5] == 1 and set(row[6:]).issubset([0, 1]):
            print('Find solution!')
            d = int(''.join(list(map(str, row[6:][::-1]))), 2)
            return d

d = attack(lis)
# print(d)

第三部分就是按照给出的签名和验证进行签名，费老半天了，用sage的椭圆曲线跑不出来不知道怎么回事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# %%
P = d*secp256k1.G
def signature(msg):
    h = int(hashlib.sha256(msg).hexdigest(),16)
    k = h^^d
    r = (k*secp256k1.G).x
    s = inverse_mod(k,secp256k1.q) * (h + r*d) % secp256k1.q
    return '%064x%064x' % (r, s)

msg = b'xenny'
m = signature(msg)
print(m)

r.interactive()
r.sendline(b'2')
r.recvline()
r.sendline(m.encode())

总结

只做出一道题，很费力，还是太菜了。