ECDSA 安全issue：有关 Signature Malleability （签名延展性）

[SpaceStation09]

Intro

ECDSA (Elliptic Curve Digital Signature Algorithm) 在我们的使用中有一个非常重要但微妙的细节，那就是其Signature Malleability，问题出在其规范上，如果我们不仔细处理，可以使得一个attacker 在不知道我们私钥的情况下，根据已有的有效的(r, s)生成另一个 可以通过验证的(r, s')进而完成一些攻击操作。

Motivation

近期在尝试开发基于 RIP-7212 / EIP-7951的智能合约钱包的过程中，意识到这个问题的重要性，我已经能想到的基于这个机制可以攻击的pattern就有：如果 合约钱包 通过记录有效签名值的方式来防止操作的重放的话，那attacker可以通过这个机制，生成另一组(r, s')来绕过这个机制完成重放。

[SpaceStation09]

回顾 ECDSA 签名过程

一个ECDSA签名由两部分(r, s)组成，其生成过程如下：

• 选择一个随机数k (k一定是保密的，且每次签名都会不一样)。
• 计算点 P = k · G， 其中G为曲线的生成元， 基点。
• 计算 r (r的取值就是点P的x坐标): 即 r = P.x mod n = (k · G).x mod n 其中 n为 曲线的阶。
• 计算 s：s = k⁻¹ * (H(msg) + r * SK) mod n, 其中：
  • k⁻¹ 是 k 对 n的模逆元。
  • H(msg) 是消息的hash。
  • SK 是签名者的私钥。

验证者持有公钥 PK (PK = SK · G), msg 和 (r, s), 其签名验证的流程如下：

• 计算 s的模逆元： s⁻¹ mod n。
• 计算两个中间值：u1 = H(msg) · s⁻¹ mod n 和 u2 = r · s⁻¹ mod n。
• 计算验证点 P_verify = u1 · G + u2 · PK。
• 验证 P_verify.x mod n == r，则签名有效。

Signature Malleability

所谓 Signature Malleability其实就是指，attacker 根据现有的 (r,s) 可以计算出另一对有效的签名数据 (r, n - s) 也可以通过签名的验证。

验证Signature Malleability的机制

一个攻击者拿到了(r, s) ，然后他对 SK 和 随机数k都不知情，现在他能构造出一对新的签名数据(r, s')，其中 s' = n - s 。验证签名如下：

1. 计算s'的模逆元：(s')⁻¹ ≡ (-s)⁻¹ ≡ -s⁻¹ (mod n)。
2. 计算新的中间值 u1' 和 u2'：
   • u1' = H(msg) · (s')⁻¹ mod n = H(msg) · (-s⁻¹) mod n = - H(msg) · s⁻¹ mod n = - u1 mod n
   • u2' = r · (s')⁻¹ mod n = r · (-s)⁻¹ mod n = - r · s⁻¹ mod n = -u2 mod n
3. 计算新的验证点：P_verify' = u1'·G + u2'·PK = - u1·G - u2·PK = - (u1·G + u2·PK)。
4. 实际上P_verify我们知道他会是一个点，然后我们知道P_verify' = - P_verify， 那么我们可以得出其x坐标是相等的，也就是r是相等的，证毕，这样一组(r, s')是可以通过签名验证的

[SpaceStation09]

解决办法

大家想到的最常见的解决办法是简单而优雅的，即，我们强制签名的唯一性。也就是在实际代码的使用中，我们在验签时，我们会同时要求s < n / 2，也就是 low - s原则。如果 用户在签名时，产生的s大于了 n / 2，那么用户要在发出前主动替换成s'。

Example

返回到最初的Motivation，我是在做P256签名验证时发现了这个issue，我在代码中引用了 Openzeppelin 提供的P256的库，在其中我发现，他也已经有相关的限制，详情可查看：P256.sol