一种改进的量子集群攻击方案

一种改进的量子集群攻击方案

肖平安

652901198201164015

摘  要：根据复杂度将攻击定位在原像攻击和碰撞搜索之间，通过量子回弹的前馈操作计算发现碰撞的概率方法，本文提出了一种改进诺查丹玛斯问题的量子集群算法，使压缩函数计算约为。还利用差分轨迹计算，使随机压缩函数能够进行超过的边界，量子集群攻击可以节省算法运行时间，结果表明算法是可行的。

关键词：哈希函数，集群攻击，诺查丹玛斯攻击，量子,搜索算法

1.前言

哈希函数在密码学中是一种通用的工具，因而产生了一些安全需求，如抗碰撞、抗前映像或抗第二前映像。在2006年，Kelsey和Kohno[1]基于状态和输出大小为的压缩函数，为迭代哈希函数引入了一种新的攻击和安全属性。这种攻击要求对手首先提交哈希值，然后在给定消息前缀后，找到消息后缀，使。这种攻击被称为选择目标强制前缀预映像攻击，但通常被称为更生动的诺查丹玛斯攻击。后者是通过与预测场景的连接来实现的:哈希值可以被视为对未来某个事件的所谓正确预测的承诺，攻击者旨在通过找到合适的后缀来证明这一点。

1.1集群攻击

所谓的集群攻击是一种诺查丹玛斯攻击，对压缩函数进行大约次评估。这距离抗碰撞的边界还很远，但显然比次评估的原图像搜索要好。集群攻击可以分为两个阶段：

离线阶段:在离线阶段，攻击者首先确定目标哈希值，并构建一个金刚石结构，这是一个高度为的哈希树。该树通过在不同的消息块上迭代，将个不同的叶子连接到根值。讨论了构建这种树的总体努力是。Blackburn等人[2]指出了分析中的一个缺陷，并给出了·的界。

在线阶段:在在线阶段，攻击者将得到前缀。它搜索链接消息部分到金刚石结构中的一个叶子，这样和树轨迹上的消息块生成后缀。

1.2量子集群攻击

作为一个基本结果，首先认为量子碰撞搜索可以用的计算来进行简单的攻击，而不需要构造金刚石结构。即任意取一个目标值，一旦接收到前缀，使用Grover搜索算法找到位的。如果假设哈希函数是近似恒定，则大约有个这样的消息块映射到目标值。但是搜索算法需要个的量子计算来找到。这已经超过了经典边界(并且对于金刚石结构不需要存储)。

攻击主要针对Merkle-Damgård类型的迭代哈希函数[3]。量子集群攻击原则上也适用于基于回弹的哈希函数，量子攻击也会产生一个对于位输出。对于基本攻击和增强攻击，回弹的容量成为构建金刚石结构的相关参数，中间值上的哈希碰撞，产生总体边界分别地为、。然而，对于[3]，有，这样后一个边界就不如简单攻击的边界。对于像这样的可扩展输出函数，最佳攻击的选择取决于和的关系。

2.量子回弹方案

2.1回弹算法

回弹算法是一种哈希函数分析技术，最早由Mendel等人提出。核心是利用内部状态的可用自由度和截断微分来实现微分轨迹的低概率部分。这部分称为入站阶段，通常位于轨迹的中间部分，然后是概率出站阶段。一般来说，回弹算法中的差分传播在入方向和出方向分别被设计为密集和稀疏。

2.2窦等人的量子回弹方案

窦等人提出了一种涵盖7轮的量子回弹方案。使用攻击状态的自由度，并考虑前馈操作计算发现碰撞的概率。

1.对于和的个值，应用搜索算法求出和的实际对。

2.对于期望的差异和，检查是否适用于和,是否适用于和。

3.将,和,传播到密码的开头和结尾后，检查前馈操作中是否发生了差值抵消。

发现碰撞的复杂度约为。在步骤2中的概率可以提高到。考虑到差分尾迹，如果被确定，将被相应的抑制。因此，从三元组,,中只能得到个自由度，实际上攻击无效。

假定一个访问量子计算机的对手，且压缩函数是可访问的，即对手可以在量子计算机上有效地实现。允许对手使用输入的任意叠加来查询-轮，类似于量子随机环模型。可以在函数依赖于压缩函数的情况下使用Grover,算法。

因为，Boyer等人讨论了即使在解的数量未知的情况下也成立。在对哈希函数的攻击中，将利用压缩函数是平衡的这一事实(通常被假设为常数)。因此，使用搜索算法在个的输入中搜索某个值，其中至少个解映射到，需要一个期望数=函数求值。对于常数，这等于。还得出，在大多数攻击中，可以多次应用搜索算法，使得的总求值的期望数由的和给出以连续的顺序。

3.实验结果

3.1算法

量子算法的局部模拟严重限制了同时可访问的量子位的数量。因此，使用了具有可调块大小和输出的迭代小型哈希函数作为算法的攻击目标。

以类似于开源项目[5]的方式构建这个小型哈希函数，该内容被[4]等人用于评估一般的量子攻击。使用这个排列作为哈希函数的基，并截断它(直到最后位)来推导我们的压缩函数:。

3.2新的差分轨迹算法

通过设置两个入站阶段并使用连接阶段将它们连接起来来构造一个轨迹(图1)。这两个入站阶段使用相同的过程来执行，并且攻击的核心是彻底分析连接阶段。首先，将入站阶段1和2分别放置在轮和上，并计算和的起点。由于哈希函数作为无密钥算法的性质，攻击者可以选择满足给定差分轨迹的消息对。从这个角度来看，从

密钥次序表中获得的自由度被用来连接和的起点。最后，可以通过将起始点和分别传播到密码的开始和结束来计算和。由于前馈操作取消一个字节的概率为，且必须保持，因此该攻击的总时间复杂度为。

具体计算过程如下:

1.从起点和计算和。

2.对于输入输出差分对,，得到与该差对兼容的。

3.确定的值，并确定，以便给定的值和可以连接起来。在这里，由于是确定的，所以也是确定的。

4.给定的值，检查是否成立。如果没有，请重复步骤2。

通过执行这个过程，可以找到连接和的轮密钥和。值得注意的是，和是成立的，和的差分是紧密相连的。

图1:量子回弹算法

3.3实验

评估结果如图2所示。

图2:算法评估结果和压缩函数。

参数表示金刚石树的高度。在线和离线分别表示在线和离线运行时，以秒为单位。和分别表示量子函数对函数的调用。表示在攻击期间为构建金刚石结构而对消息和叶子进行采样操作的数量。对于特定的哈希函数，简单攻击在某些情况下会失败，在这种情况下，不测量它的运行时间。

对于，即只包含一层的树，对函数F的调用的和是最小的。对于基本金刚石结构和增强金刚石结构的攻击，这是正确的，对于，确定了的最佳选择。此外，当时，基本在线攻击和增强在线攻击的函数调用之和已经小于或等于基于搜索算法的简单量子攻击中的16个量子函数调用。然而，金刚石结构攻击的运行时间比简单攻击的运行时间要长。在电路设计中，通过模拟了多次压缩函数和指数数量的n位Toffoli门，而在简单的量子攻击中只模拟了四次压缩函数调用，因此使用金刚石结构的优势还没有因为用小值n而得到回报大。

因为h(m,y)不是满射的，也不是β平衡的。简单攻击选择了一个随机值，导致攻击失败的值y没有原像。在这种情况下，Grover算法无法找到相应的原像。然而，更高级的攻击总是成功的。原因是树是正向构建的，这样每个值y至少有两个原像。已知所有的观察结果都是特定于参数n=B=8的。根据理论结果，对于更高的n值，即使k更小，在线运行时间的差异也会更大。

4.结论

改进方案是在一个理想化的量子模型中设计和分析的，但对这个小型示例的实现表明，原则上可以在量子计算机上运行。将这些攻击转化为真正的量子程序可能仍然需要很多工程方面的工作，这些可能会显著影响运行时间。同时，也利用基于哈希函数提出的量子回弹攻击，更新差分轨迹跟踪方案，构建了新的差分函数，通过其增大压缩函数边界，最终达到节约算法运行时间的目的。

文献