cr.yp.to 博客

较新的文章 (Access-K)：2014.02.13: 针对理想格的子域对数攻击: 计算代数数论处理基于格的密码学。

目录 (Access-I 为索引页)：2025.01.18: 像飞机票一样昂贵: 关注量子计算机无法工作的论断。#quantum #energy #variables #errors #rsa #secrecy

2024.10.28: 90年代的罪恶: 质疑关于大规模监控的一个令人困惑的说法。#attackers #governments #corporations #surveillance #cryptowars 2024.08.03: Clang vs. Clang: 你惹恼了 Clang。 你不会喜欢 Clang 发怒的样子。 #compilers #optimization #bugs #timing #security #codescans 2024.06.12: 参考文献键: 就像 [1], [2], [3] 一样简单。 #bibliographies #citations #bibtex #votemanipulation #paperwriting 2024.01.02: 双重加密: 分析 NSA/GCHQ 反对混合加密的论点。#nsa #quantification #risks #complexity #costs 2023.11.25: 又一种搞砸 Kyber-512 安全分析的方法: 回应最近的一篇博客文章。 #nist #uncertainty #errorbars #quantification 2023.10.23: 减少 Kyber-512 的 "gate" 计数: 两个算法分析，从第一性原理出发，与 NIST 的计算相矛盾。 #xor #popcount #gates #memory #clumping 2023.10.03: 无法正确计数: 揭穿 NIST 对 Kyber-512 安全级别的计算。 #nist #addition #multiplication #ntru #kyber #fiasco 2023.06.09: Turbo Boost: 如何延续安全问题。 #overclocking #performancehype #power #timing #hertzbleed #riskmanagement #environment 2022.08.05: NSA、NIST 和后量子密码学: 宣布我对美国政府的第二次诉讼。 #nsa #nist #des #dsa #dualec #sigintenablingproject #nistpqc #foia 2022.01.29: 抄袭作为专利放大器: 理解后量子密码学延迟推出的原因。 #pqcrypto #patents #ntru #lpr #ding #peikert #newhope 2020.12.06: 优化错误的指标，第 1 部分：Microsoft Word: 评论 Knauff 和 Nejasmic 的 "学术研究和开发中使用的文档准备系统的效率比较"。 #latex #word #efficiency #metrics 2019.10.24: 为什么 EdDSA 比 ECDSA 更能抵抗 Minerva 攻击: 密码系统设计者成功预测并防范实现失败。 #ecdsa #eddsa #hnp #lwe #bleichenbacher #bkw 2019.04.30: 向量化简介: 了解高速软件生态系统中最重要的变化之一。 #vectorization #sse #avx #avx512 #antivectors 2017.11.05: 重建 ROCA: 一个关于如何从有限的披露中快速开发攻击的案例研究。 #infineon #roca #rsa 2017.10.17: 寻找碰撞的量子算法: 分析了用于碰撞问题以及相关的多目标原像问题的几种算法。 #collision #preimage #pqcrypto 2017.07.23: 快速密钥擦除随机数生成器: 一项同时清理多个混乱的工作。 #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs 2017.07.19: 后量子密码学基准测试: 关于 SUPERCOP 基准测试系统的新闻，以及向 NIST 提出的更多建议。 #benchmarking #supercop #nist #pqcrypto 2016.10.30: 后量子标准化中的一些挑战: 我对 NIST 征集提交草案的评论。 #standardization #nist #pqcrypto 2016.06.07: 正当程序的死亡: 关于技术驱动的针对指控者和被指控者的私刑暴徒正常化的一些说明。 #ethics #crime #punishment 2016.05.16: 欧洲 "量子宣言 "中的安全欺诈： 量子密码学家如何从欧盟委员会窃取 2.5 亿欧元。 #qkd #quantumcrypto #quantummanifesto 2016.03.15: 托马斯·杰斐逊和苹果公司与联邦调查局的较量: 政府可以审查操作指南吗？ 如果一些读者是罪犯怎么办？ 如果这些书可以被计算机理解怎么办？ 软件出版商的言论自由简介。 #censorship #firstamendment #instructions #software #encryption 2015.11.20: 破解十几个密钥，免费获得一百万个密钥: 批量攻击通常比单目标攻击更具成本效益。 #batching #economics #keysizes #aes #ecc #rsa #dh #logjam 2015.03.14: 优化编译器的死亡: 我在 ETAPS 2015 上的教程摘要。 #etaps #compilers #cpuevolution #hotspots #optimization #domainspecific #returnofthejedi 2015.02.18: 随你打印: Equitrac 的营销部门如何歪曲和干扰您的工作。 #equitrac #followyouprinting #dilbert #officespaceprinter 2014.06.02: Saber 集群: 我们如何构建一个集群，每年只需 50000 欧元即可计算 3000000000000000000000 次乘法。 #nvidia #linux #howto 2014.05.17: 对 Intel 指令集的一些小建议: 对 CPU 架构的低成本更改将使密码学更加安全和快速。 #constanttimecommitment #vmul53 #vcarry #pipelinedocumentation 2014.04.11: NIST 的密码标准化流程: 改进的第一步是承认以前的失败。 #standardization #nist #des #dsa #dualec #nsa 2014.03.23: 如何设计椭圆曲线签名系统: 椭圆曲线签名系统有很多选择。 如果您不关心简单性、速度和安全性，那么标准选择 ECDSA 是合理的。 #signatures #ecc #elgamal #schnorr #ecdsa #eddsa #ed25519 2014.02.13: 针对理想格的子域对数攻击: 计算代数数论处理基于格的密码学。 2014.02.05: Entropy Attacks!（熵攻击！） 传统的观点认为哈希输出无法控制； 传统的观点是错误的。

2014.02.05: Entropy Attacks!（熵攻击！）传统的观点认为哈希输出无法控制；传统的观点是错误的。

传统的观点是，哈希更多的熵源不会有害：如果 H 是任何现代密码哈希函数，那么 H(x,y,z) 至少与 H(x,y) 一样好，无论 z 有多糟糕。 因此，我们将一个来源堆叠在另一个来源之上，将它们全部哈希在一起，并希望至少其中一个是好的。

但是，如果 z 来自可以监听 x 和 y 的恶意来源怎么办？ 例如，想象一下一个恶意的 "安全随机性 "USB 设备，它实际上通过各种侧信道监视所有其他随机性来源，或者--更糟糕的是--想象一下正在查看即将哈希到其中的随机性池的 RDRAND 微代码。 我应该指出，下面描述的任何攻击都不依赖于篡改 x 或 y，或者以其他方式修改恶意熵源之外的数据；您无法通过双重检查数据的完整性来阻止这些攻击。

当然，恶意设备还可以看到其他敏感信息，而不仅仅是 x 和 y。 但这并不意味着攻击者廉价地提取这些信息！ 攻击者需要找到一个从间谍设备出来的通信通道。 受设备影响的随机性生成是特别有吸引力的通道选择，我将在下面解释。

这是一个有趣的攻击示例，可以由这个恶意来源执行：

  1. 生成一个随机 r。
  2. 尝试计算 H(x,y,r)。
  3. 如果 H(x,y,r) 不是以 0000 开头，请返回到步骤 1。
  4. 输出 r 作为 z。

即使 x 和 y 是完全随机的，此攻击也会强制 H(x,y,z) 以 0000 开头。 它速度很快，平均只需要 16 次 H 计算。

也许随机数生成器实际上并不输出 H(x,y,z)；它使用 H(x,y,z) 作为某个生成器 G 的种子，并输出 G(H(x,y,z))。 好吧：攻击者将 H 更改为 G(H)，并再次强制输出 G(H(x,y,z)) 以 0000 开头。 同样，在将恶意熵源与其他熵源混合之前，对其进行预哈希处理并不能阻止攻击。 来自恶意熵源的每次混合都让攻击者产生另一个以 0000 开头的 "随机 "数字。

更一般地，恶意熵源可以产生以 AESk(0), AESk(1),... 的连续 4 位分量开头的 "随机 "数字，而不是产生以 0000, 0000, 0000 等开头的 "随机 "数字，其中 k 是只有攻击者知道的密钥。 除了攻击者之外，没有人能够检测到这种模式。

回想一下，DSA 和 ECDSA 需要随机的 "nonce" 来进行签名。 很容易想象有人从系统的随机数生成器中获取每个 nonce 作为新的 "随机 "数字。 然而，众所周知（例如，参见 https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf），如果攻击者可以预测每个 nonce 的前 4 位，那么在相当少量的签名后，就可以快速计算出用户的密钥。 显然，哈希额外的熵源_确实_会受到损害--以最坏的方式；攻击者拥有用户的密钥！--这与上面所述的传统观点相反。

EdDSA (参见 https://ed25519.cr.yp.to) 是不同的。 它使用随机性生成密钥，然后在签名生成中是完全确定性的（遵循 1997 Barwood、1997 Wigley 等人）。 恶意熵源仍然可以控制密钥的 4 位，使离散对数攻击加速 4 倍，但这不成问题--我们使用具有充足安全边际的曲线。 该源可以通过执行指数级更多的 H 计算来增加这 4 位，但这必须在检查 x 和 y 之后以及生成 "随机 "数字之前，放入可用时间。

当然，密码学中还有许多其他使用随机性的情况：例如，如果您想要前向保密，那么您会不断生成新的 ECDH 密钥。 控制每个密钥的 4 位不如控制 DSA/ECDSA nonce 的 4 位那么有害--它是上面提到的相同因子 4--但是，正如我上面提到的，恶意熵源也可以使用随机性生成作为与攻击者的通信通道。 例如，源以平均仅 2 次公钥生成的成本控制每个_公钥_的低位，并使用这些公钥的低位的串联来通信用户长期密钥的加密。 此通道是无法检测的、带宽合理且成本合理。

另一方面，实际上没有必要大量使用随机数。 如果您设法生成一个安全的 256 位密钥，那么您可以从该密钥派生出您需要的每个密码协议所需的所有 "随机 "数字--您可以以完全确定、可审核、可测试的方式执行此派生，如 EdDSA 所示。 （如果您_没有_设法生成一个安全的 256 位密钥，那么您会遇到更大的问题。）

通过这种尽可能确定性的方法，恶意熵源的整个影响仅限于控制某处的一些 "随机 "位。 至少有两种明显的方法可以进一步减少这种控制：

让我强调一下，出于安全原因，我在这里提倡的是在以下两者之间进行急剧的过渡：

这与人们今天倾向于做的事情完全相反，即不断添加新的熵。 新的熵之所以成为问题，是因为每次添加熵都是恶意熵源控制 "随机 "输出的新机会--破坏 DSA、泄露密钥等。 传统的观点认为哈希输出无法控制；传统的观点是错误的。

（对于某些特殊的熵源，此论点不适用。 例如，当我在登录时，攻击者无法对我击键的内容施加任何严重的控制；我不明白将此特定内容哈希到我笔记本电脑的熵池中如何允许任何攻击。 但我也不明白它如何提供帮助。）

是否有任何有力的论点表明不断添加新的熵是一件好事？ Linux /dev/urandom 手册页声称，如果没有新的熵，用户 "在理论上容易受到密码攻击"，但是（正如我在各种场合提到的那样），这是一个荒谬的论点--怎么会有人同时相信：

还有人断言，RNG 提供针对攻击者的 "预测抵抗 "非常重要，这些攻击者曾经见过整个 RNG 状态。 但是，如果攻击者看到用于生成您的长期 SSL 密钥、长期 PGP 密钥等的 RNG 状态，那么通过提出未来不可预测的随机数，我们究竟能获得什么好处？ 我想起了马克·吐温的一句话：

看哪，傻瓜说，"不要把所有的鸡蛋放在一个篮子里"--这只是一种说法，"分散你的钱和注意力"；但智者说，"把你的所有鸡蛋放在一个篮子里，并--看着那个篮子。"

显然，我们需要可以维护我们长期密钥机密性的系统。 如果我们有这样的系统，攻击者又该如何首先看到 RNG 状态？ 也许 "预测抵抗 "可以为隔离的 RNG 系统提供理论定义，但是我不明白它如何对完整的密码系统有意义。

[广告：如果您对这些主题感兴趣，您可能想加入 randomness-generation 邮件列表； 我几天前在那里发送了此消息。 要订阅，请发送电子邮件至 randomness-generation+subscribe@googlegroups.com。 还有一个巧妙命名的 dsfjdssdfsd 邮件列表，用于讨论 IETF 协议中的随机性。 随机性也是更通用的密码邮件列表上的常见话题。] [2022.01.09 更新：更新了上面的链接。] [2023.03.17 更新：我应该注意到 2006 年的相关工作，即 Thomas Biege 的 "强伪随机数生成器分析" 的第 3.2 节。 2006 年的论文和这篇博客文章都在分析恶意熵源可以做什么。 在此设置之后，2006 年的工作解释了线性哈希函数如何使恶意熵源完全控制输出，而这篇博客文章解释了现代密码哈希函数如何使恶意熵源部分控制输出。] 版本： 这是 20140205-entropy.html 网页的 2023.03.17 版本。