6轮Square密码算法的中间相遇攻击

李蒙福，苏凡军

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 概 述

随着信息技术的高速发展，数据安全的问题愈加凸显。无论是在理论上还是技术上，密码学在信息安全领域都是不可或缺的。分组密码具有速度快、易于标准化和便于软硬件实现等特点，通常是信息和网络安全中实现数据加密、数字签名、认证及密钥管理的核心体制，也是对称密码学的一个重要分支。分组密码已经在信息安全领域得到了非常广泛的应用，如数字通信安全、工业网络控制安全、无线传感器网络感知安全、无线射频识别安全以及电子商务支付安全等领域。分组密码的研究内容主要包括分组密码的设计和分析，两者相互作用，共同推动着分组密码理论的发展。一方面，在对密码进行安全性分析的同时，可以为设计出更加安全的密码积累更多的经验，另一方面，在密码算法的设计中也会涉及到很多具有现实意义的信息安全技术和一些具有实际应用价值的理论知识。

Square算法是由Joan Daemen和Vincent Rijmen提出的分组密码[1]，发表于1997年，是Rijndael的先驱。Square也是一个具有8轮代换-置换网络[2](SPN)结构的分组密码，可以在各种处理器上实现非常高效的操作。该算法采用了2维4×4的字节矩阵，分组长度和密钥长度都是128 bit。通常，实施对整轮密码算法攻击的难度是非常大的，但是可以利用一些攻击方法减少迭代次数并对密码算法进行分析以衡量其安全性，这样不仅能够促进密码的发展，而且对信息安全也具有重要意义。

当前，分组密码的安全性研究也是一个热点问题。很多密码学研究者在多篇文献中对多种密码算法的安全性进行分析和研究，另外，许多高效的分析方法也被陆续提出，如差分密码分析、截断差分分析、中间相遇攻击等[3-6]。

截断差分密码分析是由Knudsen等提出的差分密码分析的一个变形，与经典的差分分析考虑的具体差分值不同，截断差分只考虑差分的一部分性质。利用截断差分的思想，可以对某些抵抗经典差分密码分析的算法进行攻击。截断差分分析的一般流程是：首先，寻找一条高概率且有效的r-1轮截断差分路径；然后，加密符合要求的明文进而获得密文，从得到的密文对中筛选除差分对符合要求的密文对；最后，对上一步中的密文对进行部分解密，通过计数的方法确定正确的密钥。文献[7]给出了Crypton算法的不可能差分分析。

中间相遇攻击是在文献[8]中提出，最早是用来对分组密码的一种尝试性扩展进行攻击，之后广泛应用于分组密码和Hash函数的安全性分析中。它通过存储加密或解密的中间值，并使用这些中间值来改善强制解密密钥所需的时间，从而削弱了使用多重加密的安全性好处。这使得中间相遇攻击(MITM)成为通用的时空权衡密码分析方法。该种攻击方法的攻击原理是：首先构造出一个合适的区分器，然后将区分器前面的明文从前向后进行加密，后面的密文从后向前进行解密，接着和前面构造出的区分器连接，最后形成一条连贯的攻击路线。其中可能会出现两种结果，假设加密和解密的部分能够顺利连接上区分器，那么猜出的密钥值是无误的，不然为错误的，最后获取符合的密钥值。通过以上步骤，多数的不对密钥会被排除掉。尽管在构造区分器的过程中预计算的复杂度和存储复杂度可能有点大，不过由于仅仅只进行一次的预计算过程，从而在很大程度上也能降低攻击的时间复杂度，所以中间相遇攻击还是一种比较有效的攻击方法。

近年来，中间相遇攻击已成为比较成熟和富有成效的密码分析方法之一，广泛应用于多种分组密码的安全性分析中。文献[9]给出了8轮AES的中间相遇攻击，文献[10]给出了利用多重集和差分枚举技术进行8轮AES中间相遇攻击，文献[11]给出了利用差分枚举技术和有序差分集合进行11轮3D中间相遇攻击，文献[12]给出了缩减轮Crypton的中间相遇攻击分析，文献[13]使用中间相遇攻击对Kalyna算法进行安全性分析。

Square密码算法的安全性分析最早是文献[1]中提出的Square攻击，其成功给出了6轮Square密码的攻击结果，时间复杂度为272。文献[14]对Square进行了Boomerang攻击，运用了7轮Boomerang区分器，实现了全轮的攻击，这也是目前最好的攻击结果。但是，限于计算机的计算能力，其可行性还有待验证。2011年，文献[15]给出了5轮Square的中间相遇攻击分析，预计算时间复杂度为234，空间复杂度为272。

Dunkelman等在分析AES时提出了中间相遇攻击“多重集”的概念。主要思想为：在构造区分器的过程中，完整的输出序列不需要进行存储，只将符合要求的无序的差分筛选集合进行存储，同时再结合有关截断差分的性质，进一步减少决定区分器的参数个数，达到降低存储复杂度的目的。

在分析Square算法的结构特征和一类截断差分的性质的基础上，文中利用差分枚举技术和反弹式思想构造出Square算法的4轮中间相遇区分器，该区分器由11个参数决定。在4轮区分器的基础上前后各扩展一轮，首次实现了对6轮Square算法的中间相遇攻击。在6轮Square密码的攻击过程中，文中通过减少明文数量以降低数据复杂度，又通过使用了多重集进而将决定区分器的参数个数减少为10个，从而进一步降低了预计算的存储复杂度。

2 预备知识

2.1 Square算法描述

Square是一个分组长为128 bit，密钥长为128 bit的SPN型迭代分组密码。Square的轮变换由四个不同的变换组成。128 bit的分组可以用4×4的2维字节矩阵表示。16个字节分组A={a0,a1,…,a15}可表示为如下形式：

(1)M：列混合，对一个状态的每一列进行操作。

M∶b=M(a)⟺bi,j=cjai，0⊕cj-1ai，1⊕cj-2ai，2⊕cj-3ai，3

(2)S：非线性变换，S是一个可逆的8位替换表或S盒。

S∶b=S(a)⟺bi,j=S(ai,j)

(3)T：转置，状态的行列交换。

T∶b=T(a)⟺bi,j=ai,j，T-1=T

(4)σ：轮密钥加。

σ[kt]∶b=σ[kt](a)⟺b=a⊕kt

每一轮进行以上4个操作后，迭代8轮即可得到相关密文，解密操作基本上和加密操作一样，只是调换了密钥的顺序，Square的密钥编排详见文献[15]。

在某些情况下，在两个连续的轮次中交换M和ki的顺序。由于这些操作是线性的，所以可以互换[2]。具体操作是：首先用相等的密钥M-1(ki)排除数据，然后再应用操作M。例如，k0⊕M(x)=M(M-1(k0)⊕x)。

2.2 符号说明

xi：第i轮经过密钥加ki的状态；

yi：第i轮经过M变换的状态；

zi：第i轮经过S的状态；

wi：第i轮经过T的状态；

Δx：状态x的差分；

x[i]：状态x的第i个字节；

x[i,…,j]：状态x从第i个字节到第j个字节；

ui=M-1(ki)；

x‖y：x与y连接；

⊕：异或；

Δxm：=xm⊕xi。

3 6轮Square算法的中间相遇攻击

这一节中，将描述在6轮Square上的MITM攻击。首先，给出需要的定义、引理和推论。然后，提出4轮MITM区分器，并在6轮Square上进行MITM攻击。最后，通过改进4轮区分器，以实现相应攻击复杂度的降低。

3.1 4轮中间相遇区分器

引理1：给定Δi和Δo两个非零差分元素，方程S(x)⊕S(x⊕Δi)=Δo，平均有一个解。这个属性也适用于s-1。

推论1：选择δ集

图1 6轮Square攻击的截断差分特性图

然而，以上给出的25个字节其实可以由以下11个字节决定：

3.2 6轮中间相遇攻击

6轮Square算法中间相遇攻击由两个阶段组成：预计算阶段和在线攻击阶段。攻击过程如图2所示。

1.预计算阶段。

2.在线攻击阶段。

首先找到满足图1中截断差分特征的明文对(pi,pj)，并确定δ集，然后计算差分序列并检测它是否在预计算阶段建立的预计算表中，在线阶段的攻击过程描述如下：

(1)定义一个232个明文结构P[0,4,8,12]，其余12个字节固定为常数。使用这一结构可构成232×(232-1)/2≈263个明文对，并且每个明文对都满足明文差分特性。攻击过程中还需对281个明文结构进行加密以找到281×263×2-12×8=248个对应的密文对以验证密文差分。因此，对于正确的密钥，248对中有248×2-2×3×8=1对遵循整个截断差分特征。因为在第1轮和第5轮的M操作中有两个4→1的转换。注意，不必检查每一对去找到248个密文对，可以将结构存储在由密文中的12个非活动字节索引的散列表中，以获得正确的对。

(2)对248对中的每一对，假设它遵循图1中的整个截断差分特征，进行如下操作：

(a)猜测Δw0[0]，推导出Δz0[0]，根据明文差分推导出Δy0[0]，根据引理1得到y0[0]，然后推出u0[0]。

(b)猜测值Δx5[0]，推导出Δy5[0,4,8,12]，根据密文差分，推导出Δz5[0,4,8,12]，根据引理2可得出z5[0,4,8,12]，z5[0,4,8,12]经过T操作后得到w5[0,1,2,3]，最后推出k6[0,1,2,3]。

(3)最后只剩下1+248×216×2-936≈1个子密钥。根据得到的部分密钥，通过穷举搜索剩余未知字节以恢复全部密钥。

图2 6轮中间相遇攻击图

3.3 对6轮Square攻击的改进

通常，为了降低存储复杂度，可利用多重集把对6轮Square中间相遇攻击决定区分器的参数减少一个(w0[0]可不要)。

根据6轮Square的中间相遇攻击过程可以看出，主要的时间复杂度是对选择的明文进行加密，所以还可以通过减少选择明文的数量以降低时间复杂度。在图1对6轮Square攻击的截断差分特性中，因为对w0活动字节的差分位置有0、1、2、3这4个位置，每个选择可构造22个对应差分表，而x5处的活动字节也会有0、1、2、3这四个位置，所以就可以构造出4×4=16条不同的区分器链，从而可将数据复杂度减少24，但需要额外的预计算表，即存储复杂度则会增加24。

综上，整个攻击的时间复杂度为2109，数据复杂度降为2109，存储复杂度为284。

4 结束语

利用差分枚举技术和反弹式思想，文中构造了Square算法的4轮区分器，又通过多重集降低了预计算的存储复杂度以及通过减少明文数量降低了数据复杂度。研究了Square密码算法的中间相遇攻击技术，首次给出了6轮Square算法的中间相遇攻击，整个攻击的数据复杂度为2109，时间复杂度2109，存储复杂度为284。