三轮和四轮AES的新型区分器

王美琴　胡凯　高超

摘 要：高级加密标准（Advanced Encryption Standard，AES）是国际上最被广泛使用的加密标准之一。近年来许多新设计的算法选择使用缩减轮数的AES算法作为底层算法，所以缩减轮数AES的安全性，包括可区分性质需要更加深入的研究。论文利用AES列混合的矩阵每列有两个相同系数的性质，给出三轮和四轮AES新的区分攻击。新的区分攻击与传统的三轮和四轮积分区分器类似，拥有相同的数据和时间复杂度。

关键词：高级加密标准；AES；区分器

中图分类号：O236.2 文献标识码：B

Abstract： Advanced Encryption Standard （AES） is one of the most widely used encryption algorithms all over the world. Recently， many new cryptography schemes are designed on the reduced-round AES so the security including the distinguishing property of AES deserves more study. This paper takes advantage of the fact that the matrix used in the MixColumn has two identical coefficients in each column to construct new distinguishes on 3-round and 4-round AES. These two new distinguishers are similar with the traditional integral distinguishers and have the same complexities of time and data.

Key words： advanced encryption standard； AES； distinguisher

1 引言

網络空间的发展是当今世界科技变革的代表性领域。网络空间的安全问题也是各国重点关注的议题[1]。密码学是网络空间安全的基础学科，密码算法是保障网络安全的必备工具。自从AES公布以来，已经成为最被广泛使用的加密算法，研究AES的安全性有着重要意义。

2 研究背景与贡献

2.1 研究背景

想攻击一个密码算法，首先要发现该算法的区分器。密码算法的区分器，是指密码算法与一个随机函数之间表现上的不同。随后敌手可以利用此区分器对该密码算法进行区分攻击甚至是密钥恢复攻击。一般说来，区分攻击弱于密钥恢复攻击。然而，由于近年来新的密码算法体制的设计往往是基于已有的、被广泛分析的密码算法，密码算法的可区分性质受到了越来越多的关注。（缩短轮数的）AES从发布起经受住了密码学界的多种分析，其安全性被普遍认可。所以，有不少新的密码算法设计者会选择缩短轮数的AES来构建新算法。例如，征集认真加密标准算法的CAESAR竞赛[3]（Competition for Authenticated Encryption： Security， Application and Robustness）的候选算法AEGIS算法[4]选择四轮AES作为状态升级函数；ELmd算法[5]建议使用缩短轮数版本的AES算法作为底层算法。尽管这些新的密码算法的安全性不完全依赖于底层算法的安全性，但是对于这些新设计的算法来说，底层算法的安全性包括可区分性质仍然至关重要。

AES是被使用最广泛的加密算法之一，其安全性备受关注。对AES的大量分析显示，缩短轮数版本的AES存在区分器。传统的AES区分器主要对三轮和四轮的AES版本起作用。例如，AES存在三轮和四轮的积分区分器[5]、四轮的不可能差分区分器[7]、四轮的零相关区分器[8]等。这些区分器都是比较通用的区分器，没有考虑AES的很多组件的细节。例如，这些区分器都只利用了AES的列混合组件使用的矩阵的最大分支数是五这个性质而没有用到该矩阵的系数信息。在2016年的美密会上，孙兵等人首次利用了列混合组件的矩阵每列有两个系数相等的信息，给出了五轮的AES零相关区分器和积分区分器[9]。由于这两个区分器的表现形式和密钥的具体信息有关，这种区分器后来被定义为密钥相关区分器[10]。随后，一大批针对五轮AES的区分器被提出[10-14]，大大提高了密码学界对于AES安全性的认识。

本文探索AES的列混合的系数信息在三轮AES和四轮AES场景下的应用，从而加深对相应轮数的AES安全性的认识。

2.2 本文贡献

在本文中，利用列混合的系数信息，分别给出针对三轮和四轮AES的区分攻击。这两种区分攻击的时空复杂度和传统的积分区分器相同，但是与积分区分器相比，新的区分器能够识别更多算法的实现细节，也就是说，积分区分器只能识别出MC使用的矩阵的最大分支数是五，而新的区分器除此之外，还可以识别出该矩阵的每列上有两个系数是相等的。尽管新的区分器都采用了列混合的系数信息，但与其他利用MC系数信息的区分器不同，我们的区分器是密钥无关的，即最终区分器的表现在任何密钥下都是一致的。

3 符号约定与准备工作

3.1 符号约定

为了叙述的明确和方便，约定本文使用的符号和意义如表1所示。

3.2 AES

AES是一个分组长度为128比特的分组密码算法，它采用SPN结构。根据采用的密钥长度，AES有三个版本，分别是AES-128、AES-192和AES-256，加密轮数分别是10轮、12轮和14轮。AES的128比特的明文、密文和内部状态可以写成一个4×4的状态矩阵，矩阵的每一个块都是一个字节。AES的组件都是定义在有限域GF（28）上的操作，该有限域的不可约多项式是m（x）=x8+x4+x3+x+1。AES的每一轮的轮函数可以写成R（x）=ak○MC○SR○SB（x）。

其中MC使用的矩陣是

，

注意MC矩阵的每一列都有两个相同的系数 1。AES的更多细节请参考其设计文档[1]。

4 新的三轮AES区分器

本节将介绍如何利用MC矩阵每一行有两个相同的系数的性质得到的一个新的三轮AES区分器。此区分器如命题1所述。

命题 1：对于三轮AES算法（不包含最后的MC操作），如果明文的第（0，0）字节是遍历的，其他15个字节取任意常数，那么相应的256个密文有如下性质：

。

也就是等于某个值的个数一定是个偶数。然而，对于随机置换来说，此事件出现的概率约为2-128。

证明：P0，0是遍历的，其他字节是常数，AK和SB都是字节上的置换，SR不会改变字节内部状态，所以也是遍历的，其他字节仍然是常数。经过MC上的矩阵乘法，四个字节，，，都是遍历的。经过接下来的AK，SB， SR操作，遍历的四个字节变成了，，，，其他字节是常数。也就是每列都是一个遍历的字节和三个常数。考虑第一列，经过MC之后，有

，

。

由于对256个明文来说，上述两式的右边三项都分别是一个固定常数，而第一项都是遍历项，所以有

。

结合接下来的AK和SB操作，因为AES的所有S盒都是相同的，我们有相当于AES的S盒的输出差分值，所有其每个可能的值出现的次数，必然是偶数，异或最后的密钥不会改变这个结果。

对于随机置换来说，256个值中，只要有128个值出现的次数是偶数，那么剩下的128个值出现的次数也必然是偶数，所以要想256个值出现的次数全部是偶数，只需要其中128个值是偶数即可。对于随机置换， 个异或值是偶数的概率是2-128。证毕。

此区分器的数据复杂度是28，攻击时需要对计数器进行28次累加操作，所以数据复杂度和时间复杂度与传统的三轮积分区分器相同。但是此区分器需要存储一个256个字节的计数器，这比三轮积分区分器略大。

5 新的四轮AES区分器

从第三节三轮AES区分器的细节来看，任意一个明文集合满足一个字节是遍历的，其余字节是常数，都可得到相似的结果。和高阶积分类似，对于四轮AES，如果明文的（0，0），（1，1），（2，2），（3，3）字节是活跃的，可以将明文集合看成是224个满足三轮区分器明文的集合，由于最后对每个异或值的个数进行统计是累加的，所以最后每个异或值的个数仍然是偶数。我们不加证明地给出命题2。

命题2：对于四轮AES算法（不包含最后的MC操作），如果明文的第（0，0），（1，1），（2，2），（3，3）字节是遍历的，其他12个字节取任意常数，那么相应的232个密文有如下性质：

也就是等于某个值的个数一定是个偶数。然而，对于随机置换来说，此事件出现的概率约为2-128。

四轮的区分器需要232个选择明文，232次内存访问以更新计数器，存储复杂度仍然是256个字节。

6 结束语

利用MC矩阵每列有两个相同系数的性质，给出了三轮和四轮AES新的区分器。这两种区分器和传统的三轮和四轮AES的积分区分器类似，数据和时间复杂度也相同，但是比积分区分器能够识别更多的算法信息，也就是MC使用的矩阵每列有两个相同的系数。新的区分器可以更好地理解MC的系数对AES算法安全性的影响，为以后的算法设计和分析提供指导。

参考文献

[1] 李偲，先喻.美国网络空间战略的安全化问题研究[J].网络空间安全，2018，01，21-6.

[2] Rijmen， J.D.V.， The Design of Rijndael：AES-The Advanced Encryption Standard. Edition 1 ed. 2001， Berlin： Springer-Verlag.

[3] CAESAR： Competition for Authenticated Encryption： Security， Applicability， and Robustness， https：//competitions.cr.yp.to/index.html.

[4] Hongjun Wu， B.P.， AEGIS： A Fast Authenticated Encryption Algorithm （v1.1. 2016），https：//competitions.cr.yp.to/round3/aegisv11.pdf.

[5] Nilanjan Datta， M.N.， Proposal of ELmD v2.1. 2016. https：//competition/cr.yp.to/round2/elmdv21.pdf.

[6] Knudsen， L. and D. Wagner. Integral Cryptanalysis. 2002. Berlin， Heidelberg： Springer Berlin Heidelberg. Page 112-127.

[7] Biham， E.， Keller， N.： `Cryptanalysis of reduced variants of Rijndael'， 3rdAES Conf.， 2000.

[8] Bagdonov A， Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers. 2014： 369-83.

[9] Sun B， Liu M， Guo J， Qu L， Rijmen V. New Insights On AES-Like SPN Ciphers. In： Robshaw M， Katz J， eds.Berlin， Heidelberg： Springer Berlin Heidelberg， 2016： 605-24.

[10] Grassi L， Rechberger C， R?njom S. Subspace Trail Cryptanalysis and its Applications to AES. IACR Transactions on Symmetric Cryptology； Volume 2016， Issue 2. 2017.

[11] Cui T， Sun L， Chen H， Wang M. Statistical Integral Distinguisher with Multi-Structure and its Application on AES. In： Pieprzyk J， Suriadi S， eds.Cham： Springer International Publishing， 2017： 402-20.

[12] Grassi L， Rechberger C， R?njom S. A New Structural-Differential Property of 5-Round AES. In： Coron J， Nielsen JB， eds.Cham： Springer International Publishing， 2017： 289-317.

[13] R?njom S， Bardeh NG， Helleseth T. Yoyo Tricks with AES. In： Takagi T， Peyrin T， eds.Cham： Springer International Publishing， 2017： 217-43.

[14] Grassi L. MixColumns Properties and Attacks on （Round-Reduced） AES with a Single Secret S-Box. In： Smart NP， ed.Cham： Springer International Publishing， 2018： 243-63.

作者簡介：

王美琴（1974-），女，山东人，教授；主要研究方向和关注领域：对称密码的分析与设计。

胡凯（1992-），男，山东人，硕士研究生；主要研究方向和关注领域：对称密码的分析与设计。

高超（1981-），男，山东人，硕士研究生；主要研究方向和关注领域：对称密码的分析与设计。