ECDSA: 谨慎处理 - Trail of Bits博客

椭圆曲线数字签名算法（ECDSA）是我们代码审查中常见的数字签名方案。它具有一些理想特性，但也非常脆弱。例如，几周前发布的LadderLeak展示了通过侧信道攻击恢复密钥的可行性，该攻击仅泄露不到1位的秘密随机数。

ECDSA非常脆弱，必须谨慎处理

本文将引导您了解：

• 利用ECDSA随机数偏置的各种方式
• 在实际中出现问题时攻击的简易程度
• 如何保护自己

您可能熟悉针对ECDSA的攻击。有些攻击很简单，有些涉及高级傅里叶分析和格数学。虽然这些攻击可能很复杂，但我希望本文能展示它们在实际中易于实现。事实上，即使您对格一无所知，阅读本文后，您将能够利用格攻击，用不到100行Python代码破解由轻微故障RNG生成的ECDSA签名。

数学免责声明：阅读本文需要熟悉数学群，认识到它们具有二元运算和群生成器。您不需要是椭圆曲线专家；只需知道椭圆曲线可用于形成数学群（因此具有加法和标量乘法概念）。熟悉格等其他数学概念有帮助，但不是必需的。

DSA入门

ECDSA是数字签名算法（DSA）的一种特定形式。DSA是一种常见的数字签名方案，由三个算法定义：密钥生成、签名和验证。密钥生成算法生成私钥和公钥；私钥负责创建签名；公钥负责验证签名。签名算法以消息和私钥为输入，产生签名。验证算法以消息、签名和公钥为输入，返回true或false，指示签名是否有效。

DSA定义在任何数学群上，只要离散对数问题在该群上困难，该方案就是安全的。通常使用的群是由乘法生成器g模p生成的阶q的乘法群，其中p和q都是素数。除了这个群，我们还有某个密码学安全哈希函数H。我们可以假设p、q、g和H都是公开的。

密钥生成首先从整数模q中随机选择一个值x。然后计算值y = gx mod p。私钥设置为x，公钥为y。签名密钥必须保密，因为这是允许创建签名的原因。

签名算法从消息m和密钥x产生签名。首先，生成乘法群的随机元素k（即随机数模q）。这称为随机数（nonce），在讨论攻击时很重要。然后，计算值r = (gk mod p) mod q和s = (k-1(H(m) + xr)) mod q。这里k-1是群逆元，H(m)是计算m的哈希并将结果解释为整数的结果。签名定义为对(r,s)。（注意：如果r或s值等于0，算法使用新的k值重新启动）。

验证算法接收签名(r,s)、消息m和公钥y作为输入。令ŝ = s-1，则当且仅当r,s ≠ 0且r = [(gH(m)yr)ŝ mod p] mod q时，算法输出true。此验证检查有效，因为gH(m)yr = gH(m)+xr = gks，因此(gH(m)yr)ŝ = gk = r。

如果数字签名方案不可伪造，则被认为是安全的。不可伪造性具有正式的密码学含义，但在高层次上，它意味着您无法在不知道密钥的情况下产生签名（除非您复制了已由密钥创建的现有签名）。DSA被证明在离散对数假设下是不可伪造的。

ECDSA

DSA定义在数学群上。当DSA与椭圆曲线群一起用作此数学群时，我们称之为ECDSA。椭圆曲线群由椭圆曲线点组成，这些点是满足方程y2 = x3 + ax + b的对(x,y)，对于某些a,b。对于本文，您只需要知道，使用模某个素数p的椭圆曲线，您可以定义一个有限群，这意味着您获得一个群生成器g（椭圆曲线点），以及加法和标量乘法运算，就像整数一样。由于它们形成有限群，生成器g将具有有限阶q。本文不会解释或要求您了解这些椭圆曲线运算的工作原理，但如果您好奇，我鼓励您在此处阅读更多关于它们的信息。

ECDSA的工作方式与DSA相同，只是群不同。密钥x仍然是整数模q的随机值。现在，公钥y仍然计算为y = gx，只是现在g是椭圆曲线点。这意味着y也将是某个模p椭圆曲线上的椭圆曲线点（之前，y是模p的整数）。另一个差异出现在我们计算值r的方式中。我们仍然生成随机随机数k，作为整数模q，就像之前一样。我们将计算gk，但同样，g是椭圆曲线点，因此gk也是。因此，我们可以计算(xk,yk) = gk，并设置r = xk mod q。现在，可以像之前一样计算s值，我们获得签名(r,s)，它将是整数模q。为了验证，我们需要调整我们计算r的方式略有不同。因此，像之前一样，我们计算值(gH(m)yr)ŝ，但现在该值是椭圆曲线点，因此我们取该点的x坐标并将其与我们的r值模q进行比较。

从重复使用的随机数恢复密钥

现在我们了解了ECDSA是什么及其工作原理，让我们展示其脆弱性。再次强调，由于它是数字签名方案，密钥绝不能透露给除消息签名者之外的任何人。但是，如果签名者曾经发布签名并同时发布他们使用的随机数，攻击者可以立即恢复密钥。假设我发布消息m的签名(r,s)，并不小心透露我使用了随机数k。由于s = (k-1(H(m) + xr))，我们可以轻松计算密钥：

s = (k-1(H(m) + xr))
ks = H(m) + xr
ks – H(m) = xr
x = r-1(ks – H(m))

因此，签名者不仅需要保持他们的密钥秘密，还必须保持他们生成的所有随机数秘密。

即使签名者保持每个随机数秘密，如果他们不小心重复单个随机数（即使对于不同的消息），密钥也可以立即恢复。令(r,s1)和(r,s2)是在消息m1和m2（分别）上由相同随机数k产生的两个签名——由于它们具有相同的随机数，r值将相同，因此攻击者很容易检测到：

s1 = k-1(H(m1) + xr) 和 s2 = k-1(H(m2) + xr)
s1 – s2 = k-1(H(m1) – H(m2))
k(s1 – s2) = H(m1) – H(m2)
k = (s1 – s2)-1(H(m1) – H(m2))

一旦我们使用上述公式恢复随机数k，我们就可以通过执行先前描述的攻击来恢复密钥。

让我们花点时间消化这一点。

如果签名的随机数曾经被泄露，密钥可以立即恢复，这破坏了我们的整个签名方案。此外，如果两个随机数曾经重复，无论消息是什么，攻击者都可以轻松检测到并立即恢复密钥，再次破坏我们的整个方案。这非常脆弱，而这些只是简单的攻击！

从泄露和偏置随机数攻击ECDSA

事实证明，即使泄露随机数的一小部分也可能对签名方案非常有害。1999年，Howgrave-Graham和Smart的工作展示了使用格攻击从部分随机数泄露中破解DSA的可行性。后来，Nguyen和Shparlinski改进了他们的工作，并能够通过仅知道100个签名中每个随机数的三位来恢复160位DSA（这里160位指p）的密钥，后来是ECDSA。

后来，Mulder等人能够对部分随机数泄露执行更多攻击。他们使用了基于Bleichenbacher工作的不同的、基于傅里叶变换的攻击。使用这些技术，并仅知道4,000个签名中每个随机数的五位，他们能够从384位ECDSA恢复密钥，并利用他们的技术破解在智能卡上运行的384位ECDSA。

您可能听说过Minerva攻击：利用了几个时序侧信道来恢复部分随机数泄露，并在各种目标上执行了这些格攻击。有了足够的签名，他们甚至能够在仅泄露随机数大小的情况下成功攻击目标！

更糟糕的是，几周前，LadderLeak攻击进一步改进了傅里叶分析攻击，现在如果仅泄露随机数的1位，就可以恢复ECDSA密钥！事实上，单比特可以以小于1的概率泄露，因此攻击者技术上需要少于1位。这被用来攻击几个OpenSSL版本中Montgomery阶梯中的非常小的泄露。

再次，让我们消化这一点。即使仅泄露随机数的几位——或者进一步，即使仅泄露随机数的大小——或者进一步，如果泄露随机数的一位——那么，大多数情况下，通过观察足够的签名，可以破坏整个签名方案。这非常脆弱！

除此之外，即使您设法保持所有随机数秘密且从不重复随机数，并且从不向攻击者泄露任何随机数位，您仍然没有完全保护！Breitner和Heninger的工作表明，稍微故障的随机数生成器（RNG）也可以通过利用格攻击灾难性地破坏您的方案。具体来说，当使用256位ECDSA时，如果您的RNG在随机数中引入仅4位的偏置，您的签名方案可以通过格攻击完全破坏，即使我们不知道那些偏置值是什么。

这些攻击涉及一些复杂的数学。像大多数密码攻击一样，它们将一系列ECDSA签名表述为另一个困难的数学问题。在这种情况下，该问题称为隐藏数问题。隐藏数问题已被其他研究人员广泛研究，因此有许多技术和方法来解决它。这意味着一旦我们弄清楚如何将一系列ECDSA签名塑造成隐藏数问题的实例，我们就可以应用现有技术来找到ECDSA密钥。

从坏随机数破解ECDSA

现在，傅里叶分析、隐藏数问题和格攻击比日常密码学更复杂，它们似乎令人生畏。然而，这些攻击涉及复杂数学的事实可能会欺骗一些人认为它们在实际中很难实现。事实并非如此。正如我在开头提到的，我将教您如何使用少于100行Python代码实现这些攻击。此外，要执行此攻击，您实际上不需要了解隐藏数问题或格。我们唯一需要的格组件是访问LLL算法。但是，我们可以将此算法视为黑盒；我们不需要理解它如何工作或它在做什么。

我们将攻击由坏随机数（即坏RNG）产生的签名。具体来说，这些随机数将具有固定前缀，意味着它们的最高有效位始终相同。（即使固定位不是最高有效位，攻击仍然有效，但这最容易理解）。使用LLL时，我们只需要知道我们将输入一个值矩阵，算法将输出一个新值矩阵。如果我们以特定方式使用一系列ECDSA签名构建矩阵，LLL将输出一个允许我们恢复ECDSA私钥的矩阵。更具体地说，由于我们构建此矩阵的方式，LLL的输出行之一将包含所有签名的随机数。（需要更复杂的数学来理解原因，因此我们不会在这里讨论，但如果您好奇，请参见本文的第4节）。一旦我们恢复随机数，我们可以使用上述基本攻击来恢复密钥。

要执行攻击，我们需要在python中访问ECDSA和LLL库。我选择了这个ECDSA库，它允许我们输入自己的随机数（因此我们可以从坏RNG输入随机数以测试我们的攻击），和这个LLL库。我们将在NIST P-256椭圆曲线上执行此攻击，从最简单的攻击形式开始：我们获得两个仅由128位随机数生成的签名。首先，我们生成我们的签名。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import ecdsa
import random

gen = ecdsa.NIST256p.generator
order = gen.order()
secret = random.randrange(1,order)

pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)

nonce1 = random.randrange(1, pow(2,127))
nonce2 = random.randrange(1, pow(2,127))

msg1 = random.randrange(1, order)
msg2 = random.randrange(1, order)

sig1 = priv_key.sign(msg1, nonce1)
sig2 = priv_key.sign(msg2, nonce2)

现在我们有了签名，我们需要制作我们将输入LLL算法的矩阵：

我们将输入LLL算法的矩阵

这里N是NIST P-256的阶（上面代码片段中的ord），B是我们随机数大小的上限（在此示例中为2128，因为两个随机数都只有128位大小）；m1和m2是两个随机消息；且(r1, s1)和(r2,s2)是两个签名对。在我们的python代码中，我们的矩阵将如下所示（这里modular_inv是计算模N逆元的函数）：

1
2
3
4
5
6
7
8

r1 = sig1.r
s1_inv = modular_inv(sig1.s, order)
r2 = sig2.r
s2_inv = modular_inv(sig2.s, order)

matrix = [[order, 0, 0, 0], [0, order, 0, 0],
[r1 * s1_inv, r2 * s2_inv, (pow(2,128)) / order, 0],
[msg1 * s1_inv, msg2 * s2_inv, 0, pow(2,128)]]

现在我们将此矩阵输入黑盒LLL算法，它将返回一个新矩阵给我们。由于某些原因，此返回矩阵的行之一将包含用于生成两个签名的随机数。如果我们更多地了解算法实际在做什么，我们可能可以预测随机数将在哪里。但由于我们不关心细节，我们将只检查返回矩阵中的每一行，看看是否能找到密钥。记住，我们已经展示了如何在拥有随机数k后恢复私钥。具体来说，我们计算r-1(ks – H(m))。真实世界中的攻击者将有权访问这些签名对应的公钥。因此，为了确定我们是否找到了正确的私钥，我们将计算其对应的公钥并将其与已知公钥进行比较。攻击将如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import olll

new_matrix = olll.reduction(matrix, 0.75)
r1_inv = modular_inv(sig1.r, order)
s1 = sig1.s

for row in new_matrix:
    potential_nonce_1 = row[0]
    potential_priv_key = r1_inv * ((potential_nonce_1 * s1) - msg1)

    # 通过比较其公钥与实际公钥来检查是否找到私钥
    if ecdsa.ecdsa.Public_key(gen, gen * potential_priv_key) == pub_key:
        print("found private key!")

我应该提到，此基本攻击有明显的失败率。如果您运行呈现给您的代码，您也会注意到这一点。但再次强调，出于本文的目的，不要担心这些细节。此外，如果您使用更多签名执行相同的攻击，此失败率应该会降低。

希望此时我已经展示了为什么这些攻击不那么复杂。我们能够仅从两个签名恢复密钥，并且我们没有做任何过于复杂的事情。也就是说，你们中的一些人可能会争辩说，能够攻击仅具有128位随机数的签名并不那么有趣。因此，让我们继续讨论更现实的攻击。

利用真实世界的ECDSA错误

您可能听说过Yubikeys中生成的随机性最近的一个错误。本质上，坏随机性导致多达80位的随机数固定为相同的值。攻击此真实世界错误不会比我们刚才执行的攻击困难得多，只是我们不知道固定的80位值是什么（在前面的示例中，我们知道固定的128位都设置为0）。为了克服这一点，我们需要向攻击添加一个技巧。

想象我们接收一系列签名，其随机数具有80个固定位。为便于解释，我们将假设这80位是最高有效位（如果情况并非如此，攻击仍然可行；您只需通过将每个签名乘以2的幂来将固定位移动到最高有效位）。即使我们不知道这80位是什么，我们知道如果减去任何两个随机数，它们差异的80个最高有效位都将为零。因此，我们将执行与上述相同的攻击，只是使用我们的签名值相减。具体来说，给定一组n个签名和消息，我们将构建以下矩阵：

当随机数偏置未知时我们将输入LLL算法的矩阵

这次，我们将再次将此矩阵输入LLL并接收一个新矩阵回来。但是，由于我们从该矩阵中的每个条目中减去了第n个值，而不是接收一行充满随机数，我们实际上将接收一行每个随机数与第n个随机数之间的差异。换句话说，从LLL返回的矩阵将给我们值k1 – kn，签名1和n的随机数之间的差异。需要一些代数操作，但我们仍然可以使用以下公式从此值恢复密钥：

s1 = k1-1(m1 + xr1) 和 sn = kn-1(mn + xrn)
s1k1 = m1 + xr1 和 snkn = mn + xrn
k1 = s1-1(m1 + xr1) 和 kn = sn-1(mn + xrn)
k1 – kn = s1-1(m1 + xr1) – sn-1(mn + xrn)
s1sn(k1 – kn) = sn(m1 + xr1) – s1(mn + xrn)
s1sn(k1 – kn) = xsnr1 – xs1rn + snm1 – s1mn
x(s1rn – snr1) = snm1 – s1mn – s1sn(k1 – kn)
密钥 = x = (rns1 – r1sn)-1 (snm1 – s1mn – s1sn(k1 – kn))

有了所有这些上下文，让我们利用Yubikey错误。如果签名是由具有80个固定位的随机数产生的，我们只需要五个签名来恢复密钥。我们将使用n = 6构建上述矩阵以减少错误率：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# 生成80个最高有效位，随机数必须小于阶
yubikey_fixed_prefix = random.randrange(2**176, order)

msgs = [random.randrange(1, order) for i in range(6)]
nonces = [random.randrange(1, 2**176) + yubikey_fixed_prefix for i in range(6)]
sigs = [priv_key.sign(msgs[i],nonces[i]) for i in range(6)]

matrix = [[order, 0, 0, 0, 0, 0, 0],
[0, order, 0, 0, 0, 0, 0],
[0, 0, order, 0,