加密算法Simpira v2的不可能差分攻擊

劉 亞，宮佳欣，趙逢禹

(1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.中國科學院信息工程研究所 信息安全國家重點實驗室，北京 100093)

隨著大數據時代和量子計算機的發展，海量數據的存儲和信息安全上的需求顯著增加?，F實系統中的數據機密性需要使用安全的密碼算法來保障。目前，許多芯片公司如Intel、AMD、ARM引入AES指令改變了現代處理器上對稱加密算法的部署環境，大大加快了數據加密過程，節省了資源消耗。

如何提高對稱加密算法實現時需要的吞吐量并降低加密開銷是產業界非常關注的現實問題。2016年，文獻[1]在亞密會上提出了一個新的加密置換算法族—Simpira v2，可以作為大分組Even-Mansour結構的加密置換函數。該算法采用廣義Feistel結構，支持分組長度為128b比特(bit)的輸入，b為Simpira v2算法的分支數目，可以應用在輸入數據大于128 bit的應用環境，有效解決了在當今64位現代處理器上實現大吞吐量的問題。根據分支數目b的不同，將不同分支數的Simpira記為Simpira-b。

Simpira v2置換算法可以應用在后量子時代海量數據的保密方面，研究Simpira v2置換算法的安全性可以為現實中的使用提供有效的理論依據。目前，對Simpira v2的安全性分析包括Simpira-3的不可能差分攻擊和飛去來攻擊、Simpira-4的不可能差分攻擊。文獻[2]提出了9輪和10輪Simpira-3的不可能差分攻擊以及10輪Simpira-3的飛去來攻擊。文獻[3]對Simpira-4抵抗不可能差分攻擊的能力進行了評估，首先提出在Simpira v2的安全性聲明下，對7輪Simpira-4的不可能差分攻擊，并恢復了256位主密鑰，攻擊需要的數據和時間復雜度分別為257個選擇明文和257次加密；其次提出在Even-Mansour的安全性聲明下，對8輪Simpira-4的不可能差分攻擊，并恢復了全部512位主密鑰，攻擊需要的數據和時間復雜度分別為2170個選擇明文和2170次加密。

目前，針對Simpira-3/4的安全性分析比較多，而其他分支數情形的安全性還有待進一步研究。當Simpira-6作為Even-Mansour結構下的置換算法，主密鑰長度支持768位，相對于Simpira-3和Simpira-4，Simpira-6支持的密鑰長度更長，安全強度更強，適用于后量子時代保護信息和數據的安全。分組密碼的安全性分析保障了分組密碼未來在實際系統中的使用，不可能差分(分析)攻擊、中間相遇攻擊、零和區分器分析[4]、相關故障注入攻擊[5]、側信道分析[6]等方法是重要的密碼分析方法，而其中不可能差分攻擊是近年來比較有效的攻擊方法，已經成功地攻擊了許多著名的分組密碼算法，譬如AES[7]、QARMA[8]、CRAFT[9]、Midori[10]、Tweakable TWINE[11]、Kaylna[12]和PRINCE[13]等。不可能差分攻擊最早是由KNUDSEN和BIHAM分別提出的[14-15]，基本思想是構造一條概率為零的差分路徑，稱為不可能差分鏈，在該不可能差分鏈前后分別接若干輪，形成不可能差分分析攻擊路徑。攻擊過程中通過選取一些滿足輸入和輸出差分的明密文對，并猜測密鑰可能值，從而計算是否可以得到不可能差分區分器的輸入輸出差分，如果得到，則將錯誤密鑰從密鑰空間中刪除，重復上述過程，直到所有錯誤的密鑰被排除且僅剩惟一的密鑰，即可能為正確密鑰。鑒于不可能差分分析的重要性，故研究Simpira-6抵抗不可能差分攻擊對完善Simpira v2的安全性分析是非常重要的。

在仔細研究基本結構的基礎上，筆者對Simpira-6作為Even-Mansour結構下的置換算法進行安全性分析，并對Simpira-6在不同安全性前提下，分析其抵抗不可能差分攻擊的能力。首先，提出一條9輪Simpira-6的不可能差分鏈，此不可能差分鏈是目前為止找到的Simpira-6最長的不可能差分鏈，但是基于此不可能差分鏈對Simpira-6進行不可能差分攻擊時，在線攻擊的數據復雜度超過了窮盡搜索，因此不能被用作攻擊更高輪次的不可能差分攻擊；其次，在Simpira v2的安全性聲明下實現對7輪Simpira-6的不可能差分攻擊，恢復384位的主密鑰，需要的數據和時間復雜度分別為257.07個選擇明文和257.07次加密；最后，在Even-Mansour結構的安全性聲明下對8輪Simpira-6進行不可能差分攻擊，恢復所有768位密鑰，需要的數據和時間復雜度分別為2168個選擇明文和2168次加密。與之前Simpira-3/4的不可能差分分析相比，在進行8輪Simpira-6不可能差分攻擊時，構造了7輪不可能差分鏈的輸入差分為兩個分支非零，從而使得基于該區分器進行8輪Simpira-6不可能差分攻擊時，恢復768 bit的主密鑰所需的數據復雜度更低，攻擊效果更好。

1 預備知識

1.1 符號

(1)P，C：明文，密文；

(2) ⊕：按位異或；

(3)S：輪函數F的內部狀態；

(5) ΔS：狀態S與狀態S′的差分值；

(6) Δi：第i條差分鏈；

(7)Rj：Simpira-6的第j輪加密；

(8) 0：零差分字節；

(9) *：非零差分字節；

(10)α，β，α′i，β′i：內部狀態的差分模式。

1.2 Simpira v2算法描述

Simpira-6支持768 bit輸入，主密鑰也為768 bit，輪數為15輪，輪函數如圖1所示，加密規則如下：

圖1 Simpira-6的輪結構

(1)

Simpira-6中每個分組的一個分支128 bit可以用一個4×4的字節矩陣表示：

(2)

其中，si表示1個字節。

輪函數F內部采用了類似于高級加密標準(AES)輪函數的4種運算，其中輪密鑰加(ARK)操作轉換為輪常數加(AC)操作，分別為：

(1) 字節代替變換(SubBytes，SB)：使用S盒做非線性變換，將內部子塊的每個字節非線性地轉換為另一個字節。

(2) 行位移變換(ShiftRows，SR)：將狀態值的每個分支塊的第i行循環左移i個字節，其中0≤i≤3。

(3) 列混合變換(MixColumns，MC)：將內部狀態值的每個分支的每一列乘以矩陣M。

(4) 輪常數加(AddConstant，AC)：輪常數和內部子塊按位異或。

輪函數F重復運用了4種運算，具體形式如下：

1.3 安全性假設

定義1單一密鑰Even-Mansour結構[16]使用密鑰K將明文P加密為密文C的過程如下：

C=EK(P)=π(P⊕K)⊕K，

(3)

其中，π為置換算法。Even-Mansour結構的設計者DUNKELMAN等[17]指出，當敵手得到D個明密文對時，恢復Even-Mansour結構的密鑰K需要2n/D次置換查詢。Simpira v2設計者GUERON等[1]指出，當Simpira v2作為置換算法使用時，其安全性建立在敵手查詢算法次數少于2128的前提下。

定義2(超級S盒，Super-S盒)[18]超級S盒依次由5個操作構成：字節代替變換、行位移變換、列混合變換、輪密鑰加、字節代替變換。

性質1(超級S盒的性質)[18]對于有限域上非0輸入差分Δi和輸出差分Δo，超級S盒的每一種輪子密鑰k，平均只有一個輸入值x滿足QSuper-S(x)⊕QSuper-S(x⊕Δi)=Δo。

1.4 不可能差分攻擊

不可能差分攻擊是由KNUDSEN[14]和BIHAM[15]分別提出的一種分析分組密碼的方法。該方法作為差分分析的一種變體，廣泛應用在分組密碼的安全性分析中。其基本原理是通過尋找一條概率為零的差分鏈，稱為不可能差分鏈，在不可能差分鏈前面和后面分別增加分析輪，進行密鑰恢復攻擊，不斷從密鑰空間中剔除錯誤的密鑰，直到僅剩惟一的正確密鑰。

圖2 不可能差分攻擊的基本模式

2 Simpira-6的不可能差分分析

首先構造一條Simpira-6不可能差分鏈，然后分別在Simpira v2的安全性聲明下和Even-Mansour的安全性聲明下，對Simpira-6實施不可能差分攻擊。

2.1 9輪Simpira-6的不可能差分分析

圖3 Simpira-6的9輪不可能差分鏈

圖4 F(α)和F(β)

注：在Simpira v2置換算法的安全性聲明下，要求攻擊的時間復雜度和數據復雜度不能大于2128，而基于命題1的9輪不可能差分鏈構造攻擊路徑進行Simpira-6安全性分析時，攻擊的數據和時間復雜度將超過2128，因此不能直接使用2.1節提出的9輪不可能差分鏈進行攻擊。

2.2 7輪Simpira-6的不可能差分攻擊

圖5 6輪Simpira-6不可能差分鏈

如圖6所示，在6輪不可能差分鏈Δ1前加1輪，可以構造對7輪Simpira-6的不可能差分攻擊，恢復128位的K0。

圖6 7輪Simpira-6的不可能差分攻擊

攻擊過程如下：

(1) 選擇明文在P0[0，5]，SR-1°MC-1(P1)[0，1，2，3]字節處遍歷所有可能的取值，其他字節取固定值形成1個結構，因此1個結構共有26×8=248個可能的取值，可以形成大約248×(248-1)/2≈295對明文。選擇2n個結構，共有2n+95對明文。

(2) 將2n+95對明文經過7輪Simpira-6加密，選擇密文差分滿足ΔC1=b，ΔC4=β′3形式的明密文對，經過篩選之后，還剩大約2n+95-8×8=2n+31對明密文符合條件。

(4) 對所有的2n+31對明文重復執行步驟(3)，不斷從密鑰空間剔除錯誤的密鑰，直到僅剩惟一的正確的K0[0，5，10，15]，即ε=232×(1-2-32)2n+31=1，n≈5.48。恢復32位的K0[0，5，10，15]的數據復雜度為248+5.48=253.48個選擇明文，時間復雜度為253.48次7輪Simpira-6加密。通過調整明文的活動單元位置，可以繼續恢復所有128位的K0。整個過程需重復4次上述攻擊步驟，因此恢復所有128位K0的數據復雜度為253.48×4=255.48個選擇明文，時間復雜度為255.48次7輪Simpira-6加密。

類似地，在剩下的兩條6輪Simpira-6不可能差分鏈Δ2、Δ3前加一輪，可以攻擊7輪Simpira-6并恢復所有128位的K2和K4。攻擊過程與上述恢復K1的過程類似，不再重復。因此，恢復所有384位的K0、K2、K4數據復雜度為255.48×3=257.07選擇明文，時間復雜度為257.07次7輪Simpira-6加密。攻擊過程中明文活動單元字節與其對應的可以恢復的密鑰字節位置如表1所示。

表1 明文活動單元與密鑰字節對應表

在Simpira v2的安全性聲明的攻擊假設下，進行7輪Simpira-6不可能差分攻擊恢復384位密鑰K0、K2、K4，需要的數據復雜度為257.07個選擇明文，時間復雜度為257.07次7輪Simpira-6加密。

2.3 8輪Simpira-6的不可能差分攻擊

(a) 不可能差分鏈Δ4

利用兩條7輪Simpira-6的不可能差分鏈Δ4、Δ5構造對8輪Simpira-6的不可能差分攻擊恢復全部768位主密鑰，攻擊分為4步：① 利用不可能差分鏈Δ4，前加一輪恢復K0、K4；② 在不可能差分鏈Δ4后加一輪恢復128位的K1；③ 在不可能差分鏈Δ5前加一輪恢復128位的2；④ 在不可能差分鏈Δ5后加一輪恢復128位K3；最后，窮舉搜索K5，恢復全部768位密鑰。

2.3.1 恢復K0與K4

如圖8所示，在7輪不可能差分鏈Δ4前加1輪，可以構造對8輪Simpira-6的不可能差分攻擊，恢復256位的K0、K4。

圖8 8輪Simpira-6的不可能差分攻擊恢復K0與K4

攻擊過程如下：

(1) 取明文在P0[0，5，10，15]，SR-1°MC-1(P1)[0，1，2，3]，P4[0，5，10，15]，SR-1°MC-1(P5)[0，1，2，3]字節處遍歷所有可能的取值，其它字節取固定值形成1個結構，因此1個結構共有216×8=2128個可能的取值，可以形成大約2128×(2128-1)/2≈2255對明文；選擇2n個結構，共有2n+255對明文。

(2) 將2n+255對明文經過8輪Simpira-6加密，選擇密文差分滿足ΔC0=β，ΔC3=0，ΔC5=β′8的明密文對，經過24×8=192位的篩選之后，還剩大約2n+255-192=2n+63對明密文符合條件。

(4) 對所有的2n+63對明文對重復執行步驟(3)，不斷從密鑰空間剔除錯誤的密鑰，直到僅剩惟一的正確的K0[0，5，10，15]，K4[0，5，10，15]，即ε=264×(1-264)2n+63=1，n≈6.48。恢復64位的K0[0，5，10，15]，K4[0，5，10，15]的數據復雜度為26.48+128=2134.48個選擇明文，時間復雜度為2134.48次8輪Simpira-6加密。通過調整明文的活動單元的位置，可以繼續恢復所有的128位的K0和128位的K4。整個過程重復4次上述攻擊步驟，因此恢復所有256位K0、K4數據復雜度為2134.48×4=2136.48個選擇明文，時間復雜度為2136.48次8輪Simpira-6加密。

2.3.2 恢復K1

如圖9所示，在7輪不可能差分鏈Δ4末端添加1輪，可以構造對8輪Simpira-6的不可能差分攻擊，恢復128位的K1。

圖9 8輪Simpira-6的不可能差分攻擊恢復K1

攻擊過程如下：

(1) 取明文在P3[0，5，10，15]，P5[0，5，10，15]字節處遍歷所有可能的取值，其他字節取固定值形成1個結構。因此，1個結構共有28×8=264個可能的取值，可以形成大約264×(264-1)/2≈2127對明文。選擇2n個結構，共有2n+127對明文。

(2) 將2n+127對明文經過8輪Simpira-6加密，選擇密文差分滿足ΔC3=β的密文。經過篩選之后，還剩大約2n+127-4×8=2n+95對明密文符合條件。

(4) 對所有2n+95對明文重復執行步驟(3)，不斷從密鑰空間剔除錯誤的密鑰K1，直到僅剩惟一正確的K1，即ε=2128×(1-2-128)2n+95=1，得n≈40?；謴?28位的K1的數據復雜度是240+64=2104個選擇明文，時間復雜度為2104次8輪Simpira-6加密。

2.3.3 恢復K2

如圖10所示，在7輪不可能差分鏈Δ5前加一輪，可以構造對Simpira-6的8輪不可能差分攻擊，恢復128位的K2。攻擊過程如下：

圖10 8輪Simpira-6的不可能差分攻擊恢復K2

(1) 取明文在P2[0，5，10，15]，SR-1°MC-1(P3)[0，1，2，3]，字節處遍歷所有可能的取值，其它字節取固定值形成1個結構，因此1個結構共有28×8=264個可能的取值，可以形成大約264×(264-1)/2≈2127對明文。選擇2n個結構，共有2n+127對明文。

(2) 將2n+127對明文經過8輪Simpira-6加密，選擇密文差分形式滿足ΔC1=0，ΔC3=β′10，ΔC4=β的明密文對。經過24×8=192位的篩選之后，還剩大約2n+127-192=2n-65對明密文符合條件。

(4) 對所有的2n-65對明密文對重復執行上述步驟(3)，不斷從密鑰空間剔除錯誤的密鑰，直到僅剩惟一正確的K2[0，5，10，15]，即ε=232×(1-2-32)2n-65=1，計算得n≈102。恢復32位的K2[0，5，10，15]的數據復雜度為2102+64=2166個選擇明文，時間復雜度為2166次8輪Simpira-6加密。通過改變明文P2的活動單元的位置，可以恢復整個128位的K2。需要重復執行以上步驟4次，所以恢復所有K2的數據復雜度為2168個選擇明文，時間復雜度為2168次8輪Simira-6加密。

2.3.4 恢復K3

如圖11所示，在7輪不可能差分鏈Δ5后加一輪，可以構造對8輪Simira-6的不可能差分攻擊，恢復128位的K3，攻擊過程如下：

圖11 8輪Simpira-6的不可能差分攻擊恢復K3

(1) 選擇明文在P1[0，5，10，15]字節處遍歷所有可能的值，其它字節取固定值形成1個結構，因此1個結構共有24×8=232個可能的取值，可以形成大約232×(232-1)/2≈263對明文。選擇2n個結構，共有2n+63對明文。

(2) 將2n+63對明文經過8輪Simpira-6加密，選擇密文差分形式滿足ΔC5=β形式的明密文對。經過篩選之后，還剩大約2n+63-32=2n+31對明文符合條件。

(4) 對所有的2n+31對明文重復執行步驟(3)，不斷從密鑰空間剔除錯誤的密鑰，直到僅剩惟一正確的K3，即ε=2128×(1-2-128)2n+31=1，計算得n≈104。恢復128位的K3的數據復雜度為2104+32=2136個選擇明文，時間復雜度2136次8輪Simpira-6加密。

綜上，對8輪Simpira-6的不可能差分攻擊恢復K0、K1、K2、K3、K4共640位密鑰，通過窮舉搜索128位的K5，可以恢復所有的768位密鑰。因此，8輪Simpira-6的不可能差分攻擊恢復全部768位主密鑰數據復雜度為2168個選擇明文，時間復雜度大約為2168次8輪Simpira-6加密。

在對8輪Simpira-6的不可能差分攻擊中，不同于文獻[3]對Simpira-4提出的7輪不可能差分區分鏈只有一個分支為非零差分的輸入差分形式，文中提出的7輪Simpira-6的不可能差分鏈Δ4輸入差分有2個非零輸入差分形式。這種輸入差分可以保證使用更少的數據和時間復雜度恢復出所有主密鑰。Δ4前加一輪，可以恢復256位的K0、K4，數據復雜度為2136.48個選擇明文，Δ4后接一輪，恢復K1，數據復雜度為2104個選擇明文。提出7輪Simpira-6的不可能差分鏈Δ5用于恢復K3，數據復雜度為2136個選擇明文。相對于文獻[3]，恢復Simpira-4的K0、K1、K2、K3數據復雜度均為2168個選擇明文，文中方法用更少的數據更快的時間恢復更多的密鑰，攻擊數據復雜度和時間復雜度均降低。表2列出了目前Simpira v2的攻擊結果。

表2 Simpira v2算法的攻擊結果

3 結束語

筆者主要分析了Simpira v2加密算法抵抗不可能差分攻擊的安全性。在分析Simpira-6抵抗不可能差分攻擊的安全性時，提出一條Simpira-6的最長的9輪不可能差分鏈；在Simpira v2的安全性聲明下，提出3條Simpira-6的6輪不可能差分區分器，分別在6輪不可能差分區分器前加1輪，構造對Simpira-6的7輪不可能差分攻擊，恢復384位密鑰，攻擊需要的數據復雜度為257.07個選擇明文，時間復雜度為257.07次7輪Simpira-6加密；在Even-Mansour的安全性聲明下，提出2條7輪不可能差分區分器，分別在區分器前加1輪、后加1輪，構造對Simpira-6的8輪不可能差分攻擊，恢復了全部768位密鑰，數據復雜度為2168個選擇明文，時間復雜度為2168次8輪Simpira-6加密。相對于當前對Simpira v2的不可能差分攻擊結果，筆者用更少的數據、更快的時間恢復更多的密鑰。這些研究成果是對Simpira v2系列密碼算法安全性分析的有力補充，對未來產業界安全地運用該算法提供理論依據。