拿走你的钱包私钥，Ed25519 使用风险分析报告

2022-06-17

By Max

最近大家开始讨论 Ed25519 签名算法库的安全问题，具体参见https://github.com/MystenLabs/ed25519-unsafe-libs。一句话概括，由于一些算法库设计上的不周，以及用户对算法库接口的错误调用，可能导致攻击者根据对于同一消息的两次不同签名结果提取出用户私钥。

为了向大家解释一下这个问题的来龙去脉。本文会按照如下篇章来深入和全面的介绍：

• 为什么使用 Ed25519 签名？

• 一图掌握 Ed25519 签名原理

• Ed25519 签名的数学逻辑表述

• 算法工程实现与私钥提取攻击

• 攻击影响范围和解决办法

• 关于攻击的进一步思考

为什么使用 Ed25519 签名？

Ed25519 是美籍德裔密码学家 Daniel J. Bernstein 等人基于 25519 系列椭圆曲线 所设计的 椭圆曲线签名算法。其中，25519 系列椭圆曲线也是由 Daniel J. Bernstein 本人首次在 2005 年独立提出的。

Ed25519 算法算法具有以下优势：

• 更开放的设计：相比 NIST 系列标准中的椭圆曲线而言，25519 系列椭圆曲线的各参数的选择完全开放透明，无任何可疑之处；

• 更高的安全性：25519 系列椭圆曲线经过特别设计，将出错的概率降到了最低，从实践上来说更加安全。比如，任何一个 32 位随机数都是一个合法的 X25519 公钥，从而避免了恶意数值攻击的可能；

• 更快的计算速度：25519 系列曲线是目前计算速度最快的椭圆曲线。因为这些原因，越来越多的区块链采用了 Ed25519 作为其签名算法。

一图掌握 Ed25519 签名原理

Ed25519 签名原理

如上所示，一张图就描述清楚了 Ed25519 的原理，几乎囊括了所有的算法细节。如果读者需要了解 Ed25519 算法，读懂上面这张图即可。这里我们不会纠结于算法的所有细节。从感官上来说，Ed25519签名算法的设计看起来要比更加常见的 Ecdsa 签名算法要复杂一些，两者之间差异巨大。

Ed25519 签名的数学表述

我们会顺带介绍另一种跟 Ed25519 有亲戚关系的算法。读者如果比较了解 Schnorr 签名算法，就会在 Ed25519 签名算法中发现一种熟悉感。

Ed25519 算法其实是 Schnorr 算法的一种变形，主要差别有两个：

• 前者在多次使用了确定性随机数，甚至为此改变了私钥设计；

• 前者将椭圆曲线从常见的 Short 椭圆曲线 Secp256k1/Secp256r1 等更换成 扭曲爱德华椭圆曲线 Ed25519。

我们回归到 Schnorr 算法的架构下，以 Schnorr 算法的形式描述一下 Ed25519 的数学逻辑。通过概括上图（Ed25519 签名原理），Ed25519 签名算法可以定义为：是椭圆曲线群的基点

​$Setup$

• $G$ 是椭圆曲线群的基点
• $q$ 是椭圆曲线群的阶

$Sign(k, m)$：

• Step 1: $x = f_1(k)$
• Step 2: $A = xG$​
• Step 3: $r = f_2(k, m)$​
• Step 4: $e = f_3(R, A, m)$​
• Step 5: $R = rG$​
• Step 6: $S = r + e x \mod q$​
• Step 7: $Return \space (R, S)$

其中

• $k$ ​是私钥
• $m$​是待签名消息
• $A$​ 是公钥
• $f_1$ 是一个函数，根据私钥 $k$ 来计算公钥 $A$
• $f_2$ 是一个函数，根据私钥 $k$ 和消息 $m$ 来计算私有的确定性随机数 $r$
• $f_3$ 是一个函数，根据 $R$，公钥 $A$ 和消息 $m$ 来计算公开的确定性随机数 $e$

注意：以上的 $f_1$，$f_2$，$f_3$ 三个函数可直接从上图中推导而出，为了简化描述，我们这里不做详细推导。读者可以自行推导其计算公式。

以上算法是没有任何安全问题的。那么问题出在哪呢？问题出在工程实现。

算法工程实现与私钥提取攻击

Ed25519 签名的变型实现

现实当中，很多算法库在实现 Ed25519 签名算法时，并不会严格按照上图来实现。出于效率和使用方便考虑，公钥 $A$ 通常不会重新计算，它会被暂存起来。在签名的时候，公钥 $A$ 作为已有值，直接参与签名计算，如下所示。

$Setup$

• $G$​ 是椭圆曲线群的基点
• $q$​ 是椭圆曲线群的阶

$Sign(k, m, A)$：

• Step 1: $x = f_1(k)$​
• Step 2: $r = f_2(k, m)$​
• Step 3: $e = f_3(R, A, m)$​
• Step 4: $R = rG$​
• Step 5: $S = r + e x \mod q$​
• Step 6: $Return \space (R, S)$​

其中 $k$​, $A$​, $f_1$, $f_2$​, $f_3$ 定义保持不变。

钱包架构

如上图所示，描述一种通用的钱包架构，包括移动端钱包、硬件钱包、云钱包（运行在云端服务器上）等多种场景。在钱包架构中，私钥通常被保存在安全的场合，无法被外界直接访问，但可以参与签名计算。

私钥提取攻击

如何发起攻击呢？只要发起两次签名，每次签名时使用不同公钥（比如分别使用 $A$ 和 $A'$）即可。

第一次签名

攻击方输入 $A$​ 和 $m$​，钱包输入 $k$

$\Rightarrow e = f_3(R, A, m)$​

$\Rightarrow S = r + ex \mod q$

第二次签名

攻击方输入 $A'$​ 和 $m$，钱包输入 $k$

$\Rightarrow e' = f_3(R, A', m)$

$\Rightarrow S’ = r + e’x \mod q$

因为 $R$，$A$，$A'$，$m$， $S$，$S'$ 都是公开的，可知 $e$ 和 $e'$ 也是公开的，两式相减：

$S-S'=(r+ex)-(r+e'x) \mod q$

$=ex-e'x \mod q$

$=(e-e')x \mod q$

两边同时乘以 $(e-e')$ 的逆：

$x = (S - S')(e - e')^{-1} \mod q$

其中 $x$ 就被提取出来了。

需要强调的是，我们不需要完全提取出私钥 $k$， 只要能提取出 $x$，就能对任意消息进行签名。因此，从数字资产安全的角度来说，只要能提取出 $x$， 就等同于钱包私钥被彻底获取了，获取了私钥即获取了资产。

攻击影响范围和解决办法

不管是哪种钱包，移动端钱包、云钱包、硬件钱包，只要是按照这种方式设计 Ed25519 签名算法，即提供形如 $Sign(k,m,A)$ 的接口，且没有对公钥 $A$ 进行验证，就可能遭受这种攻击。

补充一句，这种攻击方法对 Schnorr 依然有效。

解决办法也很简单，分两种处理办法：

• 不要提供形如 $Sign(k,m,A)$ 的接口，只提供形如 $Sign(k,m)$ 的接口。通过私钥 $k$ 来计算 $A$，避免非法输入；
• 如果必须提供形如 $Sign(k,m,A)$ 的接口，一定要验证 $A==xG$ ，即保证输入公钥是合法且唯一的。

尽管这个攻击方式是切实有效的，大家也不需要过分担忧它带来的威胁。大多数实际场景中，$Sign(k,m,A)$ 接口的调用方就是用户自己，而不是第三方（潜在的攻击方），输入公钥 $A$ 也是合法的，因此不用担心遭受私钥提取攻击。如果 $Sign(k,m,A)$ 接口的调用方为第三方，就需要谨慎预防此类攻击。

关于攻击的进一步思考

这种攻击背后的思想到底是什么呢？大家可以发现，Ed25519 和 Schnorr 算法中多次使用了确定性随机数（Deterministic Random Number），这也许能解释背后攻击的根源。并不是说使用确定性随机数就是错的。恰恰相反，当一个签名系统的各个参数都是确定性的时候，系统可以是安全的，甚至相对于随机签名系统而言，具有某些更加安全的特性，比如针对相同的消息始终产生相同的签名。

但是，当一部分确定性被打破（通常是由于工程实现和使用的考虑不周）的时候，噩梦就开始了。剩余的确定性非但不能保证安全，反而可以被攻击者利用起来，通过重复签名，消去确定性不变量，实现对整个系统的攻击。对 Ed25519 签名算法和 Schnorr 签名算法的攻击，就能部分佐证这种思想。

从以上思想出发，预防这种攻击还有一种全新的方案，那就是，用“真”随机数完全取代确定性随机数，通过消除确定性来避免此种依赖于重复签名的私钥提取攻击。这种方法的具体应用，限于篇幅，以后有机会我给大家介绍。另外，Safeheron 即将开源 MPC 的相关算法，希望未来与更多伙伴开展 MPC 的交流与合作！

参考文献

[1] Daniel J. Bernstein. High-speed high-security signatures.

[2] Josefsson, S. Edwards-Curve Digital Signature Algorithm (EdDSA)

[3] ed25519-unsafe-libs