MPECA：面向多平臺的高效密碼算法

摘 要：目前基于AESNI指令集設計面向6G系統(tǒng)高速加密算法備受業(yè)界關注，如ROCCA算法。然而，如何在不支持AESNI指令集環(huán)境下設計高速實現(xiàn)的密碼算法是目前的研究難點之一。基于AES輪函數(shù)特點，設計了一個面向多平臺的高效加密算法——MPECA。該算法輪函數(shù)采用四輪AES迭代操作，使其在不支持AESNI低端環(huán)境下仍可利用固定切片技術(shù)進行高效軟件實現(xiàn)。特別地，MPECA比ROCCA在初始化和生成標簽階段少花銷32個AES輪函數(shù)操作和128個XOR操作，使得其在支持AESNI指令的環(huán)境下實現(xiàn)更快捷。實驗結(jié)果表明：與ROCCA相比，Intel平臺上，在不支持AESNI環(huán)境下，MPECA加密速度提高了3.05倍，在支持AESNI環(huán)境下，MPECA加密速度提高了30.64%；在ARM平臺上，MPECA加密速度提高了近2.37倍。此外，MPECA密碼算法具有較高的安全強度，足以抵抗差分密碼攻擊、積分攻擊及密鑰恢復攻擊等。

關鍵詞：分組密碼算法； AESNI指令； 固定切片； 差分密碼攻擊

中圖分類號：TP309文獻標志碼：A

文章編號：1001-3695（2023）08-038-2481-06

doi：10.19734/j.issn.1001-3695.2022.10.0633

MPECA： efficient cryptographic algorithm for multiple platforms

Li Keque， Feng Jingya， Wei Yongzhuang， Zhao Qi

（Guangxi Key Laboratory of Cryptography amp; Information Security， Guilin University of Electronic Technology， Guilin Guangxi 541004， China）

Abstract：The design of high-speed encryption algorithms in 6G systems via the AESNI instruction set （Intel advanced encryption standard（AES） new instructions set） is extensively received attention in academic community， such as ROCCA encryption algorithm. However， how to design an efficient cryptographic algorithm in the environment that does not support the AESNI instruction set appears to be one of the current research difficulties. This paper proposed an efficient encryption algorithm for multiple platforms（MPECA） by basing on the round function of AES. More specifically， its round function used four reduced round operations of AES so that MPECA could still be implemented by using the fixslicing technique in the lowend environment where the AESNI didn’t support. In particular， MPECA had 32 AES operations and 128 XOR operations， which were all less than the ROCCA spent in initializing and generating tags phases. MPECA could perform efficient software implementation in high-end environments that support AESNI. Compared to ROCCA， the encryption speed of MPECA on Intel platform is increased by 3.05 times without AESNI and 30.64% under AESNI environment. Moreover， on the ARM platform， MPECA has increased encryption speed by nearly 2.37 times. In addition， the MPECA has strong security level and good resistance against the differential attacks， the integration attacks and the key recovery attacks and so on.

Key words：block cipher; AESNI instruction; fixslicing technique; differential attack

0 引言

自2001年Rijndael分組密碼［1］被選為高級加密標準（AES）以來，該算法的優(yōu)化實現(xiàn)與應用引起了人們的極大興趣，根據(jù)應用環(huán)境不同，現(xiàn)有的主流優(yōu)化方法包括指令集實現(xiàn)方法和比特切片實現(xiàn)方法。2010年，Gueron［2］提出了英特爾高級加密標準指令集AESNI，提高了AES加密和解密的執(zhí)行速度。AESNI指令集是一種SIMD（單指令多數(shù)據(jù)）指令集，可在Intel和AMD的許多現(xiàn)代CPU上高效運行。隨之發(fā)展，陸續(xù)有研究者設計了一些基于AESNI指令集的高性能密碼算法。2013年，Wu等人［3］設計了AEGIS算法。2014年，文獻［4］設計了Tiaoxin-346算法，其輪函數(shù)包括AES輪函數(shù)運算和128比特異或運算，且AES輪函數(shù)運算和128 bit異或運算操作在SIMD指令集上分別只需要一條AESNI指令和一條XOR指令就能實現(xiàn)。在CAESAR競賽上，AEGIS-128被選入高性能應用的最終組合［5］。2016年，Jean等人［6］對AEGIS和TiaoXin-346的輪函數(shù)結(jié)構(gòu)進行了改進，其輪函數(shù)包括AES輪函數(shù)運算或128 bit異或運算，相比AEGIS和TiaoXin-346算法的輪函數(shù)更高效，并提供了128 bit的安全性來抵御偽造攻擊。2021年，白亮等人［7］利用單指令多數(shù)據(jù)（SIMD）技術(shù)在x86架構(gòu)處理器上對ZUC-256進行軟件優(yōu)化實現(xiàn)，軟件實現(xiàn)性能達到21 Gbps。2021年，基于AEGIS和TiaoXin-346的研究，文獻［8］提出了一種基于AES的認證加密算法ROCCA，它是第一個針對6G系統(tǒng)的密碼算法，其利用AESNI指令集可獲得高效軟件實現(xiàn)。然而，AESNI指令集是一種特殊的SIMD指令集，其應用成本相對較高，只適用于軟硬件資源充裕的高端環(huán)境，而不適用于資源受限的環(huán)境，這導致在不支持AESNI指令集的受限環(huán)境中，上述算法實現(xiàn)效率較低。

在不支持AESNI指令集的受限環(huán)境下，比特切片實現(xiàn)方法可以提升密碼算法的軟件實現(xiàn)性能［9，10］。2000年，Kwan［11］首次采用比特切片技術(shù)在資源受限的環(huán)境下實現(xiàn)分組密碼算法DES，之后比特切片技術(shù)被認為是快速恒定時間實現(xiàn)的通用技術(shù)。2009年，Ksper等人［12］介紹了基于比特切片技術(shù)實現(xiàn)AES的方法，其通過并行處理八個塊在Intel Core i7處理器上軟件實現(xiàn)速度達到6.9 CPB。2016年，Schwabe等人［13］介紹了在ARM Cortex-M3上基于比特切片技術(shù)實現(xiàn)AES的方法，其通過并行處理兩個塊使得軟件實現(xiàn)速度達到101 CPB。2019年，它還被移植到32 bit RISC-V體系結(jié)構(gòu)上，在E31處理器上實現(xiàn)124 CPB［14］。2020年，張笑從等人［15］利用比特切片技術(shù)，結(jié)合AVX2指令集提出了一種SM4算法的快速軟件優(yōu)化實現(xiàn)方法，實現(xiàn)了SM4算法的256分組數(shù)據(jù)并行加解密。2021年，一種名為固定切片的方法［16］被應用于高級加密標準AES，其通過并行兩個128 bit的塊和減少線性層操作指令來提高AES軟件實現(xiàn)性能，與基于比特切片技術(shù)的軟件實現(xiàn)相比，基于固定切片技術(shù)的AES軟件實現(xiàn)性能在ARM Cortex-M上提高了21%。

文獻［8］中，ROCCA設計者在總結(jié)中提到，在不支持AESNI環(huán)境下ROCCA的高效實現(xiàn)是值得關注和思考的問題。考慮到ROCCA是基于AES設計的密碼算法，且在不支持AESNI環(huán)境下，基于固定切片技術(shù)的AES實現(xiàn)是目前最高效的。故根據(jù)基于固定切片技術(shù)的AES實現(xiàn)思想，MPECA輪函數(shù)中采用更復雜的AES四輪迭代部件，且選取了比ROCCA輪函數(shù)擴散更好的置換操作。進一步，通過對MPECA初始化、生成標簽過程的差分分析，設置MPECA在初始化、生成標簽過程中輪函數(shù)迭代次數(shù)為4，而ROCCA在初始化、生成標簽階段的輪函數(shù)次數(shù)為20，因此MPECA相比ROCCA在初始化和生成標簽過程少花銷32個AES輪函數(shù)操作和128個XOR操作。故在不支持AESNI的環(huán)境下MPECA能使用固定切片AES高效實現(xiàn)，在支持AESNI的環(huán)境下MPECA能使用指令高效實現(xiàn)。

密碼算法在不同平臺的普適性及高效實現(xiàn)一直是研究者們關注的重點。特別地，如何在不支持AESNI指令集的受限環(huán)境下，設計高速實現(xiàn)的密碼算法是目前的研究難點之一。本文將固定切片技術(shù)思想與ROCCA算法設計思想相結(jié)合，設計了一個新的面向多平臺的高效軟件實現(xiàn)算法MPECA。該算法的輪函數(shù)采用四輪AES迭代操作，其不僅能夠在資源受限的環(huán)境下基于固定切片進行高效實現(xiàn)，也能夠在軟硬件資源充足的環(huán)境下，利用SIMD指令集的AESNI和XOR指令進行高效實現(xiàn)。此外，研究結(jié)果還表明，MPECA密碼算法具有足夠的安全強度以抵抗差分密碼攻擊、積分攻擊、偽造攻擊及密鑰恢復攻擊等。

1 MPECA算法

MPECA算法是基于AES設計的面向多平臺的認證加密算法，其使用的符號如表1所示。該算法由初始化、處理關聯(lián)數(shù)據(jù)、加密、生成標簽T四個步驟組成，且每個步驟都利用輪函數(shù)達到了較好的混淆擴散效果。

1.1 輪函數(shù)

1.2 整體描述

2 設計原理

2.1 輪函數(shù)設計

2.2 MPECA結(jié)構(gòu)設計

3 安全性分析

本章通過差分分析、偽造攻擊分析、積分分析、狀態(tài)恢復攻擊分析、已知密文的狀態(tài)恢復攻擊分析等對MPECA算法的安全性進行分析，以確保MPECA算法具有足夠的安全性。

3.1 差分分析

3.2 偽造攻擊分析

根據(jù)文獻［19］提到的偽造攻擊的評估方法，在MPECA使用一個輪函數(shù)R更新每一塊的關聯(lián)數(shù)據(jù)AD的情況下，本文評估了偽造攻擊中有效的差分路徑：其輸入輸出差分為零，但吸收非零關聯(lián)數(shù)據(jù)AD的7輪的差分路徑，然后使用基于MILP的方法得到MPECA有效差分路徑中活躍S盒的數(shù)量為48。在MPECA使用一個輪函數(shù)R_ENC來更新每一塊明文M的情況下，本文評估了偽造攻擊中有效的差分路徑：其輸入輸出差分為零，但吸收非零明文M的7輪的差分路徑，然后使用基于MILP的方法得到MPECA有效差分路徑中活躍S盒的數(shù)量為25。

由于AES的S盒的最大差分概率為2-6，且標簽T長度為128 bit，所以在評估偽造攻擊時，MPECA有效差分路徑的活躍S盒數(shù)量大于22，MPECA算法就能提供128 bit的安全性抵抗偽造攻擊。文獻［8］中ROCCA設計者使用MILP搜索ROCCA有效差分路徑中活躍S盒數(shù)量為24，這說明ROCCA能有效抵抗偽造攻擊。從上述實驗結(jié)果可知，MPECA有效差分路徑中活躍S盒的數(shù)量大于ROCCA，故MPECA可以提供128 bit的安全性來抵抗偽造攻擊，且抵抗偽造攻擊的安全性優(yōu)于ROCCA。

3.3 積分攻擊分析

3.4 狀態(tài)恢復分析

3.5 已知密文的狀態(tài)恢復攻擊

ROCCA是一種基于隨機數(shù)的AEAD方案，攻擊者不能在已知明文攻擊的情況下請求具有相同隨機數(shù)的不同消息。然而，在最近的文獻［22］中，在已知密文攻擊的情況下，且當128 bit標簽T一致時，攻擊者有可能在時間復雜度為2128的初始化階段之后恢復ROCCA完整的1 024 bit的內(nèi)部狀態(tài)。但是，先前AEGIS-256的設計者已經(jīng)觀察到這樣的狀態(tài)恢復攻擊，如果標簽T的長度很小會導致已知密文攻擊情況下的內(nèi)部狀態(tài)恢復；然而，最主要的是防止進一步的密鑰恢復攻擊。因此，AEGIS-256考慮在初始化階段使用密鑰置換來防止進一步的密鑰恢復攻擊。在MPECA算法中，攻擊者即使知道MPECA加密過程的內(nèi)部狀態(tài)，但在不知道密鑰的情況下也無法反轉(zhuǎn)初始化過程，因此在初始化過程結(jié)束以后添加某些狀態(tài)位與密鑰異或的操作來防止進一步的密鑰恢復攻擊。此外，如文獻［22］建議的那樣，在最后生成標簽T過程前添加某些狀態(tài)位與密鑰異或的操作，以防止偽造攻擊。

4 性能分析

4.1 Intel平臺

4.2 ARM平臺

5 結(jié)束語

由于AESNI指令應用平臺具有局限性，設計一個面向多平臺的基于AES的密碼算法，并保證其高效安全實現(xiàn)是一個值得關注且重要的研究課題。本文結(jié)合ROCCA算法的設計思想和固定切片AES實現(xiàn)技術(shù)，設計了面向多平臺的MPECA密碼算法。實驗結(jié)果表明，在不支持AESNI指令的環(huán)境下，MPECA算法軟件實現(xiàn)效率優(yōu)于ROCCA算法，在支持AESNI指令的環(huán)境下，MPECA算法軟件實現(xiàn)效率同樣優(yōu)于ROCCA算法。此外，從安全分析結(jié)果可以看出，MPECA算法具有更好的擴散性和抵抗差分攻擊的能力，同時也能較好地抵抗偽造攻擊、積分攻擊以及狀態(tài)恢復攻擊。

參考文獻：

［1］Daemen J，Rijmen V. The design of Rijndael［M］. New York： Springer， 2002： 83-89.

［2］Gueron S. Intel’s advanced encryption standard（AES） new instructions set［EB/OL］. （2012-02-08） ［2023-02-02］. https：//www.intel.cn/content/www/cn/zh/developer/articles/tool/intel-advanced-encryption-standard-aes-instructions-set.html.

［3］Wu Hongjun， Preneel B. AEGIS： a fast authenticated encryption algorithm［C］//Proc of the 20th International Conference on Selected Areas in Cryptography. Berlin： Springer， 2013： 185-201.

［4］Salam I， Al Mahri H Q， Simpson L， et al. Fault attacks on Tiaoxin-346［C］//Proc of Australasian Computer Science Week Multiconfe-rence. New York： ACM Press， 2018： article No.5.

［5］Zhang Fan， Liang Ziyuan， Yang Bolin， et al. Survey of design and security evaluation of authenticated encryption algorithms in the CAESAR competition［J］. Frontiers of Information Technology amp; Electronic Engineering， 2018，19（12）： 1475-1499.

［6］Jean J， Nikolic＇ I. Efficient design strategies based on the AES round function［C］//Proc of the 22nd International Conference on Fast Software Encryption. Berlin： Springer， 2016： 334-353.

［7］白亮， 賈文義， 朱桂楨. ZUC-256 算法的快速軟件實現(xiàn)［J］. 密碼學報， 2021，8（3）： 521-536. （Bai Liang， Jia Wenyi， Zhu Guizhen. Efficient software implementations of ZUC-256［J］. Journal of Cryptologic Research， 2021，8（3）： 521-536.）

［8］Sakamoto K， Liu Fukang， Nakano Y， et al. ROCCA： an efficient AES-based encryption scheme for beyond 5G［J］. IACR Trans on Symmetric Cryptology， 2021， 2021（2）： 1-30.

［9］Matsui M， Nakajima J. On the power of bitslice implementation on Intel Core2 processor［M］//Paillier P， Verbauwhede I. Cryptogra-phic Hardware and Embedded Systems. Berlin： Springer， 2007： 121-134.

［10］K?nighofer R. A fast and cache-timing resistant implementation of the AES［C］//Proc of the 8th Cryptographers’Track at the RSA Confe-rence. Berlin： Springer， 2008： 187-202.

［11］Kwan M. Reducing the gate count of bitslice DES［EB/OL］. （2000-10-09） ［2023-02-02］. https：//eprint.iacr.org/2000/051.

［12］K?sper E， Schwabe P. Faster and timing-attack resistant AES-GCM［C］//Proc of the 11th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin： Springer， 2009： 1-17.

［13］Schwabe P， Stoffelen K. All the AES you need on Cortex-M3 and M4［C］//Proc of the 23rd International Conference on Selected Areas in Cryptography. Cham： Springer， 2016： 180-194.

［14］Stoffelen K. Efficient cryptography on the RISC-V architecture［C］//Proc of the 6th International Conference on Cryptology and Information Security in Latin America. Cham： Springer， 2019： 323-340.

［15］張笑從， 郭華， 張習勇， 等. SM4算法快速軟件實現(xiàn)［J］. 密碼學報， 2020，7（6）： 799-811. （Zhang Xiaocong， Guo Hua， Zhang Xiyong， et al. Fast software implementation of SM4［J］. Journal of Cryptologic Research， 2020，7（6）： 799-811.）

［16］Adomnicai A， Peyrin T. Fixslicing AES-like ciphers： new bitsliced AES speed records on ARM-Cortex M and RISC-V［J］. IACR Trans on Cryptographic Hardware and Embedded Systems， 2021，2021（1）： 402-425.

［17］Shi Tairong， Hu Bin， Guan Jie， et al. Cryptanalysis of AEGIS-128［J］. Chinese Journal of Electronics， 2022，31（2）： 285-292.

［18］Mouha N， Wang Qingju， Gu Dawu， et al. Differential and linear cryptanalysis using mixed-integer linear programming［C］//Proc of the 7th International Conference on Information Security and Crypto-logy. Berlin： Springer， 2011： 57-76.

［19］田玉丹， 韋永壯. 認證加密算法SCREAM及iSCREAM的新偽造攻擊［J］. 網(wǎng)絡與信息安全學報， 2016，2（1）： 60-65. （Tian Yudan， Wei Yongzhuang. New forgery attack on the authenticated cipher SCREAM and iSCREAM［J］. Chinese Journal of Network and Information Security， 2016，2（1）： 60-65.）

［20］Liu Fukang， Isobe T， Meier W， et al. Weak keys in reduced AEGIS and Tiaoxin［J］. IACR Trans on Symmetric Cryptology， 2021，2021（2）： 104-139.

［21］Jiao Lin， Li Yongqiang， Du Shaoyu. Guess-and-determine attacks on AEGIS［J］. The Computer Journal， 2021，65（8）： 2221-2230.

［22］Hosoyamada A， Inoue A， Ito R， et al. Cryptanalysis of ROCCA and feasibility of its security claim［J］. IACR Trans on Symmetric Cryptology， 2022，2022（1）： 123-151.