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

劉 亞，宮佳欣，趙逢禹

(1.上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093；2.中國科學(xué)院信息工程研究所 信息安全國家重點(diǎn)實(shí)驗(yàn)室，北京 100093)

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

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

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

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

在仔細(xì)研究基本結(jié)構(gòu)的基礎(chǔ)上，筆者對Simpira-6作為Even-Mansour結(jié)構(gòu)下的置換算法進(jìn)行安全性分析，并對Simpira-6在不同安全性前提下，分析其抵抗不可能差分攻擊的能力。首先，提出一條9輪Simpira-6的不可能差分鏈，此不可能差分鏈?zhǔn)悄壳盀橹拐业降腟impira-6最長的不可能差分鏈，但是基于此不可能差分鏈對Simpira-6進(jìn)行不可能差分攻擊時，在線攻擊的數(shù)據(jù)復(fù)雜度超過了窮盡搜索，因此不能被用作攻擊更高輪次的不可能差分攻擊；其次，在Simpira v2的安全性聲明下實(shí)現(xiàn)對7輪Simpira-6的不可能差分攻擊，恢復(fù)384位的主密鑰，需要的數(shù)據(jù)和時間復(fù)雜度分別為257.07個選擇明文和257.07次加密；最后，在Even-Mansour結(jié)構(gòu)的安全性聲明下對8輪Simpira-6進(jìn)行不可能差分攻擊，恢復(fù)所有768位密鑰，需要的數(shù)據(jù)和時間復(fù)雜度分別為2168個選擇明文和2168次加密。與之前Simpira-3/4的不可能差分分析相比，在進(jìn)行8輪Simpira-6不可能差分攻擊時，構(gòu)造了7輪不可能差分鏈的輸入差分為兩個分支非零，從而使得基于該區(qū)分器進(jìn)行8輪Simpira-6不可能差分攻擊時，恢復(fù)768 bit的主密鑰所需的數(shù)據(jù)復(fù)雜度更低，攻擊效果更好。

1 預(yù)備知識

1.1 符號

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

(2) ⊕：按位異或；

(3)S：輪函數(shù)F的內(nèi)部狀態(tài)；

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

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

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

(8) 0：零差分字節(jié)；

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

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

1.2 Simpira v2算法描述

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

圖1 Simpira-6的輪結(jié)構(gòu)

(1)

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

(2)

其中，si表示1個字節(jié)。

輪函數(shù)F內(nèi)部采用了類似于高級加密標(biāo)準(zhǔn)(AES)輪函數(shù)的4種運(yùn)算，其中輪密鑰加(ARK)操作轉(zhuǎn)換為輪常數(shù)加(AC)操作，分別為：

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

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

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

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

輪函數(shù)F重復(fù)運(yùn)用了4種運(yùn)算，具體形式如下：

1.3 安全性假設(shè)

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

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

(3)

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

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

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

1.4 不可能差分攻擊

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

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

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

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

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

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

圖4 F(α)和F(β)

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

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

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

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

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

攻擊過程如下：

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

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

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

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

表1 明文活動單元與密鑰字節(jié)對應(yīng)表

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

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

(a) 不可能差分鏈Δ4

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

2.3.1 恢復(fù)K0與K4

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

圖8 8輪Simpira-6的不可能差分攻擊恢復(fù)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]字節(jié)處遍歷所有可能的取值，其它字節(jié)取固定值形成1個結(jié)構(gòu)，因此1個結(jié)構(gòu)共有216×8=2128個可能的取值，可以形成大約2128×(2128-1)/2≈2255對明文；選擇2n個結(jié)構(gòu)，共有2n+255對明文。

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

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

2.3.2 恢復(fù)K1

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

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

攻擊過程如下：

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

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

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

2.3.3 恢復(fù)K2

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

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

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

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

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

2.3.4 恢復(fù)K3

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

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

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

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

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

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

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

表2 Simpira v2算法的攻擊結(jié)果

3 結(jié)束語

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