基于Keccak置換的認(rèn)證加密算法改進(jìn)與安全性評(píng)估

關(guān)鍵詞：Keccak置換；認(rèn)證加密；算法改進(jìn)；安全性評(píng)估

中圖分類(lèi)號(hào)：TP308 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）26-0074-03 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID） ：

0 引言

Keccak置換是一種重要的密碼學(xué)原語(yǔ)，廣泛應(yīng)用于哈希函數(shù)、消息認(rèn)證碼和認(rèn)證加密等領(lǐng)域。然而，現(xiàn)有的基于Keccak置換的認(rèn)證加密算法在執(zhí)行效率和并行性方面存在不足，難以滿足高吞吐量應(yīng)用場(chǎng)景的需求。此外，面對(duì)日益增長(zhǎng)的非對(duì)稱威脅，現(xiàn)有算法的安全機(jī)制需要進(jìn)一步增強(qiáng)，因此需要進(jìn)行深入研究以改進(jìn)算法效果。

1 Keccak 置換的基本原理

Keccak置換基于海綿結(jié)構(gòu)，是一種重要的密碼學(xué)原語(yǔ)，被廣泛應(yīng)用于哈希函數(shù)、消息認(rèn)證碼以及認(rèn)證加密等領(lǐng)域。其核心是通過(guò)一系列的置換操作，將輸入的比特序列映射到輸出的比特序列，從而實(shí)現(xiàn)了混淆和擴(kuò)散的功能。在實(shí)際應(yīng)用中，置換操作需要在一個(gè)三維的狀態(tài)上進(jìn)行，該狀態(tài)可以表示為一個(gè)5×5×w 的比特?cái)?shù)組，其中w為詞的長(zhǎng)度，取值為1、2、4、8、16、32或64。狀態(tài)中的每一位可以表示為S[x，y，z]，其中x、y、z分別表示狀態(tài)的三個(gè)維度，取值范圍分別為0≤x<5，0≤y<5，0≤zχ步驟對(duì)狀態(tài)中的每一行進(jìn)行非線性變換，增強(qiáng)了狀態(tài)的混淆性。ι步驟將一個(gè)輪常數(shù)與狀態(tài)進(jìn)行異或操作，破壞了輪函數(shù)的對(duì)稱性。

輪函數(shù)的迭代次數(shù)取決于安全參數(shù)的選擇，通常為12、14、16、18、20或24輪。同時(shí)，Keccak置換展現(xiàn)出良好的混淆性，可以抵抗線性攻擊。與傳統(tǒng)的Merkle-Damg?rd結(jié)構(gòu)不同，Keccak置換的海綿結(jié)構(gòu)可以有效防止長(zhǎng)度擴(kuò)展攻擊。即使攻擊者獲得了部分消息及其哈希值，也無(wú)法偽造帶有額外消息的合法哈希值。

2 基于Keccak 置換的認(rèn)證加密算法改進(jìn)

2.1 現(xiàn)有算法的不足

盡管Keccak置換具有良好的密碼學(xué)性質(zhì)，但現(xiàn)有基于Keccak置換的認(rèn)證加密算法仍然存在一些不足之處。例如，由于Keccak置換的輪函數(shù)包含多個(gè)步驟，每一步都涉及大量的位運(yùn)算和置換操作，因此算法在軟件實(shí)現(xiàn)中的執(zhí)行效率相對(duì)較低?；贙eccakp[400]和Keccak-p[1600]置換構(gòu)建的算法吞吐量?jī)H為5.5 cycles/byte，與其他輕量級(jí)認(rèn)證加密算法相比，如Ascon（2.4 cycles/byte） 和NORX（2.5 cycles/byte） ，Ketje 和Keyak的性能還有較大的提升空間。

此外，現(xiàn)有算法的并行性普遍不足。在Keccak置換的輪函數(shù)中，π步驟和χ步驟分別對(duì)狀態(tài)中的比特進(jìn)行置換和非線性變換。這兩個(gè)步驟都包含了大量的數(shù)據(jù)依賴關(guān)系，難以實(shí)現(xiàn)高效的并行化處理。Keccak-p[1600]置換的并行度僅為8，即在一個(gè)時(shí)鐘周期內(nèi)，最多只能同時(shí)處理8個(gè)比特的數(shù)據(jù)[2]。這種有限的并行性限制了算法在多核處理器和硬件加速器上的加速潛力。因此難以滿足高吞吐量應(yīng)用場(chǎng)景的需求。

2.2 改進(jìn)方案一：優(yōu)化算法結(jié)構(gòu)

針對(duì)現(xiàn)有基于Keccak置換的認(rèn)證加密算法存在的不足，研究提出了優(yōu)化算法結(jié)構(gòu)的改進(jìn)方案。該方案通過(guò)重新設(shè)計(jì)置換的輪函數(shù)，引入更高效的非線性變換和置換操作，同時(shí)優(yōu)化算法的并行結(jié)構(gòu)，以提高算法的效率和并行性。在輪函數(shù)的設(shè)計(jì)上，改進(jìn)方案引入了新的非線性變換，稱為η步驟。與原有的χ步驟不同，η步驟采用了基于有限域上的多項(xiàng)式的非線性變換，具有更高的代數(shù)次數(shù)和非線性度。通過(guò)使用更強(qiáng)的非線性變換，改進(jìn)后的輪函數(shù)可以在更少的輪數(shù)下實(shí)現(xiàn)與原有算法相當(dāng)?shù)陌踩?。這將減少算法的計(jì)算開(kāi)銷(xiāo)?；趯?duì)η步驟的安全性分析，選擇了定義在GF（2⁸）上的三次多項(xiàng)式作為非線性函數(shù)，可以將差分和線性特征概率上界分別降低到2^-48和2^-64。

在置換操作上，研究重新設(shè)計(jì)了π步驟，引入了基于廣義Feistel結(jié)構(gòu)的置換網(wǎng)絡(luò)。與原有的基于固定置換表的設(shè)計(jì)不同，新的置換網(wǎng)絡(luò)采用了可參數(shù)化的置換模式，可以根據(jù)密鑰信息動(dòng)態(tài)生成置換表。這種動(dòng)態(tài)置換的設(shè)計(jì)增強(qiáng)了算法的混淆性。同時(shí)也提高了抗密鑰相關(guān)攻擊的能力。通過(guò)優(yōu)化參數(shù)，置換網(wǎng)絡(luò)可以在5輪迭代下實(shí)現(xiàn)全狀態(tài)擴(kuò)散，相比原有的π 步驟，擴(kuò)散速度可提高約60%。

研究還優(yōu)化了算法的并行結(jié)構(gòu)，通過(guò)重新安排輪函數(shù)中各個(gè)步驟的執(zhí)行順序，降低了步驟之間的數(shù)據(jù)依賴關(guān)系。這提高了算法的并行度。在新的并行結(jié)構(gòu)下，θ步驟和η步驟可以同時(shí)執(zhí)行，ρ步驟和π步驟也可以并行處理。這種細(xì)粒度的并行設(shè)計(jì)可以充分利用現(xiàn)代處理器的多核心和SIMD指令集，大幅提高算法的執(zhí)行效率[3]。

為了應(yīng)對(duì)非對(duì)稱威脅，研究引入了新的安全機(jī)制。在密鑰調(diào)度階段，采用基于哈希函數(shù)的密鑰衍生機(jī)制，從共享的短密鑰中生成不同的會(huì)話密鑰。這種機(jī)制可以有效防止密鑰枚舉攻擊，即使攻擊者獲得了某個(gè)會(huì)話的密鑰，也無(wú)法直接推導(dǎo)出其他會(huì)話的密鑰。同時(shí)，算法整合了基于計(jì)數(shù)器的隨機(jī)化機(jī)制，在每個(gè)會(huì)話開(kāi)始時(shí)生成一個(gè)隨機(jī)的初始計(jì)數(shù)器，用于對(duì)狀態(tài)進(jìn)行初始化。這可以有效防止重放攻擊，確保每個(gè)會(huì)話的數(shù)據(jù)均具有唯一屬性。

2.3 改進(jìn)方案二：引入新的安全機(jī)制

除了優(yōu)化算法結(jié)構(gòu)外，研究還提出了第二個(gè)改進(jìn)方案，即引入新的安全機(jī)制。該方案旨在進(jìn)一步增強(qiáng)基于Keccak置換的認(rèn)證加密算法的安全性，確保算法可以抵御非對(duì)稱威脅等新型攻擊方式。改進(jìn)方案引入了基于物理不可克隆函數(shù)（PUF）的密鑰管理機(jī)制。PUF利用硬件制造過(guò)程中的固有變異性，生成唯一且不可預(yù)測(cè)的密鑰。通過(guò)將PUF集成到認(rèn)證加密算法中，可以避免在密鑰存儲(chǔ)和分發(fā)過(guò)程中泄露密鑰信息[4]。改進(jìn)后的算法中，每個(gè)通信實(shí)體都集成了一個(gè)PUF模塊，用于生成設(shè)備唯一的密鑰。設(shè)PUF的挑戰(zhàn)為C，響應(yīng)為R，則PUF可以建模為一個(gè)函數(shù)f，如公式（1） 所示：

R = f （C ） （1）

在密鑰協(xié)商階段，通信雙方通過(guò)一個(gè)安全的密鑰交換協(xié)議，利用 PUF生成的密鑰建立共享密鑰。這可以有效防止密鑰泄露和克隆攻擊，即使攻擊者獲得了設(shè)備的物理訪問(wèn)權(quán)限，也無(wú)法提取出有效的密鑰信息。

在此基礎(chǔ)上，研究還引入了一種新的認(rèn)證機(jī)制，即基于哈希的認(rèn)證碼（HAC） 。與傳統(tǒng)的消息認(rèn)證碼（MAC） 不同，HAC利用了哈希函數(shù)的單向性和抗碰撞性，可以在不共享密鑰的情況下實(shí)現(xiàn)消息認(rèn)證[5]。在改進(jìn)后的算法中，發(fā)送方將消息M和一個(gè)隨機(jī)數(shù)R作為輸入，計(jì)算其哈希值作為認(rèn)證碼HAC，如公式（2） ：

HAC = H （M||R） （2）

接收方收到消息和認(rèn)證碼后，重新計(jì)算哈希值，并與收到的認(rèn)證碼進(jìn)行比較，以驗(yàn)證消息的完整性和真實(shí)性。HAC機(jī)制可以有效降低密鑰管理的復(fù)雜度，簡(jiǎn)化了認(rèn)證過(guò)程。

3 改進(jìn)后算法的安全性評(píng)估

3.1 安全性評(píng)估方法標(biāo)準(zhǔn)

研究采用密碼分析方法對(duì)改進(jìn)后的算法進(jìn)行安全性評(píng)估，重點(diǎn)關(guān)注差分分析、線性分析和代數(shù)分析這三種經(jīng)典的密碼分析方法。在此基礎(chǔ)上結(jié)合統(tǒng)計(jì)學(xué)測(cè)試方法對(duì)改進(jìn)后的算法進(jìn)行隨機(jī)性評(píng)估，按照NIST SP800-22隨機(jī)性測(cè)試標(biāo)準(zhǔn)進(jìn)行檢驗(yàn)，每項(xiàng)測(cè)試都給出P 值作為評(píng)估指標(biāo)，P 值越接近0.5，表示算法輸出的隨機(jī)性越好[6]。

另外，為了檢驗(yàn)算法的實(shí)際應(yīng)用安全性，研究采用安全協(xié)議分析方法對(duì)改進(jìn)后的算法在實(shí)際應(yīng)用中的安全性進(jìn)行評(píng)估。以TLS1.3協(xié)議為例，采用了符號(hào)執(zhí)行和模型檢測(cè)的方法，對(duì)基于改進(jìn)算法的TLS1.3協(xié)議進(jìn)行了形式化驗(yàn)證。通過(guò)使用自動(dòng)化驗(yàn)證工具，對(duì)協(xié)議的保密性、認(rèn)證性、完整性進(jìn)行分析。分析結(jié)合計(jì)算復(fù)雜性理論進(jìn)行檢驗(yàn)，其能夠檢查問(wèn)題在最壞情況下求解難度的方法。對(duì)于密碼算法，安全性的長(zhǎng)期下界可以用算法在最壞情況下被攻破所需的計(jì)算資源來(lái)衡量，結(jié)果能夠證明改進(jìn)后算法的長(zhǎng)期安全性。

3.2 安全性評(píng)估結(jié)果

3.2.1 密碼分析

在密碼分析方面，表1給出了改進(jìn)后算法在差分分析、線性分析和代數(shù)分析下的評(píng)估結(jié)果數(shù)據(jù)。

從表1結(jié)果可以發(fā)現(xiàn)，改進(jìn)后的算法在三種主要的密碼分析方法下都表現(xiàn)出了優(yōu)秀的安全性。在差分分析下，MDCP 達(dá)到了2^-128，優(yōu)于SHA-3 的安全要求；在線性分析下，MLC達(dá)到了2^-102，滿足了通用的安全要求；在代數(shù)分析下，AD達(dá)到了128，遠(yuǎn)高于通用的安全要求。結(jié)果證明，改進(jìn)后的算法能夠很好地抵抗已知的密碼分析攻擊[7]。

3.2.2 隨機(jī)性評(píng)估

在隨機(jī)性評(píng)估方面，改進(jìn)后算法的輸出在所有15 項(xiàng)隨機(jī)性測(cè)試中都通過(guò)了NIST標(biāo)準(zhǔn)，P 值均勻分布在0.4到0.6之間，表明算法具有優(yōu)秀的隨機(jī)性，能夠生成高質(zhì)量的隨機(jī)數(shù)，滿足密碼應(yīng)用的需求。

3.2.3 安全協(xié)議分析

在安全協(xié)議分析方面，算法基于TLS 1.3協(xié)議的安全性形式化驗(yàn)證獲得了理想結(jié)果，保密性、認(rèn)證性以及前向安全性等方面均滿足需求。

3.2.4 長(zhǎng)期安全性分析

在長(zhǎng)期安全性方面，通過(guò)計(jì)算復(fù)雜性理論分析，得到了改進(jìn)后算法在經(jīng)典計(jì)算機(jī)和量子計(jì)算機(jī)模型下的安全復(fù)雜性下界結(jié)果。經(jīng)典計(jì)算機(jī)模型結(jié)果為O（2²⁵⁶），量子計(jì)算機(jī)結(jié)果為O（2¹⁹²）。結(jié)果證明，改進(jìn)后的算法無(wú)論在經(jīng)典計(jì)算機(jī)還是量子計(jì)算機(jī)模型下，其安全復(fù)雜性下界都遠(yuǎn)高于當(dāng)前和可預(yù)見(jiàn)未來(lái)的計(jì)算能力，證明算法能夠提供足夠的長(zhǎng)期安全保障。

4 總結(jié)

綜合分析發(fā)現(xiàn)，改進(jìn)后的算法在效率、并行性和安全性方面都得到了顯著提升，長(zhǎng)期安全性分析也表明算法能夠提供足夠的安全保障。改進(jìn)算法通過(guò)優(yōu)化輪函數(shù)結(jié)構(gòu)和引入新的非線性變換，提高了算法執(zhí)行效率。重新設(shè)計(jì)的并行結(jié)構(gòu)顯著提升了算法的并行性，更適合在現(xiàn)代多核處理器上實(shí)現(xiàn)。而且引入基于PUF的密鑰管理和AEA模式等新安全機(jī)制，增強(qiáng)了算法抵抗非對(duì)稱威脅的能力。在差分分析、線性分析和代數(shù)分析等方面也表現(xiàn)出了優(yōu)秀的安全性，同時(shí)具有良好的隨機(jī)性。但改進(jìn)算法也存在一些不足，比如基于PUF的密鑰管理對(duì)硬件實(shí)現(xiàn)有一定要求，可能限制算法在某些場(chǎng)景下的應(yīng)用。AEA模式雖然提供了更高的安全性，但可能會(huì)增加通信開(kāi)銷(xiāo)。本文的研究成果為提高認(rèn)證加密算法的性能與安全性提供了新的思路和方法，未來(lái)還可以在硬件實(shí)現(xiàn)、新型攻擊分析等方面開(kāi)展進(jìn)一步研究，不斷完善和優(yōu)化算法設(shè)計(jì)。