謝敏，田峰，李嘉琪

（西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室，陜西 西安 710071）

1 引言

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

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

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

2 TWINE 分組密碼介紹

2.1 TWINE 加密算法

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

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

表1 TWINE 的S 盒

2.2 TWINE 的等價算法

Wei 等[12]將 TWINE 算法描述為等價的TWINE*算法，并對2 種算法的等價性進行了證明。TWINE*算法更加直觀地體現(xiàn)了TWINE 算法的結構特點，便于更好地展開分析。本文將在TWINE*算法的基礎上進行相關密鑰不可能飛來去器分析，算法的描述如下。

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

2)按圖2 所示加密結構進行迭代計算，其中P1和P2置換如表3 和表4 所示。

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

表2 置換IP

圖2 TWINE*的加密結構

表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 相關密鑰不可能飛來去器攻擊介紹

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

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

圖3 相關密鑰不可能飛來去器的攻擊方法

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

4 TWINE-80 的相關密鑰不可能飛來去器攻擊

4.1 路徑構造

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

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

表7 輪密鑰差分

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

圖5 解密方向差分路徑

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

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

4.2 擴展路徑

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

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

4.3 密鑰恢復算法

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

步驟1按照圖6 中明文差分的輸入結構，選取2n個明文結構，每個結構包含402 個明文，它們可以構成2n+79個明文對，記為(P1,P2)，再選擇2n+79個這樣的明文對(P3,P4)，它們組成22n+158個四元組(P1,P2,P3,P4)。

圖6 向上擴展的差分路徑

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

圖7 向下擴展的差分路徑

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

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

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

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

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

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

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

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

綜上，本次23 輪TWINE 的相關密鑰不可能飛來去器攻擊共可以恢復出68 bit 密鑰，需要的明文數(shù)為2n+40+1=262.05，計算復雜度為 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 算法已有分析結果相比，本文結果在數(shù)據(jù)復雜度和時間復雜度上都具有一定優(yōu)勢，說明相關密鑰不可能飛來去器分析對TWINE 算法具有較好的攻擊效果。具體分析結果對比如表8 所示。

表8 TWINE 的部分分析結果

5 結束語

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