AEUR：基于uBlock 輪函數(shù)的認證加密算法設(shè)計

楊亞濤，董輝，劉建韜，張艷碩

（1.北京電子科技學院電子與通信工程系，北京 100070；2.西安電子科技大學通信工程學院，陜西 西安 710071）

0 引言

認證加密（AE,authenticated encryption）算法在信息保護領(lǐng)域作用重大，能夠兼顧數(shù)據(jù)的機密性和完整性。通過將消息認證碼和加解密算法結(jié)合，可以實現(xiàn)認證標簽的單向計算過程，且在加解密環(huán)節(jié)擁有足夠的安全強度，以抵抗常見的密碼分析。

目前，主流的基于分組密碼的認證加密算法主要有2 種設(shè)計方式：一是基于分組密碼的認證加密方式，二是在現(xiàn)有的分組密碼的基礎(chǔ)上進行設(shè)計。前者依靠設(shè)計可靠模式結(jié)構(gòu)并在底層使用分組密碼算法為相關(guān)的加解密和認證驗證提供服務(wù)，但提供服務(wù)的過程是不可見的，底層的算法可以相對簡單地進行替換，這類典型的認證加密算法有OCB[1]（offset codebook）、EAX[2]（encryption with authentication for transfer）、GCM[3（]galois/counter mode）。

隨著物聯(lián)網(wǎng)等信息產(chǎn)業(yè)的迅速發(fā)展，認證加密算法的需求環(huán)境也發(fā)生了很大的變化，之前的通用算法和基于分組密碼的工作方式類在現(xiàn)有的資源受限環(huán)境下的表現(xiàn)不盡如人意，如RFID（radio frequency identification）環(huán)境。直接設(shè)計類認證加密算法是指采用已驗證安全性和其他性能指標的、成型的分組密碼部件來進行認證加密算法的設(shè)計。這種設(shè)計方式致力于降低算法的實現(xiàn)代價和提升軟硬件表現(xiàn)，因其采用消息來更新算法的狀態(tài)，用于消息認證的實現(xiàn)代價較低。但這些算法的安全性不能通過可證明安全理論來證明，需依靠各種安全性分析方法，常見的此類型的認證加密算法有AEGIS[4]、ALE（authenticated lightweight encryption）[5]、AEZ（advanced encryption standard-easy）[6]等。為獲得更好的認證加密效率與安全性，本文提出了新的方案。

本文的貢獻如下。

1) 本文提出了一種認證加密算法通用結(jié)構(gòu)R(t,s)。不同于已有采用AES（advanced encryption standard）輪函數(shù)的直接設(shè)計類認證加密算法，該結(jié)構(gòu)基于輕量級分組密碼算法uBlock[7]設(shè)計，以抵抗內(nèi)部碰撞攻擊為安全性目標，使用了混合整數(shù)線性規(guī)劃（MILP,mixed integer linear programming）[8]方法，搜索確定結(jié)構(gòu)中關(guān)鍵參數(shù)t、s和算法所使用的置換P，保證該結(jié)構(gòu)在10 輪后有不少于66 個活躍S 盒。

2) 基于通用結(jié)構(gòu)R(t,s)設(shè)計了認證加密算法AEUR（authenticated encryption algorithm based on uBlock round function）。AEUR 算法的設(shè)計基于uBlock 輪函數(shù)和廣義Feistel 結(jié)構(gòu)，以4 個uBlock輪函數(shù)和置換P組成了算法的輪函數(shù)，輪函數(shù)用來更新狀態(tài)值，狀態(tài)值保證算法的正確性。算法處理數(shù)據(jù)的過程簡潔有效，從而優(yōu)化了算法運行過程，減少了資源消耗。AEUR 算法對多種安全性分析方法具有充分的抵抗能力，為國產(chǎn)密碼算法應(yīng)用提供了一條新的參考途徑。

3) 應(yīng)用SSE（streaming SIMD extension）指令集[9]對AEUR 算法進行了軟件實現(xiàn)。對AEUR 算法進行實現(xiàn)速率測試，以軟件運行時間計算，AEUR算法相比其他同類算法在運算速度上均有不同程度的提升，具有較好的綜合性能。

1 相關(guān)研究

Bellare 等[10]在ASIACRYPT 2000 上提出了認證加密這一全新概念，將認證和加解密在同一算法中完成，通過共享一個密鑰來實現(xiàn)數(shù)據(jù)的機密性與完整性。近年來，部分學者拓寬了認證加密算法的應(yīng)用領(lǐng)域，并基于不同的經(jīng)典密碼算法實現(xiàn)了新的認證加密方式。2002 年，Rogaway[11]提出了基于相關(guān)數(shù)據(jù)的認證加密（ADAE,associated-data authenticated encryption）算法，結(jié)合OCB 和偽隨機函數(shù)PMAC（parallelizable MAC）構(gòu)造了ADAE 算法，這種認證方式在保證了明文信息的保密性和完整性同時也保證了相關(guān)數(shù)據(jù)的完整性。2008 年，Iwata[12]提出了一種針對區(qū)塊密碼的認證加密模式，其中加密部分由一個CENC（common encryption）的密鑰流生成，并結(jié)合了基于分組密碼的哈希函數(shù)。2010 年，Sarkar[13]提出了并行認證加密模式，并與IPMAC（improved parallelizable MAC）結(jié)合，獲得新的認證加密方案。

隨著對認證加密領(lǐng)域以及應(yīng)用環(huán)境的不斷研究和探索，原有的認證加密方案設(shè)計思路不能很好地適應(yīng)新的應(yīng)用環(huán)境。同時，基于新結(jié)構(gòu)和新思想的方案不斷被提出。CAESAR（competition for authenticated encryption: security,applicability,and robustness）競賽的舉辦大大推動了認證加密算法設(shè)計的發(fā)展，其第三輪算法的特點介紹[1,4,14-16]如表1 所示。

表1 CAESAR 競賽第三輪算法特點

表2 uBlock 算法S 盒

表3 PL128 和PR128 變換參數(shù)

2018 年，張建等[17]基于SM4 輪函數(shù)設(shè)計了認證加密算法SMAE，該算法利用MILP 方法構(gòu)造了消息認證碼和認證加密算法。2020 年，高國強等[18]基于AES 算法底層的輪函數(shù)，實現(xiàn)了一種基于AES 輪函數(shù)的認證加密算法AMRAE。這2 種算法都是基于現(xiàn)有的分組密碼輪函數(shù)來設(shè)計的，但安全性分析與實現(xiàn)效率尚有不足。本文綜合前述經(jīng)驗，分析了現(xiàn)有方案的不足，在上述學者的研究思路上進行了擴充改進，采用2019 年我國第一屆密碼算法設(shè)計競賽中獲得一等獎的分組密碼算法uBlock 設(shè)計認證加密算法AEUR，其在安全性和實現(xiàn)速率方面較SMAE 和AMRAE均有不同程度的提升，為國產(chǎn)認證加密算法提供了一種新的參考。

2 基礎(chǔ)知識

2.1 uBlock 輪函數(shù)

uBlock 算法[7]的分組和密鑰長度為128 bit 和256 bit，記為uBlock-128/128、uBlock-128/256、uBlock-256/256。本文采用uBlock-128/128。

uBlock 算法對差分分析、線性分析、積分分析、不可能差分分析等密碼分析方法都有相應(yīng)的安全冗余。uBlock 算法的密鑰擴展算法可以通過隨用隨生成的方法得到輪密鑰，這樣能夠減少算法需要的存儲空間。在本文中，＜＜＜b表示循環(huán)左移bbit，表示以32 bit 為單位循環(huán)左移bbit。

圖1 uBlock 算法輪函數(shù)

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

MILP[8]是在一定約束的條件下對目標函數(shù)進行優(yōu)化，遵循線性規(guī)劃的優(yōu)化問題方法。用MILP 方法對密碼算法進行差分分析和線性分析，就是通過設(shè)定相應(yīng)的約束條件，將活躍S 盒的個數(shù)之和最小設(shè)定為目標函數(shù)，并對其求解。

依據(jù)S 盒的相關(guān)特性結(jié)合約束條件，再將最小活躍S 盒的數(shù)量作為目標函數(shù)的構(gòu)造條件，設(shè)計目標函數(shù)的數(shù)值即所求的最小值。完成上述構(gòu)造后，就可以用求解器對此MILP 問題進行求解。此外，當輸入階段差分和臨時變量都被設(shè)為0 或1 時，對于求解器的求解速率更加友好[19]。

3 基于uBlock 輪函數(shù)的通用結(jié)構(gòu)設(shè)計

R(t,s)結(jié)構(gòu)以uBlock 算法輪函數(shù)和廣義Feistel結(jié)構(gòu)為基礎(chǔ)，其安全性目標為在密鑰長度為128 bit時，可以抵抗內(nèi)部碰撞攻擊。其構(gòu)建過程采用了MILP 方法，搜索符合安全性目標的結(jié)構(gòu)參數(shù)t、s和置換P，其中，t為uBlock 算法的執(zhí)行次數(shù)，s為輪函數(shù)輸入信息的長度，長度表示消息的塊數(shù)。

3.1 安全目標

因為R(t,s)是基于分組密碼算法輪函數(shù)和分組密碼算法結(jié)構(gòu)所設(shè)計的通用結(jié)構(gòu)，不具備算法的完整性，從算法分析的角度來看，可以從某些分析方法的角度來設(shè)定其安全性目標。在AEUR 算法通用結(jié)構(gòu)的設(shè)計中，主要考慮的是對內(nèi)部碰撞攻擊的防御。碰撞攻擊[20]利用生日悖論，分析算法本身或其等效結(jié)構(gòu)，結(jié)合與輪密鑰之間的對應(yīng)關(guān)系來獲得區(qū)分屬性，繼而分析得到密鑰信息。碰撞攻擊大大減少了原始窮舉攻擊的計算量。對于R(t,s)結(jié)構(gòu)，當存在2 個不同消息的差分時，引入初始差分，經(jīng)過多輪迭代，內(nèi)部狀態(tài)差分為0。R(t,s)的密鑰為128 bit，當攻擊復雜度大于128 bit 時，對該結(jié)構(gòu)的攻擊是無效的。uBlock 算法使用的4 bit S 盒的最大差分概率[7]為2-2，為滿足上述安全性條件，在進行碰撞攻擊時活躍S 盒的個數(shù)不能少于66 個。

3.2 通用結(jié)構(gòu)R(t,s)

R(t,s)結(jié)構(gòu)是一種通用的、可迭代的認證加密算法輪函數(shù)結(jié)構(gòu)，采用uBlock 算法的輪函數(shù)，結(jié)合廣義Feistel 結(jié)構(gòu)，如圖2 所示。置換P是區(qū)別于uBlock輪函數(shù)的向量置換PLn和PRn的新的置換，表示消息，S0～S7表示狀態(tài)值。MesHandl 為消息Fi與狀態(tài)值分別進行異或運算。

圖2 R(t,s)輪函數(shù)結(jié)構(gòu)

定義1要對結(jié)構(gòu)R(t,s)的效率進行計量，需要確定一個指標即處理32 bit 的消息塊需要的uBlock 輪函數(shù)的個數(shù)。

R(t,s)的效率與rate 相關(guān)性強，需要通過對結(jié)構(gòu)的設(shè)計細節(jié)進行研究，以選取更高效率的結(jié)構(gòu)。

3.3 MILP 模型搜索實驗結(jié)果

假設(shè)置換P基于32 bit，給出t、s和相應(yīng)約束，結(jié)合MILP 方法驗證是否找到符合條件的置換P。

當rate=1 時，存在只有一個活躍S 盒的差分路徑使結(jié)構(gòu)發(fā)生內(nèi)部碰撞[17]。下面證明rate 至少為2時結(jié)構(gòu)R(t,s)才可能避免內(nèi)部碰撞。在搜索了t=1 和t=2 的4!和8!個置換后，發(fā)現(xiàn)并沒有符合安全目標的結(jié)構(gòu)；當t=3 時，開始出現(xiàn)滿足結(jié)構(gòu)安全的輪函數(shù)。對于R(3,1)，找到了多個可用的P，如P=(1,2,3,4,5,6,7,8,9,10,11,0），此時P被設(shè)為一個循環(huán)移位，進行10 輪后，活躍S 盒的個數(shù)達到70，滿足安全性目標，但其rate=3，需要尋找效率值更高的P。在對R(3,2)、R(3,3)、R(4,1)、R(4,2)、R(4,3)、R(4,4)進行搜索后發(fā)現(xiàn)，以上結(jié)構(gòu)均存在滿足安全性目標的P，其中R(3,3)、R(4,4)的rate=1，效率較高。但是R(3,3)的算法全擴散輪數(shù)表現(xiàn)弱于R(4,4)，故選擇R(4,4)[18]。

表4 列出了部分使R(4,4)符合安全性目標的置換P及其活躍S 盒個數(shù)。在滿足安全性目標的前提下，綜合各個結(jié)構(gòu)的實現(xiàn)效率，P5的實現(xiàn)效率和安全性均能夠達到通用結(jié)構(gòu)對認證加密算法實現(xiàn)的要求，其擴散和混淆特性也滿足作為認證加密算法部件的要求，經(jīng)驗證P5的綜合性能優(yōu)于其他置換P，故本文方案選取P5作為通用結(jié)構(gòu)的置換P。

表4 部分使R(4,4)符合安全性目標的置換P及其活躍S 盒個數(shù)

3.4 通用結(jié)構(gòu)R(4,4)差分安全性分析

R(4,4)結(jié)構(gòu)的安全目標是抵抗內(nèi)部碰撞攻擊。考慮到該結(jié)構(gòu)作為認證加密算法的主要部件，其安全性需要從更多方面進行檢驗，可以通過差分分析來實現(xiàn)。

差分分析針對明文差分對和相應(yīng)的密文差分，盡可能地獲得更多的密鑰信息。對于R(4,4)結(jié)構(gòu)，建立MILP 差分模型，搜索該結(jié)構(gòu)的高概率差分路徑，該結(jié)構(gòu)中存在異或和移位2 種線性操作。在構(gòu)建差分模型過程中，移位只是單純地改變了差分值的位置，所以不需要進行多余限制。對于比特異或a⊕b=c，可以采用等式 △a+△b+△c=2d[21]結(jié)合R(4,4)結(jié)構(gòu)的差分性質(zhì)來求解，過程中還需利用MILP 進行約束，并用Gurobi 求解器求解。

按照R(4,4)結(jié)構(gòu)進行差分路徑分析，在每一輪都選取差分值與上一輪差分值相同的差分，構(gòu)成差分路徑，最終求得一條長度和精確度符合要求的差分路徑概率。搜索結(jié)果如表5 所示。

表5 R(4,4)結(jié)構(gòu)差分路徑概率

從上述結(jié)果可知，當R(4,4)結(jié)構(gòu)執(zhí)行9 輪時，差分路徑概率為2-152，滿足設(shè)定的差分復雜度安全目標128 bit，因此R(4,4)結(jié)構(gòu)從理論上可以抵抗差分分析，且不存在可行的差分路徑。

4 認證加密算法AEUR 設(shè)計

AEUR 算法主要考慮底層算法的選取原則、通用結(jié)構(gòu)設(shè)計和整體工作流程與安全性3 個方面。

首先，對于底層算法uBlock，主要關(guān)注其輕量級的設(shè)計思路和隨用隨生成的密鑰擴展算法，且能夠抵抗內(nèi)部碰撞攻擊。其次，對于通用結(jié)構(gòu)R(t,s)的設(shè)計，主要關(guān)注其安全性目標和使用MILP 方法搜索時的參數(shù)結(jié)果，且R(t,s)結(jié)構(gòu)可以根據(jù)底層算法的安全性需求和運行特點，選擇不同的置換P和底層輪函數(shù)個數(shù)，適用性廣泛。最后，對于整體認證加密算法工作流程，主要考慮其認證加密過程和解密過程中對消息數(shù)據(jù)處理的運算效率和正確性。AEUR 算法的設(shè)計思路如圖3 所示。

圖3 AEUR 算法的設(shè)計思路

圖4 AEUR 算法的輪函數(shù)結(jié)構(gòu)

AEUR 算法采用R(4,4)作為輪函數(shù)，密鑰、初始向量和隨機常數(shù)作為狀態(tài)值的初值，利用輪函數(shù)進行狀態(tài)值的更新，利用狀態(tài)值對數(shù)據(jù)進行加解密和生成標簽操作。

4.1 AEUR 算法認證加密過程

1) 初始化

首先進行相關(guān)數(shù)據(jù)與明文的填充。本文使用PKCS5 算法進行數(shù)據(jù)填充。PKCS7 算法是目前常用加密算法都遵循的數(shù)據(jù)填充標準，PKCS5 算法作為PKCS7 算法的子集算法，在數(shù)據(jù)塊大小blockSize 上固定為128 bit，即數(shù)據(jù)始終會被切割為128 bit 的數(shù)據(jù)塊。然后計算需要填充的長度，由需要填充的字節(jié)數(shù)目來決定要填充的內(nèi)容。此外，為了解決加解密時對于數(shù)據(jù)填充的處理問題，當數(shù)據(jù)本身長度滿足128nbit 時，依據(jù)PKCS5 的規(guī)則，在數(shù)據(jù)的尾部仍需要填充8 個字節(jié)的內(nèi)容，此時填充內(nèi)容為0x08。

將k和N賦值到狀態(tài)值中，并利用輪函數(shù)更新16 輪狀態(tài)值，再對相關(guān)數(shù)據(jù)進行初始化，如算法1所示。

算法1AEUR 算法初始化

2) 明文信息的處理

將明文信息填充后按32 bit 分塊，利用狀態(tài)值與明文異或來生成密文，之后明文進行狀態(tài)值更新，重復q-1 輪。具體算法過程如算法2 所示。

算法2AEUR 算法明文信息處理

輸入明文M

3) 標簽的生成

首先利用相關(guān)數(shù)據(jù)和消息長度adlen 和msglen更新一輪狀態(tài)值；然后迭代更新16 輪；最后利用狀態(tài)值生成標簽tag。具體過程如算法3 所示。

算法3AEUR 算法標簽生成

4.2 AEUR 解密認證過程

AEUR 的解密認證算法輸入為密鑰k、初始向量N、相關(guān)數(shù)據(jù)A和密文C；輸出為明文M或停止符⊥，認證解密過程由初始化、密文信息處理和標簽生成過程構(gòu)成。

解密認證過程的初始化、密文信息處理與加密認證過程的輸入輸出相同。最后生成狀態(tài)S16+d。

解密過程。利用狀態(tài)S16+d和密文C=(C0,…,C4q-1)生成M，同時更新狀態(tài)。具體算法如算法4所示。

算法4AEUR 算法密文信息處理

認證過程。在解密過程結(jié)束后可以得到狀態(tài)值S16+d+q，之后利用加密認證過程中的標簽生成算法，得到標簽tag′，如果標簽值tag′與之前加密認證過程中生成的標簽值tag 相同，那么解密成功且通過認證，即解密驗證算法執(zhí)行成功，輸出明文M；否則解密驗證過程失敗，輸出停止符⊥。

4.3 基于通用結(jié)構(gòu)R(t,s)的認證加密算法設(shè)計思路

R(t,s)結(jié)構(gòu)是能夠滿足不同算法使用的通用型迭代結(jié)構(gòu)，滿足分組密碼算法要求的混淆和擴散特性，且可以保障認證加密算法的安全性和正確性。采用這種結(jié)構(gòu)生成的認證加密算法總體類似于大型序列密碼算法。該結(jié)構(gòu)通過并行操作可以大大提升運行效率，根據(jù)底層算法的安全性需求和運行特點，可以選擇不同的置換P和底層輪函數(shù)個數(shù)，從而構(gòu)造出滿足安全性和實用性要求的結(jié)構(gòu)，繼而將其進行組合排列，滿足算法的設(shè)計需求。

5 正確性證明

加密認證和解密驗證使用了相同的初始化、明/密文信息處理和標簽生成過程，如算法5 和算法6 所示。

算法5AEUR 算法加密過程

算法6AEUR 算法解密過程

由于算法的加解密與狀態(tài)值緊密相關(guān)，如果在任意某一輪數(shù)時，算法在加解密過程中產(chǎn)生的狀態(tài)值Si相同，則算法滿足正確性。執(zhí)行AEUR 算法時，其加密與解密的初始化過程、相關(guān)數(shù)據(jù)處理過程完全一致，每一輪產(chǎn)生的狀態(tài)值都相同，因此AEUR 算法滿足正確性。

6 安全性分析

現(xiàn)有的可證明安全理論雖然可以對基于分組密碼的認證加密模式進行安全性分析，但對于直接設(shè)計的認證加密算法，不能給出適合的安全假設(shè)。目前，直接設(shè)計的認證加密算法普遍使用針對密碼算法的安全性分析方法[22]。為了讓AEUR 算法具備能夠抵抗密鑰恢復攻擊和偽造攻擊的能力，保證攻擊的復雜度大于2128，做出如下約束[18]。

1) 初始向量值（Nonce）的取值要隨機，且不能復用，即每次使用認證加密算法之前都要更換隨機初始向量值。

2) 在解密驗證的過程中，明文信息對用戶不可見，只有在驗證成功后才會輸出明文；如果驗證失敗，則輸出停止符⊥。

3) 加密時，相同密鑰對相關(guān)數(shù)據(jù)和明文信息加密的最大數(shù)據(jù)長度不超過2128bit。

6.1 AEUR 算法安全性分析

1) 線性攻擊

線性攻擊[23]是一種已知明文攻擊，也就是攻擊者能夠獲取當下使用密鑰狀態(tài)下的明密文對。在對明文、密文和密鑰三者滿足的某種線性關(guān)系的概率p進行研究后，得到一個統(tǒng)計特征，利用該特征能夠?qū)⒎纸M密碼和隨機置換區(qū)分開。對分組密碼而言，期待找到一個線性區(qū)分器來恢復最后一輪密鑰。采用MILP 方法構(gòu)建目標函數(shù)和約束條件來搜索其最小活躍S 盒，設(shè)置活躍S 盒的下界，從準確度考慮，將搜索過程中每一輪的S 盒個數(shù)進行輸出，結(jié)果如表6 所示。在線性攻擊的標準方法評估下，AEUR 算法的10 輪活躍S 盒下界為71，大于安全性目標設(shè)定的66 個。且AEUR 算法在標簽生成和初始化階段均使用了16 輪迭代，有足夠的安全冗余，所以其具有抵抗線性攻擊的能力。

表6 AEUR 算法在線性攻擊條件下的活躍S 盒個數(shù)

2) 滑動攻擊

滑動攻擊[24]是受相關(guān)密鑰攻擊的啟發(fā)而提出的。當分組密碼在迭代過程中出現(xiàn)一定的自相似性時，可以使用滑動攻擊對算法進行分析。與線性或者差分攻擊不同，迭代輪函數(shù)的性質(zhì)和執(zhí)行輪數(shù)對滑動攻擊的影響很小，輪數(shù)對算法抵抗滑動攻擊的能力幾乎沒有影響。在密碼算法中，如果迭代函數(shù)可以被分解為若干小的輪函數(shù)，那么就可以利用這一缺點進行滑動攻擊。為了避免滑動攻擊，算法的輪函數(shù)，特別是迭代的輪函數(shù)應(yīng)該避免在執(zhí)行過程中形成周期而被分解，在綜合考慮算法抵抗幾種攻擊方法的能力以及對運行效率的影響后，與文獻[18]的分析相同，AEUR 算法的輪函數(shù)并未生成周期，因此AEUR 算法可以抵抗滑動攻擊。

3) 猜測確定攻擊

猜測確定攻擊[25]的原理是對密碼算法實現(xiàn)過程中的一些變量進行猜測，猜測的變量在輪函數(shù)中迭代可得到新的變量，利用得到的變量恢復出算法實現(xiàn)過程中相應(yīng)的狀態(tài)值。AEUR 算法的擴散層來源于uBlock 算法，其擴散層的二元域矩陣分支數(shù)為8，攻擊者需要已知64 bit 才能得到下一個字節(jié)變量的值。AEUR 算法輪函數(shù)是基于狀態(tài)值集合Si構(gòu)造的，有16 個32 bit 的狀態(tài)值。那么對于AEUR 算法的猜測確定攻擊，則需要以32 bit 的狀態(tài)值進行攻擊，為了滿足算法的安全性目標，攻擊復雜度最高臨界值被設(shè)定為2128，顯然想通過4 個變量來恢復其他的狀態(tài)值并不現(xiàn)實，所以AEUR 算法可以抵抗猜測確定攻擊。

4) 狀態(tài)恢復攻擊

Pelican MAC 攻擊[26]主要利用小尺寸的內(nèi)部狀態(tài)來構(gòu)造基于生日悖論的碰撞。AEGIS、ALE 算法都具有較大的內(nèi)部狀態(tài)，在AEUR 算法中，狀態(tài)值Si的大小為16×32=512 bit，足以抵抗生日攻擊。當攻擊者使用相同的密鑰和隨機數(shù)進行多次重復攻擊時，可能會在標簽生成過程中對狀態(tài)值注入差分，特別是當標簽的長度小于算法的密鑰長度時，認證加密算法面對這種攻擊會顯得脆弱。在AEUR算法中，輪函數(shù)結(jié)構(gòu)的安全性目標為抵抗內(nèi)部碰撞攻擊，因此針對狀態(tài)恢復攻擊是不現(xiàn)實的。在多次攻擊之后，可能獲得相對成功的偽造，但無法恢復整個狀態(tài)值。因此AEUR 算法可以抵抗狀態(tài)恢復攻擊。

5) 偽造攻擊

偽造攻擊是指攻擊者偽造出通過驗證的密文來進行攻擊。R(4,4)在9 輪迭代情況下的差分路徑概率為2-152，遠超過設(shè)定的128 bit 安全性復雜度目標，因此，該結(jié)構(gòu)能夠抵抗差分分析，且無可用差分路徑。AEUR 算法的結(jié)構(gòu)與R(4,4)相同，且迭代輪數(shù)超過10 輪，擁有絕對安全冗余，無法實現(xiàn)偽造。因此，AEUR 可以抵抗偽造攻擊。

AEUR 算法作為直接設(shè)計類認證加密算法，其底層算法uBlock 對差分分析和不可能差分分析等具有良好的抵抗性。R(t,s)結(jié)構(gòu)可以抵抗差分分析和偽造攻擊等，并以128 bit 的復雜度為安全性目標，保障結(jié)構(gòu)的安全性。因此可以認為AEUR 算法對差分分析等方法也有足夠的抵抗能力。

6.2 安全性對比分析

為了進一步說明AEUR 算法的安全性，選用近年來最有代表性的具有同類結(jié)構(gòu)的AEGIS 算法、SMAE 算法和Pyjamask 算法[27]作為對比對象。

AEGIS 算法[4]在拒絕初始向量重用的情況下，在標簽生成過程中，恢復密鑰攻擊的速度要慢于窮舉搜索，因此狀態(tài)恢復攻擊對于拒絕Nonce重用的AEGIS 無法實施。在偽造攻擊中，解密的明文若驗證成功，當t為標簽值tag 的長度時，有2-t的概率可以被攻擊者破解。AEGIS 的標簽長度為128 bit，在恢復狀態(tài)時至少需要2128次偽造嘗試，由計算復雜性理論可知，這一數(shù)值在計算上是不可接受的。因此，AEGIS 對狀態(tài)恢復攻擊和偽造攻擊具有安全性。

SMAE 算法[17]就猜測確定攻擊而言，因為其底層函數(shù)來源于SM4 算法，SM4 算法中線性變換L的分支數(shù)為5，即對于SMAE 算法而言，要想通過猜測確定攻擊來分析算法，至少需要得到32 bit 的輸出值，才能恢復新的字節(jié)值，同時考慮到算法的128 bit 的計算安全性指標，超過3×32 bit 的恢復狀態(tài)攻擊不可行，因此SMAE 算法對于抵抗猜測確定攻擊具有安全性。在線性攻擊分析中，計算搜索線性掩碼成立的最優(yōu)偏差為2-92.43，區(qū)分攻擊和明文恢復攻擊的數(shù)據(jù)復雜度約為2184，因此SAME 算法對于線性攻擊具有安全性。

AEUR 算法對于多種攻擊具有安全性，較SMAE[17]和AEGIS[4]更全面，對比細節(jié)如表7 所示。

表7 AEUR 算法和其他算法的安全性對比

2020 年，Goudarzi 等[27]提出了Pyjamask 算法并給出其規(guī)范和AEAD（authenticated encryption with associated data）建議。2022 年，賀水喻等[28]基于Pyjamask 算法提出一種對明文進行偽造的方法，可以偽造出認證標簽。在對Pyjamask 和AEUR算法的AEAD 安全性進行對比分析時，兩者均具有良好的認證加密安全性。AEAD 安全性要求算法具有保密性、真實性、對稱性和隨機分配的特點。

1) 在實際認證加密執(zhí)行過程中，AEUR 算法能夠抵抗線性攻擊等多種攻擊方法，密文解密后對應(yīng)的明文正確，標簽值對應(yīng)正確。除了明文長度之外，其他關(guān)于明文的內(nèi)容是未知的，滿足保密性。

2) AEUR 由于R(t,s)結(jié)構(gòu)，未經(jīng)有效的密碼分析檢測，攻擊者不可能更改密文的底層，滿足真實性。

3) AEUR算法對各類明文進行加密和對各類密文進行解密時使用的密鑰相同，滿足對稱性。

4) AEUR 算法的加密過程是隨機分配的，同一明文的2 個消息會產(chǎn)生不同的密文，攻擊者無法獲知明文與密文的對應(yīng)關(guān)系，滿足隨機分配性。

綜上，AEUR 算法滿足對稱密碼算法理想的AEAD 安全性。

7 效率與實現(xiàn)分析

本節(jié)使用C 語言結(jié)合SSE 指令集實現(xiàn)AEUR 算法。環(huán)境為Intel 處理器，16 GB 內(nèi)存，Visual Studio 2019。AEUR 算法中的uBlock 輪函數(shù)采用SSE 實現(xiàn)。SSE指令集采用SIMD（single instruction multiple data）來提升數(shù)據(jù)的并行操作性和算法的實現(xiàn)效率。

將AEUR 算法的時間復雜度和空間復雜度與其他算法進行對比分析，結(jié)果如表8 所示。

表8 計算復雜度對比

由表8 可知，AEUR 算法的時間復雜度與SAME算法相同，優(yōu)于AMRAE 算法[18]；AEUR 算法的空間復雜度與SMAE 算法相同，低于AMRAE 算法。參考AEUR 的存儲開銷和運行開銷等，其綜合性能良好。

AEUR 算法認證加密速率如圖5 所示。從圖5可以看出，AEUR 算法認證最高為5.41 Gbit/s，最低為3.91 Gbit/s，平均為4.63 Git/s，考慮到AEUR算法的運行環(huán)境，相比文獻[17]中SMAE 算法3.8 Gbit/s 的加密速率，AEUR 算法認證加密速率對比SMAE 算法仍有較大優(yōu)勢。

圖5 AEUR 算法認證加密速率

由表9 可知，AEUR 的認證加密速率相比AEGIS[4]、ALE[5]效率分別提升了3%和46%，相比AES-GCM[3]、ACORN[29]算法優(yōu)勢較明顯，加密速率分別提升了74%和92%。

表9 算法速度比較

另外，通過測試不同數(shù)據(jù)長度的認證加密運算過程，可以得到如圖6 所示的狀態(tài)曲線。隨著待處理數(shù)據(jù)長度的增加，AEUR 算法執(zhí)行的效率較AEGIS 算法和AES-GCM 算法更加穩(wěn)定。

圖6 算法認證加密時間隨數(shù)據(jù)長度變化

結(jié)合圖5、圖6 和表9 可以得出結(jié)論，AEUR算法與以AES 算法為基礎(chǔ)設(shè)計的AEGIS 算法、ALE算法、AES-GCM 算法和以序列密碼為基礎(chǔ)設(shè)計的ACORN 算法相比，具有更優(yōu)的運算性能。

通過上述對計算復雜度、認證加密速率和算法效率的對比分析可以看出，本文的AEUR 算法較其他認證加密算法具有技術(shù)優(yōu)勢。其原因一方面是AEUR 的底層結(jié)構(gòu)是基于輕量級分組密碼算法uBlock，uBlock 算法的密鑰擴展算法可以通過隨用隨生成的方法得到輪密鑰，在一定程度上縮小了存儲空間，并且能夠提升運算效率。而且所使用的MILP 方法可以根據(jù)所采用的分組密碼算法S 盒的特性來設(shè)置約束條件，使其適用性得到增強。

另一方面是AEUR 算法的設(shè)計基于分組密碼uBlock 的輪函數(shù)和廣義Feistel 結(jié)構(gòu)，以4 個uBlock輪函數(shù)和置換P組成了算法的輪函數(shù)，狀態(tài)值的更新通過輪函數(shù)來完成，因此算法處理數(shù)據(jù)的過程在一定程度上得到了優(yōu)化，也減少了資源消耗，從而降低了運算復雜度，提升了運算速率。

8 結(jié)束語

本文采用國產(chǎn)分組密碼算法uBlock 輪函數(shù)結(jié)合混合整數(shù)線性規(guī)劃方法，設(shè)計了一個適用于認證加密算法的通用迭代結(jié)構(gòu)R(t,s)，并基于R(t,s)結(jié)構(gòu)設(shè)計了認證加密算法AEUR。AEUR 算法由初始化、明文信息處理和生成標簽過程構(gòu)成。對算法的正確性與安全性進行分析，并與同類算法進行對比，AEUR 表現(xiàn)較好。使用C 語言結(jié)合SSE 指令集編碼實現(xiàn)了AEUR 算法，測試了算法的軟件實現(xiàn)效率。AEUR 算法與以AES 算法為基礎(chǔ)設(shè)計的AEGIS 算法、ALE 算法、AES-GCM 算法和以SM4 算法為基礎(chǔ)構(gòu)造的SMAE 算法，以及以序列密碼為基礎(chǔ)設(shè)計的ACORN 算法相比，具有更優(yōu)的實現(xiàn)性能。

隨著口令認證加密技術(shù)的發(fā)展，該方向得到了廣泛研究[30-31]，未來AEUR 算法可結(jié)合口令安全技術(shù)應(yīng)用于物聯(lián)網(wǎng)、隱私計算等領(lǐng)域。