基于AES輪函數(shù)認(rèn)證加密算法研究與設(shè)計(jì)

高國(guó)強(qiáng)，李子臣

基于AES輪函數(shù)認(rèn)證加密算法研究與設(shè)計(jì)

高國(guó)強(qiáng)，李子臣

（北京印刷學(xué)院數(shù)字版權(quán)保護(hù)技術(shù)研究中心，北京 102600）

認(rèn)證加密算法同時(shí)保證信息的機(jī)密性和完整性，在信息安全領(lǐng)域具有廣泛的應(yīng)用前景。利用混合整數(shù)線性規(guī)劃方法，搜索高效且最小活躍S盒較多的迭代結(jié)構(gòu)，基于AES輪函數(shù)和廣義Feistel結(jié)構(gòu)設(shè)計(jì)底層的輪函數(shù)，實(shí)現(xiàn)了一個(gè)基于AES輪函數(shù)的認(rèn)證加密算法。該認(rèn)證加密算法具有抵抗碰撞攻擊、差分攻擊、線性攻擊等攻擊的能力，且效率是原有認(rèn)證加密算法AES-GCM的兩倍。

認(rèn)證加密算法；AES算法；混合整數(shù)線性規(guī)劃

1 引言

認(rèn)證加密算法能夠同時(shí)保證數(shù)據(jù)的機(jī)密性和完整性，在信息安全領(lǐng)域有著極其重要的作用。早期認(rèn)證加密算法多采用加密和消息認(rèn)證組合的方式，分為先加密后認(rèn)證、先認(rèn)證后加密、加密認(rèn)證同時(shí)進(jìn)行，認(rèn)證加密一直是密碼學(xué)科研究的熱點(diǎn)[1-2]。2000年，Bellare和Rogaway等[3-4]密碼學(xué)者正式提出認(rèn)證加密（AE，authenticated encryption）的概念，認(rèn)證和加密在一個(gè)算法中同時(shí)完成，提高了效率。目前，認(rèn)證加密算法的設(shè)計(jì)主要有兩種模式：一種為基于分組密碼的認(rèn)證加密模式，另一種為直接設(shè)計(jì)的認(rèn)證加密算法。分組密碼認(rèn)證加密模式是以S盒調(diào)用分組密碼方式，具有方便替換底層分組加密算法的優(yōu)勢(shì)，具有代表性的認(rèn)證加密模式有OCB2.0[5]、CCM[6]、EAX[7]、GCM[8]等。直接設(shè)計(jì)的認(rèn)證加密算法從密碼部件開始，具有速度快、代價(jià)低，以及靈活性高等優(yōu)點(diǎn)，其安全性的理論證明仍是研究熱點(diǎn)。其主要設(shè)計(jì)思想是借助已有的分組密碼算法或加密標(biāo)準(zhǔn)設(shè)計(jì)的設(shè)計(jì)方法，并依靠各種安全性的分析方法[9-13]進(jìn)行安全性證明。

2019年2月完成的CAESAR（competition for authenticated encryption: security, applicability, and robustness）算法遴選，使認(rèn)證加密算法的研究與設(shè)計(jì)進(jìn)入了高潮。基于AES加密標(biāo)準(zhǔn)設(shè)計(jì)了如AEGIS、TiaoXin、ALE等諸多認(rèn)證加密算法[14-17]。

2 基礎(chǔ)知識(shí)

2.1 AES輪函數(shù)

AES輪函數(shù)包含密鑰加（AddRoundKey）、字節(jié)替換（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）等密碼構(gòu)件。

2.2 差分的概念

差分密碼分析是分組密碼算法分析方法之一，也是認(rèn)證加密算法安全性分析的主要方法。其思想是通過(guò)分析明文對(duì)的差分值對(duì)密文對(duì)的差分值的影響來(lái)恢復(fù)某些密鑰比特。通常情況，差分分析是比較兩個(gè)明文的異或與相應(yīng)的兩個(gè)密文的異或。差分的定義如下。

2.3 混合整數(shù)線性規(guī)劃

混合線性整數(shù)規(guī)劃MILP用于求目標(biāo)函數(shù)在一些線性約束條件下的最大或最小值。2011年Mouha等[11]將該方法應(yīng)用于密碼算法的安全性證明，通過(guò)計(jì)算加密算法活躍S盒的個(gè)數(shù)來(lái)驗(yàn)證其安全性。在分組密碼、Hash函數(shù)以及認(rèn)證加密算法的設(shè)計(jì)方面得到了大量應(yīng)用[18-22]。

在上述約束方程下，利用優(yōu)化模型的求解工具，如CPLEX、Gurobi等[11]，對(duì)目標(biāo)函數(shù)求解。若只要求輸入差分變量和所有變量為二元變量，則上述問(wèn)題變?yōu)榛旌暇€性整數(shù)規(guī)劃問(wèn)題。利用MILP的求解方法，可以提高上述目標(biāo)函數(shù)的求解速度。

3 基于AES認(rèn)證加密算法輪函數(shù)的設(shè)計(jì)

3.1 通用輪函數(shù)結(jié)構(gòu)

圖1 認(rèn)證加密算法通用輪函數(shù)結(jié)構(gòu)

比如=2時(shí)，AddRoundMes進(jìn)行如下的運(yùn)算。

3.2 安全性目標(biāo)

AES的四輪傳播定理[21]證明了四輪AES的差分或線性特征中活躍的S盒數(shù)至少為25個(gè)。但考慮密鑰加運(yùn)算后，即在相關(guān)密鑰差分分析下，AES的四輪活躍S盒數(shù)降為5。

3.3 MILP搜索實(shí)驗(yàn)結(jié)果

本文的目標(biāo)是在通用的(,,)輪函數(shù)結(jié)構(gòu)進(jìn)行實(shí)驗(yàn)搜索，得到一些安全且高效的輪函數(shù)結(jié)構(gòu)，為設(shè)計(jì)安全的認(rèn)證加密算法奠定基礎(chǔ)。

假設(shè)是基于字（32 bit，即矩陣的一列）的向量置換，提前給定參數(shù)、、和置換，利用MILP方法驗(yàn)證其四輪活躍S盒個(gè)數(shù)下界是否大于等于25，以滿足安全性目標(biāo)抵抗內(nèi)部碰撞攻擊。實(shí)驗(yàn)過(guò)程中每輪使用相同的消息差分變量。

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

4 認(rèn)證加密算法AMRAE

4.1 關(guān)聯(lián)數(shù)據(jù)與明文的填充

本文使用斐波那契數(shù)列（Fibonacci sequence）進(jìn)行數(shù)據(jù)填充，首先，將前16個(gè)斐波那契數(shù)列的數(shù)模256，分別用8 bit二進(jìn)制序列表示，如表2所示。

表2 斐波那契數(shù)列的8 bit二進(jìn)制表示

比如，明文為0x37=(00110111101010 111100)2，使用斐波那契二進(jìn)制序列按從左到順序進(jìn)行填充，使其長(zhǎng)度為128 bit整數(shù)倍，填充結(jié)果如下。

(00110111101010111100000000010000000100000010000000110000010100001000000011010001010100100010001101110101100110010000111010010111)2

4.2 算法輪函數(shù)

4.3 AMRAE認(rèn)證加密的初始化

（1）初始狀態(tài)裝載；

（2）狀態(tài)進(jìn)行十輪迭代更新。

Figure 2 Structure diagram of round function

4.4 關(guān)聯(lián)數(shù)據(jù)處理

對(duì)填充后的關(guān)聯(lián)數(shù)據(jù)逐塊處理，這里的塊是4個(gè)32 bit的字，具體如下。

4.5 明文加密過(guò)程

4.6 認(rèn)證標(biāo)簽生成

標(biāo)簽的生成分為如下3步。

（1）依據(jù)關(guān)聯(lián)數(shù)據(jù)和明文長(zhǎng)度的更新狀態(tài)。

（3）由最后一輪狀態(tài)生成標(biāo)簽。

4.7 解密認(rèn)證過(guò)程

5 AMRAE正確性分析

AMRAE算法的加密生成標(biāo)簽過(guò)程和解密認(rèn)證過(guò)程相似，有相同的初始化過(guò)程、關(guān)聯(lián)數(shù)據(jù)處理過(guò)程和標(biāo)簽生成過(guò)程。

加密過(guò)程為

解密過(guò)程為

下面證明認(rèn)證的正確性。

加密算法和解密算法使用相同的標(biāo)簽生成方法，由于輸入狀態(tài)矩陣、關(guān)聯(lián)數(shù)據(jù)相同，生成的標(biāo)簽相同，保證了AMRAE算法認(rèn)證的正確性。

6 AMRAE安全性分析

直接設(shè)計(jì)的認(rèn)證加密算法與基于工作模式的認(rèn)證加密算法不同，不能進(jìn)行安全性證明，只能通過(guò)不同的密碼分析角度對(duì)其安全性進(jìn)行評(píng)估。

首先，為了保證認(rèn)證加密算法AMRAE抵抗密鑰恢復(fù)攻擊和偽造攻擊能力達(dá)到128 bit，且具有抵抗文獻(xiàn)[12]中攻擊方法的能力，提出如下規(guī)定。

（1）初始向量是隨機(jī)且?guī)顟B(tài)的比特串，即每次加密進(jìn)行更新以不重復(fù)使用。

線性攻擊[23]是利用密文之間高概率的線性關(guān)系，與隨機(jī)函數(shù)進(jìn)行區(qū)分。本文同樣通過(guò)文獻(xiàn)[11]中的方法對(duì)AMRAE算法進(jìn)行評(píng)估。通過(guò)MILP方法構(gòu)建其目標(biāo)函數(shù)與約束條件得到其四輪和十輪活躍S盒下界分別為25和100，不僅滿足線性特征中活躍S盒下界25的四輪傳播定理，且提高了十輪活躍S盒的下界。因此AMRAE算法具有抵抗線性攻擊的能力。

滑動(dòng)攻擊[24]是通過(guò)找到滑動(dòng)對(duì)的方法，使中間的加密過(guò)程變得毫不相關(guān)，以達(dá)到減少所要分析的密碼體制的輪數(shù)的目的。為了避免滑動(dòng)攻擊，應(yīng)該使用不同的函數(shù)進(jìn)行初始化和加密/身份驗(yàn)證，即使很小的差別也是足夠的。考慮各過(guò)程的抵抗差分/線性攻擊能力和運(yùn)行效率，使消息處理和關(guān)聯(lián)數(shù)據(jù)處理過(guò)程最小活躍S盒為25個(gè)。因此，AMRAE進(jìn)行四輪加密和身份驗(yàn)證過(guò)程，以及十輪初始化過(guò)程和生成標(biāo)簽過(guò)程。本算法具有抵抗滑動(dòng)攻擊的能力。

表3 活躍S盒下界比較

猜測(cè)確定攻擊[25]主要通過(guò)猜測(cè)一些變量利用輪函數(shù)的傳播得到一些新的變量，從而恢復(fù)出所有狀態(tài)變量。由于AMRAE中線性變換MixColumn的分支數(shù)是5，那么至少已知4 byte才能得到新的字節(jié)。其中向量置換和異或運(yùn)算都是基于32 bit的字運(yùn)算。所以整個(gè)猜測(cè)過(guò)程是以32 bit的字進(jìn)行的，因此猜測(cè)至多3個(gè)變量恢復(fù)所有狀態(tài)是不可能的，本文算法抵抗猜測(cè)確定攻擊。

7 AMRAE實(shí)現(xiàn)效率

本文在個(gè)人計(jì)算機(jī)上使用Golang語(yǔ)言編碼實(shí)現(xiàn)了AMRAE算法，采用了MacBook Pro 2015 Intel Core i5處理器。在實(shí)現(xiàn)過(guò)程中，使AMRAE輪函數(shù)結(jié)構(gòu)中的4個(gè)AES輪函數(shù)進(jìn)行并行化處理。同時(shí)，在相同條件下編碼實(shí)現(xiàn)了AEGIS和AES-GCM算法，并在表4和圖3給出3種算法加密長(zhǎng)度為128 bit到40 kB消息的時(shí)間消耗對(duì)比。

表4 算法消耗時(shí)間

通過(guò)表4和圖3可以看出，AMRAE的時(shí)間復(fù)雜度與AEGIS算法相比，具有相同的效率。當(dāng)消息長(zhǎng)度小于4 kB時(shí)，3個(gè)算法的時(shí)間復(fù)雜度相似，但當(dāng)消息長(zhǎng)度大于4 kB時(shí)，AES-GCM算法的時(shí)間復(fù)雜度明顯偏高，在消息長(zhǎng)度為40 kB時(shí)，接近AMRAE算法的兩倍。即消息長(zhǎng)度越長(zhǎng)，AMRAE算法的加密速度越快。總體來(lái)說(shuō)，AMRAE算法的效率較高。

圖3 算法效率對(duì)比折線圖

Figure 3 Algorithm efficiency comparison line chart

8 結(jié)束語(yǔ)

[1] BELLARE M, KOHNO T, NAMPREMPRE C. Authenticated encryption in SSH: Provably ?xing 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 e?cient 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 con?dentiality[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] 田玉丹, 韋永壯. 認(rèn)證加密算法SCREAM及iSCREAM的新偽造攻擊[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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] 田玉丹, 韋永壯. 認(rèn)證加密模型JAMBU的新分析[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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輪函數(shù)設(shè)計(jì)的認(rèn)證加密算法[J]. 電子學(xué)報(bào), 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] 尤加勇, 李超. 針對(duì)LEX算法的截?cái)嗷瑒?dòng)攻擊[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

高國(guó)強(qiáng)（1995? ），男，內(nèi)蒙古興安盟人，北京印刷學(xué)院碩士生，主要研究方向?yàn)檎J(rèn)證加密算法分析與設(shè)計(jì)。

李子臣（1962? ），男，河南溫縣人，博士，北京印刷學(xué)院教授、博士生導(dǎo)師，主要研究方向?yàn)楣€密碼、數(shù)字簽名、后量子密碼。

論文引用格式：高國(guó)強(qiáng), 李子臣. 基于AES輪函數(shù)認(rèn)證加密算法研究與設(shè)計(jì)[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61370188）；北京市教委科研計(jì)劃一般基金資助項(xiàng)目（No.KM201610015002, No.KM201510015009）；北京市教委科研計(jì)劃重點(diǎn)基金資助項(xiàng)目（No.KZ201510015015, No.KZ201710015010）；科技創(chuàng)新服務(wù)能力建設(shè)-科研水平提高定額基金資助項(xiàng)目（No.PXM2017_014223_000063）；北京印刷學(xué)院校級(jí)基金資助項(xiàng)目（No.Ec201803, No.Ed201802, No. Ea201806）