原作: Lejla Batina, Stjepan Picek, Bas Westerbaan

译: PQCSF

最近一篇论文的新闻报道以这样的标题引起了一些轰动，标题为:「在AI帮助下破解了NIST推荐的后量子加密演算法」。新闻文章声称所讨论的加密演算法Kyber已被「破解」，然而Kyber已在全球部署。更加戏剧性的是，新闻文章声称「这项研究的革命性在于将深度学习分析应用于旁路差分分析」，这似乎旨在让读者担心人工智慧（AI）会破解下一个什么东西？

有关这篇论文的报导非常不准确: Kyber并未被破解，而且AI被应用于旁路攻击已经行之有年了。这里要澄清，我们关注的是论文周围的新闻报导，而不是论文本身的质量。在本博客文章中，我们将解释AI在密码分析中的实际帮助，并深入研究这篇被新闻误导的 Dubrova、Ngo和Gärtner（DNG）的论文。我们很荣幸邀请到在将AI应用于旁路攻击方面的世界知名专家Prof. Dr. Lejla Batina和Dr. Stjepan Picek，加入我们的博客。

在深入探讨这篇论文之前，我们先介绍一下旁路攻击和Kyber的背景。

密码学的破解

当人们一提到破解密码学时，往往会想像一个房间里挤塞了数学家，他们对被拦截的讯息细微的特征进行解读，并且借助大型电脑来找出密钥。在二战中，纳粹的恩尼格玛密码机就是透过这种方式被破解，让盟军能够对加密的通信进行偷听。

而现今成熟的密码技术被以这种方式破解已经是极为罕见的了，最后一次被大规模破解的加密算法是1987年设计的RC4，而1998年设计的AES几乎没有任何被破解的迹象。最后一次对一个哈希算法的重大突破是对1995年设计的SHA-1的攻击，而2001年发布的SHA-2至今仍未被实际攻破。

那么，如果你不能直接破解密码，该怎么办？那就要想出巧妙的方法。

旁路攻击(Side-channel attacks)

你能猜出下面这个门的密码吗?

你应该能很容易的注意到，某些按键磨损的特别明显，这表示这几个按键经常被使用，这个讯息可以让我们获得一些密码的特征，但不能确定正确的密码顺序，可能是1580，8510，甚至是115085，但比起尝试所有密码容易的多。这是旁路攻击最经典的案例。这个例子展示了使用安全功能（输入密码）时可能会产生一些意外后果（磨损涂料），从而泄漏了一些信息。

远端时间旁路攻击(Remote timing side channel)

当编写密码学程式时，演算法的运行时间就是一个典型的旁路案例。举个例子，当我们建一个RSA签名，需要用一个私钥d来签属信息m，我们计算签名s为m^d（mod n），计算一个数的大次方不是一件容易事，而庆幸的是，我们只需要做模运算，所以有一些平方和乘法的技巧。这是一个伪代码(Pseudocode）的简单实现：

该算法遍历密钥的每个位元(bits)，如果当下位元为1，就做一次乘法。显然，这个代码的运行时间取决于密钥。这并不好，如果攻击者只能对完整运行进行计时，那么他们只能了解密钥中"1"的数量。针对RSA比较严重的计时攻击反而是隐藏在“mod n”的后面。在这上面这个简单的实现中，如果要进行模数运算的数字大于等于 n，那么减法的速度会较慢。这使得攻击者可以发送订制的信息来逐位挑出密钥，类似的攻击非常实用。

因此密码学应该要以「常数时间」运行为原则。这意味着运行时间不会取决于任何秘密信息。在上述例子中，要消除第一个时间问题，可以使用等效于"if"的其他语句来代替：

功率旁路攻击(Power side-channel)

对于功率旁路攻击，情况完全不同。同样，以RSA签名为例。如果我们连接示波器到一张智能卡，而这张智能卡在签名之前使用了一种简单的演算法，并测量其功耗，我们可以直接透过肉眼读取私钥。

即使我们使用常数时间的实现，仍然有微小的功率使用变化可以被检测到。其根本问题在于，切换的硬件闸(gates)的使用比不切换的消耗更多的功率。例如，计算 127 + 64 消耗的功率比 64 + 64 更多。

遮蔽(Masking)

遮蔽是对抗功率旁路攻击的常见对策。在使用机密信息之前，该信息会被随机分成数个部分。然后，计算的大部分工作都是在这些部分进行，最终再将它们组合起来。

在RSA的情况下，创建新签名之前，可以生成一个随机数r，然后分别计算m^(d+r) *(mod n)*和m^r (mod n)。通过这些值，可以在一些额外的注意事项下计算最终的签名m^d (mod n)。

遮蔽不是一种完美的防御方法。分割或组合共享值的部分特别容易受到攻击。但这确实提高了攻击难度：他们需要收集更多的功耗来突破杂讯。在我们的例子中，我们使用了两个共享值，但我们也可以增加它们的数量。功率旁路攻击的抵抗力和实现成本之间存在一个权衡。

在这个领域中最具挑战性的部分之一是估计实际通过跟踪泄露的机密信息的数量以及如何提取它。这就是机器学习介入的地方。

机器学习：从微小的线索中提取密钥

机器学习，其中深度学习领域的一部分，是系统通过数据提取模式来获取知识的能力 - 在这种情况下，是从功耗曲线中提取密钥的能力。机器学习可以根据它们的学习风格分为几个类别。旁路攻击中最流行的是遵循监督学习(supervised learning approach)。在监督学习中，有两个阶段：1）训练，在这里，机器学习模型基于已知的标记示例（例如，我们知道密钥的旁路测量）进行训练，2）测试，在测试阶段，基于训练好的模型和额外的旁路测量（现在，使用未知的密钥），攻击者猜测密钥。下面的图表显示了这类攻击的常见描述。

虽然该威胁模型听起来有些反常，但实实际上很容易理解，攻击者将会取得（并控制）与被攻击的装置相似的装置。

在旁路分析中，依照这两个阶段（训练与测试）所进行的攻击被称为分析攻击(profiling attacks)。

分析攻击并不是什么新东西。最早的一种分析攻击称为“模板攻击”，于2002年出现。自2010年以来，不同的机器学习技术被用于分析攻击，报告显示这些技术都能取得良好的成果，并且能够破解各种目标。然而，真正的突破是在2016年，当分析社群开始使用深度学习时。这大大提高了功率分析攻击的有效性，无论是对对称密钥还是公钥加密，即使目标受到了遮罩或其他反制措施的保护。要清楚的是：它并不能神奇地找到密钥，但它能够更好地从少量功率跟踪中提取泄漏的位元。

虽然以机器学习为基础的旁路攻击很强大，但它们也有限制。精心实施的对策可以使攻击变得更加困难。找到一个能够破解目标的好的机器学习模型可能并不容易：这个阶段通常称为调整，可能需要在强大的集群上持续进行数周。

未来机器学习/人工智慧在旁路分析中会有什么发展？我们希望看到更强大、更易于使用的攻击方法。你可能会认为这会使我们处境更糟，但结果恰恰相反，这将使我们能够更好地估计设备泄漏的实际信息量。我们也希望能够更好地理解为什么某些攻击有效（或无效），以便开发更具成本效益的对策。因此，机器学习在旁道分析中的未来前景非常璀璨，尤其是对于安全评估人员，但我们仍然远未能在现实应用中破解大多数目标。

KYBER

Kyber是一种后量子（PQ）金钥封装方法（KEM）。经过全球六年的竞争，美国国家标准技术研究所（NIST）选择了Kyber作为他们将标准化的后量子金钥协议。金钥协议的目的是让两个之前没有通过任何方式交流的双方在安全的情况下达成共识，以建立一个用于对称加密（例如Chacha20Poly1305）的共享密钥。作为KEM，Kyber的工作方式略有不同，使用不同的术语，与传统的Diffie-Hellman金钥协议（例如X25519）有所不同：

当客户端连接到网站时，客户端首先会产生一组新的临时金钥对，包括一个私钥和一个公钥。客户端将公钥发送给伺服器。伺服器使用该公钥封装一个共享金钥，得到一个随机的共享金钥，并将其保留，同时返回一个密文（其中隐藏了共享金钥）给客户端。客户端可以使用其私钥来解密来自密文中的共享金钥。现在，伺服器和客户端可以使用共享金钥互相通信。

在量子计算机攻击中，金钥协议的安全性特别重要。原因是攻击者可以存储今天的流量，并在未来破解金钥协议，揭示共享金钥和以后使用该金钥加密的所有通信。这就是为什么我们已经在我们的网络中部署了对Kyber的支持。

DNG 论文

在我们有了上面的背景知识后，现在可以开始阅读 DNG 论文了。该论文作者对他们自己实现的 Kyber 掩蔽版本（使用六个 share）进行了一次功率旁路攻击。

攻击的重点

他们攻击的目标是解密步骤。在解密步骤中，共用密钥被提取后，会再次进行封装，然后与原密文进行比较，以检测篡改。对于这个重新加密的步骤，共用密钥的前驱（我们称之为“密钥前驱”）会被逐位编码成多项式。准确地说，256位的密钥需要被转换为一个256个系数模q = 3329的多项式，其中第i个系数是(q + 1) / 2，如果第i位是1，否则为零。

这个函数听起来很简单，但创建掩码版本则很棘手。问题在于，创建密钥的共用版本的自然方式是要有共用版本，这些版本互相进行XOR操作以得到密钥，而分享多项式的自然方式则是需要有共用版本，这些版本互相相加以得到所需的多项式。

这是DNG论文攻击的两个共用版本的实现方式:

这段程式码会重复执行两个分享位元的位元。对于每个位元，它创建一个遮罩，如果该位元为1，则该遮罩为0xffff，否则为0。然后，如果适当，使用此遮罩将(q+1)/2添加到多项式分享中。处理1将使用更多功率。没有必要是AI也可以想出这将是一个有泄漏风险的函数。事实上，这种模式于2016年被指出是脆弱的，并在2020年明确提到了是遮罩Kyber的风险之一。顺便提一下，缓解这种情况的一种方法是同时处理多个位元 - 对于最先进的技术，请收听2023年4月的NIST PQC研讨会。暂时让我们接受这份论文的弱点。

作者在这里没有宣称任何新的攻击。相反的，他们通过两种方式改进了攻击的效果：他们如何训练神经网络，以及如何通过更改发送的密文更有效地使用多个微小的信息。那么他们实现了什么呢？

有效性

为了测试这种攻击，他们使用了一块Cortex M4 CPU核心的Chipwhisperer-lite开发板，他们把它降频到24Mhz。功率的使用是以24Mhz的频率进行采样，精度高达10bits。

为了训练神经网络，他们收集了150,000个功率跟踪，用于解密不同密文（使用已知共享密钥）的封装内容，以获取相同的KEM密钥对。这已经是一种相对于现实攻击而言较为不寻常的情况：对于密钥协定（KEM），密钥对是短暂的；只会被生成和使用一次。尽管如此，长期的KEM密钥对仍然存在合法的用例，例如身份验证、HPKE，特别是ECH。

训练是关键的一步：即使来自同一制造商的不同设备在运行相同代码时的能耗轨迹也可能有很大的不同。即使两个设备是同一型号，它们的能耗轨迹仍可能有显著差异。

作者强调的主要贡献是，他们训练了神经网络来攻击具有6个 shares 的实现，并开始使用训练用于攻击具有5个 shares 的实现的神经网络。一个神经网络训练用于攻击4个 shares 的实现，以此类推。因此，对于这150,000个能耗轨迹中，必须有五分之一来自具有6个 shares 的实现，另外五分之一来自具有5个 shares 的实现，以此类推。看起来不太可能有任何人会部署一个攻击者可以随时在掩蔽使用的 share 数量之间切换的设备。

在考虑了这些因素后，攻击正式开始。作者报告说，从一个具有两个 share 的解密的单个能耗轨迹中，他们可以在理想情况下以概率 0.12％ 恢复共享密钥。对于单次轨迹攻击超过两个 share，他们没有报告数字。

当我们允许多个相同的解密的轨迹时，那么利用旁路攻击就会更加有效。第二个技巧是这个攻击的一个巧妙的转折：作者将密文旋转，以使共享密钥的位于更有利的位置。使用 4 个相同讯息的旋转轨迹，对于具有两个 shares 的实现，成功概率提高到 78％。六个 shares 的实现的成功率仍为 0.5％。当允许来自具有六个 shares 的实现的 20 个轨迹时，共享密钥可以以 87％ 的概率被恢复。

在实际应用中

这个实验所使用的硬体可能与智能卡相当，但与高端设备（例如智慧手机、桌面电脑和伺服器）非常不同。即使是在只有1GHz的嵌入式处理器上，简单的功率分析旁路攻击也更具挑战性，需要使用高端示波器连接到处理器附近，使用数万个信息。对于这种物理存取的攻击，有更好的攻击途径：只需将示波器连接到记忆体汇流排即可。

除了特别脆弱的应用程式（例如智能卡和HSMs），功率旁路攻击被广泛认为是不可行的。虽然有时候，当星球排列得恰当时，一种特别有效的功率旁路攻击可能会因为节流而转化为远程定时攻击，就像Hertzbleed所演示的那样。明确地说：目前的攻击还远远不到这个层次。

即使对于这些脆弱的应用程式，例如智能卡，这种攻击也不是特别有效或令人惊讶的。在实际中，问题不在于遮蔽实现是否会泄露其密码，因为它总是会泄露。问题在于实际执行攻击的难度有多大。像DNG论文这样的论文有助于帮助制造商估计需要实施多少对抗措施，使攻击变得更加昂贵。这不是第一篇研究Kyber功率旁路攻击的论文，也不会是最后一篇。

总结来说

人工智慧并没有完全破坏新的加密技术，反而是一个有用的工具，可以处理杂讯数据，并发现其中的漏洞。直接破解密码和电源旁路攻击之间有很大的区别。 Kyber没有被破解，所呈现的电源旁路攻击也不足以引起警惕。

原文: https://blog.cloudflare.com/kyber-isnt-broken/