石淑英，何 駿

(鄭州信大捷安移動信息安全關(guān)鍵技術(shù)國家地方聯(lián)合工程實驗室，河南 鄭州 450004)

0 引言

SKINNY算法族是由BEIERLE C等人[1]在CRYPTO 2016上提出的一個可調(diào)輕量級分組密碼算法族，主要目的是為了設(shè)計出一種軟硬件實現(xiàn)都非常高效，并且性能能夠比NSA提出的候選算法SIMON更好的輕量級分組密碼算法。此外，設(shè)計者也提出了SKINNY算法的一種低延遲的變體MANTIS算法，與SPECK算法進行性能對比，安全性分析結(jié)果對比情況見表1。

SKINNY算法采用的是SPN結(jié)構(gòu)，根據(jù)分組規(guī)模和密鑰規(guī)模的不同，表示為SKINNY-n-k，具體可分為SKINNY-n-n、SKINNY-n-2n和SKINNY-n-3n三大類，其中n表示分組規(guī)模，k表示可調(diào)規(guī)模。設(shè)計者證明了該算法族對已知的分組密碼攻擊方法例如差分/線性分析、不可能差分分析、相關(guān)密鑰分析等有較強的安全性。

MANTIS算法基于PRINCE算法進行改進，即該算法基本結(jié)構(gòu)與PRINCE類似，均采用FX結(jié)構(gòu)[2-3]。輪函數(shù)的具體環(huán)節(jié)中采用的與Midori算法相同的S盒變換、P盒置換以及列混合變換，只是分組狀態(tài)的排列與Midori算法有所不同，在密鑰調(diào)度環(huán)節(jié)采用的是可調(diào)模型，設(shè)計者認(rèn)為該步驟能有效提高算法安全性。在算法實現(xiàn)方面，其具有低延遲和易于硬件實現(xiàn)的優(yōu)點。

TOLBA M等人[4]利用不可能差分技術(shù)分析了SKINNY算法在單密鑰條件下的安全性，分別對SKINNY-n-n、SKINNY-n-2n、SKINNY-n-3n攻擊至18輪、20輪、22輪；LIU G等人[5]給出了算法在相關(guān)密鑰不可能差分攻擊和相關(guān)密鑰矩陣攻擊下的攻擊結(jié)果，對SKINNY算法族的三大類分別攻擊至19輪、23輪、27輪；ANKELE R等人[6]同樣采用相關(guān)密鑰不可能差分技術(shù)對SKINNY-64-128算法進行了分析，攻擊到了21輪，并且在已知一定數(shù)量的密鑰的假設(shè)條件下，將攻擊輪數(shù)拓展到了23輪；SADEGHI S[7]等人分析給出了算法在相關(guān)密鑰不可能差分和零相關(guān)線性分析下的攻擊路徑；DOBRAUNIG C[8]等人給出了針對MANTIS5的實際密鑰恢復(fù)攻擊?，F(xiàn)有分析對SKINNY-n-n算法的最好攻擊結(jié)果僅達(dá)到了19輪，對MANTIS算法除MANTIS5外還未有其他的攻擊結(jié)果。

表1 SKINNY與MANTIS算法安全性分析結(jié)果對比

注：ID表示不可能差分分析；R-ID表示相關(guān)密鑰不可能差分分析；R-R表示相關(guān)密鑰矩陣攻擊；R-D表示相關(guān)密鑰差分分析。

本文中，針對SKINNY-n-n算法，首先通過分析算法的結(jié)構(gòu)特性，給出了兩類長度為13輪的相關(guān)密鑰不可能差分區(qū)分器，而后據(jù)其中的一種區(qū)分器，對算法進行了19輪的相關(guān)密鑰不可能差分分析。針對MANTIS算法，同樣通過分析算法結(jié)構(gòu)特性，并利用相關(guān)密鑰分析方法，給出了可用于MANTIS算法安全性分析的幾類高概率相關(guān)密鑰區(qū)分器。

在第1節(jié)中，介紹了SKINNY算法和MANTIS算法的基本結(jié)構(gòu)；在第2節(jié)中，首先介紹了SKINNY-n-n算法的相關(guān)特性，基于這些性質(zhì)，給出了兩類13輪的相關(guān)密鑰不可能差分區(qū)分器；在第3節(jié)中，運用第2節(jié)中得到的區(qū)分器中的一種，給出了19輪的SKINNY-n-n算法的相關(guān)密鑰不可能差分攻擊結(jié)果，并分析了攻擊所需的復(fù)雜度；在第4節(jié)中，首先分析了MANTIS算法的性質(zhì)，而后據(jù)此，給出了幾類MANTIS算法的相關(guān)密鑰區(qū)分器。

1 算法介紹

本節(jié)中，主要介紹SKINNY算法和MANTIS算法的具體結(jié)構(gòu)，并對文中所用到的具體符號進行解釋說明。

1.1 符號說明

SKINNY算法：

ΔXr:第r輪S盒變換前的差分狀態(tài)，也是第r-1輪列混合變換后的差分狀態(tài)；

ΔYr:第r輪S盒變換后的差分狀態(tài)；

ΔZr:第r輪密鑰加和常數(shù)加變換后的差分狀態(tài)；

ΔWr:第r輪行移位操作后的差分狀態(tài)。

MANTIS算法：

ΔX:明文差分與白化密鑰異或后的初始差分狀態(tài)；

ΔX*:密文差分與白化密鑰異或后的差分狀態(tài)；

ΔXSBr，ΔXMCr-1:第r輪S盒變換后的差分狀態(tài)，也是第r-1輪列混合變換后的差分狀態(tài)；

ΔXKAr:第r輪密鑰加和常數(shù)加變換后的差分狀態(tài)；

ΔXPTr:第r輪P盒置換后的差分狀態(tài)。

1.2 SKINNY算法

當(dāng)分組規(guī)模為64 bit時，矩陣中的每一比特塊表示一個半字節(jié)，即s=4；分組規(guī)模為128 bit時，每一比特塊表示一個字節(jié)，即s=8。具體的表示形式如下所示。

SKINNY算法的設(shè)計沿用TWEAKEY算法中的設(shè)計思想，即其采用可調(diào)的密鑰輸入來替代單純的密鑰和一對可調(diào)密鑰。該算法根據(jù)分組規(guī)模n的不同，給出了三種不同的密鑰規(guī)模，即t=n，t=2n，t=3n。

表2 SKINNY算法分組、可調(diào)和輪數(shù)的對應(yīng)關(guān)系

算法的輪函數(shù)包括Subcells、AddConStants、AddRoundTweakey、ShiftRows、MixColumns這五個變換操作，下面將進行具體介紹。此外，本文中主要介紹SKINNY-n-n算法，對其余規(guī)模的SKINNY算法不再做具體描述。

S盒變換(Subcells) S盒變換是對輸入狀態(tài)的每一比特塊均進行操作，根據(jù)分組規(guī)模不同，其變換所用的S盒也不同。在這里，僅給出了4-bit S盒S4的具體表示，如表3所示，8-bit S盒S8的具體表示詳見文獻[1]。

表3 4-bit S盒S4

輪常數(shù)加(AddConStants) 通過一個6 bit的隨機數(shù)發(fā)生器生成輪常數(shù)，并將其賦值到一個4×4矩陣第一列的前三個比特塊，而后將初始狀態(tài)的第一列的前三個比特塊與之進行異或。

輪密鑰加(AddRoundTweakey) 實現(xiàn)輪密鑰的前兩列的值和相對應(yīng)位置的輸入狀態(tài)的值進行異或，輪密鑰由下面介紹的密鑰擴展算法生成，對于SKINNY-n-n算法，其輪密鑰為TKi=TK1i。

行移位(ShiftRows) 該步驟實現(xiàn)初始狀態(tài)第0行位置不改變，第1、2、3行分別循環(huán)右移1、2、3位，其逆運算SR-1也顯而易見。具體表示形式如下：

列混合(MixColumns) 使得初始狀態(tài)每一列與列混合矩陣做矩陣的乘法運算，達(dá)到混亂和擴散的目的。下面給出列混合矩陣。

相應(yīng)地，其逆運算MC-1所用的矩陣表示為：

密鑰擴展算法密鑰擴展算法具體生成過程如圖1所示。對于TK1，在每一圈中，提取前兩行的密鑰值作為該圈的輪可調(diào)密鑰，而后經(jīng)過PT置換操作改變密鑰比特塊的位置，得到下一圈可調(diào)密鑰的輸入值，其中，

PT=[9,15,8,13,10,14,12,11,0,1,2,3,4,5,6,7]。

TK1中不需要經(jīng)過線性反饋移位寄存器的操作，而TK2、TK3需要，這里不對TK2、TK3的生成過程進行詳細(xì)介紹，詳見文獻[1]。

圖1 SKINNY算法的密鑰擴展過程

1.3 MANTIS算法

Ri=MixColumns·PermuteCells·AddTweakeyTK·

AddConstants·SubCells

其中S盒變換、P盒置換以及列混合變換的采用與Midori算法相同，具體變換環(huán)節(jié)見文獻[1]，一輪結(jié)構(gòu)如圖2所示。

圖2 輪函數(shù)Ri和的結(jié)構(gòu)圖

在算法Rr和Rr+1的中間環(huán)節(jié)有一個大S盒，可以表示為S·M·S，其中S表示S盒變換，M表示列混合變換。在本文中，將除了輸入輸出端白化密鑰加變換外的其余部分稱為MANTISrcore，圖3以MANTIS7為例給出了具體算法結(jié)構(gòu)圖。

圖3 MANTIS算法的結(jié)構(gòu)示意圖，以MANTIS7為例

2 SKINNY算法的相關(guān)密鑰不可能差分區(qū)分器構(gòu)造

本節(jié)中首先具體介紹SKINNY算法輪函數(shù)以及密鑰擴展算法的相關(guān)性質(zhì)，而后依此構(gòu)造了13輪SKINNY-n-n算法的相關(guān)密鑰不可能差分區(qū)分器。構(gòu)造得到的區(qū)分器分為兩類，一類其輸入輸出狀態(tài)均僅有一個比特塊差分活動，另一類區(qū)分器在輸入狀態(tài)僅有一個差分活動塊時，其輸出狀態(tài)在同一列有三個比特塊差分活動，且這兩類區(qū)分器的每一類均有兩種等價情況，具體過程將在第2.2節(jié)中進行介紹。

2.1 SKINNY-n-n算法相關(guān)性質(zhì)

性質(zhì)1[5]在每一輪變換中，密鑰加變換可以和移位變換以及列混合變換操作交換順序，即將輸入狀態(tài)先進行移位變換以及列混合變換，而后將得到的狀態(tài)與該輪密鑰的等效密鑰進行異或，不改變運算結(jié)果。

性質(zhì)2若列混合變換MC的輸入狀態(tài)僅在第1或第3行存在1個比特塊活動差分，則輸出狀態(tài)僅有1個比特塊差分活動；反之，若列混合變換的逆變換的輸入狀態(tài)僅在第0或第4行存在1個比特塊的活動差分，則輸出狀態(tài)也僅有1個比特塊差分活動。

證明分析算法的列混合變換矩陣可得，矩陣僅在第1列和第3列有1個1，該兩列其余位置取0，則根據(jù)矩陣運算規(guī)則可得，輸入狀態(tài)若僅在第1行或第3行存在1個差分活動比特塊時，運算結(jié)果即輸出狀態(tài)定僅有1個比特塊差分活動；同理可得，其逆變換矩陣僅在第0列和第2列有1個1，該兩列其余位置取0，則輸入狀態(tài)若僅在第0行或第2行存在1個比特塊差分活動，此時輸出狀態(tài)也僅有1個比特塊差分活動。

證畢。

性質(zhì)3[5]在對SKINNY算法進行密鑰恢復(fù)攻擊時，由于算法列混合變換所用的矩陣不是MDS矩陣，不僅需要知道活動差分比特塊位置處的差分值，還需知道該位置比特塊的具體取值。因而不僅需要猜測活動差分比特塊位置處的密鑰值，對于部分差分值為0位置處的密鑰值也需進行猜測。

性質(zhì)4對于SKINNY-n-n算法，其密鑰擴展算法為一個16圈的循環(huán)。

證明根據(jù)SKINNY-n-n算法密鑰擴展方式中PT置換操作的運算規(guī)則有TKi+16=PT(TKi)，即構(gòu)成一個周期為16的循環(huán)。具體的各輪密鑰中各個位置處的密鑰與主密鑰的對應(yīng)關(guān)系見圖4。

圖4 SKINNY-n-n算法密鑰擴展方式的周期性

證畢。

性質(zhì)5[9](S盒性質(zhì))對于確定的S盒，隨機給定S盒的一對輸入輸出差分對應(yīng)時，則平均可以確定S盒的一對輸入輸出。

2.2 13輪相關(guān)密鑰不可能差分區(qū)分器

SKINNY算法使用較為簡單的密鑰擴展算法，并且在算法設(shè)計者對算法進行介紹時，分析得出不可能差分攻擊、相關(guān)密鑰攻擊對算法均有較好的攻擊效果，因此本文結(jié)合相關(guān)密鑰攻擊和不可能差分分析這兩種方法，對SKINNY算法進行了安全性分析?？紤]到要使得攻擊的輪數(shù)盡可能多，就須控制使得活動S盒的數(shù)目盡可能少。因此結(jié)合性質(zhì)2和性質(zhì)4，通過選取特定的明文差分，使得其與某一輪的相關(guān)可調(diào)密鑰差分進行抵消，則可以獲得較少的活動S盒，實現(xiàn)差分傳遞鏈盡可能地長。

本節(jié)中，通過對性質(zhì)2和性質(zhì)4的運用，找到了兩類長度為13輪的SKINNY-n-n算法的相關(guān)密鑰不可能差分區(qū)分器，與現(xiàn)有的分析結(jié)果相比，這兩類區(qū)分器是攻擊長度最長的區(qū)分器，下面對這兩類區(qū)分器進行介紹。

第一類區(qū)分器：這類區(qū)分器分為兩種情形，特點表現(xiàn)在其輸入輸出狀態(tài)均為僅有一個比特塊差分活動。第一種情形，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[3]處存在差分，輪密鑰僅在TK4[3]處存在差分，并且兩者差分值相等，均為0x1。則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[11]存在差分，且差分值為0x1是不可能的。第二種情形與第一種情形相似，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[0]處存在差分，主密鑰僅在TK[7]即輪密鑰TK4[0]處存在差分，且ΔY4[0]=ΔTK4[0]=0x1。則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[8]=0x1是不可能的。

第二類區(qū)分器：這類區(qū)分器同樣也是兩種情形，但與第一類區(qū)分器不同的是，該類區(qū)分器在輸入狀態(tài)僅有一個差分活動塊時，其輸出狀態(tài)在同一列有三個比特塊差分活動。第一種情形中，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[1]處存在差分，輪密鑰僅在TK4[1]處存在差分，并且兩者差分值相等，均為0x1。則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[3,7,15]差分活動是不可能的。第二種情形與第一種情形相似，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[2]處存在差分，輪密鑰僅在TK4[2]處存在差分，且ΔY4[2]=ΔTK4[2]=0x1，則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[1,5,13]差分活動是不可能的。

上述兩類區(qū)分器均可以用來進行對SKINNY-n-n算法進行相關(guān)密鑰不可能差分分析，但運用第一類區(qū)分器進行攻擊所需的復(fù)雜度與第二類區(qū)分器相比較少，因此下文中主要運用第一類區(qū)分器的第一種情形，給出SKINNY-n-n算法的密鑰恢復(fù)攻擊結(jié)果，如圖5(a)所示。圖5中(a)、(b)分別表示第一類和第二類區(qū)分器中的第一種情形，分別記為區(qū)分器1.1和區(qū)分器2.1。

3 19輪SKINNY-n-n算法的相關(guān)密鑰不可能差分攻擊

本節(jié)中首先介紹基于區(qū)分器1.1對SKINNY-64-64進行相關(guān)密鑰不可能差分攻擊的具體過程，而后類似地給出對SKINNY-128-128的安全性分析結(jié)果。攻擊總共分為兩個部分：數(shù)據(jù)收集階段以及密鑰恢復(fù)階段，其中，數(shù)據(jù)收集部分由兩個步驟構(gòu)成，密鑰恢復(fù)階段由7個步驟構(gòu)成。

3.1 SKINNY-64-64算法的相關(guān)密鑰不可能差分分析

(1)構(gòu)造明文結(jié)構(gòu)，使得每個明文結(jié)構(gòu)由216個明文構(gòu)造而成，其中，在第(5,7,10,13)個半字節(jié)遍歷所有的可能值，其余位置取定值，則使得每個明文結(jié)構(gòu)產(chǎn)生的231個明文對滿足對應(yīng)的輸入差分ΔP=(0,0,0,0,0,*,0,*,0,0,*,0,0,*,0,0)。

(2)在ΔTK=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x1,0)的條件下加密明文對，得到相應(yīng)的密文對，篩選出密文在ΔW19=[2,4,5,7,10,11,13,15]差分值為0，其余位置差分活動，取值不確定的明文，選擇2n個這樣的明文結(jié)構(gòu)，則攻擊所需的明文量為2n+16，得到的對應(yīng)明文對2n+31×2-32=2n-1個。

(3)計算得到TK19[1,5]，猜測密鑰TK19[6]；首先，篩選ΔX19[10]=0x1的明文對，予以保留，此時平均剩余明文對個數(shù)為2n-1×2-4=2n-5；而后，由已知ΔY19[9,13]以及Y19[9,13]的值，可計算得ΔX19[9,13]和X19[9,13]，又由ΔX19[1,5,13]有相同的差分值，則根據(jù)已知ΔY19[1,5]以及性質(zhì)5，可確定X19[1,5]和Y19[1,5]的值，再由已知Z19[1,5]、TK19[1,5]=Y19[1,5]⊕W19[1,6]和W18[1]=M-1°X19[5]可計算出TK19[1,5]、ΔW18[1]以及W18[1]的值；而后猜測TK19[6]，計算得Y19[6]，通過S盒的逆運算可得X19[6]；由已知ΔX19[10]=0x1、ΔY19[10]以及Y19[10,14]，利用性質(zhì)5和S盒的逆運算可得X19[10,14]，進而基于W18[6]=M-1°X19[6,10,14]可計算得W18[6]；最后，由已知ΔY19[11,15]以及Y19[11,15]，篩選ΔX19[11]=ΔX19[15]的明文對，予以保留；則該步驟后，平均剩余明文對的個數(shù)為2n-5×2-4=2n-9。

圖5 13輪相關(guān)密鑰不可能差分區(qū)分器

(4)計算TK19[3]，猜測密鑰TK19[7]；在步驟(3)基礎(chǔ)上，已知ΔX19[3]=ΔX19[15]和ΔY19[3]，利用性質(zhì)5，可確定X19[3]和Y19[3]的值，再由已知Z19[3]可計算出密鑰TK19[3]=Y19[3]⊕Z19[3]；猜測密鑰TK19[7]，計算得Y19[7]，再由已知Y19[15]，則根據(jù)S盒的逆運算可得X19[7,15]，利用W18[11]=M-1°X19[7,15]可計算得ΔW18[11]以及W18[11]的值，則該步驟后，平均剩余明文對的個數(shù)仍為2n-9。

(5)猜測密鑰TK19[0]；可計算得到ΔY19[0]以及Y19[0]的值，進而可得ΔX19[0]以及X19[0]的值，再由已知Y19[12]，根據(jù)S盒的逆運算可得X19[12]，利用W18[12]=M-1°X19[0,12]可得ΔW18[12]以及W18[12]的值，則該步驟后，平均剩余明文對的個數(shù)仍為2n-9。

(6)猜測密鑰TK18[5]，計算TK18[1]；由步驟(3)～(5)，已計算得ΔW18[1,6,11,12]和W18[1,6,11,12]，進而可求得ΔY18[1,9,13]和Y18[9,13]，利用S盒逆運算，可計算出ΔX18[9,13]，篩選ΔX18[9]=ΔX18[13]的明文對予以保留，則此時平均剩余明文對個數(shù)為2n-9×2-4=2n-13；進一步由于ΔX18[1]=ΔX18[9]=ΔX18[13]，利用性質(zhì)5可確定X18[1]和Y18[1]，即計算得TK18[1]=Y18[1]⊕W18[1]；在此基礎(chǔ)上，對密鑰TK18[5]進行猜測，基于W17[9]=M-1°X[5,13]，確定ΔW17[9]以及W17[9]，再進行一輪解密，篩選滿足ΔX17[11]=0x1的明文對予以保留，則該步驟后，平均剩余明文對的個數(shù)為2n-13×2-4=2n-17。

(8)猜測密鑰TK2[0,3,4]；在步驟(7)基礎(chǔ)上，猜測TK2[0,3,4]，計算得到Z2[0,3,4,10,11,13]的具體值，其中由X3[12]=M°W2[0,8,12]=M°Z2[0,10,13]可求得ΔX3[12]以及X3[12]的值，根據(jù)Z2[3]和Z2[4,11]可分別求得X3[3]和X3[9]的值，則該步驟后，平均剩余明文對的個數(shù)為2n-29。

(9)由步驟(4)已得TK19[3]，根據(jù)密鑰擴展的對應(yīng)關(guān)系，即已知TK3[3]，在步驟(8)基礎(chǔ)上，計算得ΔZ3[12]以及Z3[3,9,12]的值，進而計算并驗證ΔY4[3]=0x1是否成立。若此時仍有明文對通過驗證，則說明猜測的密鑰錯誤，將其放入錯誤密鑰候選密鑰集。余下的未猜測的16 bit密鑰選取一個明密文對進行驗證。具體的攻擊路徑如圖6所示。

圖6 19輪相關(guān)密鑰不可能差分攻擊路徑

其中灰色表示活動比特塊，白色表示差分為0的比特塊，？表示差分值不確定的比特塊，差分值為0x1的密鑰比特塊和狀態(tài)比特塊用黑色表示，條形狀表示除具有差分的密鑰比特塊外的其余需猜測的密鑰比特塊。攻擊所需的復(fù)雜度由定理1給出。

定理1根據(jù)此攻擊，可以恢復(fù)出SKINNY-64-64算法的全部密鑰比特，攻擊所需的數(shù)據(jù)復(fù)雜度為255個選擇明文，時間復(fù)雜度為240.82次19輪SKINNY-64-64加密，存儲復(fù)雜度為248。

證明攻擊所需的復(fù)雜度主要分為數(shù)據(jù)復(fù)雜度、時間復(fù)雜度以及存儲復(fù)雜度三部分。數(shù)據(jù)復(fù)雜度方面，主要由步驟(2)決定，所需選擇明文量為2n+16，即數(shù)據(jù)復(fù)雜度為2n+16個選擇明文。時間復(fù)雜度主要集中在密鑰恢復(fù)階段，下面對各步驟所需的時間復(fù)雜度進行具體分析。

在步驟(3)中，首先篩選明文對，而后計算得到TK19[1,5]，并對TK19[6]進行猜測，篩選保留符合條件的明文對，則所需的計算復(fù)雜度為2n-5×24×2=2n；

在步驟(4)中，根據(jù)步驟(3)操作后剩余的2n-9個明文對，首先計算得到TK19[3]，然后猜測密鑰TK19[7]，所需的計算復(fù)雜度為2n-9×28×2=2n；

在步驟(5)中，根據(jù)步驟(4)操作后操作后剩余的2n-9個明文對，對密鑰TK19[0]進行猜測，所需的計算復(fù)雜度為2n-9×212×2=2n+4；

在步驟(6)中，首先篩選保留滿足ΔX18[9]=ΔX18[13]的明文對，計算出密鑰TK18[1]，而后猜測密鑰TK18[5]，所需的計算復(fù)雜度為2n-13×216×2=2n+4；

在步驟(8)中，根據(jù)步驟(7)中剩余的2n-29個明文對，猜測密鑰TK2[0,3,4]，所需的計算復(fù)雜度為2n-29×232×2=2n+4；

在步驟(9)中，已知密鑰TK3[3]，計算并驗證ΔY5[3]=0x1是否成立，若驗證滿足，仍有明文對通過檢驗，則說明之前的猜測錯誤。一個錯誤猜測無法通過檢測的概率為(1-2-4)2n-29，此時已對TK19[0,1,3,5,6,7]，TK18[1,5]，TK1[0]和TK2[0,3,4]共48 bit密鑰進行了計算和猜測，要使錯誤密鑰剩余的明文對足夠少，即有N=248×(1-2-4)2n-29≤1，得n≈39，該步驟得計算復(fù)雜度為2n-29×232×2=2n+4。總計，攻擊所需的計算復(fù)雜度為：

綜上可得，攻擊所需的數(shù)據(jù)復(fù)雜度為255個選擇明文，計算復(fù)雜度為240.82次19輪SKINNY-64-64加密，存儲復(fù)雜度主要在于存儲明文結(jié)構(gòu)及錯誤密鑰，則所需的存儲復(fù)雜度為248。

證畢。

3.2 SKINNY-128-128算法的相關(guān)密鑰不可能差分分析

上面介紹了運用第2.2節(jié)構(gòu)造得到的13輪相關(guān)密鑰不可能差分區(qū)分器對SKINNY-64-64實施攻擊的具體過程。同樣地，該攻擊步驟對于SKINNY-128-128算法也適用，但由于在這兩種密鑰規(guī)模的SKINNY算法中每一比特塊對應(yīng)的比特數(shù)一個為4，另一個為8，因此在攻擊選擇明文量、每一步驟操作后剩余明文對數(shù)目以及攻擊所需復(fù)雜度方面，二者有較大不同。所以，在這里，不再贅述針對SKINNY-128-128在密鑰恢復(fù)階段的具體攻擊步驟，只介紹每一步驟后剩余的明文對數(shù)目以及恢復(fù)的密鑰比特，并分析攻擊所需復(fù)雜度。

與第3.1小節(jié)的攻擊類似，在數(shù)據(jù)收集階段，每個明文結(jié)構(gòu)由232個明文構(gòu)造而成，即其在第(5,7,10,13)個字節(jié)遍歷所有的可能值，其余位置取定值，選擇初始密鑰在ΔTK=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x1,0)的條件下加密明文對，得到相應(yīng)的密文對，篩選出密文在ΔW20[2,4,5,7,10,11,13,15]差分值為0，其余位置差分活動，取值不確定的明文，則選擇2n個這樣的明文結(jié)構(gòu)，得到的對應(yīng)明文對2n+63×2-64=2n-1個，即攻擊所需的明文量為2n+32。下面通過表4介紹密鑰恢復(fù)階段每一步驟的具體情況，攻擊所需復(fù)雜度由定理2給出。

表4 SKINNY-128-128密鑰恢復(fù)階段的具體情況

定理2根據(jù)此攻擊，可以恢復(fù)出SKINNY-128-128算法得全部密鑰比特，攻擊所需的數(shù)據(jù)復(fù)雜度為2104個選擇明文，時間復(fù)雜度為277.76次19輪SKINNY-128-128加密，存儲復(fù)雜度為296。

證明同定理1證明類似，攻擊所需的復(fù)雜度主要分為數(shù)據(jù)、時間以及存儲復(fù)雜度三部分。數(shù)據(jù)復(fù)雜度方面，同樣地主要由步驟(2)決定，所需選擇明文量為2n+32，即數(shù)據(jù)復(fù)雜度為2n+32個選擇明文。時間復(fù)雜度主要集中在密鑰恢復(fù)階段，下面簡要分析介紹各步驟所需的時間復(fù)雜度。

步驟(3)所需的計算復(fù)雜度為2n-9×28×2=2n；步驟(4)所需的計算復(fù)雜度為2n-17×216×2=2n；步驟(5)所需的計算復(fù)雜度為2n-17×224×2=2n+8；步驟(6)所需的計算復(fù)雜度為2n-25×232×2=2n+8；步驟(7)所需的計算復(fù)雜度為2n-41×240×2=2n；步驟(8)所需的計算復(fù)雜度為2n-57×264×2=2n+8；在步驟(9)中，一個錯誤猜測無法通過檢測的概率為(1-2-8)2n-57，要使錯誤密鑰剩余的明文對足夠少，即有N=296×(1-2-8)2n-57≤1，得n≈72，該步驟得計算復(fù)雜度為2n-57×264×2=2n+8。總計，攻擊所需的計算復(fù)雜度為：

綜上可得，攻擊所需的數(shù)據(jù)復(fù)雜度為2104個選擇明文，計算復(fù)雜度為277.76次19輪SKINNY-128-128加密，存儲復(fù)雜度為296。

證畢。

4 MANTIS算法的相關(guān)密鑰差分特征

在本節(jié)中，通過分析MANTIS算法的結(jié)構(gòu)特性，利用相關(guān)密鑰分析技術(shù)，結(jié)合差分類分析方法，找到了可用于對該算法進行安全性分析的幾類高概率相關(guān)密鑰差分類區(qū)分器。首先，與PRINCE算法[10]類似，介紹基于算法α映射的性質(zhì)，得到的一種針對全輪MANTIS算法的平凡的相關(guān)密鑰差分特征；而后，根據(jù)找到的一類特殊的一輪循環(huán)區(qū)分器，構(gòu)造出了一類針對MANTISrcore的相關(guān)密鑰矩陣攻擊區(qū)分器，其中1≤r≤6；最后，通過選取特殊的可調(diào)差分，構(gòu)造得到了針對MANTIS5可進行實際攻擊的一種改進的相關(guān)密鑰差分特征。

4.1 基于α映射的平凡相關(guān)密鑰差分特征

其中，X1、X2表示P1、P2經(jīng)過白化密鑰后的MANTIScore的輸入，Y1、Y2表示C1、C2經(jīng)過白化密鑰逆運算后的MANTIScore的輸出。

圖7 基于α映射的平凡相關(guān)密鑰差分

4.2 針對MANTISr core的相關(guān)密鑰矩陣攻擊區(qū)分器

通過分析算法的結(jié)構(gòu)特性可得，要想使得對算法進行攻擊的輪數(shù)足夠多，則就需要使得活動差分比特塊的數(shù)量足夠少。基于此思想，將MANTISrcore分為E0和E1兩部分，其中E0表示MANTISrcore的前r-1輪，E1表示MANTISrcore的剩余加密環(huán)節(jié)。通過對E0、E1分別找到一條高概率的差分路徑，兩者結(jié)合，從而構(gòu)造得到了一類針對MANTISrcore的相關(guān)密鑰矩陣攻擊區(qū)分器。

定理3通過將算法分為E0和E1兩部分，構(gòu)造得到了一類針對MANTISrcore的相關(guān)密鑰矩陣攻擊區(qū)分器，區(qū)分器概率為2-8r-12.36，其中r≤6。

證明對于E0部分，主要使用的是一種特殊的一輪區(qū)分器，對其迭代r-1輪，得到E0的一條高概率差分路徑。首先根據(jù)算法S盒變換的差分分布表，選取進行一輪S盒變換時，輸入輸出在具有相同差分時，其概率達(dá)到S盒的最大概率2-2的差分值。經(jīng)過篩選，得到候選的差分值為{0xa,0xb,0xe,0xf}。在這里，為了使得E1部分的概率最大，選取輸入的差分值為0xa。此外，考慮使用的相關(guān)密鑰差分比特塊較少，選定明文輸入差分僅在第1個半字節(jié)存在，即ΔX=(0,0xa,0,0,0,0,0,0,0,0,0,0,0,0,0,0)。而后，選取密鑰差分，使得經(jīng)過PT變換和列混合變換后的輸出ΔXMC=ΔX=(0,0xa,0,0,0,0,0,0,0,0,0,0,0,0,0,0)。在這里，選取Δk=(0,0,0,0,0xa,0,0,0,0,0,0,0,0,0,0xa,0)，由此構(gòu)造得到了可用于迭代的一輪區(qū)分器，且該區(qū)分器的概率為2-2。將此區(qū)分器再向下迭代r-2輪，即得到了E0的一條概率為2-2(r-1)差分路徑，具體一輪區(qū)分器如圖8所示。

圖8 E0部分的一輪區(qū)分器

E1部分，主要由第r輪、中間環(huán)節(jié)大S盒以及后r輪組成，每一輪均使用相同的相關(guān)密鑰，即Δk=(0,0,0,0,0xa,0,0,0,0,0,0,0,0,0,0xa,0)。第r輪與部分的區(qū)分器結(jié)構(gòu)相似，所不同的是使得其經(jīng)過S盒變換的輸入與輸出差分值不同，即輸入差分為0xa，輸出差分ΔXSBr∈{0x5,0xd,0xf}，其中任一種概率均為2-2。選取S盒的輸出差分為其中任一種情況，則在經(jīng)過一輪變換后的狀態(tài)ΔXMCr在第(1,9,13)個半字節(jié)存在差分，也就是ΔXMCr=(0,*,0,0,0,0,0,0,0,t,0,0,0,t,0,0)，其中*∈{0x5,0xd,0xf},t=*⊕0xa。對于后r輪的第一輪，采用與第r輪同樣的方法，使得其經(jīng)過S盒變換后的輸出差分為0xa，但輸入差分ΔXSBr∈{0x5,0xd,0xf}，其中任一種情況的概率也為2-2，則經(jīng)過密鑰加變換和PT變換的逆變換后的狀態(tài)ΔXPTr在第(5,9,13)個半字節(jié)存在差分，即：

ΔXPTr=(0,0,0,0,0,*,0,0,0,0xa,0,0,0,0xa,0,0)

其中*∈{0x5,0xd,0xf}。余下的r-1輪與前r-1輪相同，均采用一輪區(qū)分器進行r-1輪迭代。所以當(dāng)大S盒的輸入為

ΔXMCr=(0,*,0,0,0,0,0,0,0,t,0,0,0,t,0,0)

輸出為ΔXPTr=(0,0,0,0,0,*,0,0,0,0xa,0,0,0,0xa,0,0)。通過編程實驗驗證，當(dāng)且僅當(dāng)大S盒輸入輸出中*的取值相同時，差分路徑才能成立，且所求得概率在取不同的*值時，也不全相同。當(dāng)*=0x5、0xf時，大S盒以及其前后兩輪差分路徑成立的概率均為2-2×2-7.41×2-2；當(dāng)*=0xd時，路徑成立概率為2-2×2-9×2-2。所以進行求和可得該路徑成立的最終概率為2-10.18，余下的利用一輪區(qū)分器迭代r-1輪的概率為2-2(r-1)。則E1部分的該差分路徑概率為2-10.18×2-2(r-1)=2-8.18-2r。

綜上，利用E0部分和E1部分的兩條高概率差分路徑，可以構(gòu)造得到一類針對MANTISrcore的相關(guān)密鑰矩陣區(qū)分器。該區(qū)分器的概率為(2-2(r-1)×2-8.18-2r)2=2-8r-12.36。又有算法分組規(guī)模為264，因此要使得2-8r-12.36>2-64，則1≤r≤6。圖9給出了具體的相關(guān)密鑰矩陣區(qū)分器的示意圖。

證畢。

圖9 MANTISr core的相關(guān)密鑰矩陣攻擊區(qū)分器

4.3 MANTIS5的改進相關(guān)密鑰差分特征

在文獻[8]中提出了一種針對MANTIS5的實際密鑰恢復(fù)攻擊。其主要利用密鑰擴展算法中的可調(diào)密鑰，給出了算法的一類相關(guān)密鑰截斷差分區(qū)分器，并使得該特征的概率與設(shè)計者提出的最優(yōu)差分概率相匹配，即最優(yōu)差分概率2-34×2=2-68。而本小節(jié)中，利用在特定位置選取相同的密鑰差分和可調(diào)差分，構(gòu)造得到了一種改進的相關(guān)密鑰差分特征，提高了差分概率。

在這里，選取密鑰k1在第4個半字節(jié)存在差分，且差分值為0xa，初始可調(diào)ΔT在第14個半字節(jié)存在差分值為0xa的差分。則由圖9可得，觀察差分特征在第3輪的狀態(tài)，使得經(jīng)過第3輪S盒變換后狀態(tài)為

ΔXSB3=(0xa,0,0,0,0xa,0,0,0,0,0,0,0,0,0,0,0)

此時密鑰差分為

Δk1⊕Δh3(T)=(0xa,0,0,0,0xa,0,0,0,0,0,0,0,0,0,0,0)

剛好差分抵消，再進行下一輪。在第4輪變換中，密鑰差分與可調(diào)差分存在的位置相同，差分同樣也相互抵消。因此，直到第5輪的密鑰加變換后的狀態(tài)存在差分，即:

ΔXKA5=(0,0,0,0,0xa,0,0,0,0,0,0,0xa,0,0,0,0)。

而后再進行接下來的輪變換。得到大S盒變換后的狀態(tài)與ΔXMC5的狀態(tài)相同。根據(jù)算法的FX結(jié)構(gòu)性質(zhì)，類似地可對第6～8輪進行相同構(gòu)造。差分路徑如圖10所示。

根據(jù)編程驗證，上述步驟較文獻[8]中構(gòu)造的區(qū)分器概率由2-40.51提高到了2-28.35，具體的每一輪的差分概率在此進行具體介紹。在第1輪輸入狀態(tài)選取明文差分，使得其經(jīng)過初始密鑰變換后的狀態(tài)為

ΔP′=(*,0,*,*,*,0,0,0,0,0,*,0,*,0,0,0),*∈{0x5,0xa,0xd,0xf}，則經(jīng)過S盒變換得到

ΔXSB1=(*,0,0xa,*,0xa,0,0,0,0,0,*,0,*,0,0,0),*∈{0xa,0xf},且ΔXSB1[0]=ΔXSB1[10]、ΔXSB1[3]=ΔXSB1[12]，其中該輪的概率為

在第2輪S盒變換的輸入由第一輪可得，即

ΔXMC1=(*,0,0,0,*,0,*,0,0,0,*,0,0,0,0,0),*∈{0xa,0xf},

圖10 MANTIS5相關(guān)密鑰差分特征

同一列的兩比特塊差分值相同。則變換后的狀態(tài)為使得其在第4、6個半字節(jié)差分值為0xa，第0、10半字節(jié)差分值相同，且取值屬于{0xa,0xf}，則該輪的概率為2-2×2×(2-4+2-4)=2-7。第3輪變換中，當(dāng)S盒輸入差分為0xa或0xf時，得到輸出差分為0xa的概率為2-2，因而第3輪變換的概率為2-4。大S盒的概率同樣也為2-4，后5輪變換的概率計算與前5輪類似。綜上，該區(qū)分器的概率為2-11.35×2-7×2-4×2-4×2-2=2-28.35。

從而根據(jù)上述步驟得到了針對MANTIS5的一類改進相關(guān)密鑰差分特征。進一步地，將MANTIS5的區(qū)分器分別拓展1輪或2輪，即可得到對于MANTIS6和MANTIS7的相關(guān)密鑰差分特征。

5 結(jié)論

本文首先通過分析SKINNY算法的密鑰擴展方式的Tweakey結(jié)構(gòu)特性以及算法擴散層的結(jié)構(gòu)特點，構(gòu)造了SKINNY-n-n算法的兩類13輪相關(guān)密鑰不可能差分區(qū)分器，并據(jù)此給出了對19輪SKINNY-n-n算法的安全性分析結(jié)果。其中，對于SKINNY-64-64算法，攻擊所需的數(shù)據(jù)復(fù)雜度為255，時間復(fù)雜度為240.82，存儲復(fù)雜度為248。對于SKINNY-128-128算法，攻擊所需的數(shù)據(jù)復(fù)雜度、時間復(fù)雜度以及存儲復(fù)雜度分別為2104、277.76和296。而后，針對SKINNY算法族中的低延遲變體MANTIS系列算法，分別給出了設(shè)計者提出的基于α映射一類平凡相關(guān)密鑰差分特征、對于MANTISr core(1≤r≤6)的相關(guān)密鑰矩陣區(qū)分器、對于MANTIS5的一類改進相關(guān)密鑰截斷差分路徑，豐富了對于MANTIS系列算法的安全性分析結(jié)果。