点亮信号

Nina Bindel, 2022.9.23  翻译：丁若禺

本文为合作者Nina Bindel 博士介绍我们最新工作的博文，发表在 Nina Bindel 供职的SandBox AQ公司的Blog上（https://www.sandboxaq.com/post/lighting-the-signal），由Nina Bindel授权翻译刊载。

------------------------------------

本图片由OpenAI DALL·E 2使用以下句子生成：“drawing of a female scientist breaking code by lighting the signal as van gogh”

密钥交换协议是互联网安全的基石。密钥交换是为了使两方(Alice和Bob)完成计算来得到一个共享密钥。这个密钥接下来会用于对称加密。本篇博客中我们会介绍最近提出的针对一种密钥交换协议的攻击背后的核心思想。具体来说，我们将会讨论在密钥复用情况下，针对密钥交换协议的“信号泄漏攻击”，这些协议基于错误学习问题(Learning with Errors, LWE)。

由Yue Qin, Ruoyu Ding, Chi Cheng, Nina Bindel, Yanbin Pan和Jintai Ding共同撰写的论文“Light the Signal: Optimization of Signal Leakage Attacks against LWE-Based Key Exchange”已经被ESORICS 2022（丹麦哥本哈根，2022.9.26-30）接收，并且会在9月26号以线上参加的形式进行汇报。这篇论文同样也在ePrint上(https://eprint.iacr.org/2022/131)。

最早也是最简单的密钥交换协议之一是在1976年由Diffe, Hellman还有（在另一个独立工作里）Merkle设计的。他们的想法是Alice和Bob各自选择自己的私钥s_A和s_B。简单来说，这些私钥是整数，并且在生成元为g的群上。然后他们分别用自己的私钥计算g的s_A次幂和g的s_B次幂发送给对方，传输的就是他们的公钥p_A和p_B。他们得到共享的密钥只需要用对方的公钥计算自己的私钥次幂。这个协议的安全性基于离散对数问题。也就是，即使p_A和p_B是公开的，也不可能根据p_A和p_B来算出s_A和s_B。虽然这对我们目前的计算机来说确实是困难的，但是对于大型容错量子计算机，离散对数问题将会被解决。所以在量子计算机时代，Diffie-Hellmann-Merkle（DHM）密钥交换以及一些其他的密码算法将会被破解（可以访问这个博客(https://www.sandboxaq.com/post/historic-milestone-in-cybersecurity-nist-unveils-new-pqc-suite-of-algorithms)以了解更多关于量子威胁和在量子时代维护安全的方法）。

与DHM有许多相似性的备用协议是基于所谓的错误学习问题（LWE）的密钥交换协议。像之前一样，Alice和Bob先选择自己的私钥。这次私钥是具有小系数的多项式，如s_B = 1+ 2x - 3x^2- x^213 + 4x^317 - 3x^511。通过用一个公开的多项式a（类似上面的生成元g）和他们各自的私钥，他们分别计算公钥p_A和p_B并发送给对方。然后他们就可以计算两个近似相等的h_A和h_B。为了能算出一样的共享密钥，Bob需要发送额外的信息。这个信息就是信号w_B。信号由一系列0和1组成——个数和私钥多项式系数的个数一样多。信号可以与h_A或者h_B作为函数KeyF的输入，输出是最后的共享密钥。

不幸的是，如果Bob每次都重用他的私钥，那么这个额外的信息会允许攻击者恢复s_B。这种攻击叫做密钥复用下的信号泄漏攻击，它首先被Fluhrer发现，之后被用来攻击Ding、Xie和Lin三人提出的基于LWE的DXL密钥交换。其思想是，一个伪装成诚实用户的敌手发送坏的p_A。具体来说，在某个公共参数为q的情况下, 敌手发送的不是多项式，而是q个不同的整数, 即p_A = 0，p_A = 1，…，p_A = q - 1。根据信号的计算方式，事实上这样做会导致信号的每一位会在0和1之间翻转，其频率是相应的私钥系数绝对值的两倍。因此，通过跟踪信号在p_A变化时的行为，对手可以了解到私钥的系数大小。

让我们看个例子。现在s_B = 1+2x-3x^2-x^213+4x^317-3x^511，假设敌手想找出s_B的第3个系数，即-3。为了恢复该系数，敌手给Bob发送p_A = 0，然后把信号中第3个值存起来，它对应于s_B的第3个系数。看下面这张图，我们知道这个信号值等于0。然后敌手发送p_A = 1，然后再把第3个信号值存起来，这次它还是0。如下图中所示，信号值在p_A = 1800左右时第一次从0变到1，在p_A = 4000左右时从1变0。敌手一直增大p_A直到p_A = 16384，信号值会有6次明显的翻转。所以Bob私钥s_B的第3个系数的绝对值等于3。敌手需要对所有的系数都这样做，通常会有512或1024个系数。除此之外，敌手需要做一套类似的过程来恢复系数的正负号，例如上面例子里第3个系数是负的。

放大图中其中一个明显的翻转可以看出，对于一些p_A，信号值实际上是波动的。这是由随机误差e_B引起的。基于这些波动，我们可以区分稳定区域（下图中蓝色和黄色区域）和非稳定区域（下图中波动的白线）。为了正确统计稳定和不稳定区域的数量，并且能够正确记录明显的翻转次数，其实不需要要求发送q个不同p_A。与之前的攻击相反，Bindel、Stebila和Veitch表明，只要确保在每个稳定区域至少收集一个信号值，在每个不稳定区域最多收集一个信号值，那就足够恢复可能的私钥系数的绝对值了。下面的图片展示了一个例子，假定私钥系数的绝对值最大为3，把p_A设为图中绿色点表示的值就足够确定私钥系数是否等于1，2还是3。这样一来就可以把p_A需要的值从98310个减少到只有1266个，并且足够恢复DXL密钥交换中Bob使用的私钥s_B。

最近，Qin、Ding、Cheng、Bindel、Pan和Ding可以把p_A需要的值降低到29个。最新的这个改进的想法是更加巧妙地选择p_A的值。从上图可以看出，实际上红色表示的这三个值就足以唯一地确定私钥系数的绝对值。这一想法是确定与可能的私钥系数绝对值唯一对应的码字。例如，如果码字k_1-k_2-k_3 = 0-1-1，对应私钥系数的绝对值就是1。如果码字是1-1-0或者1-0-1，我们就可以知道绝对值分别是2或3。

这种对信号泄漏的新解释不仅减少了p_A所需值的数量（因此使攻击更有效、更实用），而且还使我们更容易发现方案是否能被这种攻击破解。

最后，必须要提到的是，信号泄漏攻击可以用认证密钥交换协议的通用构造来防护。然而，为了达到更好的效率，我们更希望直接从一个困难问题（如LWE问题）来构造密钥交换。因此，尝试构造这种“直接的”认证密钥交换协议经常会失败。针对信号泄漏攻击的最新改进再次提醒我们，在尝试这种构造时，不要低估信号泄漏攻击的威力。