穆道光，胡建勇，苗旭東

（1.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041；2.保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

0 引 言

立方分析是2009 年歐密會(huì)上以色列密碼學(xué)者Dinur 和Shamir 提出的一種密碼算法分析方法[1]，目前已成為對(duì)稱密碼算法中一種常見(jiàn)的分析方法，針對(duì)流密碼算法[1-7]、哈希算法[1-2,4-5]、認(rèn)證加密算法[8]等許多典型算法，采用立方分析能得到很好的分析效果。

2017 年美密會(huì)上，日本密碼學(xué)者Todo 等人[4]提出了基于可分性的立方分析方法。該方法借助于混合整數(shù)線性規(guī)劃（Mixed Integer Linear Programming，MILP）求解工具，可以判斷出較大規(guī)模立方變量集（如大于或等于70）對(duì)應(yīng)的超級(jí)多項(xiàng)式中包含的密鑰比特變量。2018 年美密會(huì)上，王慶菊等人[5]對(duì)Todo 等人提出的基于可分性的立方分析方法作了改進(jìn)，提出了標(biāo)記技術(shù)（Flag Technique）、單項(xiàng)式枚舉（Term Enumeration）、代數(shù)次數(shù)評(píng)估（Degree Evaluation）等方法，能夠進(jìn)一步判斷出立方變量集對(duì)應(yīng)的超級(jí)多項(xiàng)式的代數(shù)式次數(shù)、可能包含的單項(xiàng)式及數(shù)量。2020 年亞密會(huì)上，胡凱等人[6]提出了基于單項(xiàng)式預(yù)估（Monomial Prediction）的立方攻擊方法；同年歐密會(huì)上，郝詠霖等人[7]提出了基于不帶未知集的三子集可分性的立方攻擊方法，以上兩種方法都能夠準(zhǔn)確地判斷超級(jí)多項(xiàng)式的代數(shù)表達(dá)式，雖然研究的角度不同，但本質(zhì)上是等價(jià)的，且均需要運(yùn)用Gurobi、Cplex 等工具求解出MILP 模型的所有可行解。當(dāng)MILP 模型規(guī)模龐大、可行解數(shù)量過(guò)多時(shí)，求解模型所有可行解往往需要耗費(fèi)大量的時(shí)間和內(nèi)存，例如，上述兩種方法都只恢復(fù)出初始化842 輪的Trivium 算法的立方變量集對(duì)應(yīng)的超級(jí)多項(xiàng)式表達(dá)式，當(dāng)初始化輪數(shù)提升至843 輪時(shí)，持續(xù)數(shù)月求解相應(yīng)的MILP 模型，均無(wú)法得到最終結(jié)果。針對(duì)上述問(wèn)題，2021 年亞密會(huì)上，胡凱等人[2]提出了嵌套單項(xiàng)式預(yù)測(cè)方法（Nested Monomial Predictions），其思想是將大輪數(shù)對(duì)應(yīng)的MILP 模型反復(fù)分解為若干小輪數(shù)對(duì)應(yīng)的MILP 模型，同時(shí)，設(shè)置輪數(shù)步長(zhǎng)以控制分解后的模型數(shù)量，設(shè)置模型求解時(shí)間戳以限制每個(gè)分解后的模型求解時(shí)間。通過(guò)該方法，能夠恢復(fù)出初始化843、844、845 輪的Trivium 算法的立方變量集對(duì)應(yīng)的超級(jí)多項(xiàng)式表達(dá)式，其中恢復(fù)出初始化845 輪的Trivium 算法的立方變量集對(duì)應(yīng)的超級(jí)多項(xiàng)式表達(dá)式的時(shí)間約21 天。

2021 年，Delaune 等人[3]根據(jù)序列密碼算法中的狀態(tài)轉(zhuǎn)移關(guān)系式，提出了一種基于有向圖的建模方法。與基于可分性的建模方法相比，該方法建立的MILP 模型更加簡(jiǎn)單，求解MILP模型的時(shí)間消耗更少，Delaune 等人恢復(fù)出初始化842 輪的Trivium 算法的立方變量集對(duì)應(yīng)的超級(jí)多項(xiàng)式表達(dá)式的時(shí)間約3 小時(shí)，但沒(méi)有給出初始化更高輪數(shù)Trivium 算法的立方攻擊結(jié)果。

本文結(jié)合Delaune 等人的有向圖建模方法以及胡凱等人的模型分解方法，提出一種Trivium算法的攻擊算法。

1 基本知識(shí)

本文介紹了立方攻擊基本原理、胡凱等人提出的嵌套單項(xiàng)式預(yù)測(cè)方法以及Delaune 等人提出的基于有向圖建模方法等相關(guān)的基本知識(shí)。

1.1 立方攻擊

1.2 嵌套單項(xiàng)式預(yù)測(cè)方法

（3）若Gurobi 求解器在時(shí)間戳0t 內(nèi)沒(méi)有反饋出MILP 模型有無(wú)解或者沒(méi)有解出所有解，則設(shè)置新的輪數(shù)步長(zhǎng)，計(jì)算出所有的的路徑數(shù)量，設(shè)置新的時(shí)間戳1t ，運(yùn)用Gurobi 求解器在時(shí)間1t 內(nèi)判斷每個(gè)集合的奇偶性；以此反 復(fù)直到Gurobi 求解器的反饋結(jié)果中不包含沒(méi)有解出的MILP 模型。

1.3 基于有向圖的建模方法

2021 年，Delaune 等人根據(jù)序列密碼算法中的狀態(tài)轉(zhuǎn)移關(guān)系式，提出了一種基于有向圖的建模方法。與基于可分性的建模方法相比，該方法建立的MILP 模型包含的變量或約束條件更少。

Delaune 等人將序列密碼的中間狀態(tài)變量和多項(xiàng)式關(guān)系用有向圖G 表示。其中，有向圖G 中的節(jié)點(diǎn)為序列密碼的中間狀態(tài)變量，有向圖G 中的邊x y→ 為變量y 在變量x 的代數(shù)表達(dá)式之中。

例如，變量1x ,2x ,3x ,1y ,2y ,1z ,2z 及它們之間的多項(xiàng)式關(guān)系為：

對(duì)應(yīng)的有向圖 G = (V , E)如圖1 所示，有向 圖G 中表示的節(jié)點(diǎn)，

用T 表示由根節(jié)點(diǎn)的代數(shù)表達(dá)式中的單項(xiàng)式對(duì)應(yīng)的一條傳播路徑，邊之間存在的邏輯關(guān)系為：

以邊E 中的元素為模型變量，得到的模型包含8 個(gè)變量、6 個(gè)約束關(guān)系，相較于基于可分性建立的模型，變量和約束關(guān)系均較少。

針對(duì)Trivium 算法，Delaune 等人給出了其模型建立方法。Trivium 算法的狀態(tài)轉(zhuǎn)移關(guān)系為3 個(gè)二次非線性關(guān)系式，每個(gè)關(guān)系式包含了5個(gè)變量，特別地，二次關(guān)系對(duì)應(yīng)的邊用雙線邊（Double Edges）表示，線性關(guān)系對(duì)應(yīng)的邊用單線邊表示，因此，每個(gè)節(jié)點(diǎn)（除葉子節(jié)點(diǎn)外）均有5 條邊，其中2 條為雙線邊。

設(shè) ( )Pred i 為節(jié)點(diǎn)i 的父節(jié)點(diǎn)， ( )Succ i 為節(jié)點(diǎn)i 的單線邊對(duì)應(yīng)的子節(jié)點(diǎn)及雙線邊對(duì)應(yīng)的其中1 個(gè)子節(jié)點(diǎn)， brother1( i )和 brother2(i )分別為節(jié)點(diǎn)i 的雙線邊對(duì)應(yīng)的2 個(gè)子節(jié)點(diǎn)。在模型中，用布爾變量 ,i jX 驗(yàn)證邊i j→ 是否存在于路徑T 之中，若(i, j ) ∈ T，則 Xi,j= 1；若(i , j ) ? T，則Xi,j= 0。 Xi,j滿足以下的約束關(guān)系：

類似地，通過(guò)運(yùn)用Gurobi 求解上述變量及約束關(guān)系建立的模型的所有可行解，當(dāng)密鑰變量的葉子節(jié)點(diǎn)組成的向量v 對(duì)應(yīng)的可行解數(shù)量為奇數(shù)時(shí)，對(duì)應(yīng)的 kv為超級(jí)多項(xiàng)式 p ( x′ , k )中包含的單項(xiàng)式。

為了提高模型求解效率，Delaune 等人還提出了一些優(yōu)化方法，包括增加約束以盡可能多地排除可行解數(shù)量為偶數(shù)的向量v、設(shè)置模型中變量的BranchPriority 權(quán)值和VarHintVal 值以加速Gurobi 求解速度等。

2 Trivium 算法的立方攻擊

本節(jié)首先介紹Trivium 算法，其次給出對(duì)Trivium 算法的攻擊算法。

2.1 Trivium 算法簡(jiǎn)介

Trivium 算法采用非線性反饋移位寄存器設(shè)計(jì)，內(nèi)部狀態(tài)共為288 比特，記為 s1, s2, …,s288，分為3 個(gè)寄存器A，B，C，其中，寄存器A 包含93 比特狀態(tài)，寄存器B 包含84 比特狀態(tài)，寄存器C 包含111 比特狀態(tài)。

Trivium 算法使用80 比特密鑰變量 k1, k2, …,k80和80 比特初始值IV 變量 v1, v2, … , v80，初始填充過(guò)程如下：

填充完成后進(jìn)行1 152 輪迭代，每輪迭代中，首先計(jì)算中間變量t1, t2, t3：

其次更新寄存器A , B , C：

迭代完成后，輸出密鑰流比特z 為：

2.2 攻擊算法

本文結(jié)合了有向圖建模方法以及模型分解方法，提出一種針對(duì)Trivium 算法的快速立方攻擊方法，攻擊過(guò)程中需要使用的一些算法如下文所述。

算法1 用于得到有向圖中的節(jié)點(diǎn)變量下標(biāo)。

算法1：節(jié)點(diǎn)變量下標(biāo)算法getvar

輸入：整數(shù)a 為節(jié)點(diǎn)變量x 的下標(biāo)

輸出：整數(shù)b 為節(jié)點(diǎn)變量x 之前與其相等的節(jié)點(diǎn)變量的下標(biāo)

1 若 288a ＜ ，返回b a= ；否則，轉(zhuǎn)到步驟2

2 令 c = a%288，若 c= 0或 c= 93或 c= 177， 返回b a= ；否則，轉(zhuǎn)到步驟3

3 返回 getvar ( a- 288 -1)

算法2 用于得到根節(jié)點(diǎn)向量為s 的r 輪Trivium 算法的有向圖G。

算法2：有向圖算法getG

輸入：輪數(shù)r，根節(jié)點(diǎn)向量s

輸出：字典g，其中，鍵表示有向圖G 中的節(jié)點(diǎn)的變量下標(biāo)，鍵值表示鍵節(jié)點(diǎn)對(duì)應(yīng)的子節(jié)點(diǎn)的變量下標(biāo)

5 返回g

算法3 用于根據(jù)節(jié)點(diǎn)向量為s 的r 輪Trivium算法的有向圖G，得到其另一種等價(jià)表示。

算法3：有向圖等價(jià)表示算法getG′

輸入：字典g，其中，鍵表示有向圖G 中節(jié)點(diǎn)的變量下標(biāo)，鍵值表示鍵節(jié)點(diǎn)對(duì)應(yīng)的子節(jié)點(diǎn)的變量下標(biāo)

輸出：字典g′ ，其中，鍵表示有向圖G 中節(jié)點(diǎn)的變量下標(biāo)，鍵值表示鍵節(jié)點(diǎn)對(duì)應(yīng)的父節(jié)點(diǎn)的變量下標(biāo)

1 g′ =?

2 對(duì)g 中任意的鍵x，記其鍵值為 [ ]y g x= ， 對(duì)任意的z y∈ ，若g′ 中不含鍵z，則將鍵z 及鍵值x 放入g′ 中；若g′ 中已包含鍵z，則將x加入鍵z 的鍵值， [ ]g′ z x←

3 返回g′

算法4 用于得到根節(jié)點(diǎn)向量為s、葉子節(jié)點(diǎn)向量為l 的r 輪Trivium 算法的MILP 模型M。其中，葉子節(jié)點(diǎn)向量l 由立方變量集和非立方變量集決定，設(shè)cube 為立方變量集，ncube 為非

立方變量集，則0 ≤ j≤288，l 中的元素賦值為（其中*表示未知或待定值）：

算法4：建模算法getM

輸入：輪數(shù)r ，根節(jié)點(diǎn)向量s，葉子節(jié)點(diǎn)向量l

輸出：MILP 模型M

5 返回M

算法5：Trivium 算法的攻擊算法

輸入：攻擊輪數(shù)r，立方變量集cube，非立方變量集ncube

輸出：可行路徑數(shù)量sol

1 初始化起始根節(jié)點(diǎn)集合S、輪數(shù)步長(zhǎng)0r 和時(shí)間戳0t

起始根節(jié)點(diǎn)集合S 由密鑰流輸出函數(shù)得到，因輸出密鑰流比特由6 個(gè)狀態(tài)比特異或得到，故S 包含6 個(gè)元素。設(shè) S = { s0: 1, s1:1, s2:1, s3:1, s4:1, s5:1}，其中 s0， s1， s2， s3， s4， s5均為288 維、權(quán)重為1 的二進(jìn)制向量，s0[ 6 5 ] = 1 ，s1[92] = 1，s2[ 1 6 1 ] = 1 ，s3[ 1 7 6 ] = 1 ，s4[ 2 4 2 ] = 1 ，s5[ 2 8 7 ] = 1

設(shè)起始輪數(shù)步長(zhǎng)0r 為100，起始時(shí)間戳0t 為50 秒

2*S =?，對(duì)任意的根節(jié)點(diǎn)向量 S∈s ，建立 MILP 模型 M= getM ( r0, s, ?)，運(yùn)用Cplex 等求解工具求解出模型M 的所有解

記 s*為一個(gè)288 維布爾向量，令 0 ≤ x ≤ 287，如果x 是模型M 中的葉子節(jié)點(diǎn)下標(biāo)，若則 s*[ x ] =1，若則 s*[ x ] =0；如果x 不是模型M 中的葉子節(jié)點(diǎn)下標(biāo)，對(duì)應(yīng)的模型M 的可行解數(shù)量為 ns*，添加到*S 中

3 若 S**=?，對(duì)任意的根節(jié)點(diǎn)向量 s*∈S*， 建立模型，運(yùn)用Cplex 等求解工具在時(shí)間戳0t 內(nèi)求解模型*M 的所有解。若模型*M 無(wú)解，說(shuō)明沒(méi)有從向量l 到*s 的傳播路徑；若模型*M 有解，則求解出所有解，記l對(duì)應(yīng)的模型*M 的可行解數(shù)量為nl，則統(tǒng)計(jì)l 及其對(duì)應(yīng)的可行解數(shù)量為。若時(shí)間戳0t 內(nèi)無(wú)法得出模型*M 有無(wú)解或者沒(méi)有解出所有解，將添加到 S**中

4 若S**=?，則終止；否則，轉(zhuǎn)到步驟5

5 令 S = S**， r = r - r0，重新設(shè)置輪數(shù)步長(zhǎng)0r 和時(shí)間戳0t ，轉(zhuǎn)到步驟2

3 實(shí)驗(yàn)結(jié)果

攻擊實(shí)驗(yàn)采用的MILP 求解工具為IBM 的Cplex 軟件，版本號(hào)12.7.1。實(shí)驗(yàn)中采用5 臺(tái)聯(lián)想SR850 服務(wù)器并行求解模型，每臺(tái)服務(wù)器含兩個(gè)處理器，每臺(tái)處理器CPU 均為Inter Xeon Gold 5117（2.00 GHz），核 心 數(shù)28，內(nèi) 存256 GB。攻擊輪數(shù)0r 為845，攻擊中選取的立方變量集cube 和非立方變量集ncube 如表1 所示。

表1 選取的立方變量集和非立方變量集

輪數(shù)步長(zhǎng)0r 和時(shí)間戳0t 可以按照表2 進(jìn)行設(shè)置。

表2 輪數(shù)步長(zhǎng)和時(shí)間戳的設(shè)置

攻擊效果對(duì)比如表3 所示，可以看出，本文通過(guò)使用有向圖建模方法以及模型分解方法，恢復(fù)845 輪Trivium 算法的超級(jí)多項(xiàng)式的時(shí)間明顯減少。

表3 845 輪Trivium 算法立方攻擊效果對(duì)比

4 結(jié) 語(yǔ)

為提高Trivium 算法立方攻擊中恢復(fù)超級(jí)多項(xiàng)式的攻擊效率，本文提出了一種快速方法，結(jié)合了有向圖建模方法和模型分解方法，恢復(fù)845 輪Trivium 算法的超級(jí)多項(xiàng)式的時(shí)間明顯減少。后續(xù)將繼續(xù)研究這種立方攻擊方法的改進(jìn)及其在其他序列密碼算法上的應(yīng)用。