TWINE 算法的相關(guān)密鑰不可能飛來(lái)去器攻擊

謝敏，田峰，李嘉琪

（西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071）

1 引言

隨著電子信息技術(shù)的迅猛發(fā)展，物聯(lián)網(wǎng)、射頻識(shí)別等技術(shù)被廣泛應(yīng)用，這使適用于資源受限設(shè)備的輕量級(jí)分組密碼迅速成為研究熱點(diǎn)。與傳統(tǒng)分組密碼相比，輕量級(jí)分組密碼具有占用資源少、功耗低、效率高和易于實(shí)現(xiàn)等優(yōu)勢(shì)。從早期的HIGHT[1]、PRESENT[2]和MIBS[3]，到后來(lái)的LBlock[4]、PRINCE[5]和 Piccolo[6]等多種算法的提出，輕量級(jí)分組密碼設(shè)計(jì)和分析的發(fā)展已經(jīng)愈顯成熟。

TWINE 分組密碼算法是Suzaki 等[7]在Selected Areas in Cryptography 2012 上提出的一種輕量級(jí)分組密碼算法，可以在計(jì)算資源受限的硬件和微型控制器上實(shí)現(xiàn)。TWINE 分組密碼算法的設(shè)計(jì)采用了廣義Feistel 結(jié)構(gòu)，分組長(zhǎng)度為64 bit，密鑰長(zhǎng)度分為80 bit 和128 bit 這2 種版本。算法的提出者對(duì)TWINE 進(jìn)行了安全性分析，提出了15 輪的不可能差分路徑，完成了對(duì)23 輪TWINE-80 和24 輪TWINE-128 的不可能差分分析；Zheng 等[8]對(duì)Suzaki 等在分析中關(guān)于計(jì)算復(fù)雜度上存在的一些漏洞進(jìn)行了更正與補(bǔ)充，提出了更嚴(yán)謹(jǐn)?shù)牟豢赡懿罘址治觯淮撕骔ang 等[9]利用零相關(guān)線(xiàn)性分析的方法，對(duì)23 輪的TWINE 進(jìn)行了分析，結(jié)論較已有分析有所改進(jìn)；Coban 等[10]和Mohamed 等[11]對(duì)36 輪的TWINE 分別進(jìn)行了Biclique 分析和中間相遇攻擊，但其計(jì)算復(fù)雜度都接近窮舉搜索；2017 年，Wei 等[12]對(duì)TWINE 進(jìn)行了相關(guān)密鑰不可能差分分析，并提出了TWINE 的等價(jià)算法，該算法描述簡(jiǎn)潔直觀(guān)，更加有利于分析，他們構(gòu)造了一條15 輪的相關(guān)密鑰不可能區(qū)分器，并向上擴(kuò)展4 輪，向下擴(kuò)展5 輪，首次對(duì)24 輪的TWINE 進(jìn)行了攻擊，但在構(gòu)造文章所述的明文對(duì)時(shí)，結(jié)構(gòu)數(shù)n最大只能取到16，這會(huì)導(dǎo)致能恢復(fù)的密鑰比特很少且無(wú)實(shí)際價(jià)值。

相關(guān)密鑰不可能飛來(lái)去器[13]是近年來(lái)提出的一種新的分析方法，它結(jié)合了3 種不同分析方法的優(yōu)勢(shì)，對(duì)于輕量級(jí)的分組密碼算法如LBlock 等已有較好的分析結(jié)果[14]。對(duì)TWINE 而言，引入相關(guān)密鑰和飛來(lái)去器的方法可以使路徑的選擇變得更加靈活，本文采用相關(guān)密鑰不可能差分飛來(lái)去器的方法對(duì)23 輪TWINE-80 算法進(jìn)行了攻擊，獲得了較優(yōu)的分析結(jié)果。

2 TWINE 分組密碼介紹

2.1 TWINE 加密算法

TWINE 算法的分組長(zhǎng)度為64 bit，密鑰長(zhǎng)度分為80 bit 和128 bit 這2 種，明文經(jīng)過(guò)36 輪迭代得到密文。其中，輪函數(shù)采用了廣義 Feistel結(jié)構(gòu)，如圖1 所示，結(jié)構(gòu)中的S 盒如表1 所示。

圖1 TWINE 算法的輪函數(shù)

表1 TWINE 的S 盒

2.2 TWINE 的等價(jià)算法

Wei 等[12]將 TWINE 算法描述為等價(jià)的TWINE*算法，并對(duì)2 種算法的等價(jià)性進(jìn)行了證明。TWINE*算法更加直觀(guān)地體現(xiàn)了TWINE 算法的結(jié)構(gòu)特點(diǎn)，便于更好地展開(kāi)分析。本文將在TWINE*算法的基礎(chǔ)上進(jìn)行相關(guān)密鑰不可能飛來(lái)去器分析，算法的描述如下。

1)第一輪進(jìn)行置換IP，如表2 所示，置換后的明文分為左32 bit 和右32 bit。

2)按圖2 所示加密結(jié)構(gòu)進(jìn)行迭代計(jì)算，其中P1和P2置換如表3 和表4 所示。

3)對(duì)最后一輪的輪函數(shù)輸出進(jìn)行置換FP，如表5所示。

表2 置換IP

圖2 TWINE*的加密結(jié)構(gòu)

表3 P1置換

表4 P2置換

表5 置換FP

2.3 TWINE-80 的密鑰編排算法

TWINE-80 算法的密鑰編排算法為

其中，K為80 bit 主密鑰，WKi(0≤i≤1 9)為半字節(jié)塊。forr←1 to 35

表6 CONi的值

3 相關(guān)密鑰不可能飛來(lái)去器攻擊介紹

相關(guān)密鑰[15]、不可能差分[16]和飛來(lái)去器[17]都是被廣泛應(yīng)用的分組密碼攻擊方法，其中相關(guān)密鑰利用了密鑰編排算法的弱點(diǎn)，構(gòu)造特定的密鑰差分影響算法的加解密，從而構(gòu)造路徑恢復(fù)密鑰；不可能差分攻擊是用一條概率為0 的差分路徑來(lái)淘汰符合這條路徑的錯(cuò)誤密鑰；飛來(lái)去器則靈活地應(yīng)用差分的特點(diǎn)將算法分為兩部分進(jìn)行分析，以尋找更好的路徑。近年來(lái)，很多研究者傾向于將多種分析方法相結(jié)合，以期對(duì)算法安全性做出更好的研究[18-20]。

相關(guān)密鑰不可能飛來(lái)去器攻擊結(jié)合了以上3 種分析方法的思想。利用飛來(lái)去器和相關(guān)密鑰的方法，可以在算法上下兩部分做不同的密鑰差分，有助于擴(kuò)展攻擊輪數(shù)；利用不可能差分，配合相關(guān)密鑰對(duì)算法分析給出更多的可能途徑，以便尋找到更好的分析路徑。相關(guān)密鑰不可能飛來(lái)去器的攻擊方法如圖3 所示。

圖3 相關(guān)密鑰不可能飛來(lái)去器的攻擊方法

算法分析過(guò)程中，加密算法E被分為2 種算法（E0和E1）的組合。P1、P2、P3、P4經(jīng)對(duì)應(yīng)密鑰K1、K2、K3、K4加密分別得到(C1、C2、C3、C4)，其中4 個(gè)密鑰滿(mǎn)足K1⊕K2=K3⊕K4=ΔK1，并且K1⊕K3=K2⊕K4=ΔK2。圖 3 中α、β、γ、δ、α′、β′、γ′、δ′均代表差分，α→β和α′→β′是E0中2 條概率為1 的差分路徑，δ→γ和δ′→γ′是中2 條概率為1 的差分路徑。在中間輪相遇時(shí)，β、β′、γ、γ′滿(mǎn)足β⊕β′⊕γ⊕γ′≠ 0。

4 TWINE-80 的相關(guān)密鑰不可能飛來(lái)去器攻擊

4.1 路徑構(gòu)造

根據(jù)2.2 節(jié)TWINE 算法的等價(jià)算法TWINE*的描述，利用相關(guān)密鑰不可能飛來(lái)去器的分析方法，構(gòu)造出一個(gè)由16 輪和17 輪2 條路徑組成的相關(guān)密鑰不可能飛來(lái)去器區(qū)分器。并將其向上擴(kuò)展4 輪，向下將2 條差分路徑分別擴(kuò)展3 輪和2 輪，完成了對(duì)23 輪TWINE 算法的分析。除特別聲明外，下文符號(hào)“*”表示非零差分，“？”表示不確定的差分。

通過(guò)對(duì)TWINE 密鑰編排算法的研究，發(fā)現(xiàn)對(duì)于每輪的密鑰更新算法，有2 個(gè)半字節(jié)的主密鑰會(huì)進(jìn)入S 盒并參與異或運(yùn)算，從而實(shí)現(xiàn)非零密鑰差分的快速擴(kuò)散。在相關(guān)密鑰不可能飛來(lái)去器的構(gòu)造中，選擇區(qū)分器上半部分主密鑰的特定半字節(jié)差分 WKi0 Δ≠，其中WKi在差分路徑α→β、α′β′→ 中不會(huì)進(jìn)入S盒，這樣可以使非零差分的擴(kuò)散變慢，同時(shí)區(qū)分器的長(zhǎng)度增加。經(jīng)過(guò)分析對(duì)比，并同時(shí)考慮到密鑰恢復(fù)算法的計(jì)算復(fù)雜度，本文在本次攻擊中選取了主密鑰差分ΔWK=00000000000000020000，即ΔWK15=2，由此決定的輪密鑰差分如表7 所示。

表7 輪密鑰差分

由主密鑰差分可推知，第6 輪、第7 輪和第8輪的輪密鑰差分分別為00000200、00000000 和00020000（如表7 所示），若令第5 輪的輸入差分為（00000000，00000020），經(jīng)過(guò)兩輪加密之后，第8 輪的輸入差分為（00020000，00000000），易知這種構(gòu)造可使得區(qū)分器的活躍S 盒數(shù)目大大降低，從而可以獲得更長(zhǎng)輪數(shù)的路徑。因此，選取第5 輪的輸入差分α和α′均為（00000000，00000020）。在區(qū)分器的下半部分，本文選擇2 條不同的差分路徑，結(jié)合不可能差分分析的思想，經(jīng)過(guò)大量分析對(duì)比后確定了輸出差分：一條差分路徑中，選取第 20 輪的輸出差分δ為（00000200，00000000）；另一條差分路徑中，選取第21 輪的輸出差分δ′為（20000000，00000000）。在此基礎(chǔ)上根據(jù)相關(guān)密鑰不可能差分飛來(lái)去器的分析方法構(gòu)造了不可能差分路徑，分別如圖4 和圖5所示。

圖5 解密方向差分路徑

令E0表示5～14 輪，E1表示15～20（21）輪。區(qū)分器的密鑰關(guān)系為K1=K3，K2=K4，K1⊕K2=K3⊕K4=00000000000000020000。E0的2條差分路徑均為(00000000,00000020)→(??**?*?*,0?0?2**0)，長(zhǎng)度為10 輪。的一條差分路徑 為(00000200,00000000)→ (0*0****0,***?***0)，長(zhǎng)度為6 輪；另一條差分路徑為：(20000000,00000000)→(****?**0,**????**)，長(zhǎng)度為7 輪；2條路徑的密鑰差分均為0。E0的2 條加密路徑在第15 輪的輸入差分分別為(??**?*?*,0?0?2**),(??**?*?*,0?0?2**)，的2 條解密路徑在第15 輪的輸入差分分別為(0*0****0,***?***),(****?**0,**????*)，其中下劃線(xiàn)標(biāo)識(shí)的4 個(gè)半做字節(jié)做異或運(yùn)算一定不為0，滿(mǎn)足不可能差分的性質(zhì)。

在路徑的下半段，為使區(qū)分器中差分路徑盡可能長(zhǎng)，本文采用2 條不同長(zhǎng)度的差分路徑（6 輪和7 輪），這種設(shè)計(jì)不但不會(huì)影響不可能差分的性質(zhì)，而且還會(huì)降低密鑰恢復(fù)算法的計(jì)算復(fù)雜度。事實(shí)上，由圖3 可知，2 對(duì)向下加密的路徑和2 對(duì)向上解密的路徑分別加密解密至某相同輪數(shù)，對(duì)應(yīng)差分γ、γ′與β、β′只要滿(mǎn)足β⊕β′⊕γ⊕γ′≠ 0就滿(mǎn)足了不可能差分的要求，而本文設(shè)計(jì)的不同長(zhǎng)度的差分路徑是滿(mǎn)足該要求的；在此基礎(chǔ)上，為完成對(duì)23 輪TWINE 算法的分析，只需要分別向下擴(kuò)展3輪和2 輪，故而密鑰恢復(fù)算法的計(jì)算復(fù)雜度也因此有所降低。

4.2 擴(kuò)展路徑

Suzaki 等[7]提出TWINE 算法時(shí)，對(duì)其S 盒的差分特征給出了如下性質(zhì)：滿(mǎn)足S 盒差分特征（α→β）的輸入對(duì)的平均對(duì)數(shù)為，即給定密鑰RK 使α→β成立的概率為。利用這個(gè)性質(zhì)，在路徑擴(kuò)展時(shí)可以篩除掉多余的明密文對(duì)，使算法的計(jì)算復(fù)雜度大大降低。

本文對(duì)不可能差分路徑向兩端擴(kuò)展，向上擴(kuò)展4 輪，如圖6 所示，其中，α1∈ΔS(2)，α2∈ΔS(α1),α3∈ΔS(α2),α4∈ΔS(α3),；向下分別擴(kuò)展2 輪和3 輪，如圖7 所示，其中，γ1∈ΔS(2),γ2∈ΔS(γ1),γ3∈ΔS(γ2),,β1∈ΔS(2),β2∈ΔS(β1)。在此基礎(chǔ)上最終完成對(duì)TWINE 算法的23 輪相關(guān)密鑰不可能差分飛來(lái)去器攻擊。符號(hào) ΔS()α表示S 盒輸入差分為α?xí)r，其輸出差分所有可能取值的集合。

4.3 密鑰恢復(fù)算法

根據(jù)圖6 和圖7 的擴(kuò)展差分路徑，本文對(duì)算法進(jìn)行密鑰恢復(fù)。具體的過(guò)程如下。

步驟1按照?qǐng)D6 中明文差分的輸入結(jié)構(gòu)，選取2n個(gè)明文結(jié)構(gòu)，每個(gè)結(jié)構(gòu)包含402 個(gè)明文，它們可以構(gòu)成2n+79個(gè)明文對(duì)，記為(P1,P2)，再選擇2n+79個(gè)這樣的明文對(duì)(P3,P4)，它們組成22n+158個(gè)四元組(P1,P2,P3,P4)。

圖6 向上擴(kuò)展的差分路徑

步驟2將四元組中的2 個(gè)明文對(duì)分別在密鑰差分為00000000000000020000 的密鑰對(duì)下加密23輪，得到對(duì)應(yīng)的密文四元組(C1,C2,C3,C4)。按照?qǐng)D7中密文差分的結(jié)構(gòu)，分別篩除密文差分不滿(mǎn)足C1⊕C3=(*000*0*0,020*0000)和C2⊕C4=(*0000020,00*00000)的四元組。經(jīng)過(guò)篩選后，剩余的四元組數(shù)為2158+2n×2-104=254+2n。利用4.2 節(jié)中S 盒的性質(zhì)，可以對(duì)剩余四元組進(jìn)行再次篩選。再次篩選后剩余四元組數(shù)為≈254+2n×2-31.01=22n+22.99。

圖7 向下擴(kuò)展的差分路徑

步驟3猜測(cè)，對(duì)剩余四元組部分加密一輪，檢查輸出的四元組中左半部分的第0、1、3、5 個(gè)半字節(jié)的差分是否為0，若不為 0 則篩除相應(yīng)的四元組。該步操作后剩余個(gè)四元組。該步的計(jì)算復(fù)雜度為(22n+22.99× 24+22n+17.37×28+22n+11.75× 212+22n+6.13×216)×=22n+20.01。

步驟4猜測(cè)，對(duì)剩余四元組的(C1,C3)部分解密一輪，檢查(C1,C3)對(duì)應(yīng)輸出左半部分的第2、3 個(gè)半字節(jié)的差分是否為0，若不是則篩除相應(yīng)的四元組。該步操作后剩余 22n-16.35個(gè)四元組。該步的計(jì)算復(fù)雜度為 22n+23.00。

步驟5猜測(cè)，對(duì)剩余四元組部分加密2 輪，檢查輸出的四元組中左半部分的第6、7 個(gè)半字節(jié)的差分是否為0，若不為0 則篩除相應(yīng)的四元組。該步操作后剩余 22n-16.35個(gè)四元組。該步的計(jì)算復(fù)雜度為 22n+23.00。

步驟 6猜測(cè)，對(duì)剩余四元組部分加密3 輪，其中，在步驟3 和步驟5 已猜測(cè)。檢查輸出的四元組中左半部分的第1、4 個(gè)半字節(jié)的差分是否為0，若不為0 則篩除相應(yīng)的四元組。該步操作后剩余22n-27.59個(gè)四元組。該步的計(jì)算復(fù)雜度為 22n+28.33。

步驟7猜測(cè)，對(duì)剩余四元組部分加密4 輪，其中已經(jīng)在步驟 6 中計(jì)算得到，在步驟3、步驟5 和步驟6 已猜測(cè)，不需要再猜測(cè)。檢查輸出的四元組中左半部分的第2、3 個(gè)半字節(jié)的差分是否為0，若不為0 則篩除相應(yīng)的四元組。該步操作后剩余22n-38.83個(gè)四元組。該步的計(jì)算復(fù)雜度為 22n+22.65。

步驟8猜測(cè)，對(duì)剩余四元組其中的(C1,C3)部分解密一輪，檢查(C1,C3)對(duì)應(yīng)輸出左半部分的第一個(gè)半字節(jié)的差分是否為0，若不為0則篩除相應(yīng)的四元組。對(duì)剩余四元組其中的(C2,C4)部分解密一輪，檢查(C2,C4)對(duì)應(yīng)輸出左半部分的第0 個(gè)半字節(jié)的差分是否為0，若不為0 則篩除相應(yīng)的四元組。該步操作后剩余 22n-44.45個(gè)四元組。該步的計(jì)算復(fù)雜度為22n+18.74。

步驟9對(duì)(C1,C3)，猜測(cè)，共有16 種可能，對(duì)剩余四元組進(jìn)行第 3 輪解密，利用完成篩選，篩選后剩余四元組個(gè)數(shù)為；對(duì)(C2,C4)，猜測(cè)，共有16 種可能，對(duì)剩余四元組進(jìn)行第2 輪解密，利用完成篩選，篩選后剩余四元組個(gè)數(shù)為。該步的計(jì)算復(fù)雜度為 22n+12.02+22n+17.21。

若在步驟1 中取n=21.05，則步驟9 中剩余四元組個(gè)數(shù)為 22n-42.07=20.03＞ 1，恰好可以剔除錯(cuò)誤密鑰，恢復(fù)出正確的密鑰。

綜上，本次23 輪TWINE 的相關(guān)密鑰不可能飛來(lái)去器攻擊共可以恢復(fù)出68 bit 密鑰，需要的明文數(shù)為2n+40+1=262.05，計(jì)算復(fù)雜度為 22n+20.01+22n+14.69+22n+23.00+22n+28.33+22n+22.65+22n+18.74+22n+12.02+22n+17.21=22n+28.39=270.49。與TWINE 算法已有分析結(jié)果相比，本文結(jié)果在數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度上都具有一定優(yōu)勢(shì)，說(shuō)明相關(guān)密鑰不可能飛來(lái)去器分析對(duì)TWINE 算法具有較好的攻擊效果。具體分析結(jié)果對(duì)比如表8 所示。

表8 TWINE 的部分分析結(jié)果

5 結(jié)束語(yǔ)

本文利用TWINE 密鑰編排算法的弱點(diǎn)，采用了相關(guān)密鑰、不可能差分和飛來(lái)去器三者結(jié)合的手段對(duì)其進(jìn)行了攻擊。充分利用了密鑰差分對(duì)路徑的影響，應(yīng)用飛來(lái)去器的方法構(gòu)造出一條盡可能長(zhǎng)的差分分析路徑，完成了對(duì)23 輪TWINE 的相關(guān)密鑰不可能差分飛來(lái)去器攻擊。該攻擊需要的數(shù)據(jù)復(fù)雜度為 262.05，時(shí)間復(fù)雜度為 270.49，與已有分析結(jié)果相比具有一定優(yōu)勢(shì)。這種將多種分析方法相結(jié)合的攻擊充分利用了各種分析方法的優(yōu)勢(shì)，有利于達(dá)到更高輪數(shù)的攻擊，對(duì)于其他分組密碼算法的安全性分析也是一種新思路。