基于量子退火技术的A5-GMR-2密码密钥恢复攻击

《Journal of Computational Science》：Quantum-annealing-aided key-recovery attack on the A5-GMR-2 cipher

　　摘要：自肖尔算法揭示出RSA等公钥密码系统在理论上易受量子计算机攻击以来，已有三十年时间。然而，构建大规模、容错性强的量子计算机的可行性仍不确定，这就引发了这样一个问题：近期的量子计算机是否会对现有的加密算法产生影响。与此同时，研究人员也在探索近期量子设备的潜力。尤其是量子退火器，以其解决特定优化问题的能力而著称。在本研究中，我们将一种用于A5-GMR-2流式密码的密钥恢复方法的某一阶段，编码为可在现有量子退火硬件上解决的二次无约束二进制优化问题。该密码的非线性加密结构通过经典预处理得到处理，而退火器仅用于处理剩余的约束满足问题，其全局最优解即为候选密钥。我们使用D-Wave Advantage混合求解器解决了这个包含2048个变量的QUBO问题。对于1、2和3个已知的密文流帧，我们分别进行了100次试验，每次都能得到一个候选密钥。不过这些候选密钥并不一定是最终密钥，而且与真实密钥的匹配概率分别为1%、79%和92%。我们还重新审视了之前的经典研究，并给出了候选密钥数量的修正数值。

引言：肖尔算法表明，只要拥有足够大的量子计算机，就可以在多项式时间内对整数进行因式分解并求解离散对数问题[1]，这威胁到了RSA和ECC等广泛使用的公钥系统。为此，NIST启动了后量子密码学标准制定工作[2]，并确定了几类抗量子攻击的加密方案，其中包括Kyber[3][4]、Dilithium[5][6]、Falcon[7]、SPHINCS+[8][9]以及HQC[10]等算法。在对称加密领域，格罗弗算法则为暴力搜索提供了二次速度提升[11]，虽然这降低了安全系数，但可以通过加倍密钥长度来缓解这一问题。不过，这些结论都是基于大规模、容错性强的量子计算机的假设，而这类计算机的出现时间仍不确定。因此，对现有加密算法的安全性评估通常都是基于未来这类硬件上肖尔算法或格罗弗算法所需的计算资源来进行的[12][13][14][15]，而很少考虑当前可用的设备。目前的量子硬件处于普雷斯基尔所称的“噪声中等规模量子”时代：量子比特数量有限，保真度不高，且还不具备完整的错误校正功能[16]。适用于这一阶段的算法包括变分量子算法[17]、量子近似优化算法[18]以及量子退火算法[19][20]，这类算法通过绝热过程将问题的哈密顿量引导至低能量状态。一旦问题被转化为合适的形式，这些算法就能用于解决组合优化问题，不过它们在处理真正的加密问题时的效果如何仍不明确。我们研究了当前硬件上的一种此类问题，目标是一种曾用于卫星电话的流式密码A5-GMR-2，通过反演攻击，该密码的密钥恢复问题可转化为一个适合当前退火器的图结构约束问题[21]。该密码的非线性结构可通过经典预处理处理掉，退火器只需处理剩余的约束满足问题，其全局最优解即为有效的候选密钥。我们将这个剩余问题编码为包含2048个变量的二次无约束二进制优化问题，然后使用D-Wave Advantage混合求解器来求解它。此前的研究已将Grain-128/128a和Bluetooth E0等实际流式密码的代数攻击转化为QUBO问题[22][23]，但这些都是作为专用退火器的计算资源估算，且退火器负责处理复杂的非线性部分。我们的目标则有所不同：我们在真实硬件上实现了明确、可重复的编码，而不声称能带来量子速度提升。量子近似优化算法和量子退火算法已被应用于多种组合优化问题[24][25]，最近的系统性综述也详细介绍了这两类算法及其混合优化框架的发展历程[26][27]。这些综述强调了量子退火算法在信息安全、机器学习等领域解决复杂优化和概率采样问题方面的巨大潜力[26]，同时也指出由于当前硬件限制，混合量子-经典算法已成为一种必要的解决方案[27]。量子近似优化算法通过经典外循环对成本函数进行参数化电路优化，而量子退火算法则是在专用退火硬件上最小化相应的伊辛/QUBO哈密顿量。在NP难问题测试中，克鲁克斯[28]发现量子近似优化算法在Max-Cut问题上的表现可与经典算法相媲美甚至更优，马托尼亚克等人[29]则表明路径积分量子退火算法在旅行商问题上的性能优于模拟退火算法。不过，这类研究都存在一个共同的问题：原始问题往往无法直接适配当前硬件，因此通常需要先通过经典预处理或问题简化步骤才能将问题提交给退火器。恰科等人明确指出了这一点：对于斯坦纳旅行商问题和两级设施选址问题，他们设计了专门的简化方法，缩小问题规模，使QUBO问题更适于当前的D-Wave硬件，从而提高解题质量（同一组作者还将量子退火算法应用于员工调度问题[32]）。还有一些研究将量子近似优化算法和量子退火算法应用于公钥密码学中的难题，如LWE问题[33]、陪集领导问题[34]以及布尔多变量系统问题[35]，不过这些研究都是针对小规模问题展开的。在基于实际NISQ设备的对称密钥加密分析方面，法布等人[36]研究了16位简单密码的已知明文密钥恢复问题，将该问题转化为Max-SAT问题，然后分别在IBM Q Experience2上使用量子近似优化算法，在D-Wave Advantage3上使用改进版的量子退火算法进行求解；由于硬件限制，基于门模型方法的求解只能进行两轮简化后的运算，而量子退火算法则需要经过不切实际的问题转换。佩伊等人[37]则在D-Wave Advantage上采用了量子-经典混合量子退火算法，成功实现了完整的密钥恢复。还有一类研究是从代数结构角度出发，针对实际流式密码展开攻击：布雷克等人[38]将对称密码的代数方程组转化为QUBO形式，在此基础上，沃龙斯基等人[22]和莱斯尼亚克等人[23]又将Grain-128/128a（约有5,751和6,761个逻辑变量）和Bluetooth E0（约有2,728个逻辑变量）的代数攻击转化为QUBO问题。这些研究在研究动机上与我们的工作最为接近，但他们都是估算专用退火器的计算资源，而非在现有硬件上实际执行攻击。

GEO-Mobile Radio Interface（GMR）是由欧洲电信标准协会制定的卫星通信标准[39]，该标准有两种版本：GMR-1被Thuraya、TerreStar和SkyTerra公司采用，而GMR-2则被Inmarsat公司使用。A5-GMR-2是GMR-2中采用的一种流式密码，2012年德里森等人通过逆向工程发现了这种密码[40][41]。在A5-GMR-2被逆向工程之后，人们提出了多种加密分析攻击方法。德里森等人提出了一种利用字节碰撞缺陷的已知明文攻击方法[40]，他们的读冲突攻击方法在有14到20个密文流帧（每个帧长15字节）的情况下，可将暴力搜索的密钥空间从264降低到约210。通过时间与数据之间的权衡，仅使用4到5个密文流帧时，搜索空间还可进一步缩小到218。随后，李等人提出了一种动态猜测与确定攻击方法，该方法仅需一个密文流帧即可将问题复杂度降低到228[42]。后来，胡等人提出了反演攻击方法，该方法利用了A5-GMR-2的某一特性，即该密码的每个组件都可以根据输出部分预测输入[21]，李等人还进一步优化了这种攻击方法[43]。他们还发现了GMR-2标准中的某些缺陷，这些缺陷使得某些明文可以被预测，从而实现仅基于密文的攻击。我们的主要贡献是将之前针对A5-GMR-2的密钥恢复攻击中动态表查找阶段进行明确、可重复的QUBO编码[21][43]，并在当前可用的退火硬件上对该问题进行了实验性求解，将其转化为一个包含2048个变量的问题。这个剩余阶段实际上是一个基于有向图的纯组合约束满足问题：我们需要找到一组满足所有约束条件的顶点，且这些顶点的选择会带来奖励，而违反约束则会受到惩罚，如此一来，全局最优解就恰好是有效的候选密钥。我们在D-Wave Advantage混合求解器上运行了这个问题，并使用1到3个已知的密文流对其进行了测试。为了将这一结果与经典算法的基准结果进行比较，我们还使用标准的经典求解器——模拟退火算法、CDCL SAT求解器、整数线性规划算法以及CP-SAT算法解决了相同的问题。比较结果显示，无论是经典算法还是量子算法，解决这个剩余问题都相当容易，因此我们并不声称能实现量子速度提升，而是将这项工作作为一个可重复的案例研究来展示，而非一种实用的破解方法。最后，我们重新审视了之前研究中的动态表查找算法，发现其中在出度大于1的节点上选择后续节点的方式存在规定不足之处，我们通过明确指定选择规则解决了这个问题，这样一来，对于两个已知的密文流帧，候选密钥的平均数量就从之前报道的29.2个降到了25.65个。本文的其余部分结构如下：第2节介绍相关基础知识，包括A5-GMR-2的标准规格以及量子退火的基本概念；第3节回顾了针对A5-GMR-2的经典密钥恢复攻击方法；第4节将候选密钥的搜索过程转化为优化问题，并介绍了用于量子退火辅助密钥恢复的QUBO建模方法；第5节描述了在D-Wave Advantage混合求解器上的实现过程，评估了相关结果，并将它们与经典算法的基准结果进行了比较；第6节探讨了将我们的方法扩展到仅基于密文的攻击场景；第7节对全文进行总结。

A5-GMR-2的规格说明：A5-GMR-2流式密码的规格是由德里森等人通过逆向工程发现的[40]。该密码以64位主密钥和22位帧编号作为输入，生成15字节的密文流。它的结构由三个部分组成：F、G和H，整体架构如图1所示，F、G和H的结构则分别如图2、图3和图4所示。该密码每时钟周期会根据其内部状态生成1字节的密文流。

对A5-GMR-2的经典攻击方法：在本节中，我们回顾了针对A5-GMR-2的经典攻击方法，重点介绍的是胡等人于2018年提出的反演攻击方法[21]，以及李等人于2023年对其进行的改进[43]。这种反演攻击分为三个阶段：表生成阶段、动态表查找阶段以及验证阶段。在表生成阶段，会根据A5-GMR-2的所谓逆向特性，确定主密钥各字节之间的约束关系。在动态表查找阶段，则会利用这些约束关系来...

利用量子退火进行A5-GMR-2的密钥恢复攻击：我们提出了一种新的攻击方法，用基于量子退火的技术替代原有的动态表查找阶段，用于寻找候选密钥。在本节中，我们假设退火器能够为QUBO问题返回最优解。首先，我们将候选密钥的查找过程转化为一个优化问题，然后再将其映射为QUBO形式。接着，我们会基于这个QUBO模型描述完整的攻击流程。关于实验细节以及在真实量子处理器上的测试结果，将在第5节中进行介绍。

使用量子退火解决我们的QUBO问题：在本节中，我们将介绍在图7所示的整体流程中用于量子退火阶段的D-Wave混合求解器，同时展示第4节中提出的QUBO问题的实验求解结果。我们在实验和评估中使用的所有源代码都可以在https://github.com/dlalswo-1234/Cryptanalysis-in-the-NISQ-Era-Breaking-the-A5-GMR-2-Cipher-using-Quantum-Annealing地址上获取。

将方法扩展到仅基于密文的攻击场景：我们的攻击方法是在已知密文流的条件下设计的，不过之前的研究也指出，由于协议本身存在的缺陷，仅基于密文的攻击也是可行的[43]。具体来说，某些通信渠道会将可能的明文范围限制在大约211个候选值之内。通过猜测一个明文值，再将其与观测到的密文进行异或运算，就可以得到两个密文流帧；这样一来，仅基于密文的攻击就变成了针对每一个猜测的明文值反复进行已知密文流攻击的过程。

结论：我们通过一个案例研究，展示了如何将曾经用于卫星电话的流式密码A5-GMR-2的密钥恢复攻击中的候选密钥搜索阶段编码为QUBO问题，然后在当前可用的量子硬件——D-Wave Advantage混合求解器上对其进行求解。我们的核心贡献在于，将之前经典攻击中的动态表查找阶段进行了完整、可重复的重新建模，将其转化为一个包含2048个变量的QUBO问题，该问题的最优解恰好就是有效的候选密钥。李东在：监督。致谢本研究部分得到了韩国教育部资助的韩国国家研究基金会基础科学研究计划（编号25411243）的支持，还部分得到了江原国立大学2026年度研究基金的资助。利益冲突声明作者声明自己没有已知的、可能影响本文所述工作的财务利益或个人关系。李民在|金仁成|赵俊焕|姜泰勋|金顺烨|李东在韩国江原省春川市，江原国立大学融合安全系，邮编24341