蔣梓龍 金晨輝

(戰(zhàn)略支援部隊信息工程大學 鄭州 450001)

1 引言

在NIST輕量級密碼標準競賽中，TweAES算法[1]是進入到第2輪的認證加密候選算法。TweAES是類AES-128的可調分組密碼，具體而言，是在AES-128算法[2]的基礎上，可以額外選取4 bit主調柄，通過簡單的線性運算將主調柄擴展為8 bit子調柄，將擴展的8 bit子調柄值與偶數輪輸出進行異或加操作，即得到了TweAES算法。

不可能差分攻擊[3,4]是差分攻擊的一種變體，之后Tsunoo等人[5]提出了多重不可能差分的思想，Boura等人[6,7]和Li等人[8,9]運用多重不可能差分攻擊，對分組密碼算法AES, CLEFIA[10], LBlock[11]，Fox[12]等均得到很好的效果。經過了多年以來對AES-128的密碼分析[13-18]，大量的分析結果涌現而出，Leurent等人[19]在2021年的歐洲密碼年會上，詳細地分析了AES的密鑰生成算法，揭示了子密鑰擴散的不完全性。在這些攻擊方案中，最好的攻擊結果可以攻擊到7輪的AES-128，不可能差分攻擊也取得了很好的攻擊結果。TweAES算法在AES-128的基礎上，新引入了4 bit主調柄，所以其安全性更值得深入研究。

TweAES算法設計報告[1]的第3.4.2小節(jié)，在選擇調柄的條件下，設計者給出了TweAES算法對積分攻擊、不可能差分攻擊、截斷差分攻擊、中間相遇攻擊的安全性分析。在這些攻擊方案中，最有效的是不可能差分攻擊，設計者構造了一個6輪的相關調柄不可能差分區(qū)分器，并給出了一個8輪的不可能差分攻擊方案。Niu等人[20]利用自動求解器STP，搜索了更多高效TweAES算法的不可能差分區(qū)分器。此外，Niu等人還指出了TweAES算法設計報告中的8輪不可能差分攻擊有瑕疵，其時間復雜度大于窮舉攻擊，所以不是一個有效攻擊，并給出了對8輪TweAES算法的有效不可能差分攻擊方案。

為進一步研究TweAES算法抵抗不可能差分攻擊的安全性，本文提出了對TweAES算法的相關調柄多重不可能差分攻擊。首先，本文構造了兩條都需要攻擊16 Byte子密鑰的攻擊路徑，他們有相同的明文結構與14 Byte公共子密鑰。因相同的明文結構和大量的公共密鑰，攻擊者可以利用同一個明文結構下的明密對，篩選兩次子密鑰，提高了攻擊方案對子密鑰篩選的效率。此外，本文利用密鑰生成算法的不完全性，有針對性地選擇了子密鑰位置，可以提高主密鑰恢復階段的效率，從而改進整體攻擊方案。

本文組織結構如下：第2節(jié)給出TweAES的算法描述和符號說明；第3節(jié)闡述6輪相關調柄的不可能差分區(qū)分器；第4節(jié)給出TweAES算法的8輪多重不可能差分攻擊方案及復雜度分析；第5節(jié)總結全文。

2 基本概念

在本節(jié)，2.1節(jié)先簡要描述了TweAES算法，2.2節(jié)對符號進行了說明。

2.1 TweAES算法描述

TweAES算法是基于AES-128的可調認證加密算法，屬于SPN結構分組密碼算法。其分組長度為128 bit，可看作一個16 Byte的 4 ×4矩陣，主密鑰長度設置為128 bit。由Byte替換 SB、行移位變換SR 、列混合變換M C、 輪密鑰加 AK、 調柄加A T這5種變換構成。其中前4種變換與AES-128完全一致，而調柄加變換每隔兩輪注入一次調柄值，5種變換簡述如下：

(1)字節(jié)替換S B：由AES算法中的16個S盒并置而成，對128 bit輸入進行非線性變換。

(2)行移位變換S R：由行號值對每行循環(huán)左移，即第i行循環(huán)左移iByte(i=0,1,2,3)。

(3)列混合變換 M C：由AES算法的左乘矩陣，對狀態(tài)的每列進行乘法運算。

(4)輪密鑰加 AK：每輪輸入值與對應子密鑰異或加，本文記k0為主密鑰，其余子密鑰是由AES-128的密鑰擴展方案生成k1,k2,...,k10共10個128 bit子密鑰。

(5)調柄加 AT ： 4 bit主調柄為(t0,t1,t2,t3)，然后通過簡單的線性變換將其擴展為8 bit的子調柄，記t=t0⊕t1⊕t2⊕t3，則擴展的8 bit調柄為(t0,t1,t2,t3)→(t0,t1,t2,t3,t ⊕t0,t ⊕t1,t ⊕t2,t ⊕t3)

記擴展的8 bit調柄為T=(t0,t1,t2,t3,t4,t5,t6,t7)， 將第ibit異或加到前兩行第iByte的最低比特位，字節(jié)位置如圖1所示。子調柄加每隔兩輪操作一次，即在第2, 4, 6, 8, 10輪注入擴展的8 bit子調柄。

圖1 TweAES算法的輪函數圖(偶數輪)

關于TweAES算法的更多細節(jié)可以查閱文獻[1]。

2.2 符號說明

若無特殊說明，本文使用表1所示符號約定。

表1 符號說明

3 TweAES的6輪相關調柄不可能差分區(qū)分器

本文運用的TweAES的6輪相關調柄不可能差分區(qū)分器與文獻[1,20]相似，本文的攻擊方案用到了8個區(qū)分器，具體的輸入差分和輸出差分如表2所示。在這里以第1個區(qū)分器為例，對其進行簡要闡述，具體的區(qū)分器差分傳遞過程如圖2所示。

表2 TweAES的8個6輪相關調柄不可能差分區(qū)分器

本小節(jié)選取的主調柄4 bit差分值為 ( 1,0,0,1)，經過線性變換擴展的子調柄的8 bit差分值為(1,0,0,1,1,0,0,1)。注意，因為子調柄加操作是將1 bit值異或加至對應字節(jié)的最低比特位，所以子調柄差分非零字節(jié)對應的差分值均為0x01。以圖2的不可能差分區(qū)分器為例，本文描述其性質如下：

圖2 TweAES算法的6輪相關調柄不可能差分區(qū)分器

是算法TweAES的一個6輪的相關調柄不可能差分區(qū)分器。 證畢

其余的7個不可能差分區(qū)分器的證明，與上述證明類似。

4 TweAES的8輪多重不可能差分攻擊

本節(jié)基于上述的兩類6輪不可能差分區(qū)分器，提出8輪的多重不可能差分攻擊方案。將上一節(jié)中，從第3輪到第8輪的6輪不可能差分區(qū)分器，分別往前和往后各擴展一輪，得到了第2輪到第9輪的8輪不可能差分攻擊路徑。用兩類不可能差分區(qū)分器可以分別構造兩條攻擊路徑，每條攻擊路徑需要攻擊14 Byte子密鑰，具體而言，第1條攻擊路徑需要攻擊(k1,(0,1,5,6,10,11,12,15),k9,(0,7,9,10,12,13))，第2條攻擊路徑需要攻擊 (k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,9,12,13))。值得注意的是，兩條攻擊路徑有相同的明文結構，并且有12 Byte的公共子密鑰(k1,(0,1,5,6,10,11,12,15),k9,(0,9,12,13))。第1條攻擊路徑如圖3所示。

圖3 TweAES算法的8輪相關調柄不可能差分攻擊路徑

由文獻[20]給出的8輪不可能差分攻擊方案可知，時間復雜度最大的階段在于數據處理階段，即數據量過大，對明密文進行排序的時間遠大于篩選錯誤子密鑰的時間。針對這個情況，本文提出的改進可以降低所需要的數據量，從而可以降低整體攻擊方案的時間復雜度，其降低數據量的思想如下：

(1)因為兩條攻擊路徑有相同的明文結構，則對一個明文結構中的明密文，可以用兩條不同的攻擊路徑去篩選子密鑰。相較于只用一條攻擊路徑，極大地提升了對錯誤子密鑰的篩選效率，從而可以減少攻擊方案數據量。

(2)在每條攻擊路徑需要猜測14 Byte子密鑰的情況下，有12 Byte的公共子密鑰。在兩條攻擊路徑篩選完畢后，得到候選子密鑰(k1,(0,1,5,6,10,11,12,15),k9,(0,7,9,10,12,13))和 (k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,9,12,13))，只有12 Byte公共子密鑰(k1,(0,1,5,6,10,11,12,15),k9,(0,9,12,13))值相同時，才可以判定16 Byte子密鑰(k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,7,9,10,12,13))為候選密鑰，此時錯誤密鑰的通過率為2-96，可以再次提高對錯誤密鑰的篩選效率，減少數據量。

(3)利用密鑰生成算法的不完全性，找到了子密鑰間的關聯(lián)，從而可以更高效地在主密鑰恢復階段篩選錯誤候選密鑰。這樣本文的攻擊方案就可以在主密鑰恢復階段，篩選更多的錯誤密鑰，從而可以減少一定的數據量。

利用上述的改進，本文的攻擊方案對3項復雜度均有所改進。

4.1 TweAES的8輪相關調柄不可能差分攻擊步驟

本文攻擊步驟包括：預處理階段、數據處理階段、子密鑰篩選階段和主密鑰恢復階段，一共4個部分。分別闡述如下：

數據處理階段：先選取兩個主調柄記作T1,T2，且兩個主調柄的差分值為( 1,0,0,1)。在明文的(2, 3, 4, 7, 8, 9, 13, 14)這8 Byte位置取固定值，遍歷其他8 Byte，可以得到 264明文，將其稱為一個明文結構。對每個明文結構下的 264明文，用兩個調柄T1, T2對這 264個明文進行加密查詢，分別可以得到兩組 264個密文。以兩組密文的12 Byte (1, 2,3, 4, 5, 6, 7, 8, 10, 11, 14, 15)共24 Byte為指標，運用快速排序技術[20]對明文及對應的兩組密文一同排序，將其存入表?中，再選取對應的有效明密對。

第1條攻擊路徑的有效明密對：選取在密文的(1, 2, 3, 4, 5, 6, 8, 11, 14, 15)這10 Byte值相同的密文段，分別從兩組密文中各取一個組成密文對，則保證了主調柄差分值為 ( 1,0,0,1)，且滿足第1條攻擊路徑的明密對差分要求。在只使用一對主調柄的條件下，一個明文結構可以生成2128-80=248個有效明密對。

第2條攻擊路徑的有效明密對：選取在密文的(1, 2, 4, 5, 7, 8, 10, 11, 14, 15)這10 Byte值相同的密文段，分別從兩組密文中各取一個組成密文對，則保證了主調柄差分值為 ( 1,0,0,1)，且滿足第2條攻擊路徑的明密對差分要求。在只使用一對主調柄的條件下，一個明文結構可以生成248個有效明密對。

本文選取 2n個明文結構，每條攻擊路徑可得2n+48對有效明密對。

(5) 明文結構中的全部有效明密文對篩選完畢后，用下一個明文結構重復(1)至(4)步。若全部明文結構均已檢測完畢，進入主密鑰恢復階段。

主密鑰恢復階段：現有兩個候選子密鑰表G1K和G2K，其中索引地址上值為0的為候選子密鑰，值為1的為錯誤子密鑰，設每個表中有Nk個候選密鑰。只有12 Byte公共子密鑰值相同時，才可以判定16 Byte(k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,7,9,10,12,13))子密鑰為候選密鑰，故1 6 B y t e 候選密鑰有(Nk)2×2-96個。

文獻[18,19]研究了AES的密鑰生成算法，本文利用子密鑰擴散的不完全性，提高主密鑰恢復的效率。如表3所示，第9輪子密鑰后12 Byte，只與第1輪部分子密鑰字節(jié)相關。故本文先窮舉部分第1輪子密鑰字節(jié)，對比驗證排除部分錯誤候選密鑰后，再窮舉第1輪其余部分子密鑰字節(jié)，直至得到全部的第1輪子密鑰。如果還未唯一確定正確密鑰，再用加密驗證排除剩余的錯誤密鑰，直至得到正確密鑰?，F在已知第1輪子密鑰k1,(0,1,5,6,10,11,12,15)與第9輪子密鑰k9,(0,3,6,7,9,10,12,13)。主密鑰恢復階段的具體步驟如下：

(1) 窮舉第1輪子密鑰中的5 Bytek1,(3,7,9,13,14)，此時第1輪子密鑰只有3 Bytek1,(2,4,8)未知，由表3知k9,(12)與k1,(2,4,8)無關，則可以由第1輪子密鑰計算密鑰k9,(12)的 值，若與候選密鑰k9,(12)的值不相符，則判定其為錯誤密鑰排除。檢測完還有(Nk)2×2-96×240×2-8=(Nk)2×2-64個候選密鑰。

(2) 窮舉第1輪子密鑰中的1 Bytek1,(4)，此時第1輪子密鑰只有2 Bytek1,(2,8)未知，由表3知k9,(6)與k1,(2,8)無關，則可以由第1輪子密鑰計算密鑰k9,(6)的 值，若與候選密鑰k9,(6)的值不相符，則判定其為錯誤密鑰排除。檢測完還有(Nk)2×2-64×28×2-8=(Nk)2×2-64個候選密鑰。

(3) 窮舉第1輪子密鑰中的1 Bytek1,(8)，此時第1輪子密鑰只有1 Bytek1,(2)未知，由表3知k9,(9,10,13)與k1,(2)無關，則可以由第1輪子密鑰計算密鑰k9,(9,10,13)的 值，若與候選密鑰k9,(9,10,13)的值不相符，則判定其為錯誤密鑰排除。檢測完還有(Nk)2×2-64×28×2-24=(Nk)2×2-80個候選密鑰。

表3 AES-128中第9輪子密鑰后12 Byte與第1輪子密鑰關聯(lián)

(4) 窮舉第1輪子密鑰中的1 Bytek1,(2)，此時得到了全部16 Byte第1輪子密鑰，可以由第1輪子密鑰計算密鑰k9,(0,4,7)的 值，若與候選密鑰k9,(0,4,7)的值不相符，則判定其為錯誤密鑰排除。檢測完還有(Nk)2×2-96個候選密鑰。若此時仍有多個候選密鑰，則通過加密驗證排除剩余的錯誤密鑰，直至得到正確密鑰。

4.2 復雜度分析

主密鑰恢復階段：由AES-128的密鑰生成算法，由k1計 算出k9需要8次查表。故第1步所需的時間復雜度為(Nk)2×2-96×240×23=(Nk)2×2-53次查表，第2步所需的時間復雜度為(Nk)2×2-64×28×23=(Nk)2×2-53次查表；第3步所需的時間復雜度為(Nk)2×2-64×28×23=(Nk)2×2-53次查表，第4步所需的時間復雜度為(Nk)2×2-80×28×23=(Nk)2×2-69次查表，若最后仍有候選密鑰需加密驗證，則需要(Nk)2×2-96次8輪AES加密驗證。由文獻知，一輪AES加密約為20次查表。主密鑰恢復階段所需的時間復雜度為4步所需時間總和，故主密鑰恢復階段時間復雜度為Tmk=3×(Nk)2×2-53+20×(Nk)2×2-96次查表。存儲復雜度最大的在第2 步 ， 需 要(Nk)2×2-64×(22×8)=(Nk)2×2-56.54bit。

綜上，本文攻擊方案的數據復雜度為 2n+64；存儲復雜度為 2113b i t；時間復雜度為Ttotal=Td+Tsk+Tmk。本文取n=58.10 ，可得Td=2128.10次查表，Tsk=2117.10次查表，Nk=287.26，Tmk=2123.10次 查 表， 則Ttotal=Td+Tsk+Tmk=2128.14次查表。故本文攻擊方案所需的數據復雜度為 2122.10個 選擇明文，存儲復雜度為2113bit，時間復雜度為 2128.14/(20×8)≈2120.82次8輪AES加密。本文的攻擊方案改進了時間、數據、存儲3項復雜度，表4給出了與TweAES算法相關的攻擊結果。

表4 TweAES的攻擊結果

5 結束語

本文提出了對8輪TweAES算法相關調柄的多重不可能差分攻擊。首先，本文利用兩類不可能差分區(qū)分器，構造了兩條攻擊路徑，每條攻擊路徑需要攻擊16 Byte子密鑰。值得注意的是，兩條攻擊路徑有相同的明文結構和14 Byte的公共子密鑰，攻擊者可以利用同一個明文結構下的有效明密文對，篩選兩次子密鑰，且因為有大量的公共子密鑰，可以提高攻擊方案對子密鑰篩選的效率。其次，本文利用密鑰生成算法的不完全性，有針對性地設置子密鑰字節(jié)位置，利用子密鑰之間的相關性，提高主密鑰恢復效率，從而改進整體攻擊方案的結果。本文的攻擊方案在時間、數據、存儲3項復雜度結果上均有所改進，所需的數據復雜復雜為 2122.10個選擇明文，時間復雜度為2120.82次8輪AES加密，存儲復雜度為2113bit。