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

劉 晨, 田 甜

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

1 引言

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

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

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

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

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

2 預備知識

2.1 Trivium-型算法介紹

Trivium-型算法主寄存器部分為Galois 非線性反饋移位寄存器, 每個時刻有三個比特通過不同的二次反饋函數(shù)更新, 其它的中間狀態(tài)比特則通過移位更新. 具體地, 令A,B,C 分別表示長度為nA,nB,nC的移位寄存器. 當時刻t ≥0 時, 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 時刻的狀態(tài), 且記第t 時刻Trivium-型算法的中間狀態(tài)為s(t)=(At,Bt,Ct). 狀態(tài)更新函數(shù)描述如下:

其中, lλ為線性函數(shù), 且1 ≤rλ≤nλ, λ ∈{A, B, C}. 記f 為輸出函數(shù), 經(jīng)過N 輪的初始化迭代之后,密碼算法對每一個t ≥N 計算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 除了三個寄存器A,B,C 以外, 還額外采用了兩個寄存器K?和V?用來分別存儲密鑰KEY 和IV, 并以異或加的方式不斷參與到反饋運算中. 此外, Trivium 和Kreyvium 的輸出函數(shù)為線性布爾函數(shù), 而TriviA-SC 的輸出函數(shù)為二次布爾函數(shù). 具體算法見附錄B.

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

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

2.3 立方檢測

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

其中q 中的每一項都不是tI的倍式, ptI稱為f 關(guān)于指標集I 的超多項式, 并稱由指標集I 確定的變元集合CI= {xi1,xi2,··· ,xi|I|} 為立方變元集, xij∈CI稱為一個立方變元. 遍歷CI中變元所有2|I|種可能取值, 對函數(shù)f(x1,x2,··· ,xn) 求和可得

在序列密碼分析中, 函數(shù)f(x1,x2,··· ,xn) 是輸出比特關(guān)于密鑰變元和IV 變元的布爾函數(shù). 由于在初始化階段經(jīng)過了多輪非線性迭代, 函數(shù)f(x1,x2,··· ,xn) 的代數(shù)正規(guī)型是未知的, 從而超多項式的代數(shù)正規(guī)型也是未知的. 立方檢測的基本思想是選取立方指標集I, 在遍歷立方變元的所有可能取值以及非立方變元固定為常值的條件下, 對超多項式ptI的代數(shù)性質(zhì)進行檢測, 例如平衡性、代數(shù)次數(shù)、每個變元是否出現(xiàn)等, 從而能夠使輸出函數(shù)f 和隨機函數(shù)進行區(qū)分. 特別地, 通過代數(shù)次數(shù)估計的方法可以判斷零常值超多項式, 即若deg(f) < |I| 時, 則超多項式ptI一定是零常值多項式. 零常值多項式是概率1 成立的區(qū)分器, 也稱為零和立方區(qū)分器.

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

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

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

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

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

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

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

記改進的比特運算分別為copyf, xorf, andf, 此時其MILP 模型描述如下.

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

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

基于數(shù)值映射的代數(shù)次數(shù)估計 針對內(nèi)部狀態(tài)更新采用NFSR 的序列密碼, 文[16] 提出了基于數(shù)值映射的代數(shù)次數(shù)估計方法, 并實際應用于Trivium-型序列密碼, 對一些立方變元集得到了比較好的估計結(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ù)值映射估計的代數(shù)次數(shù)大于等于實際的代數(shù)次數(shù), 并且容易證明下述性質(zhì)4 成立.

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

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

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

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

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

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

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

針對同一加密算法, 兩種方法各有優(yōu)勢, 同時也有一定的局限性. 相比于可分性方法, 線性的時間復雜度和存儲復雜度是數(shù)值映射所具有的優(yōu)勢. 可以對給定立方集, 快速給出輸出比特的次數(shù)上界, 且沒有輪數(shù)的限制, 即使對初始化輪數(shù)較高的輸出比特也能夠快速給出估計. 但是利用數(shù)值映射對代數(shù)次數(shù)進行迭代估計時, 會產(chǎn)生以下幾個問題, 以例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 時刻的狀態(tài)為s(t)= (st,st+1,st+2,st+3). 根據(jù)更新函數(shù)計算可得s4= s0s1+s2s3,s5=s1s2+s2s3+s0s1s3,s6=s2s3+(s0s1+s2s3)(s1s2+s2s3+s0s1s3)=s0s1s2+s0s1s3+s1s2s3.而利用數(shù)值映射對s6進行代數(shù)次數(shù)估計的結(jié)果為5.

通過例子可以看出, 估計結(jié)果偏高的原因為:

(1) 不能處理兩個含有相同變元的項相乘時重復變元計數(shù)的問題. 例1 中, s4的兩個單項式分別與s5中的最高次項s0s1s3有相同的變元s0和s1, 因此在實際計算時, 并不會出現(xiàn)5 次項, 但數(shù)值映射方法并不能處理這樣的情況.

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

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

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

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

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

(2) 隨著初始化輪數(shù)的增加, MILP 模型中的變元和限制條件大幅增加, 當初始化輪數(shù)較高時, 普通PC 機求解MILP 模型是困難的.

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

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

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

(1) 對給定的指標集I 確定多項式的變元, 并選取合適的l 和h, 使得t = l + h, 且滿足k?=l ?(nC?2)?(nA?2)≥1;

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

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

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

算法1 代數(shù)次數(shù)估計Input: 給定輪數(shù)N; h; 指標集I;Output: s(N)out 的代數(shù)次數(shù)估計.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 在給定指標集I, 輪數(shù)N, 參數(shù)h, 算法1 的輸出為N-輪Trivium-型算法輸出比特的一個代數(shù)次數(shù)上界.

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

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

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

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

算法2 給定指標集I 下的零和立方區(qū)分器搜索算法Input: 初始化輪數(shù)N; 輪數(shù)h; 指標集I Output: 給定指標集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 應用

4.1 Trivium-型算法全變元的代數(shù)次數(shù)估計

本節(jié)將IV 變元IV 和密鑰變元KEY 均作為輸入變元, 并利用本文方法對Trivium、Kreyvium和TriviA-SC 進行實驗, 檢測在全變元的條件下, Trivium-型算法在何時能夠充分混合, 達到代數(shù)次數(shù)為#IV+#KEY. 雖然對于全變元條件下的代數(shù)次數(shù)估計結(jié)果不能直接用于攻擊, 但其從代數(shù)次數(shù)的角度衡量了密鑰變元和IV 變元在初始化迭代過程中混合的速度和程度, 對于評估算法的安全性具有一定意義.

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

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

表1 Trivium-型算法在KEY 和IV 全變元條件下未達到代數(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ù)估計結(jié)果

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

首先, 測試了隨機選擇的100 組48 維立方集CI. 將48 比特的立方變元作為更新函數(shù)和輸出函數(shù)的輸入變元, 利用算法2, 我們在給定立方集下, 給出了零和立方區(qū)分器能夠達到的最高輪數(shù)的估計. 同時,我們對實驗結(jié)果進行統(tǒng)計, 并與數(shù)值映射方法進行了對比, 具體結(jié)果參見表2.

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

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

其次, 測試了隨機選擇的100 組39 維的立方集, 利用算法2 對其進行實驗檢測. 同樣, 我們將所得結(jié)果與數(shù)值映射方法的結(jié)果進行了對比, 具體結(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 可以看出, 對隨機選取的100 個39 維立方集, 算法2 同樣能夠給出更優(yōu)的零和立方區(qū)分器, 平均提高36 輪, 最多提高58 輪(見附錄A), 并且在隨機實驗中, 最高給出了821 輪的零和區(qū)分器.

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

針對Kreyvium 算法, 本節(jié)隨機選取了100 組72 維的立方集. 將72 比特立方變元作為更新函數(shù)和輸出函數(shù)的輸入變元, 并利用算法2, 在給定立方集下對零和區(qū)分器能夠達到的最高輪數(shù)進行估計, 并與數(shù)值映射方法進行比較. 統(tǒng)計結(jié)果如表4 所示.

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

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

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

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

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

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

5 結(jié)論

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