基于AES轮函数认证加密算法研究与设计

高国强，李子臣

基于AES轮函数认证加密算法研究与设计

高国强，李子臣

（北京印刷学院数字版权保护技术研究中心，北京 102600）

认证加密算法同时保证信息的机密性和完整性，在信息安全领域具有广泛的应用前景。利用混合整数线性规划方法，搜索高效且最小活跃S盒较多的迭代结构，基于AES轮函数和广义Feistel结构设计底层的轮函数，实现了一个基于AES轮函数的认证加密算法。该认证加密算法具有抵抗碰撞攻击、差分攻击、线性攻击等攻击的能力，且效率是原有认证加密算法AES-GCM的两倍。

认证加密算法；AES算法；混合整数线性规划

1 引言

认证加密算法能够同时保证数据的机密性和完整性，在信息安全领域有着极其重要的作用。早期认证加密算法多采用加密和消息认证组合的方式，分为先加密后认证、先认证后加密、加密认证同时进行，认证加密一直是密码学科研究的热点[1-2]。2000年，Bellare和Rogaway等[3-4]密码学者正式提出认证加密（AE，authenticated encryption）的概念，认证和加密在一个算法中同时完成，提高了效率。目前，认证加密算法的设计主要有两种模式：一种为基于分组密码的认证加密模式，另一种为直接设计的认证加密算法。分组密码认证加密模式是以S盒调用分组密码方式，具有方便替换底层分组加密算法的优势，具有代表性的认证加密模式有OCB2.0[5]、CCM[6]、EAX[7]、GCM[8]等。直接设计的认证加密算法从密码部件开始，具有速度快、代价低，以及灵活性高等优点，其安全性的理论证明仍是研究热点。其主要设计思想是借助已有的分组密码算法或加密标准设计的设计方法，并依靠各种安全性的分析方法[9-13]进行安全性证明。

2019年2月完成的CAESAR（competition for authenticated encryption: security, applicability, and robustness）算法遴选，使认证加密算法的研究与设计进入了高潮。基于AES加密标准设计了如AEGIS、TiaoXin、ALE等诸多认证加密算法[14-17]。

2 基础知识

2.1 AES轮函数

AES轮函数包含密钥加（AddRoundKey）、字节替换（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）等密码构件。

2.2 差分的概念

差分密码分析是分组密码算法分析方法之一，也是认证加密算法安全性分析的主要方法。其思想是通过分析明文对的差分值对密文对的差分值的影响来恢复某些密钥比特。通常情况，差分分析是比较两个明文的异或与相应的两个密文的异或。差分的定义如下。

2.3 混合整数线性规划

混合线性整数规划MILP用于求目标函数在一些线性约束条件下的最大或最小值。2011年Mouha等[11]将该方法应用于密码算法的安全性证明，通过计算加密算法活跃S盒的个数来验证其安全性。在分组密码、Hash函数以及认证加密算法的设计方面得到了大量应用[18-22]。

在上述约束方程下，利用优化模型的求解工具，如CPLEX、Gurobi等[11]，对目标函数求解。若只要求输入差分变量和所有变量为二元变量，则上述问题变为混合线性整数规划问题。利用MILP的求解方法，可以提高上述目标函数的求解速度。

3 基于AES认证加密算法轮函数的设计

3.1 通用轮函数结构

图1 认证加密算法通用轮函数结构

比如=2时，AddRoundMes进行如下的运算。

3.2 安全性目标

AES的四轮传播定理[21]证明了四轮AES的差分或线性特征中活跃的S盒数至少为25个。但考虑密钥加运算后，即在相关密钥差分分析下，AES的四轮活跃S盒数降为5。

3.3 MILP搜索实验结果

本文的目标是在通用的(,,)轮函数结构进行实验搜索，得到一些安全且高效的轮函数结构，为设计安全的认证加密算法奠定基础。

假设是基于字（32 bit，即矩阵的一列）的向量置换，提前给定参数、、和置换，利用MILP方法验证其四轮活跃S盒个数下界是否大于等于25，以满足安全性目标抵抗内部碰撞攻击。实验过程中每轮使用相同的消息差分变量。

表1 R(4,4,1)的部分安全置换P

4 认证加密算法AMRAE

4.1 关联数据与明文的填充

本文使用斐波那契数列（Fibonacci sequence）进行数据填充，首先，将前16个斐波那契数列的数模256，分别用8 bit二进制序列表示，如表2所示。

表2 斐波那契数列的8 bit二进制表示

比如，明文为0x37=(00110111101010 111100)2，使用斐波那契二进制序列按从左到顺序进行填充，使其长度为128 bit整数倍，填充结果如下。

(00110111101010111100000000010000000100000010000000110000010100001000000011010001010100100010001101110101100110010000111010010111)2

4.2 算法轮函数

4.3 AMRAE认证加密的初始化

（1）初始状态装载；

（2）状态进行十轮迭代更新。

Figure 2 Structure diagram of round function

4.4 关联数据处理

对填充后的关联数据逐块处理，这里的块是4个32 bit的字，具体如下。

4.5 明文加密过程

4.6 认证标签生成

标签的生成分为如下3步。

（1）依据关联数据和明文长度的更新状态。

（3）由最后一轮状态生成标签。

4.7 解密认证过程

5 AMRAE正确性分析

AMRAE算法的加密生成标签过程和解密认证过程相似，有相同的初始化过程、关联数据处理过程和标签生成过程。

加密过程为

解密过程为

下面证明认证的正确性。

加密算法和解密算法使用相同的标签生成方法，由于输入状态矩阵、关联数据相同，生成的标签相同，保证了AMRAE算法认证的正确性。

6 AMRAE安全性分析

直接设计的认证加密算法与基于工作模式的认证加密算法不同，不能进行安全性证明，只能通过不同的密码分析角度对其安全性进行评估。

首先，为了保证认证加密算法AMRAE抵抗密钥恢复攻击和伪造攻击能力达到128 bit，且具有抵抗文献[12]中攻击方法的能力，提出如下规定。

（1）初始向量是随机且带状态的比特串，即每次加密进行更新以不重复使用。

线性攻击[23]是利用密文之间高概率的线性关系，与随机函数进行区分。本文同样通过文献[11]中的方法对AMRAE算法进行评估。通过MILP方法构建其目标函数与约束条件得到其四轮和十轮活跃S盒下界分别为25和100，不仅满足线性特征中活跃S盒下界25的四轮传播定理，且提高了十轮活跃S盒的下界。因此AMRAE算法具有抵抗线性攻击的能力。

滑动攻击[24]是通过找到滑动对的方法，使中间的加密过程变得毫不相关，以达到减少所要分析的密码体制的轮数的目的。为了避免滑动攻击，应该使用不同的函数进行初始化和加密/身份验证，即使很小的差别也是足够的。考虑各过程的抵抗差分/线性攻击能力和运行效率，使消息处理和关联数据处理过程最小活跃S盒为25个。因此，AMRAE进行四轮加密和身份验证过程，以及十轮初始化过程和生成标签过程。本算法具有抵抗滑动攻击的能力。

表3 活跃S盒下界比较

猜测确定攻击[25]主要通过猜测一些变量利用轮函数的传播得到一些新的变量，从而恢复出所有状态变量。由于AMRAE中线性变换MixColumn的分支数是5，那么至少已知4 byte才能得到新的字节。其中向量置换和异或运算都是基于32 bit的字运算。所以整个猜测过程是以32 bit的字进行的，因此猜测至多3个变量恢复所有状态是不可能的，本文算法抵抗猜测确定攻击。

7 AMRAE实现效率

本文在个人计算机上使用Golang语言编码实现了AMRAE算法，采用了MacBook Pro 2015 Intel Core i5处理器。在实现过程中，使AMRAE轮函数结构中的4个AES轮函数进行并行化处理。同时，在相同条件下编码实现了AEGIS和AES-GCM算法，并在表4和图3给出3种算法加密长度为128 bit到40 kB消息的时间消耗对比。

表4 算法消耗时间

通过表4和图3可以看出，AMRAE的时间复杂度与AEGIS算法相比，具有相同的效率。当消息长度小于4 kB时，3个算法的时间复杂度相似，但当消息长度大于4 kB时，AES-GCM算法的时间复杂度明显偏高，在消息长度为40 kB时，接近AMRAE算法的两倍。即消息长度越长，AMRAE算法的加密速度越快。总体来说，AMRAE算法的效率较高。

图3 算法效率对比折线图

Figure 3 Algorithm efficiency comparison line chart

8 结束语

[1] BELLARE M, KOHNO T, NAMPREMPRE C. Authenticated encryption in SSH: Provably fixing the SSH binary packet protocol[C] //Proceedings of the 9th ACM Conference on Computer and Communications Security. 2002: 1-11.

[2] KRAWCZYK H. The order of encryption and authentication for protecting communications (or: How secure is SSL) [C]//Advances in Cryptology-CRYPTO 2001. 2001: 310-331.

[3] BELLARE M, NAMPREMPRE C. Authenticated encryption: Relations among notions and analysis of the generic composition paradigm[C]//Advances in Cryptology-ASIACRYPT 2000. Berlin:Springer. 2000: 531-545.

[4] BELLARE M, ROGAWAY P. Encode-then-encipher encryption: how to exploit nonces or redundancy in plaintexts for efficient cryptography[C]//Advances in Cryptology—ASIACRYPT 2000. 2000: 317-330.

[5] ROGAWAY P, BELLARE M, BLACK J. OCB: a block-cipher mode of operation for efficient authenticated encryption[J]. ACM Transactions on Information and System Security (TISSEC), 2003, 6(3): 365-403.

[6] DWORKIN M J. National institute of standards and technology (NIST). Recommendation for block cipher modes of operation: the CCM mode for authentication and confidentiality[R]. 2004.

[7] BELLARE M, ROGAWAY P, WAGNER D. The EAX mode of operation[M]//Fast Software Encryption. 2004.

[8] MCGREW D A, VIEGA J. The Galois/counter mode of operation (GCM)[J]. Submission to NIST Modes of Operation Process, 2004, (20).

[9] GOLDWASSER S, MICALI S. Probabilistic encryption[J]. Journal of Computer and System Sciences, 1984, 28(2): 270-299.

[10] SASAKI Y, LEI W. Message extension attack against authenticated encryptions: application to PANDA[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2016, 99(1): 49-57.

[11] MOUHA N, WANG Q, GU D, et al. Differential and linear cryptanalysis using mixed-integer linear programming[C]//International Conference on Information Security and Cryptology. 2011: 57-67.

[12] 田玉丹, 韦永壮. 认证加密算法SCREAM及iSCREAM的新伪造攻击[J]. 网络与信息安全学报, 2016, 2(1): 60-64. TIAN Y D, WEI Y Z. New forgery attack on the authenticated cipher SCREAM and iSCREAM[J]. Chinese Journal of Network and Information Security, 2016, 2(1): 60-64.

[13] 田玉丹, 韦永壮. 认证加密模型JAMBU的新分析[J]. 网络与信息安全学报, 2017, 3(7): 53-57.TIAN Y D, WEI Y Z. New cryptanalysis of the authenticated cipher model JAMBU[J]. Chinese Journal of Network and Information Security, 2017, 3(7): 53-57.

[14] WU H, PRENEEL B. AEGIS: a fast authenticated encryption algorithm[C]//Selected Areas in Cryptography-SAC. 2014: 185-201.

[15] BOGDANOV A, MENDEL F, REGAZZONI F, et al. ALE: AES-based lightweight authenticated encryption[C]//International Workshop on Fast Software Encryption. 2013: 447-466.

[16] NIKOLIC I. TiaoXin-346 [EB].

[17] HOANG V T, KROVETZ T. AEZ v5: authenticated encryption by enciphering[EB].

[18] ZHANG J, WU W, ZHENG Y. Security of SM4 against (related-key) differential cryptanalysis[C]//Information Security Practice and Experience. 2016: 65-78.

[19] BILGIN B, BOGDANOV A, KNEŽEVIĆ M, et al. Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware[M]//Cryptographic Hardware and Embedded Systems - CHES 2013. 2013.

[20] BEIERLE C, JÉRÉMY J, STEFAN K, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]//Annual Cryptology Conference. Berlin: Springer, 2016.

[21] 张建, 吴文玲. 基于SM4轮函数设计的认证加密算法[J]. 电子学报, 2018, 46(6): 1294-1299.ZHANG J, WU W L. Authentication encryption based on SM4 round function[J]. Chinese Journal of Electronics, 2018, 46(6):1294-1299.

[22] DAEMEN J, RIJMEN V. The design of rijndael[M]. Berlin: Springer, 2002.

[23] MATSUI M. Linear cryptanalysis method for DES cipher[C]// Advances in Cryptology -EUROCRYPT ’93. 1994.

[24] 尤加勇, 李超. 针对LEX算法的截断滑动攻击[J]. 信息安全与通信保密, 2007(9): 96-98.YOU J Y, LI C. Interruption slide attack against stream cipher lex algorithm[J]. Information Security and Communications Privacy, 2007(9): 96-98.

[25] MINAUD B. Linear biases in AEGIS keystream[C]//Selected Areas in Cryptography. 2014: 290-305.

Research and design of authenticated encryption algorithm based on AES round function

GAO Guoqiang, LI Zichen

Research Center for digital copyright protection technology, Beijing Institute of Graphic Communication, Beijing 102600,China

The authenticated encryption algorithm guarantees the confidentiality and integrity of the information at the same time, and has extensive research and application prospects in the field of information security. With the mixed integer linear programming (MILP) method, the iterative structure with high efficiency and more active S boxes is searched. Based on this new round iterative function and the generalized Feistel structure, an authenticated encryption algorithm with the ability to resist collision attack, differential attack, linear attack and other attacks was designed and implemented, and the efficiency was twice that of AES-GCM.

authenticated encryption algorithm, AES algorithm, MILP

The National Natural Science Foundation of China (No.61370188), The Scientific Research Common Program of Beijing Municipal Commission of Education (No.KM201610015002, No.KM201510015009), The Beijing City Board of Education Science and Technology Key Project (No.KZ201510015015, No.KZ201710015010), Project of Beijing Municipal College Improvement Plan (No.PXM2017_014223_000063), BIGC Project (No.Ec201803, No.Ed201802, No.Ea201806)

TP393

A

10.11959/j.issn.2096−109x.2020028

高国强（1995− ），男，内蒙古兴安盟人，北京印刷学院硕士生，主要研究方向为认证加密算法分析与设计。

李子臣（1962− ），男，河南温县人，博士，北京印刷学院教授、博士生导师，主要研究方向为公钥密码、数字签名、后量子密码。

论文引用格式：高国强, 李子臣. 基于AES轮函数认证加密算法研究与设计[J]. 网络与信息安全学报, 2020, 6(2): 106-115.

GAO G Q, LI Z C. Research and design of authenticated encryption algorithm based on AES round function[J]. Chinese Journal of Network and Information Security, 2020, 6(2): 106-115.

2019−11−15；

2020−02−03

李子臣，lizc2020@163.com

国家自然科学基金资助项目（No.61370188）；北京市教委科研计划一般基金资助项目（No.KM201610015002, No.KM201510015009）；北京市教委科研计划重点基金资助项目（No.KZ201510015015, No.KZ201710015010）；科技创新服务能力建设-科研水平提高定额基金资助项目（No.PXM2017_014223_000063）；北京印刷学院校级基金资助项目（No.Ec201803, No.Ed201802, No. Ea201806）