Gimli認(rèn)證加密方案的不可能差分分析

譚 豪，申 兵，苗旭東，張文政

(保密通信重點實驗室，四川 成都 610041)

近年來，隨著物聯(lián)網(wǎng)快速發(fā)展，適用于資源受限環(huán)境下進行數(shù)據(jù)加密的輕量級算法成為研究熱點。Gimli置換在2017年[1]被首次提出。基于Gimli置換設(shè)計的雜湊函數(shù)和認(rèn)證加密方案是32個NIST輕量級加密算法標(biāo)準(zhǔn)[2]第二輪候選方案之一。在Gimli安全性分析方面，HAMBURG等[3]實現(xiàn)了對22.5輪的Gimli密鑰恢復(fù)，但該攻擊只能在ad-hoc模型下實現(xiàn)，并不能應(yīng)用于正式的認(rèn)證加密方案；LIU等[4]在2020年實現(xiàn)了對9輪Gimli認(rèn)證加密(Authenticated Encryption，AE)方案的狀態(tài)恢復(fù)，并在2021年成功構(gòu)造了時間復(fù)雜度僅為252的全輪Gimli置換區(qū)分器[5]；GUTIERREZ等[6]在 2020年成功找到Gimli雜湊函數(shù)的12輪碰撞(從中間步驟發(fā)起的攻擊)。但以上文獻均未提出適用于Gimli 認(rèn)證加密方案狀態(tài)恢復(fù)的不可能差分區(qū)分器。

筆者找到了Gimli的7輪不可能差分，實現(xiàn)了對11輪Gimli 認(rèn)證加密方案的狀態(tài)恢復(fù)。在對Gimli 認(rèn)證加密方案已有的分析中，文中的攻擊分析輪數(shù)更高，且時間復(fù)雜度和數(shù)據(jù)復(fù)雜度都較低，是目前Gimli 認(rèn)證加密方案狀態(tài)恢復(fù)的最好結(jié)果。目前已有的Gimli分析結(jié)果如表1所示。

表1 Gimli攻擊結(jié)果對比

不可能差分分析是由BIHAM等[7]首次提出的。該方法主要分為兩個步驟：一是尋找一條合適的不可能差分；二是根據(jù)該不可能差分前后擴展，利用概率為零的差分排除所有的錯誤密鑰，進而實現(xiàn)密鑰恢復(fù)。不可能差分分析對Skipjack、PRINCE等分組密碼有較好的分析效果[7-8]。

目前主要有通過自動化搜索的方法尋找不可能差分，例如u方法[9]、WW方法[10]，以及利用MILP搜索不可能差分的方法[11]等。但以上方法只能找到輸入和輸出固定的不可能差分。由于Gimli認(rèn)證加密方案為sponge結(jié)構(gòu)，具有以下特點：參與加密運算的384 bit只會輸出128 bit的信息，另外256 bit的信息一直處于未知狀態(tài)。因此，這些方法搜索的不可能差分難以直接用于Gimli認(rèn)證加密方案分析。筆者設(shè)計了面向比特的差分傳播系統(tǒng)，找到了適用于分析Gimli認(rèn)證加密方案的7輪不可能差分。在該不可能差分前面擴展4輪，成功實現(xiàn)了11輪的Gimli認(rèn)證加密方案狀態(tài)恢復(fù)。

1 Gimli簡介

1.1 符號和說明

符號表示和基本概念如表2所示。

表2 符號說明

1.2 Gimli置換

Gimli置換將一個384 bit的輸入狀態(tài)迭代24輪，每一輪迭代包括了非線性運算和線性運算兩部分。384 bit狀態(tài)分為12個字，每個字為32 bit，12個字呈3行4列排列，如圖1所示。具體Gimli置換過程如下。

圖1 Gimli狀態(tài)

Gimli：

(1) 輸入Γ={si，j|0≤i≤2，0≤j≤3}。

(2) 對r=24，23，…，2，1，執(zhí)行

(非線性層)；

對j=0，1，2，3，執(zhí)行

x←s0，j<<<24，y←s1，j<<<9，z←s2，j

s2，j←x⊕(z<<1)⊕((y∧z)<<2)，s1，j←y⊕x⊕((x∨z)<<1)，s0，j←z⊕y⊕((x∧y)<<3)

(線性層)。

當(dāng)rmod4=0時，執(zhí)行(Small-Swap)：

s0，0，s0，1，s0，2，s0，3←s0，1，s0，0，s0，3，s0，2；

當(dāng)rmod4=2時，執(zhí)行(Big-Swap)：

s0，0，s0，1，s0，2，s0，3←s0，2，s0，3，s0，0，s0，1；

當(dāng)rmod4=0時，執(zhí)行

s0，0←s0，0⊕0x9e37790⊕r。

(3) 輸出Γ={si，j|0≤i≤2，0≤j≤3}。

下文中，加密1輪是指從當(dāng)前狀態(tài)迭代一個輪函數(shù)(包括線性層運算和非線性層運算兩部分)；加密0.5輪是只進行線性運算或非線性運算中的一個。

1.3 Gimli認(rèn)證加密方案

在介紹Gimli認(rèn)證加密方案前，先介紹absorb和squeeze兩個函數(shù)。

(1) absorb：

② 對i=0，1，2，3，執(zhí)行

s0，i←touint32(m4i，…，m4(i+1))。

③Γ←Gimli(Γ)。

④ 輸出Γ。

(2) squeeze：

① 輸入Γ={si，j|0≤i≤2，0≤j≤3}。

②h←tobytes(s0，0)‖tobytes(s0，1)‖tobytes(s0，2)‖tobytes(s0，3)。

③ 輸出h。

Gimli認(rèn)證加密方案的加密過程如下：

(初始化狀態(tài)，引入nonce，密鑰)。

② 初始化si，j=0，0≤i≤2，0≤j≤3。

③ 對i=0，1，2，3，執(zhí)行

s0，i←touint32(N4i‖…‖N4i+3)，s1，i←touint32(K4i‖…‖K4i+3)，s2，i←touint32(K16+4i‖…‖

K16+4i+3)。

④ 對Γ={si，j|0≤i≤2，0≤j≤3}進行Gimli置換

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

對i=1，2，…，l，執(zhí)行：

如果i=l，執(zhí)行s2，3←s2，3⊕0x01000000，

?！鸻bsorb(ai，Γ)

(生成密文)。

對i=1，2，…，t，執(zhí)行

ki←squeeze(Γ)，ci←ki⊕mi；

如果i=t，執(zhí)行s2，3←s2，3⊕0x01000000，

Γ←absorb(mi，Γ)，

C←c1‖…‖ct

(生成標(biāo)簽tag)，

T←squeeze(Γ)。

⑦ 輸出C，T。

加密過程如圖2所示。

圖2 Gimli認(rèn)證加密方案

2 Gimli不可能差分分析

在節(jié)2.1介紹差分傳播系統(tǒng)以及適用于Gimli 認(rèn)證加密方案分析的不可能差分，并在節(jié)2.2介紹Gimli認(rèn)證加密方案的狀態(tài)恢復(fù)攻擊。

2.1 7輪不可能差分

由節(jié)1.3可知，Gimli認(rèn)證加密方案僅能在s0，0，s0，1，s0，2，s0，3這4個字引入差分，且加密后僅輸出這4個字的信息。因此，能應(yīng)用于Gimli認(rèn)證加密方案的不可能差分需滿足以下條件：

(1) 輸入差分僅在s0，0，s0，1，s0，2，s0，34個字非零；

(2) 輸出差分只能限制在s0，0，s0，1，s0，2，s0，34個字的取值，其他字不得進行限制；

(3) 輸出差分受限比特盡可能少(在狀態(tài)恢復(fù)階段，輸出差分受限比特越少，時間復(fù)雜度與數(shù)據(jù)復(fù)雜度越低)。

本節(jié)給出Gimli置換的差分傳播系統(tǒng)以及7輪不可能差分。

令Δa=a1⊕a2，Δb=b1⊕b2，差分之間的與、或運算分別為η(Δa，Δb，∧)=(a1∧b1)⊕(a2∧b2)，η(Δa，Δb，∨)=(a1∨b1)⊕(a2∨b2)。差分運算具有如下性質(zhì)。

性質(zhì)1若Δa≠0或Δb≠0，則η(Δa，Δb，∧)=2，η(Δa，Δb，∨)=2。

性質(zhì)2若Δa=0且Δb=0，則η(Δa，Δb，∧)=0，η(Δa，Δb，∨)=0。

對性質(zhì)1和性質(zhì)2進行證明：

η(Δa，Δb，∧)，Δa，Δb，a1，a2，b1，b2的關(guān)系如表3所示。

表3 η(Δa，Δb，∧)，Δa，Δb，a1，a2，b1，b2關(guān)系表

由表3可得當(dāng)且僅當(dāng)Δa=0且Δb=0時，η(Δa，Δb，∧)=0。其他情況需根據(jù)a1，a2，b1，b2具體的值來確定η(Δa，Δb，∧)的取值。

同理可證η(Δa，Δb，∨)=2。

性質(zhì)1與性質(zhì)2得證。

性質(zhì)3若Δa=2或Δb=2，則Δa⊕Δb=2，η(Δa，Δb，∨)=2，η(Δa，Δb，∧)=2。

利用上述性質(zhì)，節(jié)2.2的Gimli置換差分傳播過程如例1所示。

圖3 非線性層差分傳播

圖4 線性層差分傳播示意圖

圖5 7輪差分路徑

圖6 7輪不可能差分

2.2 Gimli狀態(tài)恢復(fù)

由節(jié)1.3中的Gimli認(rèn)證加密方案可知，引入關(guān)聯(lián)數(shù)據(jù)對AD時，可將s0，0，s0，1，s0，2，s0，3引入差分，再加密無差分的明文對，根據(jù)密文C得到經(jīng)過一次Gimli置換后s0，0，s0，1，s0，2，s0，3的差分。運用節(jié)2.1中的7輪不可能差分，向前擴展4輪，成功分析了11輪Gimli認(rèn)證加密方案。分析過程如圖7所示。

具體恢復(fù)過程如下：

圖7 11輪Gimli認(rèn)證加密方案的不可能差分分析

2.3 Gimli狀態(tài)恢復(fù)補充說明

由于Gimli認(rèn)證加密方案采取sponge結(jié)構(gòu)，因此適用于恢復(fù)狀態(tài)的不可能差分應(yīng)滿足節(jié)1.3中給出的3個條件。節(jié)2.1中給出了一個差分傳播系統(tǒng)，找到了一條滿足條件的7輪不可能差分。由于Gimli置換前1.5輪迭代中每一列字是獨立運算的，節(jié)2.2利用這一特點將s1，1，s2，1，s1，3，s2，34個字的猜測量分成兩部分進行，大幅度地降低了狀態(tài)恢復(fù)的時間復(fù)雜度和數(shù)據(jù)復(fù)雜度。

節(jié)2.2中的從初始狀態(tài)加密到1.5輪(第2列概率為2-32，第4列概率2-64)，以及從1.5輪狀態(tài)加密到4輪的概率在計算時(概率為2-96)，都將輪函數(shù)視為隨機加密。但在實際運算中，低輪數(shù)加密的差分?jǐn)U散和混淆程度遠(yuǎn)不如隨機加密?；谶@個原因，可能會出現(xiàn)任意差分加密4輪，都無法得到節(jié)2.1中7輪不可能差分的輸入差分這樣的情況。為此，通過MILP建模[12]，驗證了經(jīng)過4輪加密存在一條差分路徑，該路徑的輸出差分為7輪不可能差分的輸入差分。同理，由于上述原因，一旦驗證存在這樣的4輪差分路徑，則初始狀態(tài)加密到1.5輪，以及從1.5輪狀態(tài)加密到4輪的概率都比隨機加密的概率大。換言之，實際恢復(fù)所需要的時間復(fù)雜度和數(shù)據(jù)復(fù)雜度會小于節(jié)2.2中給出的結(jié)果。由于Gimli置換運算具有對稱性，可根據(jù)相同的方法恢復(fù)第1列和第3列的狀態(tài)。

3 結(jié)束語

以上介紹了Gimli有關(guān)聯(lián)數(shù)據(jù)的認(rèn)證加密方案，并根據(jù)該方案的特殊性構(gòu)造了一個差分傳播系統(tǒng)，找到了適用于分析Gimli認(rèn)證加密方案的不可能差分。利用Gimli置換前兩輪的弱擴散性，在該不可能差分前擴展4輪，將原來2128的密鑰猜測量縮小至264+264=265密鑰猜測量，成功分析了11輪的Gimli認(rèn)證加密方案。與現(xiàn)有的對Gimli認(rèn)證加密方案的狀態(tài)恢復(fù)結(jié)果相比，文中的輪數(shù)更高，時間復(fù)雜度和空間復(fù)雜度更低。