TSS-lib EdDSA 中的子群攻击分析

#crypto

MPC

Author: Nicola Von

1.子群攻击问题的定义

在带有 cofactor 的椭圆曲线（例如 Ed25519）上，曲线点群不是一个大素数阶群，而是可以分解成：

  • 一个阶为大素数的 大子群，记为 (Q)；
  • 一个阶很小的 小子群，记为 (T)。

如Ed25519曲线的结构是： $$ |G|=8\cdot \ell，\ell \text{是252bit的素数} $$ 子群攻击（small subgroup attack） 的典型模型：

  • 有一个需要保护的秘密标量 (x)（比如私钥或其线性组合）；

  • 攻击者可以构造并发送任意曲线点 (P) 给（特别是包含小子群成分的点），例如： $$ P = q + t, \quad q \in Q,\ t \in T $$

  • 协议要求计算： $$ Q = x \cdot P $$ ，并把 (Q)（或其某种编码）返回给对方。

攻击者可以多次构造不同的小子群点，观察输出的 (xP) 在小子群上的投影，逐步恢复 (x) 的若干低位比特，甚至结合其他结构性弱点恢复出完整私钥。这就是 small subgroup attack 的核心：利用“拿秘密标量去乘他构造的坏点”。

关键点：

  • 危险对象是“对手给的点 P”，
  • 利用的是“用 自己的 secret x 去乘 P 并泄露结果”。

2.Ed25519 曲线的特征与群结构

Ed25519 使用的曲线（Edwards25519）上所有点构成一个有限 Abel 群 (G)：

总阶： $$ |G| = 8 \cdot \ell $$ 其中( l ) 是 252 位大素数。

可以分解为：

  • 阶为 l 的大素数阶子群 Q，其中 B 是 Ed25519 的标准基点；
  • 阶为 8 的 小子群 (T)。

重要性质：

  • 任意点 ( P ∈ Q) 都可以唯一写成：P = q + t，q ∈ Q，t ∈ T。
  • 两个子群交集只包含单位元，不可能有非零点同时属于大子群和小子群。

这直接带来一个结论： $$ \text{对任意}， a \in \mathbb{Z}_\ell，\text{有 } A= aB \in Q，\text{ 且不含任何非零小子群成分， 即所有“标量×基点”的点都是“纯净的大子群点”。} $$ 换句话说，只要标量是模 ( l ) 的，且只乘标准基点 B（或 B 的线性组合），就天然工作在 prime-order 子群里面。

3.clamp 操作的作用与适用场景

根据 RFC 8032 定义的 Ed25519 的私钥生成流程，clamp 在这里起到的作用包括：

  • 将任意 SHA 输出的 32 字节映射为“合法标量”

    • 避免直接做昂贵的 ；

    • 确保范围、分布、位型满足 Ed25519 安全证明的要求。

  • 让标量成为 8 的倍数

    • 对任意阶 ( |8 ) 的小子群点 (t)，有：at = 0

    • 这在那些需要 secret × 不可信点 的场景（例如 X25519/ECDH）中，能抵抗小子群攻击。

4.tss-lib EdDSA 中标量与点是怎么用的

4.1 标量的来源

在 DKG 的第一轮中，每个参与方本地生成私钥份额：

ui := common.GetRandomPositiveInt(round.Params().EC().Params().N)

这里

N = round.Params().EC().Params().N

在 EdDSA 场景下就是 ( l )（大子群的阶），因此 ui 是直接在大子群中随机采样的标量。

后续：

  • VSS 多项式系数、share 等全部在大子群上做加减乘；

  • 公钥相关点、VSS 承诺点等均形如 标量 × 基点 B 或其线性组合。

4.2 点的使用

协议中涉及两类点：

  • 本地生成的点（安全）

    • 形如 ui B、多项式系数承诺 a_k B、临时 nonce ri B 等；

    • 因为 B 阶为 ( l )，所有这类点必然在大子群 (Q) 内，不含小子群成分。

  • 从其他参与方接收的点（必须防御的接口）

    • DKG 中接收到的 VSS 承诺 decommit（多项式系数点）；

    • 签名协议中接收到的各参与方的 nonce 点 (R_i)；

    • 重分配协议中的各种承诺点。

    • 恶意参与方可以在这里构造点: P = q + t，t ∈ T，即带小子群成分的“坏点”。

tss-lib 在设计上通过：

  • 对关键点附带 离散对数证明（Schnorr PoK）；

  • 在处理小子群问题后，引入 cofactor clearing / 子群检查；

来防止恶意参与方向协议中注入小子群点（参考 Baby Sharks 披露前后的修复方案）。

5.tss-lib 的设计

5.1 标量侧：已经在 prime 子群内采样，无 seed→标量问题

与 RFC 8032 的 Ed25519 不同：

RFC 从一个任意 32 字节 seed 出发，必须通过 hash + clamp 把它变成合法标量；

tss-lib 直接在大子群中采样：

ui := GetRandomPositiveInt(N) // N = ℓ

因此，一开始就已经生活在“大子群的标量空间”里，不存在 “hash(seed) 可能落在错误的 coset” 之类的问题。

5.2 子群攻击的真正入口在“点”，不是“标量 ui”

如第 1 节所述，小子群攻击的模型是：

  • 攻击者控制 点 P（可以故意让 P 带 torsion）；

  • 用 secret x 去乘 P 并泄露结果。

在 tss-lib 的 EdDSA 协议中，需要特别防御的是“收到的点”：

  • 别的参与方发来的 decommit、nonce Rᵢ、部分公钥等；

  • 如果没有子群检查 / cofactor 清理，恶意方可以像 Baby Sharks 那样，把小子群点 T 注入联合公钥或临时点。

解决办法是：

  • 对收到的点进行 子群成员检查；或

  • 执行 cofactor clearing，去掉 torsion 成分；

  • 配合 Schnorr PoK，证明“P 确实等于某个标量乘基点”。

5.3 “tss-lib 不怕子群攻击”的精确定义

  • tss-lib 不需要靠“对 ui 做 clamp”来防小子群攻击，原因是：

    • 标量 ui 直接在 ( ) 中采样，已经是 prime-order 子群的合法标量；

    • 所有本地生成的点都是 标量×基点 B，天然落在大子群 (Q) 中；

    • 子群攻击真正的攻击面在“收到的点”，需要通过 cofactor 清理与子群检查来加固；

    • Baby Sharks 之后的修复方案，正是围绕“处理收到的点”而不是“clamp 标量”。

  • 如果实现忽略对子方点的子群检查 / cofactor 清理， 那么即使对 ui 做 clamp，也 不能 阻止恶意参与方向协议注入小子群点，仍然会受到类似攻击。

6.结论

tss-lib本身无需修改底层库代码来规避子群攻击问题。