關(guān)于Trivium-型序列密碼代數(shù)次數(shù)估計(jì)的研究*

劉 晨, 田 甜

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

1 引言

序列密碼是對(duì)稱密碼的分支之一, 用于對(duì)傳輸數(shù)據(jù)的加密. 序列密碼的加密方式為密鑰流比特與明文比特異或加, 其中密鑰流由密鑰和公開的初始化向量生成. 目前面向硬件實(shí)現(xiàn)的序列密碼都采用基于非線性反饋移位寄存器(NFSR) 的設(shè)計(jì), 例如Trivium[1]、Grain[2]等. Trivium 是由de Cannière 和Preneel 設(shè)計(jì)的面向硬件實(shí)現(xiàn)的序列密碼, 是歐洲序列密碼征集項(xiàng)目eSTREAM 計(jì)劃的勝選算法之一. 并且, Trivium 已經(jīng)成為輕量級(jí)序列密碼算法的國(guó)際標(biāo)準(zhǔn)(ISO/IEC 29192-3:2012)[3]. Trivium 由一個(gè)二次非線性反饋移位寄存器和一個(gè)線性過濾函數(shù)構(gòu)成, 因其設(shè)計(jì)結(jié)構(gòu)簡(jiǎn)單, 受到國(guó)際學(xué)者的廣泛關(guān)注. 到目前為止, Trivium 可以抵抗已有的所有攻擊方法. 受Trivium 設(shè)計(jì)的啟發(fā), 一系列Trivium-型密碼算法被提出, 主要包括Kreyvium[4]和TriviA-SC[5].

對(duì)于Trivium-型算法, 立方攻擊(cube attacks)[6]是最有效的攻擊方法. 立方攻擊是由Dinur 和Shamir 在2009 年歐密會(huì)上提出的一種選擇IV 攻擊. 在立方攻擊中, 將輸出的密鑰流比特看成是關(guān)于密鑰變?cè)猭 和IV 變?cè)獀 的可調(diào)布爾函數(shù)f(k,v), 其核心思想是在選定的IV 取值集合上對(duì)函數(shù)f 的輸出求和從而對(duì)f 的代數(shù)正規(guī)型進(jìn)行簡(jiǎn)化, 得到低代數(shù)次數(shù)的密鑰變?cè)匠? 自從立方攻擊思想提出以后, 得到了一系列的發(fā)展, 包括實(shí)驗(yàn)立方攻擊[6–10]、相關(guān)立方攻擊[11]以及基于可分性質(zhì)的立方攻擊[12–15]等.在實(shí)驗(yàn)立方攻擊中, 攻擊者主要通過隨機(jī)檢測(cè)的方法對(duì)超多項(xiàng)式進(jìn)行線性和二次檢測(cè). 受限于立方變量的維數(shù), 對(duì)于Trivium 算法, 實(shí)驗(yàn)立方攻擊的最高輪數(shù)為802 輪[9]. 在相關(guān)立方攻擊中[11], Liu 利用超多項(xiàng)式和一些簡(jiǎn)單密鑰表達(dá)式之間的相關(guān)性給出了835-輪Trivium 的密鑰恢復(fù)攻擊. 2017 年美密會(huì)上由Todo 提出基于可分性的立方攻擊, 受益于可分性和MILP 工具, 攻擊者可以使用高維數(shù)的立方集, 這也進(jìn)一步提高了立方攻擊的效果. 例如, 在文[13] 中, 作者給出了891-輪Kreyvium 算法, 184-輪Grain-128a算法以及750-輪Acorn 算法的密鑰恢復(fù)攻擊.

另一方面, 在立方攻擊中, 如果發(fā)現(xiàn)超多項(xiàng)式是零常值多項(xiàng)式, 則可以進(jìn)行區(qū)分攻擊, 區(qū)分攻擊的輪數(shù)往往高于密鑰恢復(fù)攻擊. 常用的判斷零常值多項(xiàng)式的方法是對(duì)立方變量在f(k,v)中的代數(shù)次數(shù)進(jìn)行估計(jì).對(duì)于指標(biāo)集為I 的立方變量, 若變量集{vi|i ∈I} 在f(k,v) 中的代數(shù)次數(shù)小于|I|, 則以集合{vi|i ∈I}中變量為立方變量的超多項(xiàng)式是零常值. 對(duì)于高輪Trivium-型算法, 目前最有效的代數(shù)次數(shù)估計(jì)方法主要有Liu 提出的基于數(shù)值映射的方法[16]和Wang 等人給出的基于可分性的方法[13]. 基于數(shù)值映射的方法中, 利用數(shù)值映射的概念, 迭代計(jì)算每一個(gè)中間狀態(tài)比特的代數(shù)次數(shù)上界. 該方法的優(yōu)點(diǎn)是具有線性的時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度, 計(jì)算速度快. Wang 等人提出的基于可分性質(zhì)的估計(jì)方法是在Todo 給出的MILP 模型[12]的基礎(chǔ)上, 通過設(shè)置目標(biāo)函數(shù), 求解包含輸入變?cè)疃嗟捻?xiàng)以估計(jì)布爾函數(shù)的代數(shù)次數(shù).上述兩種估計(jì)代數(shù)次數(shù)的方法除了尋找零和區(qū)分器, 在密鑰恢復(fù)攻擊中也有重要應(yīng)用. 例如, 在相關(guān)立方攻擊[11]中, 搜索基多項(xiàng)式主要依靠對(duì)超多項(xiàng)式進(jìn)行代數(shù)次數(shù)估計(jì), 基多項(xiàng)式是超多項(xiàng)式的一部分, 用來還原密鑰信息; 在還原超多項(xiàng)式的代數(shù)方法中[14], 利用代數(shù)次數(shù)估計(jì)篩選有效立方集, 一個(gè)有效立方集的超多項(xiàng)式可以用代數(shù)的方法以概率1 還原; 在基于可分性的立方攻擊中[13], 估計(jì)超多項(xiàng)式的代數(shù)次數(shù)可以更精確的評(píng)估立方攻擊的理論復(fù)雜度.

針對(duì)Trivium-型算法, 本文對(duì)基于數(shù)值映射和基于可分性的兩種代數(shù)次數(shù)估計(jì)方法進(jìn)行了研究. 首先, 我們給出了對(duì)這兩種方法優(yōu)缺點(diǎn)的分析. 數(shù)值映射的效率高，但基于可分性的估計(jì)方法準(zhǔn)確性相對(duì)更好. 通過將這兩種方法結(jié)合, 我們給出一個(gè)改進(jìn)算法: 利用可分性對(duì)Trivium-型算法低輪更新比特進(jìn)行代數(shù)次數(shù)估計(jì), 然后利用基于數(shù)值映射的方法迭代估計(jì)高輪輸出比特的代數(shù)次數(shù). 改進(jìn)算法既可以基本保持?jǐn)?shù)值映射的效率，也可以提高代數(shù)次數(shù)估計(jì)的準(zhǔn)確性. 在Trivium-型的全變?cè)獥l件下, 通過應(yīng)用改進(jìn)算法,我們將Trivium 算法未達(dá)到次數(shù)為160 的最大輪數(shù)下界從907 輪改進(jìn)到了912 輪, 是目前已知的最優(yōu)結(jié)果. 此外, 關(guān)于三個(gè)Trivium-型算法, 即Trivium、Kreyvium 和TriviA-SC, 我們對(duì)隨機(jī)選擇的固定維數(shù)立方集進(jìn)行了代數(shù)次數(shù)估計(jì)的實(shí)驗(yàn). 實(shí)驗(yàn)表明, 與數(shù)值映射相比, 改進(jìn)后的算法能夠給出更優(yōu)的代數(shù)次數(shù)估計(jì)結(jié)果, 例如, 對(duì)于一個(gè)給定的立方集, 判斷其是零和區(qū)分器的輪數(shù)可平均提高20 輪以上.

本文剩余部分結(jié)構(gòu)安排如下: 第2 節(jié)為預(yù)備知識(shí). 第3 節(jié)主要介紹了兩種代數(shù)次數(shù)估計(jì)方法的優(yōu)缺點(diǎn), 并結(jié)合兩種方法, 給出了本文估計(jì)代數(shù)次數(shù)的具體算法. 第4 節(jié), 我們對(duì)Trivium-型算法進(jìn)行了實(shí)際的估計(jì), 并與之前的結(jié)果進(jìn)行了對(duì)比. 第5 節(jié)對(duì)全文進(jìn)行了總結(jié).

2 預(yù)備知識(shí)

2.1 Trivium-型算法介紹

Trivium-型算法主寄存器部分為Galois 非線性反饋移位寄存器, 每個(gè)時(shí)刻有三個(gè)比特通過不同的二次反饋函數(shù)更新, 其它的中間狀態(tài)比特則通過移位更新. 具體地, 令A(yù),B,C 分別表示長(zhǎng)度為nA,nB,nC的移位寄存器. 當(dāng)時(shí)刻t ≥0 時(shí), At= (xt,xt+1,··· ,xt+nA?1), Bt= (yt,yt+1,··· ,yt+nB?1), Ct=(zt,zt+1,··· ,zt+nC?1) 分別為寄存器A, B, C 在第t 時(shí)刻的狀態(tài), 且記第t 時(shí)刻Trivium-型算法的中間狀態(tài)為s(t)=(At,Bt,Ct). 狀態(tài)更新函數(shù)描述如下:

其中, lλ為線性函數(shù), 且1 ≤rλ≤nλ, λ ∈{A, B, C}. 記f 為輸出函數(shù), 經(jīng)過N 輪的初始化迭代之后,密碼算法對(duì)每一個(gè)t ≥N 計(jì)算f(s(t)), 輸出密鑰流比特.

Trivium-型算法包含Trivium, Kreyvium 以及TriviA-SC, 且初始化輪數(shù)均為1152 輪. 其中, Trivium 支持80 比特密鑰和80 比特IV; Kreyvium 是Trivium 的128 比特版本, 支持128 比特密鑰和128比特IV; TriviA-SC 也支持128 比特密鑰和128 比特IV. Kreyvium 除了三個(gè)寄存器A,B,C 以外, 還額外采用了兩個(gè)寄存器K?和V?用來分別存儲(chǔ)密鑰KEY 和IV, 并以異或加的方式不斷參與到反饋運(yùn)算中. 此外, Trivium 和Kreyvium 的輸出函數(shù)為線性布爾函數(shù), 而TriviA-SC 的輸出函數(shù)為二次布爾函數(shù). 具體算法見附錄B.

2.2 代數(shù)正規(guī)型與代數(shù)次數(shù)

其中wt(c) 為n 維向量c 的漢明重量, ac為ANF 的系數(shù).

2.3 立方檢測(cè)

設(shè)f ∈Bn, 給定指標(biāo)集I = {i1,i2,··· ,i|I|} ?{1,2,··· ,n}, 并記tI= xi1xi2···xi|I|, 根據(jù)f 中的項(xiàng)是否能夠被tI整除進(jìn)行分類, 可以將f 唯一地表示為

其中q 中的每一項(xiàng)都不是tI的倍式, ptI稱為f 關(guān)于指標(biāo)集I 的超多項(xiàng)式, 并稱由指標(biāo)集I 確定的變?cè)螩I= {xi1,xi2,··· ,xi|I|} 為立方變?cè)? xij∈CI稱為一個(gè)立方變?cè)? 遍歷CI中變?cè)?|I|種可能取值, 對(duì)函數(shù)f(x1,x2,··· ,xn) 求和可得

在序列密碼分析中, 函數(shù)f(x1,x2,··· ,xn) 是輸出比特關(guān)于密鑰變?cè)虸V 變?cè)牟紶柡瘮?shù). 由于在初始化階段經(jīng)過了多輪非線性迭代, 函數(shù)f(x1,x2,··· ,xn) 的代數(shù)正規(guī)型是未知的, 從而超多項(xiàng)式的代數(shù)正規(guī)型也是未知的. 立方檢測(cè)的基本思想是選取立方指標(biāo)集I, 在遍歷立方變?cè)乃锌赡苋≈狄约胺橇⒎阶冊(cè)潭槌Ｖ档臈l件下, 對(duì)超多項(xiàng)式ptI的代數(shù)性質(zhì)進(jìn)行檢測(cè), 例如平衡性、代數(shù)次數(shù)、每個(gè)變?cè)欠癯霈F(xiàn)等, 從而能夠使輸出函數(shù)f 和隨機(jī)函數(shù)進(jìn)行區(qū)分. 特別地, 通過代數(shù)次數(shù)估計(jì)的方法可以判斷零常值超多項(xiàng)式, 即若deg(f) < |I| 時(shí), 則超多項(xiàng)式ptI一定是零常值多項(xiàng)式. 零常值多項(xiàng)式是概率1 成立的區(qū)分器, 也稱為零和立方區(qū)分器.

2.4 基于比特的可分性與MILP 建模

基于比特的可分性 2015 年歐密會(huì)上, Todo 首次提出分組密碼的可分性概念[17], 針對(duì)基于S 盒設(shè)計(jì)的分組密碼, 描述了可分性質(zhì)關(guān)于輪函數(shù)中一些基本運(yùn)算的擴(kuò)散規(guī)則, 從而由明文可分性質(zhì)可以迭代求解密文的可分性質(zhì), 獲得積分區(qū)分器. 2015 年, Todo 利用可分性質(zhì)得到MISTY1 算法6 輪積分區(qū)分器[18],并給出MISTY1 首個(gè)全輪的理論攻擊. 之后, 2016 年FSE 會(huì)議上, 針對(duì)基于比特運(yùn)算設(shè)計(jì)的SIMON 算法, Todo 和Morii 進(jìn)一步提出基于比特的可分性[19]. 基于比特的可分性定義如下:

2016 年亞密會(huì)上, Xiang 等首次將混合整數(shù)線性規(guī)劃(MILP) 建模方法引入到輕量級(jí)分組密碼可分路徑的搜索[20], 大大提高了可分路徑搜索的效率.

混合整數(shù)線性規(guī)劃問題(MILP) 混合整數(shù)線性規(guī)劃問題是通過建立整系數(shù)不等式方程組, 求解符合條件的最優(yōu)整數(shù)解問題, 其中模型M 包含模型變量M.var, 模型限制條件M.con 以及模型的目標(biāo)函數(shù)M.obj. 通過求解MILP 模型, MILP 將返回最優(yōu)解或者無解; 若模型沒有目標(biāo)函數(shù), 則只返回模型是否可解. 目前對(duì)于MILP 模型的求解, 主要依賴于Gurobi 和CPLEX 等求解器.

基于比特可分性的MILP 模型 在文[20] 中, Xiang 等將可分性關(guān)于copy, xor, and 的傳播規(guī)則轉(zhuǎn)化為MILP 模型, 利用MILP 求解器對(duì)模型進(jìn)行求解. 若模型可解, 則可以得到滿足條件的一條可分路徑, 若模型無解, 則可以說明不存在滿足條件的可分路徑.

2017 年美密會(huì)上, Todo 首次將基于比特的可分性引入到了序列密碼分析中, 并給出了可分性質(zhì)在序列密碼中的傳播規(guī)則和MILP 建模, 具體參見文[12]. Todo 等人[12]給出了一個(gè)重要的引理, 見引理1.

通過引理1 可以得到文[12] 中的命題4. 基于引理1 和命題4, Todo 首次給出了基于可分性的立方攻擊. 隨后, 文[13] 對(duì)基于比特可分性的MILP 模型進(jìn)行了改進(jìn). 特別地, flag 技術(shù)的提出使得攻擊者能更準(zhǔn)確的描述可分性的傳播. 在flag 技術(shù)中, 通過對(duì)每個(gè)狀態(tài)比特增加標(biāo)識(shí)var.flag ∈{0c,1c,δ}, 分別標(biāo)記狀態(tài)比特為常值0、常值1 和變量δ, 并根據(jù)狀態(tài)比特的標(biāo)識(shí)修正可分性的傳播. 標(biāo)識(shí)var.flag 的運(yùn)算規(guī)則如下:

記改進(jìn)的比特運(yùn)算分別為copyf, xorf, andf, 此時(shí)其MILP 模型描述如下.

注1 性質(zhì)3 中的限制條件存在冗余, 但并不妨礙得到正確的結(jié)果.

2.5 主要的代數(shù)次數(shù)估計(jì)方法

基于數(shù)值映射的代數(shù)次數(shù)估計(jì) 針對(duì)內(nèi)部狀態(tài)更新采用NFSR 的序列密碼, 文[16] 提出了基于數(shù)值映射的代數(shù)次數(shù)估計(jì)方法, 并實(shí)際應(yīng)用于Trivium-型序列密碼, 對(duì)一些立方變?cè)玫搅吮容^好的估計(jì)結(jié)果. 數(shù)值映射的定義描述如下:

定義2 (數(shù)值映射) 設(shè)f(x1,x2,··· ,xn)∈Bn為n 元布爾函數(shù), 存在如下映射, 記為DEG:

其中D =(d1,d2,··· ,dn)∈Zn為n 維向量, 且ac為上述f 的代數(shù)正規(guī)型的系數(shù).

記G = (g1,g2,··· ,gn) 為n 元向量布爾函數(shù), 并且令deg(G) = (deg(g1),deg (g2),··· ,deg (gn)),根據(jù)映射的性質(zhì)易知

這表明通過數(shù)值映射估計(jì)的代數(shù)次數(shù)大于等于實(shí)際的代數(shù)次數(shù), 并且容易證明下述性質(zhì)4 成立.

性質(zhì)4 若給定的n 維向量D =(d1,d2,··· ,dn) 滿足deg (gi)≤di, 1 ≤i ≤n, 則有

由性質(zhì)4 可知, 利用數(shù)值映射估計(jì)的代數(shù)次數(shù)是實(shí)際代數(shù)次數(shù)的一個(gè)上界. 為了方便描述, 我們記復(fù)合函數(shù)h=f ?G 的數(shù)值映射為DEG(h)?=DEG(f,deg (G)).

基于可分性質(zhì)的代數(shù)次數(shù)估計(jì) Todo 等提出的基于可分性的立方攻擊, 其核心思想是選擇合適的指標(biāo)集I, 在給定輪數(shù)下, 利用可分性確定輸出比特的超多項(xiàng)式ptI中包含的密鑰變?cè)? 這些密鑰變?cè)獦?gòu)成集合J. 然后, 通過計(jì)算真值表恢復(fù)超多項(xiàng)式以建立代數(shù)方程組, 從而恢復(fù)密鑰變?cè)? 但是在實(shí)際攻擊過程中, 該攻擊受到指標(biāo)集I 和集合J 大小的限制, 當(dāng)|I|+|J| ≥n 時(shí), 該攻擊沒有意義. 因此, 為了保證攻擊的有效性, 文[12] 提出了關(guān)于立方攻擊的兩個(gè)假設(shè), 但在Trivium-型算法初始化輪數(shù)較高時(shí)并不能驗(yàn)證其合理性. 為此, 在文[13] 中, Wang 等針對(duì)上述不足對(duì)基于可分性的立方攻擊進(jìn)行了改進(jìn). 在提出flag技術(shù)的同時(shí), Wang 等將文[12] 中的命題4 進(jìn)行了一般化的推廣, 得到了命題1.

根據(jù)命題1, 針對(duì)Trivium-型序列密碼, 文[13] 給出了建立帶flag 技術(shù)的MILP 模型的算法Algorithm 4. 同時(shí), 作者給出了基于可分性的估計(jì)代數(shù)次數(shù)的算法Algorithm 2, 將可分性質(zhì)引入到了估計(jì)代數(shù)次數(shù)的問題中. 為了使Algorithm 2 能夠?qū)Ω卤忍剡M(jìn)行代數(shù)次數(shù)估計(jì), 本文將Algorithm 4 中的限制語句進(jìn)行了修改. 為了敘述的簡(jiǎn)潔, 本文約定用“可分性方法” 來簡(jiǎn)稱“基于可分性質(zhì)的代數(shù)次數(shù)估計(jì)的方法”, 且為了本文算法描述的簡(jiǎn)潔性, 記DegEval(I,r,flagλ) 為利用可分性方法對(duì)給定輪數(shù)r 的更新比特進(jìn)行估計(jì), 其中flagλ為更新比特的位置, I 為輸入變?cè)闹笜?biāo)集.

3 Trivium-型算法代數(shù)次數(shù)估計(jì)的改進(jìn)

在本節(jié)中, 我們首先分析了數(shù)值映射方法和可分性方法這兩種估計(jì)代數(shù)次數(shù)方法的優(yōu)缺點(diǎn), 并通過具體的實(shí)例展示了兩種方法中存在的不足. 隨后針對(duì)Trivium-型算法, 通過將這兩種方法進(jìn)行結(jié)合, 我們?cè)?.2 節(jié)中給出了一個(gè)改進(jìn)的估計(jì)代數(shù)次數(shù)的算法. 此外, 基于改進(jìn)后的算法, 我們?cè)?.3 節(jié)中給出了一個(gè)搜索零和區(qū)分器的算法.

3.1 兩種代數(shù)次數(shù)估計(jì)方法的優(yōu)缺點(diǎn)

針對(duì)同一加密算法, 兩種方法各有優(yōu)勢(shì), 同時(shí)也有一定的局限性. 相比于可分性方法, 線性的時(shí)間復(fù)雜度和存儲(chǔ)復(fù)雜度是數(shù)值映射所具有的優(yōu)勢(shì). 可以對(duì)給定立方集, 快速給出輸出比特的次數(shù)上界, 且沒有輪數(shù)的限制, 即使對(duì)初始化輪數(shù)較高的輸出比特也能夠快速給出估計(jì). 但是利用數(shù)值映射對(duì)代數(shù)次數(shù)進(jìn)行迭代估計(jì)時(shí), 會(huì)產(chǎn)生以下幾個(gè)問題, 以例1 為例.

例1 現(xiàn)設(shè)有4-bit NFSR, 其更新函數(shù)為f(x1,x2,x3,x4) = x1x2+x3x4, 記序列的初態(tài)為s(0)=(s0,s1,s2,s3), 并記第t 時(shí)刻的狀態(tài)為s(t)= (st,st+1,st+2,st+3). 根據(jù)更新函數(shù)計(jì)算可得s4= s0s1+s2s3,s5=s1s2+s2s3+s0s1s3,s6=s2s3+(s0s1+s2s3)(s1s2+s2s3+s0s1s3)=s0s1s2+s0s1s3+s1s2s3.而利用數(shù)值映射對(duì)s6進(jìn)行代數(shù)次數(shù)估計(jì)的結(jié)果為5.

通過例子可以看出, 估計(jì)結(jié)果偏高的原因?yàn)?

(1) 不能處理兩個(gè)含有相同變?cè)捻?xiàng)相乘時(shí)重復(fù)變?cè)?jì)數(shù)的問題. 例1 中, s4的兩個(gè)單項(xiàng)式分別與s5中的最高次項(xiàng)s0s1s3有相同的變?cè)猻0和s1, 因此在實(shí)際計(jì)算時(shí), 并不會(huì)出現(xiàn)5 次項(xiàng), 但數(shù)值映射方法并不能處理這樣的情況.

(2) 不能解決多項(xiàng)式中的消項(xiàng)問題. 計(jì)算過程中, s6的表達(dá)式中單項(xiàng)式s0s1s2s3出現(xiàn)了兩次, 但數(shù)值映射方法同樣無法解決這樣的問題.

(3) 迭代導(dǎo)致的估計(jì)偏差的累積. 對(duì)s7進(jìn)行估計(jì)時(shí), 利用了s6的次數(shù)估計(jì), 顯然會(huì)使得估計(jì)結(jié)果繼續(xù)偏高.

此外, 實(shí)際應(yīng)用數(shù)值映射方法對(duì)Trivium-型算法進(jìn)行代數(shù)次數(shù)估計(jì)時(shí), 可以發(fā)現(xiàn): 由于Trivium-型算法具有反饋函數(shù)二次項(xiàng)是相鄰比特相乘的特點(diǎn), 數(shù)值映射對(duì)于不包含相鄰變量的情形估計(jì)效果很好, 對(duì)于含有相鄰變量的情形估計(jì)效果較差, 例如在文[16] 中, 對(duì)于Trivium 算法, 作者檢測(cè)了所有37 維到40 維不相鄰的立方變量集. 而這一實(shí)驗(yàn)型現(xiàn)象主要是因?yàn)閿?shù)值映射不能處理兩個(gè)含有相同變?cè)捻?xiàng)相乘時(shí)重復(fù)變?cè)?jì)數(shù)的問題.

可分性方法可以有效解決上述第1 個(gè)和第3 個(gè)問題. 因此相比于數(shù)值映射方法, 可分性方法給出的次數(shù)上界更緊. 但是可分性的傳播規(guī)則和對(duì)MILP 模型的求解, 同樣使得可分性方法存在以下兩個(gè)問題:

(1) 不能解決多項(xiàng)式中的消項(xiàng)問題.

(2) 隨著初始化輪數(shù)的增加, MILP 模型中的變?cè)拖拗茥l件大幅增加, 當(dāng)初始化輪數(shù)較高時(shí), 普通PC 機(jī)求解MILP 模型是困難的.

通過分析可以看出, 在初始化輪數(shù)較低時(shí), 可分性方法能夠給出比數(shù)值映射方法更加準(zhǔn)確的次數(shù)上界;當(dāng)初始化輪數(shù)較高時(shí), 用可分性方法估計(jì)代數(shù)次數(shù)是困難的, 但此時(shí)數(shù)值映射方法可以快速給出較為準(zhǔn)確的次數(shù)估計(jì). 因此, 針對(duì)Trivium-型算法, 本文通過結(jié)合兩種方法的優(yōu)勢(shì), 能夠?qū)θ我饨o定的立方集, 在初始化輪數(shù)較高的情況下, 給出比數(shù)值映射方法更加準(zhǔn)確的結(jié)果.

3.2 對(duì)Trivium-型算法的代數(shù)次數(shù)估計(jì)

對(duì)于立方攻擊以及與立方攻擊相關(guān)的分析方法, 都需要進(jìn)行大量的測(cè)試才能找到合適的立方集, 所以有效的時(shí)間內(nèi)檢測(cè)立方集的數(shù)量也是攻擊成功的一個(gè)因素. 針對(duì)Trivium-型算法, 為了能夠在有效時(shí)間內(nèi)對(duì)初始化輪數(shù)較高的輸出比特進(jìn)行代數(shù)次數(shù)估計(jì), 我們主要采用數(shù)值映射方法. 在實(shí)際估計(jì)過程中, 我們采用了文[16] 中提出的針對(duì)Trivium-型算法優(yōu)化后的方法. 在該方法中, 對(duì)于i 時(shí)刻更新比特的次數(shù)上界是基于前nA+nC?3 個(gè)時(shí)刻更新比特的次數(shù)來進(jìn)行估計(jì)的, 其中nA和nC分別是寄存器A 和寄存器C 的長(zhǎng)度. 由于數(shù)值映射對(duì)估計(jì)偏差有累加的效果, 參見第3.1 節(jié)分析, 早期更新比特的代數(shù)次數(shù)上界估計(jì)越準(zhǔn)確, 其最終的估計(jì)結(jié)果也就越準(zhǔn)確. 值得注意的是, 基于可分性的估計(jì)方法能夠給出更緊的次數(shù)上界. 同時(shí), 當(dāng)初始化輪數(shù)較低時(shí), 可分性方法能夠快速的給出更新比特的代數(shù)次數(shù)的上界. 因此, 為利用數(shù)值映射方法給出更緊的上界, 我們基于可分性方法對(duì)于早期的更新比特的代數(shù)次數(shù)上界進(jìn)行了估計(jì). 具體過程描述如下:

(1) 對(duì)給定的指標(biāo)集I 確定多項(xiàng)式的變?cè)? 并選取合適的l 和h, 使得t = l + h, 且滿足k?=l ?(nC?2)?(nA?2)≥1;

(2) 利用可分性方法, 對(duì)從第k 時(shí)刻到第l 時(shí)刻的更新比特進(jìn)行次數(shù)估計(jì), 并保存結(jié)果;

(3) 將(2) 中所估計(jì)的代數(shù)次數(shù)用于數(shù)值映射的初始化, 并用數(shù)值映射方法對(duì)從l 時(shí)刻的更新比特進(jìn)行估計(jì), 最終給出輸出比特s(N)out的次數(shù)上界.

現(xiàn)對(duì)具體的估計(jì)過程給出算法1.

算法1 代數(shù)次數(shù)估計(jì)Input: 給定輪數(shù)N; h; 指標(biāo)集I;Output: s(N)out 的代數(shù)次數(shù)估計(jì).1 endround ←h 2 startround ←endround ?nA ?nC +3 3 for t ←startround to endround do 4 for λ ∈{A,B,C} do λ ←DegEval(I,t,flagλ);6 end 7 end 8 D(endround)←(d(endround?nA+1)5 d(t)A ,···,d(endround)A ,d(endround?nB+1)B ,···,d(endround)B ,d(endround?nC+1)C ,··· ,d(endround)C );9 for t ←endround+1 to N do 10 for λ ∈{A,B,C} do λ ←max {DegMul(g(t)λ ),DEG(lλ,D(t?1))};12 end 13 D(t) ←(d(t?nA+1)11 d(t)A ,··· ,d(t)A ,d(t?nB+1)B ,··· ,d(t)B ,d(t?nC+1)C ,··· ,d(t)C );14 end 15 return DEG(f,D(N));

命題2 在給定指標(biāo)集I, 輪數(shù)N, 參數(shù)h, 算法1 的輸出為N-輪Trivium-型算法輸出比特的一個(gè)代數(shù)次數(shù)上界.

其中s(t)為第t 時(shí)刻的中間狀態(tài), D(t)為由dλ構(gòu)造的第t 時(shí)刻中間狀態(tài)的代數(shù)次數(shù). 又由數(shù)值映射的性質(zhì)可知, 若給定的輸入變?cè)拇鷶?shù)次數(shù)大于等于實(shí)際代數(shù)次數(shù), 則估計(jì)的輸出比特的代數(shù)次數(shù)也大于等于實(shí)際次數(shù). 綜上, 算法1 給出的輸出比特的代數(shù)次數(shù)一定為實(shí)際次數(shù)的上界.

命題2 可以保證, 算法1 能夠用來估計(jì)給定指標(biāo)集I 和初始化輪數(shù)為r 的Trivium-型算法的代數(shù)次數(shù)的上界. 并且可以看出, h 越大, 數(shù)值映射方法的初始化值就越準(zhǔn)確, 迭代的輪數(shù)也越少, 但是所需時(shí)間就越長(zhǎng).

3.3 搜索給定指標(biāo)集I 下的零和立方區(qū)分器

利用算法1 給出的代數(shù)次數(shù)上界,我們可以搜索給定指標(biāo)集I 下的零和立方區(qū)分器. 具體見算法2. 通過分析算法1 可知, DEG(f,D(t)) 給出的值為t 時(shí)刻輸出比特的代數(shù)次數(shù)上界. 因此, 算法2 能夠保證, 在給定指標(biāo)集I 下, Trivium-型算法在第maxround 輪一定存在關(guān)于該指標(biāo)集I 的零和立方區(qū)分器.

算法2 給定指標(biāo)集I 下的零和立方區(qū)分器搜索算法Input: 初始化輪數(shù)N; 輪數(shù)h; 指標(biāo)集I Output: 給定指標(biāo)集I 下, 能夠構(gòu)造的零和立方區(qū)分器的最大輪數(shù)maxround 1 endround ←h;2 maxround ←1;3 upperbound ←#I;4 startround ←endround ?nA ?nC +3;5 for t ←startround to endround do λ ←DegEval(I,t,flagλ);8 end 9 end 10 D(endround) ←(d(endround?nA+1)6 for λ ∈{A,B,C} do 7 d(t)A ,··· ,d(endround)A ,d(endround?nB+1)B ,··· ,d(endround)B ,d(endround?nC+1)C ,··· ,d(endround)C );11 for t ←endround+1 to N do 12 for λ ∈{A,B,C} do 13 d(t)λ ←max {DegMul(g(t)λ ),DEG(lλ,D(t?1))};14 end 15 D(t) ←(d(t?nA+1)A ,··· ,d(t)A ,d(t?nB+1)B ,··· ,d(t)B ,d(t?nC+1)C ,··· ,d(t)C );16 if DEG(f,D(t)) < upperbound then 17 maxround ←t ?1;18 end 19 end 20 return maxround;

4 應(yīng)用

4.1 Trivium-型算法全變?cè)拇鷶?shù)次數(shù)估計(jì)

本節(jié)將IV 變?cè)狪V 和密鑰變?cè)狵EY 均作為輸入變?cè)? 并利用本文方法對(duì)Trivium、Kreyvium和TriviA-SC 進(jìn)行實(shí)驗(yàn), 檢測(cè)在全變?cè)臈l件下, Trivium-型算法在何時(shí)能夠充分混合, 達(dá)到代數(shù)次數(shù)為#IV+#KEY. 雖然對(duì)于全變?cè)獥l件下的代數(shù)次數(shù)估計(jì)結(jié)果不能直接用于攻擊, 但其從代數(shù)次數(shù)的角度衡量了密鑰變?cè)虸V 變?cè)诔跏蓟^程中混合的速度和程度, 對(duì)于評(píng)估算法的安全性具有一定意義.

根據(jù)文[16] 中的結(jié)果, 將Trivium 的160 比特變?cè)鳛檩斎胱冊(cè)? 其未達(dá)到代數(shù)次數(shù)為160 的最大輪數(shù)下界為907, 這也是目前最新的結(jié)果. 我們通過實(shí)驗(yàn)嘗試, 最終選擇l =601, 計(jì)算可得k =400, 即首先利用可分性方法對(duì)Trivium 的400 到601 輪的更新比特進(jìn)行代數(shù)次數(shù)估計(jì). 利用算法2, 我們給出的下界為912. 與數(shù)值映射方法給出的結(jié)果相比, 我們對(duì)代數(shù)次數(shù)的估計(jì)更精確. 算法2 在利用了可分性優(yōu)勢(shì)的同時(shí), 保證了代數(shù)次數(shù)估計(jì)的效率. 由于所需時(shí)間太長(zhǎng), 可分性估計(jì)方法無法對(duì)全變?cè)拇鷶?shù)次數(shù)進(jìn)行估計(jì), 目前也沒有關(guān)于可分性對(duì)全變?cè)M(jìn)行代數(shù)次數(shù)估計(jì)的公開結(jié)果.

類似地, 我們還對(duì)Kreyvium 和TriviA-SC(v2) 進(jìn)行了實(shí)驗(yàn), 現(xiàn)將實(shí)驗(yàn)結(jié)果展示在表1 中.

表1 Trivium-型算法在KEY 和IV 全變?cè)獥l件下未達(dá)到代數(shù)次數(shù)為#KEY+#IV 的最大輪數(shù)下界Table 1 A lower bound for the maximum number of rounds of not achieving the algebraic degree # KEY+# IV for Trivium-like ciphers with all KEY and IV variables

4.2 關(guān)于Trivium 代數(shù)次數(shù)估計(jì)結(jié)果

針對(duì)Trivium 算法, 本節(jié)對(duì)算法2 和數(shù)值映射的估計(jì)結(jié)果進(jìn)行了比較.

首先, 測(cè)試了隨機(jī)選擇的100 組48 維立方集CI. 將48 比特的立方變?cè)鳛楦潞瘮?shù)和輸出函數(shù)的輸入變?cè)? 利用算法2, 我們?cè)诮o定立方集下, 給出了零和立方區(qū)分器能夠達(dá)到的最高輪數(shù)的估計(jì). 同時(shí),我們對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì), 并與數(shù)值映射方法進(jìn)行了對(duì)比, 具體結(jié)果參見表2.

表2 關(guān)于100 組48 維立方集, 算法2 與數(shù)值映射方法關(guān)于Trivium 估計(jì)結(jié)果的比較Table 2 Comparison of Algorithm 2 and numeric mapping method for Trivium under 100 cubes of dimension 48

從表2 可以看出, 對(duì)任意給定的立方集, 算法2 對(duì)代數(shù)次數(shù)的估計(jì)更加準(zhǔn)確, 所得零和立方區(qū)分器的輪數(shù)更高, 平均能夠提高33 輪, 最高能夠提高52 輪(具體立方集見附錄A). 在實(shí)際估計(jì)過程中, 與可分性方法相比, 本節(jié)使用的方法速度更快, 能夠?qū)Ω嗟牧⒎郊M(jìn)行估計(jì).

其次, 測(cè)試了隨機(jī)選擇的100 組39 維的立方集, 利用算法2 對(duì)其進(jìn)行實(shí)驗(yàn)檢測(cè). 同樣, 我們將所得結(jié)果與數(shù)值映射方法的結(jié)果進(jìn)行了對(duì)比, 具體結(jié)果參見表3.

表3 關(guān)于100 組39 維立方集, 算法2 相較于數(shù)值映射方法的提升效果Table 3 Comparison of Algorithm 2 and numeric mapping method for Trivium under 100 cubes of dimension 39

從表3 可以看出, 對(duì)隨機(jī)選取的100 個(gè)39 維立方集, 算法2 同樣能夠給出更優(yōu)的零和立方區(qū)分器, 平均提高36 輪, 最多提高58 輪(見附錄A), 并且在隨機(jī)實(shí)驗(yàn)中, 最高給出了821 輪的零和區(qū)分器.

4.3 關(guān)于Kreyvium 代數(shù)次數(shù)估計(jì)結(jié)果

針對(duì)Kreyvium 算法, 本節(jié)隨機(jī)選取了100 組72 維的立方集. 將72 比特立方變?cè)鳛楦潞瘮?shù)和輸出函數(shù)的輸入變?cè)? 并利用算法2, 在給定立方集下對(duì)零和區(qū)分器能夠達(dá)到的最高輪數(shù)進(jìn)行估計(jì), 并與數(shù)值映射方法進(jìn)行比較. 統(tǒng)計(jì)結(jié)果如表4 所示.

表4 算法2 與數(shù)值映射方法關(guān)于Kreyvium 估計(jì)結(jié)果的比較Table 4 Comparison of Algorithm 2 and numeric mapping method for Kreyvium

通過實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果可以看出, 在給定立方集下, 對(duì)于Kreyvium, 算法2 同樣能夠給出比數(shù)值映射方法更準(zhǔn)確的次數(shù)估計(jì), 找到更高輪數(shù)的零和區(qū)分器. 其中, 最大輪數(shù)的零和區(qū)分器為844 輪, 平均能夠提高22 輪, 且提升輪數(shù)最高的為39 (見附錄A). 但由于Kreyvium 算法結(jié)構(gòu)的原因, 在使用可分性方法對(duì)其400 到601 輪更新比特進(jìn)行代數(shù)次數(shù)估計(jì)時(shí), 所需時(shí)間較長(zhǎng). 盡管如此, 所需時(shí)間依舊遠(yuǎn)少于可分性方法.

4.4 關(guān)于TriviA-SC 代數(shù)次數(shù)估計(jì)結(jié)果

針對(duì)TRIVIA-SC(v2) 算法, 本文同樣隨機(jī)選取了100 組72 維的立方集, 利用算法2 估計(jì)零和區(qū)分器的最大輪數(shù), 與數(shù)值映射方法的比較見表5.

表5 算法2 與數(shù)值映射方法關(guān)于Kreyvium 估計(jì)結(jié)果的比較Table 5 Comparison of Algorithm 2 and numeric mapping method for Kreyvium

由表5 結(jié)果可以看出, 算法2 同樣給出了TriviA-SC(v2) 更優(yōu)的零和區(qū)分器, 在隨機(jī)情況下能夠找到的最高輪數(shù)為914, 并且與數(shù)值映射方法相比, 平均提升的輪數(shù)為20 輪, 其中提升輪數(shù)最多的為37 輪(見附錄A). 因此, 相比于數(shù)值映射方法, 算法2 搜索零和區(qū)分器的能力更強(qiáng). 同時(shí), 盡管與Kreyvium 相比,TriviA-SC(v2) 使用了更長(zhǎng)的中間狀態(tài), 但是在同樣72 維的條件下, 利用可分性方法對(duì)TriviA-SC(v2) 前期更新比特進(jìn)行代數(shù)次數(shù)估計(jì)時(shí), 所需時(shí)間少于Kreyvium.

5 結(jié)論

對(duì)于Trivium-型算法的代數(shù)次數(shù)估計(jì), 目前最有效的兩個(gè)方法分別是數(shù)值映射方法和可分性方法. 本文主要通過分析兩種估計(jì)方法的優(yōu)勢(shì)和劣勢(shì), 對(duì)Trivium-型算法的代數(shù)次數(shù)估計(jì)方法進(jìn)行了改進(jìn): 利用可分性方法對(duì)低輪數(shù)內(nèi)部狀態(tài)的代數(shù)次數(shù)進(jìn)行了估計(jì), 作為數(shù)值映射的初始化值. 在本文中, 我們對(duì)隨機(jī)選取的立方集進(jìn)行了實(shí)驗(yàn). 實(shí)驗(yàn)結(jié)果表明: 與數(shù)值映射方法相比, 改進(jìn)后的方法給出的零和區(qū)分器輪數(shù)更高;而且與可分性相比, 改進(jìn)后的方法效率更高. 因此, 改進(jìn)后的方法能夠?qū)Ω嗑S數(shù)更高的立方集進(jìn)行搜索,在隨機(jī)情況下, 更容易找到高輪數(shù)的零和區(qū)分器. 特別地, 對(duì)Trivium-型算法全變?cè)那樾? 利用改進(jìn)后的方法, 我們給出了優(yōu)于數(shù)值映射的新結(jié)果. 雖然本文使用的方法實(shí)際是對(duì)數(shù)值映射和可分性方法的折中,但對(duì)于在立方攻擊中提高大維數(shù)立方超多項(xiàng)式代數(shù)次數(shù)估計(jì)的效率仍有一定的意義.