Gimli認證加密方案的不可能差分分析

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

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

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

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

表1 Gimli攻擊結果對比

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

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

1 Gimli簡介

1.1 符號和說明

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

表2 符號說明

1.2 Gimli置換

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

圖1 Gimli狀態

Gimli：

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

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

(非線性層)；

對j=0，1，2，3，執行

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)

(線性層)。

當rmod4=0時，執行(Small-Swap)：

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

當rmod4=2時，執行(Big-Swap)：

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

當rmod4=0時，執行

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

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

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

1.3 Gimli認證加密方案

在介紹Gimli認證加密方案前，先介紹absorb和squeeze兩個函數。

(1) absorb：

② 對i=0，1，2，3，執行

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認證加密方案的加密過程如下：

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

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

③ 對i=0，1，2，3，執行

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置換

(處理關聯數據AD)。

對i=1，2，…，l，執行：

如果i=l，執行s2，3←s2，3⊕0x01000000，

Γ←absorb(ai，Γ)

(生成密文)。

對i=1，2，…，t，執行

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

如果i=t，執行s2，3←s2，3⊕0x01000000，

Γ←absorb(mi，Γ)，

C←c1‖…‖ct

(生成標簽tag)，

T←squeeze(Γ)。

⑦ 輸出C，T。

加密過程如圖2所示。

圖2 Gimli認證加密方案

2 Gimli不可能差分分析

在節2.1介紹差分傳播系統以及適用于Gimli 認證加密方案分析的不可能差分，并在節2.2介紹Gimli認證加密方案的狀態恢復攻擊。

2.1 7輪不可能差分

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

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

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

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

本節給出Gimli置換的差分傳播系統以及7輪不可能差分。

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

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

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

對性質1和性質2進行證明：

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

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

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

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

性質1與性質2得證。

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

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

圖3 非線性層差分傳播

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

圖5 7輪差分路徑

圖6 7輪不可能差分

2.2 Gimli狀態恢復

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

具體恢復過程如下：

圖7 11輪Gimli認證加密方案的不可能差分分析

2.3 Gimli狀態恢復補充說明

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

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

3 結束語

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