Ed25519/EdDSA签名算法导致的密钥泄露的漏洞研究

近期，针对Ed25519算法爆出私钥泄露的漏洞，比原技术团队及时跟进研究，我们来探讨一下本次问题的发生：

Ed25519/EdDSA的签名过程

EdDSA签名算法由Schnorr签名发展变化而来，可以在RFC8032中看到它的定义实现，由曲线和参数的选择不同又可以划分为Ed25519和Ed448算法，他们的分别是基于curve25519还是curve448曲线，一般用的比较多的是Ed25519算法，相比Ed448而言运算速度要更快，秘钥与签名空间也较小，二者的使用场景还是有点区别，下面我们主要讲的也是Ed25519。

Ed25519所使用的曲线由curve25519变换而来，curve25519是蒙哥马利曲线，经过变换得到Ed25519使用的扭爱德华曲线edwards25519，curve25519曲线的安全性是非常高的。

下面我们来看看Ed25519的具体签名过程：

Ed25519的私钥k长度为b bit，一般是256，其使用的hash算法H的输出长度为2b bit，一般选择的是SHA512，对应b等于256。

首先，对私钥k进行hash,得到，

使用hash的结果我们可以计算得到参数a，

这样我们就可以得到私钥k对应的公钥A、A=aB、B为选取的基点，下面我们准备对消息M进行签名，过程如下，其中l为基点B的阶，

这样就得到了消息M的签名(R,S)，签名的验证则需满足下面的等式，

观察整个签名过程，我们不难发现，一个私钥k，当对同一个消息M进行签名时R与S都是固定的，所以说EdDSA是一种确定性的签名算法，不像ECDSA那样每次签名都根据选取的随机数的变化而不同，所以EdDSA的安全性也就不再依赖于随机数生成器。

漏洞产生

那么这次漏洞的产生就是恰恰是确定性上。

为了严谨的构造一个Ed25519/EdDSA知识证明，我们需要在challenge hash中明确的包含公钥，但是在指定的Ed25519随机数生成函数中并没有在hash中包含公钥，所以普遍的在Ed25519的签名算法中接受公钥作为参数，避免从私钥重复生成公钥而花费更多的时间。

假如我用一个不匹配或损坏的公钥进行签名，签名算法可以成功，但得到一个无效的签名值，表面来看这好像是无害的：我为什么要关心是否有人能用无效的签名欺骗我？无需我的帮助他们也可以构造任意多的无效的签名。但是假如我用相同私钥和不同的公钥参数来签署同一段信息，而你可以根据这些签名用随机数重用的方式来计算得到我的私钥，这就是非常致命的问题了。我们来看重用的流程。

对于同一签名消息，r是相同的，因为：

所以我们每次使用同样的消息进行签名，保证每次的r值相同。

然后我们使用不同的公钥，假设为公钥A1,A2对同一消息M进行签名，

那么就可以求出，

其中S1，S2都可以通过重用观察到，所以即可以获得 a 值，很多人说a是私钥的hash值，还是得不到私钥，但我们看验签过程中，其实并不需要原始的私钥k，但是签名的验证仍然是可以通过的，也就是说只要知道了a的值我们就可以进行签名的伪造了，并不需要知道原本的私钥，其实这里a已经可以看作是私钥了 。

那么这个漏洞主要影响就是，如果你提供了一个接受公钥作为参数的签名方法，并不加验证就使用这个传递进来的公钥参数，攻击者们就可以通过使用多个错误的公钥值来对同一个信息进行签名并获取不同的签名值，从而通过这些签名值来反推出用户的私钥，从而达到获取用户私钥的目的。

有部分的 Python，C和Rust都受到了这个问题的影响，我们来看

https://ed25519.cr.yp.to/python/ed25519.py

def signature(m,sk,pk): h = H(sk) a = 2**(b-2) + sum(2**i * bit(h,i) for i in range(3,b-2)) r = Hint(''.join([h[i] for i in range(b/8,b/4)]) + m) R = scalarmult(B,r) S = (r + Hint(encodepoint(R) + pk + m) * a) % l return encodepoint(R) + encodeint(S)

signature直接传入pk作为参数，通过传入假的公钥值，对相同的消息m进行签名，获得不同的签名S值，然后推导出a值。

当然存在并不一定能够或者会被利用，毕竟系统的利用的漏洞并发动攻击也需要做一系列的准备。

如何避免

解决方法也非常简单，不提供接受公钥作为参数的签名方法，或者校验传入的公钥参数，当然这也是一个效率和安全的平衡，比原链在设计之初就考虑这个因素，在私钥中存储了公钥信息，签名过程中使用的公钥只要获取即可，即提升了效率又保证了安全性，下面为比原链签名相关的方法：

func Ed25519InnerSign(privateKey ExpandedPrivateKey, message []byte) []byte { if l := len(privateKey); l != ExpandedPrivateKeySize { panic("ed25519: bad private key length: " + strconv.Itoa(l)) } var messageDigest, hramDigest [64]byte
h := sha512.New() h.Write(privateKey[32:]) h.Write(message) h.Sum(messageDigest[:0]) var messageDigestReduced [32]byte edwards25519.ScReduce(&messageDigestReduced, &messageDigest) var R edwards25519.ExtendedGroupElement edwards25519.GeScalarMultBase(&R, &messageDigestReduced) var encodedR [32]byte R.ToBytes(&encodedR) publicKey := privateKey.Public().(ed25519.PublicKey) h.Reset() h.Write(encodedR[:]) h.Write(publicKey[:]) h.Write(message) h.Sum(hramDigest[:0]) var hramDigestReduced [32]byte edwards25519.ScReduce(&hramDigestReduced, &hramDigest)
var sk [32]byte copy(sk[:], privateKey[:32]) var s [32]byte edwards25519.ScMulAdd(&s, &hramDigestReduced, &sk, &messageDigestReduced)
signature := make([]byte, ed25519.SignatureSize) copy(signature[:], encodedR[:]) copy(signature[32:], s[:])
return signature }

我们看到代码中使用 privateKey.Public()方法来获取签名所需的公钥，我们再看 Public()方法，比原链将公钥存储在私钥相关的数组后 32 位中，这样既避免了每次签名重复计算的效率损失，又防止外部传入的漏洞

func (priv PrivateKey) Public() PublicKey { publicKey := make([]byte, PublicKeySize) copy(publicKey, priv[32:]) return PublicKey(publicKey)}

涉及范围

因为 EdDSA/Ed25519 的比较优势，现在不少区块链项目也在使用这个曲线作为其密码学的基础，我们查阅《Things that use Ed25519》可以看到BigchainDB等开源项目都在使用Ed25519，在此建议大家自查一下是否受到了影响。

参考资料

1. 《Ed25519/EdDSA key leakage due to fragility in recommended nonce procedure》；

2. 《Generalizing EdDSA》；

3. 《针对EdDSA的fault attack》；

—-

编译者/作者：比原链

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。