安全与密码学2022eprint.iacr.org编辑精选
用一台笔记本电脑在一个周末破解 Rainbow
Breaking rainbow takes a weekend on a laptop
专业 · 约 80 分钟读完前置知识：线性代数、多元二次方程组、后量子密码基础
导读
这篇论文提出针对 Rainbow 签名方案的新密钥恢复攻击。Rainbow 是 NIST 后量子密码标准化项目的决赛签名方案之一。新攻击在所有提交给 NIST 的参数集上都优于此前已知攻击，并且对 SL1 参数实现了实用化密钥恢复：在标准笔记本上平均约 53 小时（一个周末）即可由公钥恢复对应私钥。
HN 关注点：是因为它把 NIST 后量子签名决赛候选 Rainbow 的实际安全性拉到笔记本一个周末可攻破的程度，并引发对 PQC 标准化和剩余候选可靠性的讨论。
后来怎么样
该攻击直接促使 NIST 在 2022 年后量子签名标准遴选中放弃 Rainbow，最终仅选择 Dilithium、Falcon 和 SPHINCS+，Rainbow 未被标准化。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
补充评论者正考虑采用 Rainbow，并发现 Cloudflare 博客已讨论该攻击。
这真是不可思议的结果。我最近想在自己的东西里采用一些 PQC，并把 Rainbow 列为选择之一。我也知道 Cloudflare 正在尝试采用这些 PQC 协议[0][1]，所以看到这个攻击后去查了 Cloudflare 博客，然后发现一篇提到这个攻击的博客[2]，笑死。
ototot查看英文原文
This is truly an incredible result. I want to adopt some PQC to my own stuff recently and considering Rainbow as one of my choice. I also know that Cloudflare is now trying to adopt these PQC protocols[0][1], so I checked the Cloudflare blog post after seeing this attack. Then, I found out a blog mentioning this attack[2], lol. [0] https://blog.cloudflare.com/making-protocols-post-quantum/ [1] https://blog.cloudflare.com/post-quantum-key-encapsulation/ [2] https://blog.cloudflare.com/post-quantum-future/
支持引用摘要说明攻击对所有参数集更优，SL1 可在笔记本上一个周末恢复私钥。
这是 Ward Beullens 的惊人成果，他实际上攻破了 NIST PQ 第三轮候选 Rainbow[0]。论文摘要：本工作提出针对 Rainbow 签名方案的新密钥恢复攻击，Rainbow 是 NIST 后量子密码标准化项目中仍存的三项决赛签名方案之一。新攻击在所有提交给 NIST 的参数集上都优于此前已知攻击，并使 SL1 参数下的密钥恢复变得可行。具体而言，给定第二轮提交中 SL1 参数的 Rainbow 公钥，我们的攻击在标准笔记本上平均计算 53 小时（一个周末）后返回对应私钥。
jack4818查看英文原文
This is an incredible result from Ward Beullens, who has practically broken the 3rd round NIST PQ candidate "Rainbow"[0] Paper Abstract: This work introduces new key recovery attacks against the Rainbow signature scheme, which is one of the three finalist signature schemes still in the NIST Post-Quantum Cryptography standardization project. The new attacks outperform previously known attacks for all the parameter sets submitted to NIST and make a key-recovery practical for the SL 1 parameters. Concretely, given a Rainbow public key for the SL 1 parameters of the second-round submission, our attack returns the corresponding secret key after on average 53 hours (one weekend) of computation time on a standard laptop. [0] https://www.pqcrainbow.org
质疑外行总结后质疑剩余候选资格和标准化流程的可靠性。
多亏 jack4818 和 ototot 链接的资料，我勉强理解了一点。我分享一下自己非常外行、朴素的理解，希望能帮到处于类似位置的人。如果我说的有错请纠正！量子计算机有特殊性质，能破解常用加密方案。我们的安全通信（比如登录银行网站）依赖这些方案。因此 NIST 一直在寻找量子计算机难以破解的加密方案。NIST 项目进行到认为三种具体方案满足要求的阶段，这是审查许多候选之后。Rainbow 进入了前三。Ward Buellens 实际上攻破了 Rainbow，使其不适合用于量子计算未来。我猜这会让剩下两个候选的资格也受质疑。是要求不足，还是项目因量子计算本质而固有失败风险？
nefitty查看英文原文
Thanks to the informative resources linked to by jack4818 and ototot I was able to slightly wrap my head around this. I'll share my barely informed, naive understanding in the hopes that it'll help others in a similar position build on it. Please correct me if any of what I share is mistaken! Quantum computers have special properties that make them capable of breaking commonly used encryption schemes. We're dependent on those schemes for secure communication, like logging into a bank website. Due to this, the organization NIST has been working on finding encryption schemes that would be diffcult to break with a quantum computer. NIST was at the stage of this project where they felt reasonably confident that three specific encryption schemes met the requirements. This is after review of many candidates. Rainbow made it to the top three. Ward Buellens essentially managed to break Rainbow, thereby making it ineligible for use in a quantum computer-powered future. I assume this puts the two remaining candidates' eligibility into question. Were the requirements lacking, or is the project inherently at risk of failure due to the nature of quantum computing?
补充Rainbow 团队承认攻击并通过增大参数补偿，认为这不是系统性失败。
Rainbow 团队刚在 pqc 开发邮件列表发帖，承认该攻击并感谢作者。他们提高了参数集来补偿，暗示我不懂的数学不会造成系统性失败，而是带来足够显著的攻击复杂度降低。
olliej查看英文原文
The rainbow team just posted to the pqc development list acknowledging the attack and thanking the authors. They’ve increased the parameter sets to compensate, implying that the maths I don’t understand doesn’t create a systemic failure but rather a sufficiently meaningful reduction in attack complexity
历次讨论
- 2022Hacker News 讨论帖155 分 · 64 评
同领域还值得读
如何入侵一台已关机的电脑：在 Intel ME 中运行未签名代码
How to hack a turned-off computer, or running unsigned code in Intel ME
这篇 Black Hat 2017 白皮书讨论 Intel Management Engine（ME）的安全问题：如何在 ME 中运行未签名代码，以及攻破处于关机状态的电脑的相关…
安全与密码学2017 · 543 分 · 107 评专业 · 约 40 分钟编辑精选比特币：一种点对点的电子现金系统（2008）
Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
中本聪 2008 年发表的比特币白皮书，提出了无需可信第三方的点对点电子现金系统。
安全与密码学2017 · 536 分 · 394 评入门 · 约 45 分钟编辑精选GPRS 加密算法 GEA-1 的密码分析表明存在故意弱点
Cryptanalysis of GPRS Encryption Algorithms GEA-1 suggest intentional weakness
首次公开了对 GPRS 加密算法 GEA-1 和 GEA-2 的密码分析攻击。
安全与密码学2021 · 487 分 · 107 评专业 · 约 90 分钟编辑精选Signal 消息协议的形式化安全分析
A Formal Security Analysis of the Signal Messaging Protocol
用形式化方法分析 Signal 消息协议（TextSecure）的安全性：作者在多阶段密钥交换模型下，借助自动化证明工具对协议的密钥协商与 Double Ratchet 密钥更新…
安全与密码学2016 · 353 分 · 230 评专业 · 约 120 分钟编辑精选A2：模拟恶意硬件
A2: Analog Malicious Hardware
论文研究如何在芯片设计阶段植入模拟电路形式的恶意硬件后门，使其难以被常规检测发现。
安全与密码学2016 · 315 分 · 94 评专业 · 约 75 分钟编辑精选