# 攻破超奇异同源 Diffie-Hellman（SIDH）

:::info
作者：Steven Galbraith
译者：Kurt Pan
原文链接：https://ellipticnews.wordpress.com/2022/07/31/breaking-supersingular-isogeny-diffie-hellman-sidh/
:::

Wouter Castryck 和 Thomas Decru的论文[An effective key recovery attack on SIDH](https://eprint.iacr.org/2022/975)是同源密码分析的重大突破。这个结果与 Jao 和 De Feo 的 SIDH 协议以及 NIST 第 4 轮决赛入围方案 [SIKE](https://sike.org/) 有关。

我没有时间解释所有的技术细节，但这里有一些对你急迫问题的快速解答。

## 1. 结果是真的吗？

没有理由怀疑这一点。提供了[代码](https://homes.esat.kuleuven.be/~wcastryc/)（虽然我自己没有运行过），而且SIKE 团队已经确认了该攻击。解决了 Microsoft 的 [\$IKEp217 挑战](https://github.com/microsoft/SIKE-challenges/blob/main/%24IKEp217.txt)，Castryck 和 Decru 有资格获得 50,000 美元的奖金。

攻击的某些方面及其复杂性分析是启发式的，但这对于密码分析来说是正常的和可接受的。实验结果表明该攻击非常实用。

## 2. 攻击如何运作？

该攻击利用了 SIDH 具有辅助点且秘密同源的阶是已知的事实。SIDH 中的辅助点一直是个讨厌的东西和潜在的弱点，被用于故障攻击、GPST 适应性攻击、扭点攻击等。

令$E_{0}$是基曲线，令$P_{0}, Q_{0} \in E_{0}$具有阶$2^{a}$。令$E, P, Q$ ，存在度为$3^{b}$的同源$\phi$使得$\phi: E_{0} \rightarrow E, \phi\left(P_{0}\right)=P$, $\phi\left(Q_{0}\right)=Q$

SIDH 的一个关键方面是不直接计算$\phi$，而是作为度为3同源的组合。换句话说，存在一系列的由 3-同源连接的$E_{0} \rightarrow E_{1} \rightarrow E_{2} \rightarrow \cdots \rightarrow E$曲线。

本质上，就像在 GPST 中一样，该攻击确定了中间曲线$E_{i}$，因此最终确定了私钥。在步骤$i$中，该攻击对所有可能的$E_{i} \rightarrow E_{i+1}$ 进行暴力搜索，神奇的点在于一个显示哪个是正确的小工具。

（以上过于简化了，比如攻击中的同源$E_{i} \rightarrow E_{i+1}$不是度为3，而是3的小幂次。）

## 3. 神奇的小工具是什么？

是 Ernst Kani 提出的关于阿贝尔曲面的可约子群的一个定理。

## 4. 有没有简单的方法解释这个定理？

没有。去学[Richelot同源](https://eprint.iacr.org/2021/1617.pdf)和[阿贝尔曲面](https://en.wikipedia.org/wiki/Abelian_surface)。

## 5. 这对 NIST 第 4 轮候选方案 SIKE 意味着什么？

NIST 提交中[SIKE](https://sike.org/)中指定的方案已被攻破。

## 6. SIDH可以修复吗？
推特上已经有一些关于如何避免该攻击的可能建议。例如可以去关注 Peter Kutas [@kutasp](https://twitter.com/kutasp?lang=en)和 Boris Fouotsa [@FouotsaB](https://twitter.com/FouotsaB)。

为了能使用神奇的小工具，攻击者必须有效地计算多个具有$2^{i}-3^{j}$形式的度的同源，其中$1 \leq i \leq a .1 \leq j \leq b$。如果我们不结束在具有小判别式复数乘法的曲线，则不清楚如何做到这一点。所以一个希望点在于可以通过选择具有未知自同态环的基曲线$E_0$的来拯救 SIDH（这可能需要某种公共设置）。

该论文指出 SIDH 的变体，例如 [B-SIDH](https://eprint.iacr.org/2019/1145)（使用除了2和3之外的素数），应该是可攻击的。所以看起来改变素数并不能阻止该攻击。

## 7. 会攻破 CSIDH 或其他同源密码系统吗？

不会，该攻击非常具体地依赖于两件事：
1. 秘密同源的度是已知的；
2. 攻击者被提供了辅助点。

因此，该攻击似乎没有攻破 [CSIDH](https://csidh.isogeny.org/) 或 [SQISign](https://eprint.iacr.org/2020/1240)。

## 8. 会攻破椭圆曲线密码学吗？

不会，攻击假设同源的度是已知的，而这正是椭圆曲线密码学中的私钥。没有特别的理由认为对 SIDH 的攻击会导致对椭圆曲线密码学的攻击。

## 9. 为什么现在才发现？

Kani 在 1997 年的[一篇论文](https://www.mast.queensu.ca/~kani/papers/numgenl.pdf)中描述了该攻击的理论基础（Howe、Leprévost 和 Poonen 2000 年的[一篇论文](https://arxiv.org/abs/math/9809210)中也描述了一些有用的工具）。因此某种意义上说，攻击随时都可能被注意到。但关键点是，这不是一个只去思考椭圆曲线之间的同源就能发现的攻击。该攻击深入利用了 Richelot 同源和椭圆曲线的乘积，我怀疑如果没有这种语言，该攻击能否被有意义地表达。这就是泛化和扩展的力量。因此，找到攻击的必要条件是让一群学者去研究“深奥”的主题，例如将同源密码扩展到阿贝尔曲面。

## 10. 对后量子密码的影响

毫无疑问，这一结果会降低对同源的信心。突然出现如此强大的攻击，说明该领域还没有成熟。Ward Beullens 最近对 Rainbow 的[攻击](https://eprint.iacr.org/2022/214)对多变量密码也有类似的影响。对此的正确反应不是试图最小化影响，也不是条件反射性地去宣布该事物的死亡。相反，我们应该保持开放的心态，让数学家去找出其中全部的可能结果，无论最终会导向哪里。就个人而言，我迫不及待地想看看 Wouter 和 Thomas 以及所有的同源学者接下来会想出什么！