Safeheron 深层剖析 Ed25519 私钥提取攻击的来龙去脉。

作者: Max @ Safeheron Team

最近大家开始讨论 Ed25519 签名算法库的安全问题。一言蔽之,由于一些算法库设计上的不周,以及用户对算法库接口的错误使用,可能导致这样的风险:攻击者通过分析同一消息的两次不同签名结果,提取出用户私钥。

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

  • 为什么使用 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 签名算法的设计看起来要比更加常见的 ECDSA 签名算法要复杂一些,两者之间差异巨大。

Ed25519 签名的数学表述

我们会顺带介绍另一种跟 Ed25519 有亲戚关系的算法。读者如果比较了解 Schnorr 签名算法,就会在 Ed25519 签名算法中发现一种熟悉感。Ed25519 算法其实是 Schnorr 算法的一种变型,主要差别有两个:

  • 前者多次使用了确定性随机数,甚至为此调整了私钥设计;
  • 前者将椭圆曲线从常见的 Short 椭圆曲线  Secp256k1/Secp256r1 等更换成 扭曲爱德华椭圆曲线 Ed25519。

让我们回归到 Schnorr 算法的架构下,描述一下 Ed25519 的数学逻辑。通过概括上图,Ed25519 签名算法可以定义为:

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

Ed25519 签名的变型实现

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

钱包架构

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

私钥提取攻击

如何发起攻击呢?只要发起两次签名,每次签名时使用不同公钥(比如分别使用    和  )即可。

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

攻击影响范围和解决办法

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

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

解决办法也很简单,分两种处理办法:

  • 不要提供形如   的接口,只提供形如   的接口。通过私钥   来计算  ,避免非法输入;
  • 如果必须提供形如   的接口,一定要验证  ,即保证输入公钥是合法且唯一的。

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

关于攻击的进一步思考

这种攻击背后的思想到底是什么呢?大家可以发现,Ed25519 和 Schnorr 算法中多次使用了确定性随机数(Deterministic Random Number),这也许能解释背后攻击的根源。并不是说使用确定性随机数就是错的。恰恰相反,当一个签名系统的各个参数都是确定性的时候,系统可以是安全的,甚至相对于随机签名系统而言,具有某些更加安全的特性,比如针对相同的消息始终产生相同的签名。但是,当一部分确定性被打破(通常是由于工程实现和使用的考虑不周)的时候,噩梦就开始了。剩余的确定性非但不能保证安全,反而可以被攻击者利用起来,通过重复签名,消去确定性不变量,实现对整个系统的攻击。对 Ed25519 签名算法和  Schnorr 签名算法的攻击,就能部分佐证这种思想。

从以上思想出发,预防这种攻击还有一种全新的方案,那就是,用 “真” 随机数完全取代确定性随机数,通过消除确定性来避免此种依赖于重复签名的私钥提取攻击。这种方法的具体应用,限于篇幅,以后有机会我给大家介绍。

参考文献

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

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

[3] ed25519-unsafe-libs

免责声明:作为区块链信息平台,本站所发布文章仅代表作者及嘉宾个人观点,与 Web3Caff 立场无关。本文内容仅用于信息分享,均不构成任何投资建议及要约,并请您遵守所在国家或地区的相关法律法规。