Solana/私钥, 公钥与地址/私钥的密码学解释(中篇)

同学们, secp256k1 与 ecdsa 签名算法现在已经被广泛用于许多系统中了. 我知道椭圆曲线在密码学中有优势, 因为它们可以在较小的密钥长度下提供更高的安全性. 但是, 这可能意味着什么呢?

从最近的新闻来看, 它似乎有了一些问题. 美国国家标准与技术研究院认为 secp256k1 存在一些安全风险, 已经不建议使用, 作为替代, 美国建议使用另一条名为 secp256r1 的椭圆曲线. 另一方面, 比特币自身也在改变, 比特币在 2021 年引入了一种叫做 schnorr 的签名算法来尝试替代 ecdsa.

是因为算法本身的问题还是其他因素导致 secp256k1 + ecdsa 不再受追捧? 我们来尝试探究下隐藏在其之下的深层原因.

随机数重用攻击

因为比特币的原因, secp256k1 椭圆曲线以及 ecdsa 签名算法变得无人不知, 无人不晓. 但其实在比特币之前, 它们也并非无人问津. 例如在 playstation 3 时代, 索尼就使用存储在公司总部的私钥将其 playstation 固件标记为有效且未经修改. Playstation 3 只需要一个公钥来验证签名是否来自索尼. 但不幸的是, 索尼因为他们糟糕的代码实现而遭到了黑客的破解, 这意味着他们今后发布的任何系统更新都可以毫不费力地解密.

在 fail0overflow 大会上, 黑客展示了索尼 ecdsa 的部分代码, 发现索尼让随机数的值始终保持 4, 这导致了 ecdsa 签名步骤中的随机私钥 k 始终会得到相同的值. Ecdsa 签名要求随机数 k 是严格随机的, 如果重复使用 k, 将直接导致私钥泄露. 这个攻击并不难, 因此小伙子们快来挑战一下吧!

def get_random_number():
  # Chosen by fair dice roll. Guaranteed to be random.
  return 4

例: 有以下信息

  • 信息 m₁, 及其签名 (r₁, s₁)
  • 信息 m₂, 及其签名 (r₂, s₂)
  • 信息 m₁ 和 m₂ 使用相同的随机数 k 进行签名, k 的具体数据则未知

求私钥 prikey.

答:

s₁ = (m₁ + prikey * r₁) / k
s₂ = (m₂ + prikey * r₂) / k = (m₂ + prikey * r₁) / k
s₁ / s₂ = (m₁ + prikey * r₁) / (m₂ + prikey * r₁)
prikey = (s₁ * m₂ - s₂ * m₁) / (s₂ - s₁) / r₁

这里有一个实际的例子可以帮助大家更直观的理解如何通过两个使用相同随机数 k 的签名来还原私钥.

import pabtc

m1 = pabtc.secp256k1.Fr(0x72a963cdfb01bc37cd283106875ff1f07f02bc9ad6121b75c3d17629df128d4e)
r1 = pabtc.secp256k1.Fr(0x741a1cc1db8aa02cff2e695905ed866e4e1f1e19b10e2b448bf01d4ef3cbd8ed)
s1 = pabtc.secp256k1.Fr(0x2222017d7d4b9886a19fe8da9234032e5e8dc5b5b1f27517b03ac8e1dd573c78)

m2 = pabtc.secp256k1.Fr(0x059aa1e67abe518ea1e09587f828264119e3cdae0b8fcaedb542d8c287c3d420)
r2 = pabtc.secp256k1.Fr(0x741a1cc1db8aa02cff2e695905ed866e4e1f1e19b10e2b448bf01d4ef3cbd8ed)
s2 = pabtc.secp256k1.Fr(0x5c907cdd9ac36fdaf4af60e2ccfb1469c7281c30eb219eca3eddf1f0ad804655)

prikey = (s1 * m2 - s2 * m1) / (s2 - s1) / r1
assert prikey.x == 0x5f6717883bef25f45a129c11fcac1567d74bda5a9ad4cbffc8203c0da2a1473c

心脏点攻击

Invalid curve attacks (心脏点攻击) 指攻击者通过生成不在标准曲线上的点, 通过这种方式绕过签名验证, 密钥生成, 或者其他基于曲线的操作.

每个公钥实际上是曲线上的一个点, 私钥是一个标量值, 通过标量乘法操作与基点生成公钥.

在签名过程中, 攻击者可以通过某种方式构造一个无效的公钥. 该无效公钥与攻击者的私钥之间存在某种数学关系(例如, 攻击者通过伪造一个无效的公钥进行签名), 这使得攻击者能够生成一个看似有效的签名. 正常情况下, 签名验证算法会检查公钥是否在 secp256k1 曲线范围内. 如果公钥无效, 系统应该拒绝该签名. 但是, 假设系统没有进行充分的曲线点有效性检查, 攻击者可能会提交一个包含无效公钥和伪造签名的请求. 在某些情况下, 系统可能会错误地接受这个无效签名, 认为它是合法的. 攻击者的签名可能会通过系统的检查, 导致恶意的交易或操作被错误地认为是有效的, 从而执行某些非法操作, 比如转移资金或修改数据.

一个现实中的例子是 openssl 中的椭圆曲线验证漏洞. 2015 年, openssl 的一个版本(1.0.2 之前的版本)存在一个椭圆曲线验证漏洞. 攻击者可以通过构造一个无效的椭圆曲线点并将其用作公钥, 利用 openssl 的某些漏洞绕过验证, 进而攻击使用该库的系统. 这个漏洞被称为 cve-2015-1786, 它允许攻击者通过伪造无效的公钥来绕过签名验证. 同样的问题也曾发生在 bitocin core 使用的 ecdsa 库中, 早期版本的库没有对椭圆曲线点进行足够的检查.

在这个漏洞被修复之前, 攻击者可以在不进行正确验证的情况下, 绕过系统对曲线有效性的检查, 从而导致可能的拒绝服务或其他安全问题.

交易延展性攻击

Mt.Gox(门头沟) 一度是世界上最大的比特币交易所. 该公司总部位于东京, 估计 2013 年占比特币交易量的 70%. 2014 年, 门头沟交易所被黑客攻击, 造成了约 85 万枚比特币的损失. 在门头沟事件中, 黑客所采用的是一种名为交易延展性攻击(transaction malleability attack)的手法.

此次攻击的具体过程如下: 攻击者首先在门头沟发起一笔提现交易 a, 接着在交易 a 被确认之前通过篡改交易签名, 使得标识一笔交易唯一性的交易哈希发生改变, 生成伪造的交易 b. 之后, 交易 b 被区块链确认, 而交易所则收到了交易 a 失败的信息. 交易所误认为提现失败从而重新为攻击者构造一笔新的提现交易.

要使得攻击成立, 其核心是攻击者能够修改交易的签名部分(如输入的签名)或者其他非关键的字段, 从而改变交易的哈希值, 但不会改变交易的实际内容.

巧合的是, secp256k1 + ecdsa 确实存在一种十分便捷的方式, 使得攻击者可以修改签名结果的同时仍然能通过签名验证. 如果我们分析 ecdsa 验签算法, 会发现验签结果和签名 (r, s) 中的 s 值的符号是无关的. 为了验证这一点, 我们编写如下测试代码:

import pabtc

prikey = pabtc.secp256k1.Fr(1)
pubkey = pabtc.secp256k1.G * prikey
msg = pabtc.secp256k1.Fr(0x72a963cdfb01bc37cd283106875ff1f07f02bc9ad6121b75c3d17629df128d4e)

r, s, _ = pabtc.ecdsa.sign(prikey, msg)
assert pabtc.ecdsa.verify(pubkey, msg, r, +s)
assert pabtc.ecdsa.verify(pubkey, msg, r, -s)

在上述代码中, 我们使用私钥对一条消息进行了签名, 然后对签名中的 s 值取负号, 发现修改后的签名依然能通过 ecdsa 验证.

比特币在早期版本中存在这种攻击的风险, 攻击者通过延展性攻击破坏了交易的不可篡改性, 导致了严重的安全问题. 为了解决这一问题, 比特币在 segregated witness(segwit) 升级中做了改进, segwit 将交易的签名部分与其他数据分开存储, 使得即使攻击者篡改签名部分, 交易哈希也不再受影响, 从而解决了交易延展性问题.

这个问题在其他区块链系统中也有类似的影响, 因此许多项目都采取了类似 segwit 的解决方案, 来确保交易的完整性和可追溯性. 另一种解决方案是以太坊所采取的, 以太坊对签名中的 s 做了额外的要求, 要求 s 必须小于 pabtc.secp256k1.N / 2, 您可以 https://ethereum.github.io/yellowpaper/paper.pdf, Appendix F. Signing Transactions 找到以太坊针对交易延展性攻击的详细解决方式.

在古代, 如果我们把一枚金币敲变形之后, 虽然形状有所改变, 但质量却没有发生变化, 在市场交易中它仍然会被认可为一枚金币, 甚至您将金币敲成金块, 它依然会被认可, 这种特性呢被称为"延展性"或"可锻性".

有诗云:

门头交易所, 用户真是多.

比特币被盗, 大伙冷汗冒,

黑客改哈希, 交易无踪兆,

冷钱包空空, 财富随风飘.

旁路攻击

我坐飞机旁边有个大哥一直在看股票, 我俩聊了几句股票. 他说今年行情不好, 让我猜他亏了多少钱,

我说: "也就十来万吧." 大哥一愣, 问我: "你咋猜的呢?"

我说虽然你穿着衬衫西裤, 看着很商务, 但是却背了个瑞士军刀牌双肩包, 大老板有背这个的么?

一看你就是个跑业务的. 再看你戴了块阿玛尼这种杂牌子手表, 三十多岁的人了, 连个劳力士都没混上, 说明收入很一般.

你的衬衣是旧的, 但是熨得很板正, 领子也干净, 这都是你老婆给你收拾的. 你包上有个 hellokitty 小挂件, 这应该是你女儿给你挂的.

你自选股里都是一些 5G 移动芯片之类的股票, 你觉得自己很懂, 你应该是互联网企业上班的. 方方面面综合下来, 你的可支配资金也就20-30 万, 结合今年的行情, 亏损 10 万左右. 再看看你这个黑眼圈和与年龄不成比例的稀疏发型, 压力不小.

你老婆应该还不知道你股票亏了这么多钱. 刚才看到你手机界面上还有炒虚拟币的软件, 在最后一位, 说明是最近刚刚下载的.

如果你股票再亏, 你就打算去炒虚拟币放手一搏, 但是你只会亏得更惨. 说完我点了下他手机炒股软件界面, 上面显示总投入 28 万, 当前亏损 10.2 万.

大哥沉默了, 一路上再也没跟我说一句话, 只是偶尔低头用食指关节揉一揉微微发红的的眼眶, 飞机餐的盒饭打开了, 但是没吃.

上述故事来自中国互联网, 最早出现在 2015 年, 由于被转载太多次, 因此作者实在不明. 在这个故事里, "我"就对"大哥"发动了一次旁路攻击. 大哥虽然没有向我透露任何关于自身的投资信息, 但是由于大哥的资产收益会影响大哥的穿着, 因此我们可以通过大哥的穿着来反向推断大哥的资产收益.

在密码学中, 所谓的旁路攻击(side-channel attacks), 就是一种利用设备执行任务时产生的物理或行为信息(如执行时间, 用电模式, 电磁辐射等)来破解密码或签名方案的方法. 对于 secp256k1 椭圆曲线和 ecdsa 签名方案, 这种攻击可能通过分析关键运算的执行特性来推断私钥.

在 Ecdsa 中, 签名过程涉及生成一个随机数 k, 然后用它来计算签名的一部分. 这个随机数的安全性至关重要, 如果 k 被泄漏, 攻击者就能通过它恢复私钥. 那么, 令人激动的课堂作业来了:

例: 有以下信息, 请计算 secp256k1 的私钥.

  • 消息 m = 0x72a963cdfb01bc37cd283106875ff1f07f02bc9ad6121b75c3d17629df128d4e
  • 随机数字 k = 0x1058387903e128125f2715d7de954f53686172b78c3f919521ae4664f30b00ca
  • 签名
  • r = 0x75ee776c554b1dd5e1680a4cc9a3d0e8cb11400742d8af0222ce383e642f98db
  • s = 0x35fd48c9157256558184e20c9392ff3c9517f9753e3745aede06cab285f4bc0d

答: 根据 ecdsa 签名算法, 容易得到私钥计算公式为 prikey = (s * k - m) / r, 代入数字计算, 得到私钥为 1. 验证代码如下:

import pabtc

m = pabtc.secp256k1.Fr(0x72a963cdfb01bc37cd283106875ff1f07f02bc9ad6121b75c3d17629df128d4e)
k = pabtc.secp256k1.Fr(0x1058387903e128125f2715d7de954f53686172b78c3f919521ae4664f30b00ca)
r = pabtc.secp256k1.Fr(0x75ee776c554b1dd5e1680a4cc9a3d0e8cb11400742d8af0222ce383e642f98db)
s = pabtc.secp256k1.Fr(0x35fd48c9157256558184e20c9392ff3c9517f9753e3745aede06cab285f4bc0d)

prikey = (s * k - m) / r
assert prikey == pabtc.secp256k1.Fr(1)

随机数字 k 的计算涉及到椭圆曲线点乘和逆元操作(通常通过扩展欧几里得算法实现). 这些操作的时间可能会与 k 相关, 旁路攻击者可以测量执行时间差异来提取 k. 为了揭示原理, 我将尝试把攻击过程简化.

例: 有未知随机数字 k, 现在黑客通过某种手段可探测出 g * k 的执行时间, 请尝试是否可以得到随机数字 k 的一些信息.

答: 观察椭圆曲线上的点的乘法算法, 得出当 k 的比特位不同时, 会执行不同的操作. 当比特位为 0 时, 其计算量小于比特位为 1 时. 我们事先取两个不同的 k 值, 一个大多数位为 0, 另一个大多数位位 1, 计算它们的执行时间之差. 当有新的未知 k 进行计算时, 探测得到它的执行时间, 与前两个值进行比对, 可大致得到未知 k 其比特位为 1 的数量. 实验代码如下. 注意, 为了简化攻击步骤, 在实验代码中我们假设所有参与计算的 k 的第一个比特位始终为 1.

import pabtc
import random
import timeit

k_one = pabtc.secp256k1.Fr(0x8000000000000000000000000000000000000000000000000000000000000000) # Has one '1' bits
k_255 = pabtc.secp256k1.Fr(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff) # Has 255 '1' bits
k_unknown = pabtc.secp256k1.Fr(random.randint(0, pabtc.secp256k1.N - 1) | k_one.x) # The unknown k

a = timeit.timeit(lambda: pabtc.secp256k1.G * k_one, number=1024)
b = timeit.timeit(lambda: pabtc.secp256k1.G * k_255, number=1024)
c = timeit.timeit(lambda: pabtc.secp256k1.G * k_unknown, number=1024)

d = (c - a) / ((b - a) / 254)
print(d)

上述攻击过程是旁路攻击中的时间攻击(timing attacks), 如果要对该攻击做防护, 可以通过在代码中引入常量时间操作(constant-time operations)来避免泄露信息. 例如, 使用固定时间的加法和乘法, 防止时间差异被利用. 那么作为一道课后习题, 希望同学们可以自行尝试修改椭圆曲线上的乘法算法实现, 来避免老师上面提到的时间攻击.

在实际应用中, 为了避免密码学算法中的旁路攻击, 需要在算法, 硬件和软件层面做出多方面的安全优化. 可惜的是 secp256k1 与 ecdsa 方案在设计时未充分考虑该攻击方式, 这是其算法本身的固有缺陷.

小结

总之, 虽然 secp256k1 和 ecdsa 在许多应用中广泛使用, 并且它们在合理的实现和正确的使用下是相当安全的, 但也不能忽视它们存在的一些潜在漏洞. 得益于比特币的发展, secp256k1 和 ecdsa 名声大噪的同时也吸引了更多的密码学家和不怀好意的黑客们. 未来, 更多关于 sepc256k1 的一些攻击方式可能会逐步被发现并利用. 因此, 保持警惕, 及时更新以及遵循最新的安全最佳实践对于确保系统安全至关重要. 随着加密领域的不断进步, 目前已经有一些更加安全且高效的替代方案出现, 但无论如何, 理解并应对当前的风险, 仍然是我们每一个开发者的责任和挑战.