SKINNY-n-n算法和MANTIS算法的相關(guān)密鑰分析*

石淑英，何 駿

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

0 引言

SKINNY算法族是由BEIERLE C等人[1]在CRYPTO 2016上提出的一個(gè)可調(diào)輕量級(jí)分組密碼算法族，主要目的是為了設(shè)計(jì)出一種軟硬件實(shí)現(xiàn)都非常高效，并且性能能夠比NSA提出的候選算法SIMON更好的輕量級(jí)分組密碼算法。此外，設(shè)計(jì)者也提出了SKINNY算法的一種低延遲的變體MANTIS算法，與SPECK算法進(jìn)行性能對(duì)比，安全性分析結(jié)果對(duì)比情況見表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è)計(jì)者證明了該算法族對(duì)已知的分組密碼攻擊方法例如差分/線性分析、不可能差分分析、相關(guān)密鑰分析等有較強(qiáng)的安全性。

MANTIS算法基于PRINCE算法進(jìn)行改進(jìn)，即該算法基本結(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è)計(jì)者認(rèn)為該步驟能有效提高算法安全性。在算法實(shí)現(xiàn)方面，其具有低延遲和易于硬件實(shí)現(xiàn)的優(yōu)點(diǎn)。

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

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

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

本文中，針對(duì)SKINNY-n-n算法，首先通過分析算法的結(jié)構(gòu)特性，給出了兩類長度為13輪的相關(guān)密鑰不可能差分區(qū)分器，而后據(jù)其中的一種區(qū)分器，對(duì)算法進(jìn)行了19輪的相關(guān)密鑰不可能差分分析。針對(duì)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é)中，運(yùn)用第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)，并對(duì)文中所用到的具體符號(hào)進(jìn)行解釋說明。

1.1 符號(hào)說明

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時(shí)，矩陣中的每一比特塊表示一個(gè)半字節(jié)，即s=4；分組規(guī)模為128 bit時(shí)，每一比特塊表示一個(gè)字節(jié)，即s=8。具體的表示形式如下所示。

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

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

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

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

表3 4-bit S盒S4

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

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

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

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

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

密鑰擴(kuò)展算法密鑰擴(kuò)展算法具體生成過程如圖1所示。對(duì)于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需要，這里不對(duì)TK2、TK3的生成過程進(jìn)行詳細(xì)介紹，詳見文獻(xiàn)[1]。

圖1 SKINNY算法的密鑰擴(kuò)展過程

1.3 MANTIS算法

Ri=MixColumns·PermuteCells·AddTweakeyTK·

AddConstants·SubCells

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

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

在算法Rr和Rr+1的中間環(huán)節(jié)有一個(gè)大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ù)以及密鑰擴(kuò)展算法的相關(guān)性質(zhì)，而后依此構(gòu)造了13輪SKINNY-n-n算法的相關(guān)密鑰不可能差分區(qū)分器。構(gòu)造得到的區(qū)分器分為兩類，一類其輸入輸出狀態(tài)均僅有一個(gè)比特塊差分活動(dòng)，另一類區(qū)分器在輸入狀態(tài)僅有一個(gè)差分活動(dòng)塊時(shí)，其輸出狀態(tài)在同一列有三個(gè)比特塊差分活動(dòng)，且這兩類區(qū)分器的每一類均有兩種等價(jià)情況，具體過程將在第2.2節(jié)中進(jìn)行介紹。

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

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

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

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

證畢。

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

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

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

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

證畢。

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

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

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

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

第一類區(qū)分器：這類區(qū)分器分為兩種情形，特點(diǎn)表現(xiàn)在其輸入輸出狀態(tài)均為僅有一個(gè)比特塊差分活動(dòng)。第一種情形，選取區(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)僅有一個(gè)差分活動(dòng)塊時(shí)，其輸出狀態(tài)在同一列有三個(gè)比特塊差分活動(dòng)。第一種情形中，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[1]處存在差分，輪密鑰僅在TK4[1]處存在差分，并且兩者差分值相等，均為0x1。則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[3,7,15]差分活動(dòng)是不可能的。第二種情形與第一種情形相似，選取區(qū)分器的輸入狀態(tài)僅在ΔY4[2]處存在差分，輪密鑰僅在TK4[2]處存在差分，且ΔY4[2]=ΔTK4[2]=0x1，則其在經(jīng)過13輪加密后，得到的輸出狀態(tài)僅在ΔY17[1,5,13]差分活動(dòng)是不可能的。

上述兩類區(qū)分器均可以用來進(jìn)行對(duì)SKINNY-n-n算法進(jìn)行相關(guān)密鑰不可能差分分析，但運(yùn)用第一類區(qū)分器進(jìn)行攻擊所需的復(fù)雜度與第二類區(qū)分器相比較少，因此下文中主要運(yùn)用第一類區(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對(duì)SKINNY-64-64進(jìn)行相關(guān)密鑰不可能差分攻擊的具體過程，而后類似地給出對(duì)SKINNY-128-128的安全性分析結(jié)果。攻擊總共分為兩個(gè)部分：數(shù)據(jù)收集階段以及密鑰恢復(fù)階段，其中，數(shù)據(jù)收集部分由兩個(gè)步驟構(gòu)成，密鑰恢復(fù)階段由7個(gè)步驟構(gòu)成。

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

(1)構(gòu)造明文結(jié)構(gòu)，使得每個(gè)明文結(jié)構(gòu)由216個(gè)明文構(gòu)造而成，其中，在第(5,7,10,13)個(gè)半字節(jié)遍歷所有的可能值，其余位置取定值，則使得每個(gè)明文結(jié)構(gòu)產(chǎn)生的231個(gè)明文對(duì)滿足對(duì)應(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)的條件下加密明文對(duì)，得到相應(yīng)的密文對(duì)，篩選出密文在ΔW19=[2,4,5,7,10,11,13,15]差分值為0，其余位置差分活動(dòng)，取值不確定的明文，選擇2n個(gè)這樣的明文結(jié)構(gòu)，則攻擊所需的明文量為2n+16，得到的對(duì)應(yīng)明文對(duì)2n+31×2-32=2n-1個(gè)。

(3)計(jì)算得到TK19[1,5]，猜測(cè)密鑰TK19[6]；首先，篩選ΔX19[10]=0x1的明文對(duì)，予以保留，此時(shí)平均剩余明文對(duì)個(gè)數(shù)為2n-1×2-4=2n-5；而后，由已知ΔY19[9,13]以及Y19[9,13]的值，可計(jì)算得Δ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]可計(jì)算出TK19[1,5]、ΔW18[1]以及W18[1]的值；而后猜測(cè)TK19[6]，計(jì)算得Y19[6]，通過S盒的逆運(yùn)算可得X19[6]；由已知ΔX19[10]=0x1、ΔY19[10]以及Y19[10,14]，利用性質(zhì)5和S盒的逆運(yùn)算可得X19[10,14]，進(jìn)而基于W18[6]=M-1°X19[6,10,14]可計(jì)算得W18[6]；最后，由已知ΔY19[11,15]以及Y19[11,15]，篩選ΔX19[11]=ΔX19[15]的明文對(duì)，予以保留；則該步驟后，平均剩余明文對(duì)的個(gè)數(shù)為2n-5×2-4=2n-9。

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

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

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

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

(8)猜測(cè)密鑰TK2[0,3,4]；在步驟(7)基礎(chǔ)上，猜測(cè)TK2[0,3,4]，計(jì)算得到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]的值，則該步驟后，平均剩余明文對(duì)的個(gè)數(shù)為2n-29。

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

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

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

證明對(duì)于E0部分，主要使用的是一種特殊的一輪區(qū)分器，對(duì)其迭代r-1輪，得到E0的一條高概率差分路徑。首先根據(jù)算法S盒變換的差分分布表，選取進(jìn)行一輪S盒變換時(shí)，輸入輸出在具有相同差分時(shí)，其概率達(dá)到S盒的最大概率2-2的差分值。經(jīng)過篩選，得到候選的差分值為{0xa,0xb,0xe,0xf}。在這里，為了使得E1部分的概率最大，選取輸入的差分值為0xa。此外，考慮使用的相關(guān)密鑰差分比特塊較少，選定明文輸入差分僅在第1個(gè)半字節(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)個(gè)半字節(jié)存在差分，也就是ΔXMCr=(0,*,0,0,0,0,0,0,0,t,0,0,0,t,0,0)，其中*∈{0x5,0xd,0xf},t=*⊕0xa。對(duì)于后r輪的第一輪，采用與第r輪同樣的方法，使得其經(jīng)過S盒變換后的輸出差分為0xa，但輸入差分ΔXSBr∈{0x5,0xd,0xf}，其中任一種情況的概率也為2-2，則經(jīng)過密鑰加變換和PT變換的逆變換后的狀態(tài)ΔXPTr在第(5,9,13)個(gè)半字節(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ū)分器進(jìn)行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)。通過編程實(shí)驗(yàn)驗(yàn)證，當(dāng)且僅當(dāng)大S盒輸入輸出中*的取值相同時(shí)，差分路徑才能成立，且所求得概率在取不同的*值時(shí)，也不全相同。當(dāng)*=0x5、0xf時(shí)，大S盒以及其前后兩輪差分路徑成立的概率均為2-2×2-7.41×2-2；當(dāng)*=0xd時(shí)，路徑成立概率為2-2×2-9×2-2。所以進(jìn)行求和可得該路徑成立的最終概率為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)造得到一類針對(duì)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的改進(jìn)相關(guān)密鑰差分特征

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

在這里，選取密鑰k1在第4個(gè)半字節(jié)存在差分，且差分值為0xa，初始可調(diào)ΔT在第14個(gè)半字節(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)

此時(shí)密鑰差分為

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

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

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

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

根據(jù)編程驗(yàn)證，上述步驟較文獻(xiàn)[8]中構(gòu)造的區(qū)分器概率由2-40.51提高到了2-28.35，具體的每一輪的差分概率在此進(jìn)行具體介紹。在第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個(gè)半字節(jié)差分值為0xa，第0、10半字節(jié)差分值相同，且取值屬于{0xa,0xf}，則該輪的概率為2-2×2×(2-4+2-4)=2-7。第3輪變換中，當(dāng)S盒輸入差分為0xa或0xf時(shí)，得到輸出差分為0xa的概率為2-2，因而第3輪變換的概率為2-4。大S盒的概率同樣也為2-4，后5輪變換的概率計(jì)算與前5輪類似。綜上，該區(qū)分器的概率為2-11.35×2-7×2-4×2-4×2-2=2-28.35。

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

5 結(jié)論

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