# 我的加密算法不可能这么脆弱！

*作者：叶万标，*[*Nervos Network*](https://www.nervos.org/) *CKB 开发者*

---

Secp256k1 与 ECDSA 椭圆曲线不仅常见，更是当今区块链数字签名的基础。从比特币（见 [Bitcoin Wiki](https://en.bitcoin.it/wiki/Secp256k1)）到以太坊（见 [*Yellow Paper*, Appendix E. Precompiled Contract](https://ethereum.github.io/yellowpaper/paper.pdf)）再到 CKB (见 [RFC 24](https://github.com/nervosnetwork/rfcs/blob/4b502ffcb02fc7019e0dd4b5f866b5f09819cfbe/rfcs/0024-ckb-genesis-script-list/0024-ckb-genesis-script-list.md?plain=1#L13) 相关部分) ，secp256k1 + ECDSA 都是它们的默认选择。它们让你通过私钥证明所有权——你的链上资产属于你，且仅属于你。

椭圆曲线之所以在密码学中有优势，因为它们可以在较小的密钥长度下提供更高的安全性。 但是， 它们真的是安全且完美的算法吗？美国国家标准与技术研究院（NIST）最近认为 secp256k1 存在一些安全风险，已经不建议使用。作为替代，它们建议使用另一条名为 [secp256r1](https://www.nervos.org/knowledge-base/what_is_secp256r1) 的椭圆曲线（见 [*Recommendations for Discrete Logarithm-based Cryptography*](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf), p1）。另一方面，比特币自身也在改变——在 2021 年引入了一种叫做 [Schnorr](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) 的签名算法来尝试替代 ECDSA。

促成这些改变的本质原因是因为 ECDSA 签名算法自身的问题——极其容易受到攻击，并造成过许多灾难性的后果。在本次分享中，我将带领大家回顾历史，并尝试重现这些历史上的著名攻击：随机数重用攻击、心脏点攻击、交易延展攻击、旁路攻击。最后我将指出 CKB 所采用的**隔离见证**，配合**支持加密算法升级**的方式——交易哈希不包含 ECDSA 签名，并允许算法升级，在确保安全的同时让用户可以采用更适合自己需求的方案。

本文会使用一些数学符号，约定如下:

| `m` | 消息 | 256 位整数 |
| --- | --- | --- |
| `r` | 签名的一部分 | 256 位整数 |
| `s` | 签名的一部分 | 256 位整数 |
| `k` | 随机数字，在签名时需要用到 | 256 位整数 |
| `g` | 椭圆曲线的生成点，代表坐标 x 和 y | 两个 256 位整数 |

## **随机数重用攻击**

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

在 [fail0overflow](https://wiibrew.org/wiki/Fail0verflow) 大会上， 黑客展示了索尼 ECDSA 的部分代码， 发现索尼让随机数的值始终保持 4， 这导致了 ECDSA 签名步骤中的随机私钥 k 始终会得到相同的值。**ECDSA 签名要求随机数 k 是严格随机的， 如果重复使用 k， 将直接导致私钥泄露**.

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

例：有以下信息，求私钥 prikey

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

答：

```plaintext
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 的签名来还原私钥：

```python
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 v1.0.2 之前的一个版本存在一个椭圆曲线验证漏洞。攻击者可以通过构造一个无效的椭圆曲线点并将其用作公钥， 利用 OpenSSL 的某些漏洞绕过验证，进而攻击使用该库的系统。这个漏洞被称为 [CVE-2015-1786](https://nvd.nist.gov/vuln/detail/CVE-2015-1786)， 它允许攻击者通过伪造无效的公钥来绕过签名验证。同样的问题也曾发生在 Bitocin Core 使用的 ECDSA 库中，早期版本的库没有对椭圆曲线点进行足够的检查。

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

## **交易延展性攻击**

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

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

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

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

巧合的是，secp256k1 + ECDSA 确实存在一种十分便捷的方式，使得攻击者可以修改签名结果的同时仍然能通过签名验证。如果我们分析 ECDSA 验签算法，会发现**验签结果和签名（r, s）中的 s 值的符号是无关的。**

为了验证这一点，我们编写如下测试代码：

```python
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`。您可以在 [Ethereum *Yellow paper*](https://ethereum.github.io/yellowpaper/paper.pdf) 的 Appendix F. Signing Transactions (p. 26) 部分找到以太坊针对交易延展性攻击的详细解决方式。

有诗云:

> 门头交易所，用户真是多，  
> 比特币被盗，大伙冷汗冒，  
> 黑客改哈希，交易无踪兆，  
> 冷钱包空空，财富随风飘。

## **旁路攻击**

> 我坐飞机旁边有个大哥一直在看股票，我俩聊了几句股票。他说今年行情不好，让我猜他亏了多少钱。
> 
> 我说：“也就十来万吧。”
> 
> 大哥一愣，问我：“你咋猜的呢？”
> 
> 我说：“虽然你穿着衬衫西裤，看着很商务，但是却背了个瑞士军刀牌双肩包，大老板有背这个的么？一看你就是个跑业务的。再看你戴了块阿玛尼这种杂牌子手表，三十多岁的人了，连个劳力士都没混上，说明收入很一般。你的衬衣是旧的，但是熨得很板正，领子也干净，这都是你老婆给你收拾的。你包上有个 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。

验证代码如下：

```python
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。

```python
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 方案在设计时未充分考虑该攻击方式，因此防护此类攻击非常困难且复杂。

## CKB 的方式：隔离见证 + 加密算法可升级

在交易结构上，CKB 采用了比特币的隔离见证方案，也就是交易哈希不会包含 ECDSA 签名。这种设计可以防止交易延展性攻击。详情见 RFC 的 [Transaction Hash](https://github.com/nervosnetwork/rfcs/blob/master/rfcs/0022-transaction-structure/0022-transaction-structure.md#transaction-hash) 部分。

Secp256k1 + ECDSA 方案是 CKB 的默认签名方案，但得益于 CKB 的自定义密码学原语和原生账户抽象能力，在 CKB 上可以非常容易地实现更多其它加密算法和升级现有算法。CKB 上的开发者可以选择任意信任算法来保护资产，包括但不限于:

* [**Secp256r1**](https://www.nervos.org/knowledge-base/what_is_secp256r1)
    
* [**SPHINCS+** 抗量子签名](https://blog.cryptape.com/quantum-computation-new-challenge-to-ckbs-security)
    
* **RSA**, **Ed25519** and more
    

## 结语

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

---

## 🧑‍💻 ***关于作者***

叶万标是 CKB-VM 的开发者之一，专注于提升虚拟机的性能与能力。他一直在探索指令集设计与宏指令融合等方向，以使系统更加高效且灵活。

他的文章和演讲包括：

* [Spawn: Direct Cross-Script Calling Method in CKB Virtual Machine](https://blog.cryptape.com/spawn-direct-cross-script-calling-method-in-ckb-virtual-machine)
    
* [How To Beat Rust's Zero-Cost Abstraction With Hand-Coded Assembly?](https://blog.cryptape.com/how-to-beat-rusts-zero-cost-abstraction-with-hand-coded-assembly)
    
* [RVV (RISC-V V Extension): Key to the Efficient On-Chain Cryptography](https://blog.cryptape.com/rvv-risc-v-v-extension-key-to-the-efficient-on-chain-cryptography)