Breaking Ecdsa From Nonce Bits
如果对HNP不太了解,可以先看一下我的另一篇文章HNP
Preview
先简单回顾一下HNP和ECDSA。
Hidden Number problem(HNP) :有一个对外保密的数α和对外公开的模数n。随机的选择ti计算si=αti mod n,并且泄漏出si的最高有效位,就可以利用CVP的方法去恢复α。
ECDSA :在有限域Fp上选择椭圆曲线E(Fp),以及阶为n的子群的基点G。私钥为0≤d<n,公钥为dG=Q。 签名:
- 选择nonce为随机数k
- 计算明文的hash,h=Hash(m)
- 计算r=(kG)x,x表示kG的x坐标
- 计算s=k−1⋅(h+d⋅r) mod n
- 签名为(r,s)
ECDSA as a HNP
由ECDSA的签名过程,重写一下公式。
−s−1⋅h+k≡s−1⋅r⋅d(modn)
与HNP问题对应一下,令
α=dti=s−1⋅rai=s−1⋅h
由于nonce相较于ai来说较小,所以
MSBα,k(ti)=MSBk(α⋅ti mod n)=MSBk(d⋅s−1⋅r)=MSBk(−ai+k)=n−ai
Solving the HNP with lattices
在之前讲的HNP中,Boneh and Venkatesan给出了这样的格
[n00⋯000n0⋯00⋮⋯000⋯n0t0t1t2⋯tm−11/n]
但是在后来的研究中Kannan给出了改进后的格
[n00⋯0000n0⋯000⋮⋮000⋯n00t0t1t2⋯tm−12ℓ/n0a0a1a2⋯am−102ℓ]
ℓ是nonce的位长度,2ℓ就是nonce的上界。
在这个格中存在一个向量
vk=(k0,k1,…,km−1,2ℓ⋅α/n,2ℓ)
用到数第二行向量乘α加上最后一行,tiα+ai=−ai+ki+ai=ki。
这个向量在格中是很短的。它的模∣∣vk∣∣≤√m+2⋅2ℓ。但是格中还有一个更短的向量
(0,0,⋯,0,2ℓ,0)
所以在利用LLL算法之后,要找的向量并不再第一行。
Example & Demo
from sage.all import *
from hashlib import sha1
import time
# use secp128r1 curve to test
# The parameters:
_p = 0xfffffffdffffffffffffffffffffffff
_b = 0xe87579c11079f43dd824993c2cee5ed3
_a = -0x3
_Gx = 0x161ff7528b899b2d0c28607ca52c5b86
_Gy = 0xcf5ac8395bafeb13c02da292dded7a83
order = 340282366762482138443322565580356624661
E = EllipticCurve(GF(_p), [_a, _b])
G = E(_Gx, _Gy)
# The Lattice attack paramters
# n = ceil(log(order, 2))
# k = ceil(sqrt(n)) + ceil(log(n, 2))
# print(f"The number of significant bits = {k}")
# m = 2*ceil(sqrt(n))
m = 24
print(f"about {m} signatures")
# Ecdsa sign Algorithm
def EcdsaSign(number, k):
r = ZZ((k*G)[0])
s = (inverse_mod(k, order) * (number + d*r)) % order
return (ZZ(r), ZZ(s))
# This function is not used in this test
def string_to_number(str_msg:str, hash:callable):
"""parameters:
str_msg: the massage be converted to number
hash: callable hash function
"""
return int(hash(str_msg.encode()).hexdigest(), 16)
def generator():
"""Return a_i , t_i , msb, h
a_i = s^(-1) * h
t_i = s^(-1) * r
msb = -a_i % order
h: the message to be signed
"""
h = randint(0, 2**128) % order
k = randint(1, 2**120) % order
r, s = EcdsaSign(h, k)
a_i = (inverse_mod(s, order) * h) % order
t_i = (inverse_mod(s, order) * r) % order
return t_i, a_i, -a_i % order, h
## Solving the HNP with Boneh and Venkatesan's lattice
def build_basis(oracle_inputs):
"""Returns a basis using the HNP game parameters and inputs to our oracle
"""
basis_vectors = []
for i in range(m):
p_vector = [0] * (m+1)
p_vector[i] = order
basis_vectors.append(p_vector)
basis_vectors.append(list(oracle_inputs) + [QQ(1)/QQ(order)])
return Matrix(QQ, basis_vectors)
def approximate_closest_vector(basis, v):
"""Returns an approximate CVP solution using Babai's nearest plane algorithm.
"""
BL = basis.LLL()
G, _ = BL.gram_schmidt()
_, n = BL.dimensions()
small = vector(ZZ, v)
for i in reversed(range(n)):
c = QQ(small * G[i]) / QQ(G[i] * G[i])
c = c.round()
small -= BL[i] * c
return (v - small).coefficients()
def Boneh_Venkatesan_method():
# print("[+] using Boneh and Venkatesan's method to recover the private key")
inputs = []
answers = []
for _ in range(m):
t_i, a_i, msb, h = generator()
inputs.append(t_i)
answers.append(msb)
time0 = time.time()
lattice = build_basis(inputs)
u = vector(ZZ, list(answers) + [0])
v = approximate_closest_vector(lattice, u)
recovered_alpha = (v[-1] * order) % order
spend = time.time() - time0
# print("spend %.3fs" % spend)
# assert recovered_alpha == d
if recovered_alpha == d:
# print("Recovered alpha! Alpha is %d" % recovered_alpha)
return 1, spend
else:
# print("fault to recover!")
return 0, spend
def build_Kannan_basis(t_i, a_i):
"""Returns a basis using the HNP game parameters and inputs to our oracle
"""
basis_vectors = []
for i in range(m):
p_vector = [0] * (m+2)
p_vector[i] = order
basis_vectors.append(p_vector)
basis_vectors.append(list(t_i) + [QQ(2**120)/QQ(order)] + [0])
basis_vectors.append(list(a_i) + [0] + [QQ(2**120)])
return Matrix(QQ, basis_vectors)
def Kannan_method():
# print("\n[+] using Kannan's method to recover the private key")
inputs = []
answers = []
hs = []
for _ in range(m):
t_i, a_i, msb, h = generator()
inputs.append(t_i)
answers.append(a_i)
hs.append(h)
time0 = time.time()
lattice = build_Kannan_basis(inputs, answers)
# print("Solving SVP using lattice with basis:\n%s\n" % str(lattice))
L = lattice.LLL()
# print(L)
ks = L[1]
spend = time.time() - time0
# print("spend %.3fs" % spend)
if (-answers[0] + ZZ(ks[0])) % order == (inputs[0] * d) % order:
# print(f"Recovered nonce! {ks}")
recovered_d = ( (-answers[0] + ZZ(ks[0])) * inverse_mod(inputs[0], order) ) % order
assert recovered_d == d
# print("Recovered private key! private key is %d" % recovered_d)
return 1, spend
else:
# print("fault to recover!")
return 0, spend
if __name__ == "__main__":
method1_spend = []
method1_success = 0
method2_spend = []
method2_success = 0
for _ in range(20):
d = randint(1, order-1)
# print(f"the privet key is {d}")
pubkey = d*G
flag0, spend0 = Boneh_Venkatesan_method()
flag1, spend1 = Kannan_method()
method1_success += flag0
method2_success += flag1
method1_spend.append(spend0)
method2_spend.append(spend1)
print("[+] Boneh_Venkatesan_method:")
print(f"successed: {method1_success}/20\ntime spend: {sum(method1_spend)/20}")
print("[+] Kannan_method:")
print(f"successed: {method2_success}/20\ntime spend: {sum(method2_spend)/20}")
test result
-
当k的位数很小,比如只有几十位长甚至几位长,然后调小m,会发现Boneh_Venkatesan_method和Kannan_method的时间相差不大,但是前者的正确率更高。
-
当k的位数比较大,比如有一百多甚至一百二十多,为了保证正确率需要调大m,这个时候Kannan_method的正确率以及速度都比Boneh_Venkatesan_method要表现的好。
当然我这里只是20次为一组,测试结果肯定是不太准确的。
Reference
- On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem by Martin R. Albrecht and Nadia Heninger
- Intended Solution to NHP in GxzyCTF 2020 by Soreat_u