查看: 673|回复: 1

[Crypto] TetCTF 2020-yaecc

[复制链接]
发表于 2020-2-26 17:43:41 | 显示全部楼层 |阅读模式
题目描述如下:
Who knows the backdoor wins!
nc 207.148.119.58 7777
审计代码可知,题目模拟了一版ECDSA(NIST-p256 曲线)的实现,我们的任务是根据若干消息/签名对来求私钥,为了便于描述我们先描述一下本题用到的符号系统:
(R,S):签名
a:私钥
k:nonce
H:msg的哈希值
N:曲线的点群阶
在ECDSA中,有如下表达式成立:
R*a − S*k + H ≡ 0 (mod N)
根据ECDSA算法,当对消息进行签名时,nonce应当随机均匀的从区间[0,N)当中进行选择,以p256为例,N的大小应当为256比特,但是在本题当中,nonce只有240比特,因此我们可以考虑将我们本题当中的问题(根据消息/签名对求私钥)转化为格上的CVP问题
假设我们已经收集了D对消息/签名对,此时有:
Ri*a − Si*ki + Hi ≡ 0 (mod N) i=1,2,3,...,D
等式两边乘上Si的逆,得:
(Si^(-1))*Ri*a − ki + (Si^(-1))*Hi ≡ 0 (mod N)
设Ai = (Si^(-1))*Ri,Bi = -(Si^(-1))*Hi,整理得:
Ai*a ≡ Bi + ki (mod N)
即:
Ai*a - li*N = Bi + ki (li为整数)
将方程用向量形式表示如下:

TetCTF 2020-yaecc

TetCTF 2020-yaecc
其中(1/2**16)是根据256(a的比特数)-240(k的比特数)= 16计算而来。
对于每一个表达式Ri*a − Si*ki + Hi ≡ 0 (mod N)来讲,一对消息/签名对就可以提供私钥的16比特的信息,因此理论上来讲D(即消息/签名对的对数)= 256/16 = 16即可,在写脚本时我们收集的数量比这一理论值略多一些即可。
将上述推导写成SageMath代码形式如下:
from sage.all import *
from pwn import *
from hashlib import sha256
import os
from Crypto.Util.number import bytes_to_long

EC = EllipticCurve(
    GF(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff),
    [-3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b]
)
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
Zn = Zmod(n)
G = EC((0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
        0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5))
P = G
Q = EC((0xc97445f45cdef9f0d3e05e1e585fc297235b82b5be8ff3efca67c59852018192,
        0xb28ef557ba31dfcbdd21ac46e2a91e3c304f44cb87058ada2cb815151e610046))
pubkey = EC((50590195252452518804028762265927043036734617153869060607666882619539230027822,
        36611353725619757431858072740028832533174535444901899686884685372270344860185))

class DualEcDrbg(object):
    def __init__(self, seed):
        self.s = ZZ(bytes_to_long(seed))

    def next_bits(self):
        self.s = ZZ((self.s * P)[0])
        return ZZ((self.s * Q)[0]) & (2 ** 240 - 1)

def sign(private_key, message, rand):
    z = Zn(ZZ(sha256(message).hexdigest(), 16))
    k = Zn(rand.next_bits())
    assert k != 0
    K = ZZ(k) * G
    r = Zn(K[0])
    assert r != 0
    s = (z + r * private_key) / k
    assert s != 0
    return r, s

data = []
for _ in range(50):
    s = remote("207.148.119.58", 7777)
    m = eval(s.recvline())
    sig = eval(s.recvline())
    data.append((m, sig))
    s.close()
print len(data)
print data[0]
with open("data.txt", "w") as f:
    f.write(str(data))

size = 20
m = []
Ai = [-1]
Bi = [0]
r0, s0 = map(Zn, data[0][1])
z0 = Zn(ZZ(sha256(str(data[0][0])).hexdigest(), 16))
for i in range(size):
    message, sig = data[i+1]
    ri, si = map(Zn, sig)
    zi = z = Zn(ZZ(sha256(str(message)).hexdigest(), 16))
    A = - (s0 * ri) / (r0 * si)
    B = (z0 * ri) / (si * r0) - zi / si
    Ai.append(A)
    Bi.append(B)

Ai.append(0)
Bi.append(n//2^16)
m.append(Ai)
for i in range(size):
    m.append([0]*(i+1) + [n] + [0]*(size-i))

m.append(Bi)
m = Matrix(ZZ, m)

mLLL = m.LLL()

for irow, row in enumerate(mLLL):
    k0 = Zn(row[0])
    d = (s0*k0-z0)/r0
    if pubkey == ZZ(d)*G:
        print d
        break
    k0 = Zn(-row[0])
    d = (s0*k0-z0)/r0
    if pubkey == ZZ(d)*G:
        print d
        break

msg2 = b"I am admin"
rand = DualEcDrbg(os.urandom(16))
sig = sign(ZZ(d), msg2, rand)
s = remote("207.148.119.58", 7777)
s.sendline(str(sig))
ret = s.recvline()
print ret
执行脚本即可得到flag:
TetCTF{_0oops____Sm4ll_k_ru1n3d_th3_p4rty_}

温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
论坛交流群:672619046

0

主题

179

帖子

0

精华

解密专家

Rank: 16

学币
477
荣耀
0
rank
0
违规
0

神出鬼没

    发表于 2020-3-1 20:20:08 | 显示全部楼层
    支持学逆向论坛,资源不错!
    学逆向论坛-免费的逆向学习论坛
    微信公众号
    快速回复 返回顶部 返回列表