Trivium-like算法中可滑動(dòng)Cube的研究*

曾凡洋, 田 甜

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

1 引言

Cube 攻擊由 Dinur 和 Shamir 在 2009 年歐密會(huì)上提出[1], 是對(duì)稱密碼算法的重要分析方法之一.特別地, 對(duì)于 Trivium-like 系列算法, 即 Trivium 算法[2]、Kreyvium 算法[3]以及 TriviA-SC 算法[4,5],cube 攻擊是最有效的密鑰恢復(fù)方法之一.近兩年,關(guān)于cube 攻擊的研究有較大進(jìn)展.目前,針對(duì)Triviumlike 系列算法的cube 攻擊可分為實(shí)驗(yàn) cube 攻擊 (或傳統(tǒng)cube 攻擊)[1]、基于分離性質(zhì)的cube 攻擊[6]、相關(guān) cube 攻擊[7].

序列密碼的輸出密鑰流比特可以看作關(guān)于密鑰和IV 變?cè)亩囗?xiàng)式f(Key,IV),其中Key 表示密鑰變?cè)?IV 表示IV 變?cè)?在cube 攻擊中,選擇一組活動(dòng)IV 變?cè)淖蛹疘,稱為cube 變?cè)?非cube 變?cè)话愎潭槌Ｖ?當(dāng)cube 變?cè)”樗锌赡艿?/1 組合時(shí), 對(duì)f(Key,IV) 求和得到關(guān)于密鑰和非cube 變?cè)囊粋€(gè)多項(xiàng)式pI(Key,IVI), 其中cube 變?cè)娜≈导戏Q為一個(gè)cube, 記為CI, 多項(xiàng)式pI(Key,IVI)稱為CI的超多項(xiàng)式(superpoly).Cube 攻擊中通過在線獲得超多項(xiàng)式pI(Key,IVI) 的值來建立關(guān)于密鑰變?cè)姆匠?由于在序列密碼中, f(Key,IV) 是一個(gè)非常復(fù)雜的多項(xiàng)式(變?cè)唷⒋鷶?shù)次數(shù)高、未知代數(shù)正規(guī)型), 如何求解有用的超多項(xiàng)式是cube 攻擊的一個(gè)難點(diǎn).

實(shí)驗(yàn) cube 攻擊也即 Dinur 和 Shamir 在 2009 年歐密會(huì)上提出的 cube 攻擊[1].在實(shí)驗(yàn) cube 攻擊中, 攻擊者通過黑盒布爾函數(shù)的低次檢測方法來尋找具有低次超多項(xiàng)式的cube, 從而建立關(guān)于密鑰變?cè)牡痛畏匠探M.已有結(jié)果均為線性或二次超多項(xiàng)式.在文[1]中, 對(duì)于767-輪Trivium, 作者利用線性檢測給出了 35 個(gè)線性超多項(xiàng)式.在文 [8]中, 作者首次將二次檢測引入到 cube 攻擊中.針對(duì) 709-輪 Trivium,作者給出了 41 個(gè)線性超多項(xiàng)式和38 個(gè)二次超多項(xiàng)式.在文 [9]中, 作者對(duì)于Trivium 算法的 cube 攻擊給出了兩個(gè)改進(jìn).首先, 利用Meobius 變換, 作者可以同時(shí)對(duì)一批cube 進(jìn)行檢測.其次, 作者給出了一個(gè)遞歸方法來構(gòu)造具有線性超多項(xiàng)式的cube.對(duì)于799-輪Trivium, 作者給出了12 個(gè)線性超多項(xiàng)式和6 個(gè)二次超多項(xiàng)式.在文 [10]中, 針對(duì) Trivium-like 算法, 作者利用線性化技術(shù), 給出了一種檢測非線性超多項(xiàng)式的新方法, 從而容易獲得更多 Trivium-like 算法的二次超多項(xiàng)式.對(duì)于 802-輪 Trivium, 他們給出 6個(gè)線性超多項(xiàng)式和 2 個(gè)二次超多項(xiàng)式; 對(duì)于 776-輪 Kreyvium, 他們給出 8 個(gè)二次超多項(xiàng)式; 對(duì)于 862-輪TriviA-SC-v2, 他們給出 12 個(gè)線性超多項(xiàng)式和 3 個(gè)二次超多項(xiàng)式.這是目前文獻(xiàn)中實(shí)驗(yàn) cube 攻擊給出最高輪數(shù)超多項(xiàng)式.

在實(shí)驗(yàn)cube 攻擊中, 對(duì)于一個(gè)d 維cube, 至少需要運(yùn)行2d次加密運(yùn)算, 從而受計(jì)算資源的限制, 對(duì)于能夠進(jìn)行實(shí)驗(yàn)檢測的cube, 維數(shù)通常不會(huì)超過40.在2017 年美密會(huì)上, Todo 等給出了基于分離性質(zhì)(division property) 的 cube 攻擊[6].這一攻擊方法的明顯優(yōu)點(diǎn)是可以利用高維數(shù) cube 分析算法的安全性, 例如大于70 維的cube.分離性質(zhì)是2015 年歐密會(huì)上提出的分組密碼積分區(qū)分器的一種搜索技術(shù), 并隨后用于全輪 MISTY1 分組密碼的分析.在 cube 攻擊中引入分離性質(zhì), 可以利用 MILP 求解器計(jì)算超多項(xiàng)式中可能出現(xiàn)的密鑰變?cè)? 進(jìn)而給出cube 攻擊的理論復(fù)雜度估計(jì).文[6]中對(duì)832-輪Trivium, 給出了一個(gè) 72 維 cube, 其超多項(xiàng)式至多包含 5 個(gè)密鑰變?cè)? 以大約 277的時(shí)間復(fù)雜度至多恢復(fù) 1 比特密鑰信息.另外, 文 [11]中針對(duì) 872-輪 Kreyvium, 給出一個(gè) 85 維 cube, 其至多包含 39 個(gè)密鑰變?cè)? 以大約2124的時(shí)間復(fù)雜度至多恢復(fù)1 比特密鑰信息.在文[12]中, 作者對(duì)[6]中的工作進(jìn)行了若干技術(shù)上的改進(jìn),包括更準(zhǔn)確地找到非常值IV 變?cè)馁x值以及降低恢復(fù)超多項(xiàng)式代數(shù)正規(guī)型的復(fù)雜度.文 [12]對(duì)839-輪Trivium, 給出一個(gè)78 維cube, 其超多項(xiàng)式至多包含1 個(gè)密鑰變?cè)? 從而以279的時(shí)間復(fù)雜度至多恢復(fù)1比特密鑰信息.文 [12]對(duì)文 [11]中給出的 872-輪 Kreyvium 的 85 維 cube, 將計(jì)算復(fù)雜度降低至 294.61;對(duì) 891-輪 Kreyvium, 給出一個(gè) 113 維 cube, 其超多項(xiàng)式是平衡的且至多包含 20 個(gè)密鑰變?cè)? 以 2120.73的時(shí)間復(fù)雜度至多恢復(fù)1 比特密鑰信息.上述基于分離性質(zhì)的cube 攻擊結(jié)果中, 當(dāng)超多項(xiàng)式實(shí)際為常值多項(xiàng)式時(shí), 密鑰恢復(fù)攻擊退化為區(qū)分攻擊.

在 2018 年歐密會(huì)上, Liu 等提出相關(guān) cube 攻擊方法[7].在相關(guān) cube 攻擊中, 攻擊者利用文 [13]中提出的代數(shù)次數(shù)估計(jì)方法, 找到一組關(guān)于密鑰的低次多項(xiàng)式{g1,g2,··· ,gu} 滿足超多項(xiàng)式 p 可以形式地表示成其中 fi是未知代數(shù)正規(guī)型的布爾函數(shù).然后, 攻擊者通過實(shí)驗(yàn)測試, 獲得 p 的取值與gi取值之間的條件相關(guān)概率Pr(g = b|p).在獲得真實(shí)密鑰下超多項(xiàng)式p 的值后, 可以得到一些關(guān)于密鑰變量的概率方程.對(duì)于 805-和 835-輪 Trivium, 文 [7]中給出的相關(guān) cube 攻擊可以分別恢復(fù)約 7 個(gè)密鑰比特信息和5 個(gè)密鑰比特信息, 數(shù)據(jù)復(fù)雜度245, 預(yù)處理時(shí)間復(fù)雜度是251, 在線時(shí)間復(fù)雜度是244.

注意到在文 [1]中, 利用線性檢測, 針對(duì)減輪 Trivium 算法, 作者給出了大量具有線性超多項(xiàng)式的cube.在這些給出的 cube 中, 存在滑動(dòng)的現(xiàn)象, 即存在 IV 變?cè)?{v0,v1,··· ,vm?1} 的子集 I1和 I2, 使得 CI1對(duì)于 zt的超多項(xiàng)式 pI1(k1,k2,··· ,kn?1) 和 CI2對(duì)于 zt+1的超多項(xiàng)式 pI2(k0,k1,··· ,kn?2) 滿足 pI2(k0,k1,··· ,kn?2)= σ(pI1(k1,k2,··· ,kn?1)), 其中 ki表示密鑰變量, I2={vi?1|vi∈ I1}, σ 將 ki映射到ki?1.由于Kreyvium 和TriviA-SC(v1 和v2)算法與Trivium 算法具有非常類似的結(jié)構(gòu),這使得其cube 攻擊與Trivium 算法具有較為相似的性質(zhì).對(duì)于給定的I1如果我們能夠快速判斷出其具有滑動(dòng)性, 那么我們就能夠直接根據(jù) CI1對(duì)于 zt的超多項(xiàng)式 pI1(x1,x2,··· ,xn?1) 計(jì)算出 CI2對(duì)于 zt+1的超多項(xiàng)式 pI2(x0,x1,··· ,xn?2).因此, 本文主要關(guān)注 Trivium-like 算法中 cube 的滑動(dòng)性.首先, 我們通過對(duì)比分析第0 時(shí)刻內(nèi)部狀態(tài)S0和第1 時(shí)刻內(nèi)部狀態(tài)S1的代數(shù)正規(guī)型(Algebraic Normal Form, ANF),從理論上給出了cube 具有可滑動(dòng)性的一個(gè)充分條件.進(jìn)一步, 我們將充分條件的判斷轉(zhuǎn)化為MILP 模型的可行性判斷, 在實(shí)際分析中基于MILP 求解器能夠快速判斷出具有滑動(dòng)性的cube.最后, 我們將充分條件應(yīng)用到實(shí)驗(yàn) cube 攻擊、基于分離性質(zhì)的 cube 攻擊和相關(guān) cube 攻擊, 驗(yàn)證了方法的正確性并在實(shí)驗(yàn)cube 攻擊中得到了一個(gè) 803-輪 Trivium 的新結(jié)果.

本文剩余部分安排如下: 第 2 節(jié)介紹了 cube 攻擊、Trivium-like 算法、MILP 模型和可滑動(dòng) cube的概念.在第 3 節(jié)中, 針對(duì) Trivium-like 算法, 我們給出了一個(gè) cube 具有滑動(dòng)性的充分條件.在第 4 節(jié)中, 介紹了如何將充分條件應(yīng)用到實(shí)驗(yàn)cube 攻擊、基于分離性質(zhì)的cube 攻擊和相關(guān)cube 攻擊中, 并給出了相關(guān)結(jié)果.第5 節(jié)總結(jié)了全文.

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

2.1 Cube攻擊

在 cube 攻擊中, 目標(biāo)密碼算法的輸出比特 z 被看作關(guān)于 IV 變?cè)?IV = (v0,v1,··· ,vm?1) 和密鑰變?cè)?Key = (k0,k1,··· ,kn?1) 的布爾函數(shù), 即 z = f(IV,Key).選定一個(gè) IV 變?cè)淖蛹疘 ={vi0,vi1,··· ,vi|I|?1}, 令 tI是 I 中變?cè)某朔e, 即 tI=vi0vi1···vi|I|?1, 則 z 可以表示為

其中多項(xiàng)式 pI不含 I 中的變?cè)? 多項(xiàng)式 q(IV,Key) 中的任意項(xiàng)不被 tI整除.令是 I 中變?cè)囊粋€(gè)取值集合滿足I 中每個(gè)變?cè)?dú)立取遍F2中元素, 則有

在 cube 攻擊中, I = {vi0,vi1,··· ,vi|I|?1} 中變?cè)Q為 cube 變?cè)? 其余 IV 變?cè)Q為非 cube 變?cè)?非cube 變?cè)偸窃O(shè)為常值并且通常設(shè)置為 0 常值.多項(xiàng)式 pI(IVI,Key) 稱為超多項(xiàng)式.顯然, 當(dāng)給定非cube 變?cè)≈岛? 例如 0 常值, 則 pI(0,Key) 是關(guān)于密鑰的一個(gè)多項(xiàng)式.在 cube 攻擊中, 通過恢復(fù)超多項(xiàng)式來建立關(guān)于密鑰變?cè)姆匠?最后, 包含 cube 變?cè)?2|I|種可能取值 (非 cube 變?cè)潭槌Ｖ?的集合 CI稱為一個(gè)|I|-維 cube.

Cube 攻擊包含離線階段和在線階段.

離線階段: 由于函數(shù)f(IV,Key) 的代數(shù)正規(guī)型是未知的, 攻擊者通過線性/二次檢測等黑盒布爾函數(shù)的檢測方法來尋找具有低次超多項(xiàng)式的cube 以及恢復(fù)超多項(xiàng)式的代數(shù)正規(guī)型.

在線階段: 根據(jù)離線階段找到的 cube 和超多項(xiàng)式, 攻擊者通過查詢密碼機(jī)確定其超多項(xiàng)式在當(dāng)前密鑰下的函數(shù)值, 從而建立關(guān)于密鑰變?cè)牡痛畏匠探M.通過求解方程組, 攻擊者可以恢復(fù)密鑰變?cè)牟糠只蛉啃畔?

2.2 Trivium-like算法

本小節(jié)主要介紹 Trivium-like 算法, 主要包括 Trivium 算法、Kreyvium 和 TriviA-SC 算法.

2.2.1 Trivium 算法

Trivium 算法是由 Canniere 和 Preneel 設(shè)計(jì)的面向硬件實(shí)現(xiàn)的流密碼算法.Trivium 算法包括三個(gè)寄存器, 級(jí)數(shù)分別為 93、84 和 111, 內(nèi)部狀態(tài)長度為 288 比特, 分別用 s1,s2,··· ,s288表示.密鑰 Key和 IV 長度均為 80 比特, 分別用 k0,k1,··· ,k79和 v0,v1,··· ,v79表示.初始化時(shí), 首先, 用密鑰和 IV 填充前兩個(gè)寄存器, 其余位置均填充常值; 然后, 內(nèi)部狀態(tài)更新 1152 輪.初始化完成后, 內(nèi)部狀態(tài)每更新一拍, 輸出1 比特密鑰流, 由內(nèi)部狀態(tài)6 個(gè)位置的比特異或得到.算法1 給出了Trivium 算法的密鑰流生成的偽代碼描述.

?

2.2.2 Keryvium 算法

Kreyvium 算法是Canteaut 等人設(shè)計(jì)的Trivium 算法的128 比特密鑰版本, 目標(biāo)在于高效實(shí)現(xiàn)同態(tài)加密中的同態(tài)密文壓縮[3].Kreyvium 算法的密鑰和IV 都是128 比特, 與Trivium 算法的不同之處在于:除了和Trivium 算法完全一樣的288 比特主寄存器以外, 還添加了兩個(gè)128 比特的寄存器來分別存儲(chǔ)密鑰和IV, 密鑰寄存器和IV 寄存器只做循環(huán)移位更新; 在288 比特主寄存器更新時(shí), 不斷以異或加的方式添加密鑰和 IV 比特.因此 Kreyvium 內(nèi)部狀態(tài)為 544 比特, 由 5 個(gè)長度為 93、84、111、128 和 128 比特的寄存器組成.算法2 描述了Kreyvium 的密鑰流生成算法的偽代碼描述.

2.2.3 TriviA-SC 算法

TriviA-SC 算法由 Chakraborti 等人設(shè)計(jì)的流密碼算法, 它是 CAESAR 競賽的第二輪候選認(rèn)證加密算法 TriviA 的基礎(chǔ)組件.TriviA-SC 算法有兩個(gè)版本, 即 TriviA-SC-v1 和 TriviA-SC-v2.在下文中,TriviA-SC 算法都指的是 TriviA-SC-v2 算法.TriviA-SC 算法的密鑰和 IV 都是 128 比特, 內(nèi)部狀態(tài)由三個(gè)長度為 132、105 和 147 比特寄存器構(gòu)成, 總共為 384 比特.采用和 Trivium 算法相似的更新函數(shù),初始化輪數(shù)也是1152.算法3 給出了TriviA-SC 的密鑰流生成算法的偽代碼描述.

?

?

2.3 混合整數(shù)線性規(guī)劃

線性規(guī)劃(Linear Programming) 是一類實(shí)數(shù)域上的優(yōu)化問題, 其標(biāo)準(zhǔn)形式如下

其中 x ∈Rn,A ∈Rm,n,b ∈Rm,c ∈Rn.若變?cè)?x 的部分或全部取值限制在整數(shù)范圍, 則該優(yōu)化問題稱為混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming, MILP).求解MILP 模型的求解器有Gurobi[14]和CPLEX[15]等.如果模型有解, 則求解器會(huì)返回一個(gè)解; 如果模型沒有解, 則求解器返回不可行.若模型沒有目標(biāo)函數(shù), 則求解器僅返回是否可行.

2.4 可滑動(dòng)cube

為表述方便, 在介紹可滑動(dòng) cube 的定義以前, 先介紹符號(hào) σ.設(shè) X = {x0,x1,··· ,xn?1} 是一組變?cè)? 對(duì)于任意非空子集 U ={xi1,xi2,··· ,xim} ? X, 記

上述變?cè)峡梢允?IV 變?cè)? 也可以是密鑰變?cè)?進(jìn)一步, 關(guān)于變?cè)?U 的一個(gè)布爾函數(shù)f(xi1,xi2,··· ,xim), 記

也即 σ(f(U))=f(σ(U)).我們規(guī)定 σ(0)=0,σ(1)=1.下面我們定義可滑動(dòng) cube.

定義 1 (可滑動(dòng) cube)設(shè) I ={vi0,vi1,··· ,vi|I|?1}(ij? 1,j =0,1,··· ,|I|?1) 是一組 IV 變?cè)?并設(shè) Cube CI關(guān)于算法在 t 時(shí)刻的輸出zt的超多項(xiàng)式為pI.如果Cube Cσ(I)關(guān)于該算法t+1 時(shí)刻的輸出 zt+1的超多項(xiàng)式為 pσ(I)=σ(pI), 則稱 CI為可滑動(dòng) cube, 并稱 (CI,Cσ(I)) 為滑動(dòng) cube 對(duì).

例 1取 I = {v3,v9,v14,v20,v23,v27,v31,v47,v48,v63,v70,v72}, Cube CI關(guān)于 Trivium 算法 673輪輸出比特的超多項(xiàng)式為 pI= k31．容易驗(yàn)證, Cσ(I)關(guān)于 Trivium 算法 674 輪輸出比特的超多項(xiàng)式為pσ(I)=k30= σ(pI).故, CI為可滑動(dòng) cube, (CI,Cσ(I)) 為滑動(dòng) cube 對(duì).

3 可滑動(dòng)cube的充分條件

在本節(jié)中, 針對(duì) Trivium-like 算法, 我們給出了可滑動(dòng) cube 的一個(gè)充分條件.因?yàn)門riviA-SC 算法和 Kreyvium 算法的結(jié)構(gòu)與 Trivium 算法結(jié)構(gòu)相似度較高, 所以, 在本節(jié)中我們只對(duì) Trivium 算法的可滑動(dòng)cube 的充分條件給出了詳細(xì)證明.對(duì)于 TriviA-SC 算法和 Kreyvium 算法, 可滑動(dòng) cube 的充分條件的證明可以類似得出.

3.1 Trivium算法可滑動(dòng)cube的充分條件

本節(jié)討論 Trivium 算法可滑動(dòng) cube 的充分條件.記 Trivium 算法密鑰變?cè)獮?Key = {k0,k1,··· ,k79}, IV 變?cè)獮?IV={v0,v1,··· ,v79}, 第 t 時(shí)刻內(nèi)部狀態(tài)比特為第 t 時(shí)刻的輸出比特為zt.顯然, 每個(gè)內(nèi)部狀態(tài)比特都可以看作Key 和IV 的布爾函數(shù), 即

若選定一組 cube 變?cè)?I ={vi0,vi1,··· ,vi|I|?1}?IV, 非 cube 變?cè)潭槌Ｖ?0 或 1, 則我們用符號(hào)

定義 2設(shè) I = {vi0,vi1,··· ,vi|I|?1} ? IV 是一組 cube 變?cè)? 集合 J ? {1,2,··· ,288}.對(duì)于Trivium 算法的連續(xù)兩個(gè)內(nèi)部狀態(tài)若對(duì)每個(gè)k ? J 有

成立, 則稱 (St,St+1) 關(guān)于 (I,J) 是滑動(dòng)狀態(tài), 其中 d ∈{0,1}.上述(1)式也簡寫為

引理 1設(shè) I = {vi0,vi1,··· ,vi|I|?1} ? IV 是一組 Cube 變?cè)? 集合 J ? {1,2,··· ,288}, 并且(St,St+1) 關(guān)于 (I,J) 是滑動(dòng)狀態(tài).對(duì)于到 F2的任意布爾函數(shù) F(X)=F(x0,x1,··· ,xn?1), 有

證明:不妨設(shè)F(X) 的代數(shù)正規(guī)型為:

集合 J ={j0,j1,··· ,jn?1}, 則有

設(shè) I ? IV 是一組 cube 變?cè)?對(duì)于 I 和 σ(I), 記它們對(duì) zt和 zt+1的超多項(xiàng)式分別為 pI和 pσ(I).由于 zt=F(St) 且 zt+1=F(St+1), 那么根據(jù)引理1, 若 J ={1,2,··· ,288} 且存在時(shí)刻 t 滿足 (St,St+1)關(guān)于 (I,J) 是滑動(dòng)狀態(tài), 那么 zt+1= σ(zt), 從而有 pσ(I)= σ(pI).注意到在實(shí)際中, 超多項(xiàng)式 pI并不一定與每一個(gè)內(nèi)部狀態(tài)都相關(guān), 所以考慮cube 的可滑動(dòng)性時(shí)并不需要J ={1,2,··· ,288} 這么苛刻的條件.

為了給出Trivium 算法可滑動(dòng)cube 的充分條件, 我們首先考察Trivium 算法第0 時(shí)刻內(nèi)部狀態(tài)S0和第 1 時(shí)刻內(nèi)部狀態(tài) S1, 具體見表1.在表1 中, 我們給出了S0和S1中每一個(gè)狀態(tài)比特關(guān)于 IV 變?cè)兔荑€變?cè)腁NF.

定理 1 (充分條件)設(shè) I = {vi0,vi1,··· ,vi|I|?1} ? IV 是一組 IV 變?cè)? 令 Keynew= Key ∪{knew0,knew1,knew2}, 并且在初始化時(shí)令設(shè) Trivium 算法第 t時(shí)刻輸出zt(I,0IVI,Keynew) 關(guān)于CI的超多項(xiàng)式為pI.若以下兩個(gè)條件成立:

(i) I 中不包含 v0,v69,v78;

(ii) pI中不包含k0,knew0,knew1,knew2;

則 (CI,Cσ(I)) 是滑動(dòng) cube 對(duì), 即 Cσ(I)關(guān)于 zt+1(σ(I),0IVσ(I),Key) 的超多項(xiàng)式為 pσ(I)= σ(pI).

表1 Trivium 算法第 0 時(shí)刻與第 1 時(shí)刻內(nèi)部狀態(tài)Table 1 Internal states of Trivium at Time 0 and Time 1

表2 Trivium 算法添加新變?cè)蟮? 時(shí)刻與未添加新變?cè)? 時(shí)刻內(nèi)部狀態(tài)Table 2 Internal state with new variables at Time 0 and internal state without new variables at Time 1 of Trivium

證明:觀察表2 可以發(fā)現(xiàn),對(duì)于j{1,81,94,174,178,286},均有成立.由于v0,v69,v78不屬于 I, 于是 v68,v77不屬于 σ(I).因此, 對(duì)于 S0可以令 v0,v69,v78等于 0, 而對(duì)于 S1可以令 v68,v77等于 0.又根據(jù)定義1 可知 v79不會(huì)屬于 σ(I), 故可以令 S1中 v79等于 0.從而, 有下述等式成立

我們?cè)诒? 中給出了滿足定理?xiàng)l件時(shí)的S0和S1.觀察表3 可得

于是, zt(I,0IVI,Keynew) 可以表示成如下唯一形式

由定理?xiàng)l件可知, CI對(duì)于 zt的超多項(xiàng)式 pI不包含 k0,knew0,knew1,knew2, 由式(2)知 tI= ∏i∈Ivi只能出現(xiàn)在分量函數(shù)F0(S0) 中, 也即

又由式(3)知 Fi(S1)= σ(Fi(S0)),0 ? i ? 15, 所以 tσ(I)出現(xiàn)在 Fi(S1) 中當(dāng)且僅當(dāng) tI出現(xiàn)在 Fi(S0) 中.從而, tσ(I)只能出現(xiàn)在 F0(S1) 中, 即

這表明 pσ(I)= σ(pI).故 (CI,Cσ(I)) 為滑動(dòng) cube 對(duì).

表3 滿足定理1 條件時(shí)Trivium 算法第0 時(shí)刻與第 1 時(shí)刻內(nèi)部狀態(tài)Table 3 Internal states at Time 0 and Time 1 of Trivium when Theorem 1 is satisfied

3.2 Kreyvium算法和TriviA-SC算法可滑動(dòng)cube的充分條件

在這一小節(jié)中, 針對(duì)Kreyvium 算法算法和TriviA-SC 算法, 我們直接給出可滑動(dòng)cube 的充分條件.Kreyvium 算法第 0 時(shí)刻與第 1 時(shí)刻的內(nèi)部狀態(tài)如表4 所示, 其可滑動(dòng) cube 的充分條件由定理2 給出;TriviA-SC 算法第 0 時(shí)刻與第 1 時(shí)刻的內(nèi)部狀態(tài)如表5 所示, 其可滑動(dòng) cube 的充分條件由定理3 給出.

定理 2設(shè) I = {vi0,vi1,··· ,vi|I|?1} ? IV 是一組 IV 變?cè)? 令 Keynew= Key ∪{knew0,knew1,knew2}, 并且在初始化時(shí)令設(shè) Kreyvium 算法第 t 時(shí)刻輸出zt(I,0IV(I∪{v0,v69}),1{v0,v69},Keynew) 關(guān)于 CI的超多項(xiàng)式為 pI.若以下兩個(gè)條件成立:

(i) I 中不包含 v0,v69,v78,v83,v84;

(ii) pI中不包含k0,knew0,knew1,knew2;

則 (CI,Cσ(I)) 是滑動(dòng) cube 對(duì), 即 Cσ(I)關(guān)于 zt+1(σ(I),0IV(σ(I)∪{v127,v68}),1{v127,v68},Key) 的超多項(xiàng)式為 pσ(I)= σ(pI).

定理 3設(shè) I = {vi0,vi1,··· ,vi|I|?1} ? IV 是一組 IV 變?cè)? 令 Keynew= Key ∪{knew0,knew1,knew2}, 并且在初始化時(shí)令設(shè) Trivia-SC 算法算法第 t 時(shí)刻輸出zt(I,0IVI,Keynew) 關(guān)于CI的超多項(xiàng)式為pI.若以下兩個(gè)條件成立:

(i) I 中不包含 v0,v66,v120;

(ii) pI中不包含k0,knew0,knew1,knew2;

則 (CI,Cσ(I)) 是滑動(dòng) cube 對(duì), 即 Cσ(I)關(guān)于 zt+1(σ(I),0IVσ(I),Key) 的超多項(xiàng)式為 pσ(I)= σ(pI).

表4 Kreyvium 算法第 0 時(shí)刻與第 1 時(shí)刻內(nèi)部狀態(tài)Table 4 Internal states of Kreyvium at Time 0 and Time 1

4 可滑動(dòng)cube充分條件的驗(yàn)證與應(yīng)用

在第3 節(jié)中, 我們從理論上給出了可滑動(dòng)cube 的充分條件.本節(jié)討論在實(shí)際中如何驗(yàn)證可滑動(dòng)cube的充分條件, 方法的正確性已經(jīng)過大量實(shí)驗(yàn)驗(yàn)證.并且, 我們嘗試對(duì)已有文獻(xiàn)中列舉的cube 攻擊最好結(jié)果進(jìn)行了滑動(dòng)性的判斷.

表5 TriviA-SC 算法第 0 時(shí)刻與第 1 時(shí)刻內(nèi)部狀態(tài)Table 5 Internal states of TriviA-SC at Time 0 and Time 1

4.1 基于MILP的驗(yàn)證方法

根據(jù)上文給出的 Trivium-like 算法可滑動(dòng)cube 的充分條件, 我們可以快速判斷某些 cube 是否具有滑動(dòng)性, 如果具有滑動(dòng)性, 那么我們可以直接獲得一些新的密鑰方程, 而無需其他的操作.下面我們將介紹如何具體判斷充分條件是否成立.

我們?nèi)砸?Trivium 算法為例.由定理1 知, 充分條件需滿足: (i) I 中不包含 v0,v69,v78; (ii) pI中不包含 k0,knew0,knew1,knew2.對(duì)于給定的 Cube CI, 條件 (i) 可以直接判斷 cube 變量中是否含有變量 v0,v69,v78.而對(duì)于條件 (ii) 的判斷, 我們轉(zhuǎn)化為 MILP 模型來解決, 轉(zhuǎn)化的理論依據(jù)由文 [6]中的Proposition 4 給出.

定理 4[6]設(shè) f(IV,Key) 為 IV 變?cè)?IV=(v0,v1,··· ,vm?1) 和密鑰變?cè)?Key=(k0,k1,··· ,kn?1)的多項(xiàng)式, 集合 I = {vi1,vi2,··· ,vi|I|} 為 cube 變?cè)? lI= (l0,l1,··· ,lm) 為 m 維的比特向量滿足IVlI= tI= vi1,vi2,··· ,vi|I|, 其中 vi∈ I, 則 li= 1, 否則 li= 0.設(shè) eλ為 n 維比特向量 (第 λ 比特為1, 其余比特為 0) 滿足 Keyeλ=kλ.若沒有滿足 (eλ,lI)1 的分離路徑 (division trail), 則 CI的超多項(xiàng)式 pI與變?cè)?kλ無關(guān), 也即 kλ不出現(xiàn)在 pI的代數(shù)正規(guī)型中.

根據(jù)定理4, 對(duì)于 Trivium 算法, 我們將判斷 cube 的可滑動(dòng)性轉(zhuǎn)化為求解 MILP 模型.對(duì)于給定的Cube CI, 通過求解MILP 模型來判斷是否存在滿足(eλ,lI)1(λ =0,new1,new2,new3) 的分離路徑.如果均不存在這樣的分離路徑, 則變?cè)猭0,knew0,knew1,knew2不會(huì)出現(xiàn)在Cube CI的超多項(xiàng)式中.那么,CI一定是可滑動(dòng)的 cube.值得注意的是, 即使存在滿足 (eλ,lI)1(λ = 0,new1,new2,new3) 的分離路徑, 也并不能說明變?cè)?k0,knew0,knew1,knew2一定出現(xiàn)在 CI的超多項(xiàng)式中, CI仍然有可能是可滑動(dòng)的.因此, 上述基于 MILP 模型的判斷方法, 可能會(huì)丟掉一些可滑動(dòng) cube, 但并不會(huì)影響正確性, 即通過MILP 檢測的一定滿足可滑動(dòng)的充分條件.關(guān)于分離性質(zhì)、分離路徑以及如何建立求解分離性質(zhì)的MILP模型, 請(qǐng)參見文獻(xiàn)[6,11].

為了說明利用求解 MILP 模型來判斷可滑動(dòng) cube 的有效性, 我們對(duì) 672-輪 Trivium 做了大量實(shí)驗(yàn)驗(yàn)證.首先, 我們通過低次檢測尋找到許多具有線性和二次超多項(xiàng)式的 cube (cube 變量中不包含v0,v69,v78), 然后對(duì)這些 cube 求解 MILP 模型, 仍然有大量 cube 滿足其超多項(xiàng)式不包含 k0,knew0,knew1,knew2.我們從中選取部分放在表6 中.對(duì)于這些 cube, 我們根據(jù)定理1 計(jì)算出滑動(dòng)后的 cube 及其超多項(xiàng)式, 具體見表7.對(duì)于滑動(dòng)后的每組 cube, 我們隨機(jī)選取了1000 組密鑰值對(duì)超多項(xiàng)式進(jìn)行檢驗(yàn), 發(fā)現(xiàn)對(duì)cube 求和所得值與超多項(xiàng)式的值完全一致.這就表明了利用求解MILP 模型來判斷cube 的滑動(dòng)性的有效性.

4.2 滑動(dòng)cube的應(yīng)用

利用求解分離性質(zhì)的 MILP 模型, 我們將可滑動(dòng) cube 的充分條件應(yīng)用到已有文獻(xiàn)中針對(duì) Trviumlike 算法給出的攻擊結(jié)果, 包括實(shí)驗(yàn) cube 攻擊、基于分離性質(zhì)的 cube 攻擊和相關(guān) cube 攻擊, 最終在實(shí)驗(yàn) cube 攻擊中獲得了一個(gè)803-輪 Trivium 的新結(jié)果.

表6 672-輪 Trivium 超多項(xiàng)式中不包含 k0,knew0,knew1,knew2 的 cubeTable 6 Cubes whose superpolies do not contain k0,knew0,knew1,knew2 for 672-Trivium

表7 滑動(dòng)后的cube 及其超多項(xiàng)式Table 7 Cubes and their superpolies after sliding

4.2.1 實(shí)驗(yàn) cube 攻擊

在文[10]中, 對(duì)于802-輪Trivium, 作者給出6 個(gè)線性的超多項(xiàng)式和2 個(gè)二次超多項(xiàng)式; 對(duì)于776-輪Kreyvium, 作者給出 8 個(gè)二次超多項(xiàng)式; 對(duì)于 862-輪 TriviA-SC, 作者給出 12 個(gè)線性超多項(xiàng)式和 3 個(gè)二次超多項(xiàng)式.這是目前文獻(xiàn)中實(shí)驗(yàn)cube 攻擊給出最高輪數(shù)超多項(xiàng)式.對(duì)于這些cube 我們利用可滑動(dòng)cube 的充分條件, 依次判斷了其是否具有滑動(dòng)性, 最終我們獲得了減輪803-輪Trivium 一個(gè)新的cube 及超多項(xiàng)式, 具體結(jié)果見表8.

4.2.2 基于分離性質(zhì)的cube 攻擊

在文獻(xiàn) [11,12]中, 針對(duì) Trivium 算法和 Kreyvium 算法, 作者給出的 cube 中都包含 IV 變量 v0, 這已經(jīng)不滿足可滑動(dòng)cube 充分條件中cube 變量不能包含v0的規(guī)定.因此利用充分條件, 我們無法判斷出這些cube 的可滑動(dòng)性.

表8 803-輪 Trivium 的 cube 及超多項(xiàng)式Table 8 Cube and its superpoly for 803-round Trivium

4.2.3 相關(guān) Cube 攻擊

在文 [7]中, 作者在 835-輪 Trivium 的相關(guān) cube 攻擊中, 給出 28 個(gè) cube 及其基多項(xiàng)式.根據(jù)定理1, 若cube 滿足滑動(dòng)性, 則超多項(xiàng)式具有滑動(dòng)性.由于基多項(xiàng)式是超多項(xiàng)式的一部分, 所以基多項(xiàng)式也具有滑動(dòng)性.我們對(duì)于這 28 個(gè) cube 進(jìn)行了可滑動(dòng)性判斷, 最終得到 837-輪的 1 組 cube 及其基多項(xiàng)式.具體結(jié)果見表9.但這組 cube 并不是一個(gè)新的cube, 在文 [7]中, 作者已經(jīng)給出了這組cube 及其基多項(xiàng)式, 這與我們利用滑動(dòng)性給出的結(jié)果是一致的.

表9 837-輪 Trivium 的 cube 和基多項(xiàng)式Table 9 Cube and its basis for 837-round Trivium

5 結(jié)論

在本文中, 針對(duì) Trivium-like 算法, 我們研究了 cube 的可滑動(dòng)性.首先, 針對(duì) Trivium-like 算法, 我們給出了 cube 可滑動(dòng)性的充分條件.其次, 我們將充分條件應(yīng)用到實(shí)驗(yàn) cube 攻擊、基于分離性質(zhì)的cube 攻擊和相關(guān)cube 攻擊, 驗(yàn)證了方法的正確性并最終在實(shí)驗(yàn)cube 攻擊中得到了一個(gè)803-輪Trivium的新結(jié)果.希望本文中對(duì)cube 滑動(dòng)性質(zhì)的研究, 能夠?yàn)?cube 攻擊中在恢復(fù)密鑰信息時(shí)提供一些新的攻擊思路.此外, cube 的滑動(dòng)性與算法的初態(tài)的填充方式有較大聯(lián)系, 希望本文的研究能為算法設(shè)計(jì)提供一定的借鑒意義.