menu badmonkey's blog
more_vert
chevron_right 首页 » Crypto » 正文
ECDSA_SVP_Attack
2020-04-05 | Crypto | 暂无评论 | 229 次阅读 | 620字

ECDSA_SVP_Attack

很有意思的一个点,之前做cryptoals的时候又遇到类似的点,但是只是简单了解了一下,没想到真的会有这样的漏洞,而且还是在2019年发现的,只能说太牛x了.
利用点,ECDSA中随机数k的选择不同,导致k的大小有差异,从而导致了在计算 sig中的 r 所用的时间也会不同,利用时间来判断k的位数,进而利用lattice进行分析和攻击.符号具体含义参考ECDSA实现过程

$$s \equiv k^{-1}( H(m + dr ) \mod p $$

两边同时乘$s^{-1}$得到下面的式子

$$ k \equiv \underbrace{s^{-1} \cdot H(m)}_{A} + \underbrace{s^{-1} \cdot r }_{B} \cdot d \mod p $$

进一步得到

$$ k = A + B \cdot d + n \cdot p,n \in Z$$

这样可以根据$A,B,p$构造格子,使得$k$在格子里,利用点在于如果$k$很小,对格子适当扩展可以用LLL算法求出$k$,进而求出$d$,接下来就可以伪造签名了!构造的格子如下

lattice

前$t$列其实是原始的格子,后面两列是用于攻击$d$所构造出来的.如果通过LLL算法算出的最短向量恰好是(实际上并不是最短向量,而是第二短,不过也可以近似看做SVP问题...

$$(k_1,k_2,\cdots k_t,Kd/p,K)$$

已知$p$的情况下,我们是可以算出$d$的,因为K是我们设定的值.那么怎么设定$K$呢?
实际上只需要考虑等式$(4)$所表示的向量就可以了,只需要让它比较小,小于其他行的范式即可.下面这些等式能够满足的话,就说明$(4)$是足够小的

$$\sqrt{ A_1^2 +A_2^2 + \cdots + A_t^2+K^2} \ > \ \sqrt{ k_1^2 +k_2^2 + \cdots + k_t^2+(Kd/p)^2+K^2} $$
$$\sqrt{ B_1^2 +B_2^2 + \cdots + B_t^2+(Kd/p)^2} \ > \ \sqrt{ k_1^2 +k_2^2 + \cdots + k_t^2+(Kd/p)^2+K^2} $$
$$ p \ > \ \sqrt{ k_1^2 +k_2^2 + \cdots + k_t^2+(Kd/p)^2+K^2} $$

$(5),(6)$显然是满足的,因为$A_i,B_i$都是很大的(p只有128位,hash后的是64位hex,约等于200多位,所以只需要考虑$(7)$即可,下面对等式$(7)$,进一步分析

$$\sqrt{ k_1^2 +k_2^2 + \cdots + k_t^2+(Kd/p)^2+K^2} \le \sqrt {t \cdot \max(k_1,k_2,\cdots k_t)^2+(Kd/p)^2+K^2} $$
由于$k_i$的位数比$p$要低好几位,所以$ \max(k_1,k_2,\cdots k_t)^2 < p^2$,即便有$t$,两者也不是一个数量级的,由于$d$有很大概率是和$p$一个数量级的,所以原式很大可能上为$\sqrt {t \cdot \max(k_1,k_2,\cdots k_t)^2+K^2+K^2}$,为了保持向量的整齐度??,很容易想到$K$的位数应该和$k_i$一个数量级,于是有$K$应该设置成和$k_i$一个数量级

总的思路就是将问题转换成SVP问题求解(最短向量是$(0,0,0,\cdots,K,0)$,第二短才是利用点),实际上这种问题也可以转换成CVP问题,下次再整理CVP的解法(整体思路是一样的.),下面简单实现一下ECDSA的攻击流程.

from hashlib import *
p = random_prime(2^128)
R = GF(p)
E = EllipticCurve(R,[-3,1])
P = E.random_element()
d = ZZ(R.random_element())
Q = d*P
username = b'badmonkey'
Hm = int(sha256(username).hexdigest(),16)
ns = 50
ks = []
A = []
B = []
for i in range(0, ns):
    k = ZZ(R.random_element())>>5
    ks += [k]
    r,_,_ = k*Q
    s = 1/R(k)*(Hm +d*r)
    A += [1/s * Hm]
    B += [1/s * r]
K = p>>5
# 单位矩阵,第一个参数指定作用域,第二个参数规模
X = p*identity_matrix(QQ,ns)
# 装置,构造倒数第二列
Z = matrix(QQ, [0] * ns + [K/p] + [0]).transpose()
# 倒数第一列
Z2 = matrix(QQ, [0] * (ns+1)+ [K]).transpose()
# 拼接操作
Y = block_matrix([[X],[matrix(QQ, B)], [matrix(QQ, A)]])
# 再次拼接
Y = block_matrix([[Y, Z,Z2]])
# print(Y)
Y = Y.LLL()
# print(Y[0])
for i in range(ns+2):
    if Y[i][-1] == K:
        print(Y[i][-2]*p/K)
    elif Y[i][-1] == -K:
        print(-Y[i][-2]*p/K)
print (d)
print(-d%p)

参考链接

tpm

发表评论
暂无评论
textsms
account_circle
email
link
arrow_back 上一篇
arrow_forward 下一篇