序列密碼立方攻擊研究進(jìn)展綜述*

田 甜, 戚文峰

信息工程大學(xué), 鄭州 450001

1 引言

2000 年前后, 相關(guān)攻擊和代數(shù)攻擊的發(fā)展對(duì)基于線性反饋移位寄存器(LFSR) 的序列密碼算法的安全性構(gòu)成嚴(yán)重威脅.2004–2008 年, ECRYPT 啟動(dòng)了序列密碼征集項(xiàng)目eSTREAM, 出現(xiàn)了一批基于非線性序列源的序列密碼算法.特別地, 非線性反饋移位寄存器(NFSR) 廣泛用于面向硬件實(shí)現(xiàn)的序列密碼算法, 例如eSTREAM 項(xiàng)目面向硬件實(shí)現(xiàn)的勝選算法Trivium 以及Trivium 的128 比特密鑰版本Kreyvium、Grain 系列算法等都是典型的基于NFSR 的序列密碼算法.采用NFSR 作為序列源, 可以有效抵抗針對(duì)基于LFSR 序列密碼算法的相關(guān)攻擊和代數(shù)攻擊.近十年, 立方攻擊是針對(duì)基于NFSR 序列密碼算法的重要攻擊方法, 在Trivium、Kreyvium、Grain 系列算法的安全性分析方面不斷取得新的進(jìn)展.目前, 在立方攻擊基礎(chǔ)上發(fā)展的攻擊方法有: 實(shí)驗(yàn)立方攻擊、基于可分性的立方攻擊、動(dòng)態(tài)立方攻擊、相關(guān)立方攻擊等.

立方攻擊由Dinur 和Shamir 在2009 年歐密會(huì)上首次提出[1], 是一種高階差分攻擊和代數(shù)攻擊.立方攻擊的基本思想是通過(guò)對(duì)序列密碼的初始化向量(IV) 進(jìn)行差分, 獲得關(guān)于密鑰的低次方程組.在立方攻擊中, 每個(gè)立方集(cube) 對(duì)應(yīng)了一個(gè)關(guān)于密鑰的多項(xiàng)式, 稱為關(guān)于該立方集的超多項(xiàng)式(superpoly),其中立方集一般是IV 的一個(gè)仿射子空間.由于基于NFSR 的序列密碼是迭代型密碼算法, 經(jīng)過(guò)初始化算法后, 輸出密鑰流比特關(guān)于密鑰和IV 的代數(shù)正規(guī)型是未知的并且規(guī)模很大, 在文獻(xiàn)[1] 中, 自然將輸出密鑰流比特看作密鑰和IV 的黑盒布爾函數(shù), 通過(guò)線性檢測(cè)的方法搜索線性超多項(xiàng)式.文獻(xiàn)[1] 具體恢復(fù)了一批672 輪和767 輪Trivium 的線性超多項(xiàng)式.2013 年, 文獻(xiàn)[2] 提出利用M?bius 變換原理對(duì)一個(gè)大立方集的部分子集同時(shí)進(jìn)行超多項(xiàng)式的線性檢測(cè)或二次檢測(cè), 給出了784 輪Trivium 的42 個(gè)線性超多項(xiàng)式、799 輪Trivium 的12 個(gè)線性和6 個(gè)二次超多項(xiàng)式.文獻(xiàn)[3] 針對(duì)Trivium-型算法, 提出線性化技術(shù),降低檢測(cè)Trivium-型算法二次超多項(xiàng)式的復(fù)雜度, 給出了802 輪Trivium 的6 個(gè)線性超多項(xiàng)式和2 個(gè)二次超多項(xiàng)式、776 輪Kreyvium 的8 個(gè)二次超多項(xiàng)式.以上立方攻擊稱為實(shí)驗(yàn)立方攻擊或傳統(tǒng)立方攻擊,都是通過(guò)黑盒布爾函數(shù)檢測(cè)的方法判斷超多項(xiàng)式的代數(shù)次數(shù)和恢復(fù)代數(shù)正規(guī)型.

在實(shí)驗(yàn)立方攻擊中, 對(duì)一個(gè)d維立方集的超多項(xiàng)式進(jìn)行一次線性檢測(cè)的復(fù)雜度是O(2d), 因此, 實(shí)際計(jì)算資源限制了立方集的維數(shù)很難超過(guò)40 維, 目前文獻(xiàn)中最大的立方集是43 維[4].2017 年, Todo 等人將分組密碼搜索積分區(qū)分器的可分性(division property) 引入到立方攻擊中[5], 結(jié)合混合整數(shù)線性規(guī)劃(mixed integer linear programming, MILP) 模型可以處理高維立方集的超多項(xiàng)式.對(duì)于給定的立方集, 文獻(xiàn)[5] 利用基于MILP 建模的二子集可分性可以排除一部分不出現(xiàn)在超多項(xiàng)式中的密鑰變?cè)? 降低恢復(fù)超多項(xiàng)式的復(fù)雜度.然而, 文獻(xiàn)[5] 的方法包括后續(xù)的改進(jìn)方法[6]均不能準(zhǔn)確恢復(fù)超多項(xiàng)式的代數(shù)正規(guī)型, 這也導(dǎo)致文獻(xiàn)[6] 中所列833 輪到839 輪Trivium 的密鑰恢復(fù)攻擊均是無(wú)效的, 實(shí)際是區(qū)分攻擊[7].2019 年, 文獻(xiàn)[7] 提出基于二子集可分性的代數(shù)方法, 文獻(xiàn)[8] 提出基于三子集可分性MILP 建模的超多項(xiàng)式恢復(fù)方法, 均可以準(zhǔn)確恢復(fù)超多項(xiàng)式的代數(shù)正規(guī)型, 但都只適用于非常稀疏的超多項(xiàng)式.2020年, Hao 等人在文獻(xiàn)[9] 中提出不含未知集的三子集可分性(3SDP/u) 的MILP 建模方法, 解決了基于MILP 建模準(zhǔn)確恢復(fù)超多項(xiàng)式的問(wèn)題, 并且基于MILP 建模的超多項(xiàng)式求解效率有了很大程度的提高.利用該模型, 文獻(xiàn)[9] 中分別給出了841 輪和842 輪Trivium 的超多項(xiàng)式, 立方集的維數(shù)為78, 超多項(xiàng)式的次數(shù)為4 次, 項(xiàng)數(shù)分別為67 和53, 與之前文獻(xiàn)中恢復(fù)的超多項(xiàng)式相比, 代數(shù)正規(guī)型的規(guī)模明顯增大.2021年, Hu 等人在文獻(xiàn)[10] 中提出一個(gè)更高效的超多項(xiàng)式恢復(fù)算法, 該算法結(jié)合了文獻(xiàn)[9] 中的3SDP/u 的MILP 模型和文獻(xiàn)[7] 中將輸出比特表達(dá)為中間狀態(tài)變?cè)紶柡瘮?shù)的分治技術(shù), 可以恢復(fù)超大規(guī)模的超多項(xiàng)式.在文獻(xiàn)[10] 中, 給出845 輪Trivium、191 輪Grain-128AEAD 以及894 輪Kreyvium 的超多項(xiàng)式, 其中845 輪Trivium 超多項(xiàng)式的單項(xiàng)式數(shù)量均超過(guò)107.2022 年, 文獻(xiàn)[11] 對(duì)文獻(xiàn)[10] 的算法做了一些局部改進(jìn), 給出了848 輪Trivium、192 輪Grain-128AEAD、895 輪Kreyvium 的超多項(xiàng)式.當(dāng)超多項(xiàng)式的規(guī)模增長(zhǎng)到一千萬(wàn)個(gè)單項(xiàng)式時(shí), 其是否平衡都是未知的, 很難評(píng)估在密鑰恢復(fù)攻擊階段的貢獻(xiàn).針對(duì)這一問(wèn)題, 文獻(xiàn)[12] 考慮了平衡超多項(xiàng)式的恢復(fù), 針對(duì)具有獨(dú)立線性變?cè)?不在非線性項(xiàng)中出現(xiàn)) 的超多項(xiàng)式提出立方集的篩選算法, 給出一個(gè)843 輪Trivium 的平衡超多項(xiàng)式.

對(duì)于實(shí)驗(yàn)立方攻擊和基于可分性的立方攻擊, 如何構(gòu)造立方集或確定一個(gè)立方集的選擇范圍使得以較大概率可搜索到低次超多項(xiàng)式一直是一個(gè)困難問(wèn)題.以實(shí)驗(yàn)立方攻擊為例, 采用隨機(jī)搜索立方集的方法,很難找到800 輪以上Trivium 算法的線性超多項(xiàng)式.2021 年, Ye 等人在文獻(xiàn)[4] 中, 從實(shí)際密鑰恢復(fù)攻擊的角度考慮, 針對(duì)Trivium 的線性超多項(xiàng)式搜索給出一個(gè)立方集的啟發(fā)式構(gòu)造方法, 結(jié)合M?bius 變換和線性檢測(cè), 對(duì)于805 輪Trivium 恢復(fù)了1000 多個(gè)線性超多項(xiàng)式(含線性相關(guān)).隨后, 文獻(xiàn)[13] 將文獻(xiàn)[4] 中構(gòu)造方法與平衡多項(xiàng)式的篩選以及MILP 建模的超多項(xiàng)式恢復(fù)方法相結(jié)合, 對(duì)于恢復(fù)820 輪以下低次超多項(xiàng)式非常有效.

在立方攻擊的基礎(chǔ)上, 2011 年FSE 會(huì)議上, Dinur 和Shamir 進(jìn)一步提出動(dòng)態(tài)立方攻擊[14].在動(dòng)態(tài)立方攻擊中, 通過(guò)設(shè)置動(dòng)態(tài)IV 變?cè)? 可以零化某些中間狀態(tài)變?cè)? 達(dá)到簡(jiǎn)化輸出函數(shù)代數(shù)正規(guī)型的目的,從而一批立方集的超多項(xiàng)式能夠形成區(qū)分器, 例如零和區(qū)分器.利用動(dòng)態(tài)立方攻擊, 文獻(xiàn)[14] 分析了全輪Grain-128 算法, 給出了一個(gè)弱密鑰下的攻擊結(jié)果, 其弱密鑰空間為2118.隨后, 2011 年亞密會(huì)上, Dinur等人改進(jìn)了這一結(jié)果, 利用更低的計(jì)算復(fù)雜度攻擊了全輪Grain-128 算法, 并對(duì)該攻擊在正確密鑰下進(jìn)行了實(shí)驗(yàn)驗(yàn)證, 其中對(duì)于7.5% 的正確密鑰輸出具有明顯偏差[15].2020 年, Hao 等人在文獻(xiàn)[16] 中指出一個(gè)成功的攻擊不僅要評(píng)估正確密鑰的非隨機(jī)性, 還需要評(píng)估錯(cuò)誤密鑰的隨機(jī)性.基于這一想法, Hao 等人基于MILP 技術(shù)給出評(píng)估動(dòng)態(tài)立方攻擊成功概率的理論方法, 并對(duì)全輪Grain-128 給出一個(gè)新的動(dòng)態(tài)立方攻擊, 理論上成功概率為99.83%.

針對(duì)Trivium 算法的密鑰恢復(fù)攻擊, Liu 等人在文獻(xiàn)[17] 中提出了相關(guān)立方攻擊.相關(guān)立方攻擊利用超多項(xiàng)式與一組特定的低次多項(xiàng)式(稱之為基) 之間的條件相關(guān)概率建立關(guān)于密鑰變?cè)母怕史匠?利用該方法, 對(duì)于835 輪Trivium 算法, 以244的計(jì)算復(fù)雜度平均可以恢復(fù)5 比特密鑰信息.進(jìn)一步, 2023 年,Che 等人給出了一種新的相關(guān)立方攻擊框架, 能夠以245的計(jì)算復(fù)雜度恢復(fù)844 輪Trivium 算法的4 比特密鑰信息[18].

總的來(lái)說(shuō), 立方攻擊方法和技術(shù)不斷發(fā)展, 已成為評(píng)估基于NFSR 序列密碼算法安全性的重要方法.利用立方攻擊, 既可以對(duì)密碼算法進(jìn)行密鑰恢復(fù)攻擊, 也可以對(duì)密碼算法的代數(shù)性質(zhì)進(jìn)行檢測(cè), 具有較好的實(shí)用性和通用性.

本文內(nèi)容安排如下: 第2 節(jié)介紹立方攻擊基本原理; 第3 節(jié)介紹實(shí)驗(yàn)立方攻擊方法; 第4 節(jié)介紹基于可分性立方攻擊的研究進(jìn)展; 第5 節(jié)介紹立方集構(gòu)造研究進(jìn)展; 第6 節(jié)介紹動(dòng)態(tài)立方攻擊研究進(jìn)展; 第7 節(jié)介紹相關(guān)立方攻擊研究進(jìn)展; 第8 節(jié)對(duì)全文進(jìn)行總結(jié).

2 立方攻擊基本原理

序列密碼算法的每個(gè)輸出密鑰流比特可以自然視為關(guān)于密鑰Key 和公開初始化向量IV 的布爾函數(shù).以下均以序列密碼第一個(gè)輸出密鑰流比特為例進(jìn)行描述.設(shè)f(x,v) 表示第一個(gè)密鑰流比特關(guān)于密鑰變?cè)獂=(x0,x1,···,xn?1) 和IV 變?cè)獀=(v0,v1,···,vm?1) 的函數(shù).選擇若干IV 變?cè)? 并記這些IV 變?cè)南聵?biāo)集合為I ?{0,1,···,m ?1}, 那么函數(shù)f可以唯一地表示成f=t·pI ⊕q, 其中t=∏i∈I vi, 并且q的代數(shù)正規(guī)型中沒有t的倍式.記CI是IV 變?cè)囊唤M取值, 滿足下標(biāo)在I中的變?cè)?dú)立取遍0/1而下標(biāo)不在I中的變?cè)潭槌Ｖ?通常固定為0).那么,f(x,v) 關(guān)于CI求和有

集合CI稱為一個(gè)立方集(cube),{vi|i ∈I}稱為立方變?cè)?I稱為立方變?cè)南聵?biāo)集, 集合I的基數(shù)|I| 稱為CI的維數(shù), 多項(xiàng)式pI(x) 稱為I的超多項(xiàng)式(superpoly) 或CI的超多項(xiàng)式.

立方攻擊由離線階段和在線階段兩部分組成.離線階段的主要工作是搜索立方集和恢復(fù)超多項(xiàng)式的代數(shù)正規(guī)型; 在線階段的主要工作是獲得當(dāng)前密鑰條件下超多項(xiàng)式的函數(shù)值, 從而得到關(guān)于密鑰變?cè)姆匠探M, 求解方程組獲得密鑰信息.由于序列密碼算法在輸出第一個(gè)密鑰流比特以前, 內(nèi)部狀態(tài)經(jīng)過(guò)了高輪非線性迭代更新(例如Trivium 是1152 輪初始化), 所以函數(shù)f(x,v) 代數(shù)正規(guī)型的規(guī)模非常大, 在攻擊中是未知的.因此, 如何恢復(fù)超多項(xiàng)式一直是立方攻擊的關(guān)鍵問(wèn)題.

本文如果沒有特殊說(shuō)明, 設(shè)f(x,v) 表示支持n比特密鑰且m比特IV 的某個(gè)序列密碼算法的第一個(gè)輸出密鑰流比特, 其中x=(x0,x1,···,xn?1),v=(v0,v1,···,vm?1).

3 實(shí)驗(yàn)立方攻擊

2009 年, Dinur 和Shamir 提出立方攻擊的同時(shí), 也提出超多項(xiàng)式的線性檢測(cè)方法, 稱為實(shí)驗(yàn)立方攻擊.實(shí)驗(yàn)立方攻擊將序列密碼的輸出密鑰流比特看作黑盒布爾函數(shù), 通過(guò)對(duì)黑盒布爾函數(shù)的輸出進(jìn)行查詢,從而判斷超多項(xiàng)式是否是線性函數(shù), 如果是線性函數(shù), 則同樣通過(guò)查詢黑盒布爾函數(shù)恢復(fù)其代數(shù)正規(guī)型.

3.1 線性檢測(cè)和二次檢測(cè)

將f(x,v) 看作黑盒布爾函數(shù).設(shè)I是一個(gè)立方變?cè)南聵?biāo)集,pI是f(x,v) 關(guān)于I的超多項(xiàng)式.設(shè)a,b ∈Fn2, 通過(guò)查詢函數(shù)f(x,v) 的輸出, 可以計(jì)算出pI在變?cè)獂分別為a,b,a ⊕b,0 時(shí)的函數(shù)值, 驗(yàn)證下式是否成立

若pI是關(guān)于x的線性函數(shù)或常值函數(shù), 則式(1)總是成立; 否則,pI是關(guān)于x的非線性函數(shù), 則式(1)以一定概率成立.在實(shí)驗(yàn)立方攻擊中, 對(duì)于給定的I, 隨機(jī)選擇a,b ∈Fn2, 重復(fù)多次對(duì)式(1)進(jìn)行檢測(cè), 若pI通過(guò)了所有檢測(cè), 則認(rèn)為pI是線性超多項(xiàng)式1實(shí)際中, pI 有可能不是線性函數(shù), 但非常接近線性函數(shù)..一般地, 檢測(cè)的次數(shù)越多, 檢測(cè)結(jié)果的正確性越高, 也即pI是線性函數(shù)或常值函數(shù)的可能性越大.

若pI通過(guò)了線性檢測(cè), 則仍然通過(guò)訪問(wèn)黑盒布爾函數(shù)f(x,v) 可以進(jìn)一步得到pI的代數(shù)正規(guī)型.設(shè)

其中c,c0,···,cn?1是待定的系數(shù).對(duì)0≤i ≤n ?1,ei ∈Fn2表示第i+1 個(gè)分量等于1 且其余分量等于0 的F2上n維向量, 那么

類似線性檢測(cè), 也可以對(duì)超多項(xiàng)式pI(x) 進(jìn)行二次檢測(cè)并恢復(fù)函數(shù)的代數(shù)正規(guī)型.設(shè)a,b,c ∈Fn2, 若deg(pI(x))≤2, 則

成立; 若deg(pI(x))> 2, 則式(2)以一定概率成立.值得注意的是, 對(duì)于相同維數(shù)的立方集, 進(jìn)行1 次二次檢測(cè)的復(fù)雜度是進(jìn)行1 次線性檢測(cè)復(fù)雜度的兩倍.雖然二次檢測(cè)相較于線性檢測(cè), 計(jì)算復(fù)雜度僅是2 倍增長(zhǎng)關(guān)系, 實(shí)際攻擊中很少采用二次檢測(cè).主要原因有以下兩點(diǎn):

? 恢復(fù)二次超多項(xiàng)式并不能顯著降低立方集的維數(shù);

? 隨著立方集維數(shù)的增長(zhǎng), 例如40 維, 對(duì)超多項(xiàng)式進(jìn)行一次線性檢測(cè)的計(jì)算復(fù)雜度超過(guò)240, 而判斷一個(gè)超多項(xiàng)式是否為線性函數(shù)需要上百次測(cè)試, 這對(duì)于普通PC 機(jī)已需要耗費(fèi)大量時(shí)間, 2 倍復(fù)雜度的增長(zhǎng)往往超過(guò)了實(shí)際能夠承受的計(jì)算時(shí)間.

3.2 M?bius 變換

在立方攻擊中, 利用M?bius 變換可以同時(shí)對(duì)立方變?cè)疘的所有子立方變?cè)M(jìn)行線性檢測(cè), 這有效提高了檢測(cè)的效率, 從而增加了攻擊成功的可能性.

令h(x0,x1,···,xk?1) 是F2上k元布爾函數(shù), 其代數(shù)正規(guī)型可以表示為:

已知h真值表 (h(0),h(1),···,h(2k ?1)), 利用 M?bius 變換可以計(jì)算出h的代數(shù)正規(guī)型, 即(α0,α1,···,α2k?1), 參見算法1[19].對(duì)于一個(gè)k元布爾函數(shù), 算法1 的存儲(chǔ)復(fù)雜度為2k, 計(jì)算復(fù)雜度為k·2k.

下面介紹M?bius 變換在立方攻擊中的應(yīng)用.注意到在做線性檢測(cè)時(shí), 關(guān)鍵是求得超多項(xiàng)式在給定密鑰下的函數(shù)值, 因此, 這里僅需討論如何同時(shí)獲得一個(gè)立方集全體子立方集的超多項(xiàng)式在給定密鑰下的函數(shù)值.設(shè)I={i1,i2,···,id}是一個(gè)立方變?cè)聵?biāo)集.給定密鑰x=a, 并且下標(biāo)不在I中的IV 變?cè)潭槌Ｖ?.那么, 在此條件下,f是關(guān)于立方變?cè)囊粋€(gè)函數(shù), 其代數(shù)正規(guī)型可以表示為

其中J取遍I的所有子集,pJ(a) 是立方變?cè)瘂vj|j ∈J}所對(duì)應(yīng)的超多項(xiàng)式在x=a的函數(shù)值.當(dāng)IV 取遍d維立方集CI中的元素時(shí), 記錄函數(shù)f(a,v) 的2d個(gè)函數(shù)值, 也即f(a,0,{vi|i ∈I}) 關(guān)于變?cè)獅vi|i ∈I}的真值表S, 利用算法1, 可得函數(shù)f(a,0,{vi|i ∈I}) 代數(shù)正規(guī)型中全體單項(xiàng)式系數(shù), 由式(3)知, 也即每個(gè)單項(xiàng)式∏j∈J vj前面的系數(shù)pJ(a).這樣就獲得了I的全體子集所對(duì)應(yīng)的超多項(xiàng)式在x=a的函數(shù)值.

一般地, 在實(shí)際攻擊中, 對(duì)于一個(gè)d維立方集, 只需要檢測(cè)維數(shù)較大的子立方集, 不需要檢測(cè)其所有子立方集, 這是因?yàn)殡S著維數(shù)的降低, 找到線性或二次超多項(xiàng)式的可能性越來(lái)越小.在文獻(xiàn)[4] 中, 針對(duì)只考慮大維數(shù)立方子集的情形, 作者提出了一種改進(jìn)的M?bius 變換, 可以降低存儲(chǔ)復(fù)雜度.

算法1 M?bius 變換Input: h(x0,x1,··· ,xk?1) 的真值表S Output: h 的單項(xiàng)式系數(shù)S 1 for i from 0 to k ?1 do 5 for j from 0 to Sz ?1 do 2 Sz ←2i;3 Pos ←0;4 while Pos < 2k do 6 S[Pos+Sz +j] ←S[Pos+j]⊕S[Pos+Sz +j];7 end Pos ←Pos+2·Sz;9 end 10 end 8

3.3 應(yīng)用

實(shí)驗(yàn)立方攻擊主要應(yīng)用于Trivium 算法.2009 年, 文獻(xiàn)[1] 中給出35 個(gè)767–774 輪的線性超多項(xiàng)式.2012 年, 文獻(xiàn)[20] 中給出38 個(gè)709–712 輪的二次超多項(xiàng)式.2013 年, 文獻(xiàn)[2] 給出12 個(gè)799 輪線性超多項(xiàng)式和6 個(gè)799 輪二次超多項(xiàng)式.2018 年, 文獻(xiàn)[3] 中給出8 個(gè)802 輪線性超多項(xiàng)式和2 個(gè)802輪二次超多項(xiàng)式.2021 年, 文獻(xiàn)[4] 在結(jié)合立方集構(gòu)造方法條件下, 利用線性檢測(cè)恢復(fù)了大量805 輪線性超多項(xiàng)式以及2 個(gè)810 輪線性超多項(xiàng)式, 這是線性檢測(cè)方法恢復(fù)的最高輪數(shù)超多項(xiàng)式.

4 基于可分性和MILP 的立方攻擊

在實(shí)驗(yàn)立方攻擊中,對(duì)一個(gè)d維立方集的超多項(xiàng)式進(jìn)行線性檢測(cè)的計(jì)算復(fù)雜度和存儲(chǔ)復(fù)雜度是O(2d).所以, 一般情況下, 攻擊者至多只能對(duì)40 維左右的立方集進(jìn)行檢測(cè), 這在很大程度上限制了立方攻擊的效果和基于立方攻擊的安全性評(píng)估能力.2017 年, Todo 等人將分組密碼搜索積分區(qū)分器的二子集可分性引入到立方攻擊中[5], 結(jié)合混合整數(shù)線性規(guī)劃MILP 模型可以有效分析高維立方集對(duì)應(yīng)超多項(xiàng)式的代數(shù)性質(zhì).基于可分性和MILP 的立方攻擊是目前針對(duì)序列密碼算法最有效且應(yīng)用最廣泛的一類密碼分析方法.

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

混合整數(shù)線性規(guī)劃(mixed integer linear programming, MILP) 是一類數(shù)學(xué)優(yōu)化問(wèn)題, 由變?cè)?、線性限制條件、目標(biāo)函數(shù)組成, 其中部分或全部取值限制在整數(shù)范圍, 其標(biāo)準(zhǔn)形式可以表示如下:

其中x ∈Zk×Rn?k,A ∈Rm,n,b ∈Rm,c ∈Rn, 且x,b,c是列向量.在一個(gè)MILP 模型M中, 用M.var 表示變?cè)?M.con 表示限制條件,M.obj 表示目標(biāo)函數(shù).常用的MILP 模型求解器有Gurobi[21]等.如果模型有解, 則求解器根據(jù)參數(shù)設(shè)置返回一個(gè)解或全部解; 如果模型沒有解, 則求解器返回?zé)o解.若模型沒有目標(biāo)函數(shù), 則求解器僅返回是否可解.實(shí)際上, 在序列密碼的立方攻擊中, MILP 模型的變?cè)际侨≌麛?shù)0 或1.

4.2 基于比特的可分性

可分性由Todo 在2015 年歐密會(huì)上首次提出[22], 是針對(duì)分組密碼算法的一種廣義積分性質(zhì), 可用來(lái)搜索分組密碼的積分區(qū)分器.同年, Todo 在文獻(xiàn)[23] 中利用可分性得到了MISTY1 算法6 輪積分區(qū)分器, 進(jìn)而給出了MISTY1 算法首個(gè)全輪的理論攻擊.在2016 年FSE 會(huì)議上, Todo 等人針對(duì)基于比特運(yùn)算設(shè)計(jì)的SIMON 類密碼算法進(jìn)一步提出了基于比特的可分性(bit-based division property), 包括傳統(tǒng)的基于比特的可分性(conventional bit-based division property, CBDP) 和基于比特的三子集可分性(bit-based division property using three subsets, BDPT), 以及它們的傳播規(guī)則[24].在序列密碼算法分析中, 主要采用基于比特的可分性.傳統(tǒng)的基于比特的可分性與基于比特的三子集可分性的定義如下.

雖然基于比特的可分性能夠用來(lái)搜索更準(zhǔn)確的積分特征, 但是計(jì)算其傳播所需要的時(shí)間和存儲(chǔ)復(fù)雜度通常比較大.為了解決該問(wèn)題, Xiang 等人在文獻(xiàn)[25] 中引入了基于MILP 建模的搜索方法.文獻(xiàn)[25]首次給出了可分路徑的概念, 用來(lái)描述可分性在分組密碼算法中的傳播; 同時(shí), 給出了傳統(tǒng)的基于比特的可分性關(guān)于AND (與運(yùn)算)、XOR (異或運(yùn)算) 以及COPY (復(fù)制運(yùn)算) 傳播規(guī)則的MILP 建模方法.利用自動(dòng)化工具求解對(duì)應(yīng)的MILP 模型, 顯著提高了搜索積分區(qū)分器的效率.

是E的一條r輪可分路徑.

需要注意的是給定一個(gè)輸入可分性質(zhì)k0和一個(gè)輸出可分性質(zhì)kr, 可能存在很多條從k0到kr的可分路徑.下面給出可分性關(guān)于AND、XOR 以及COPY 傳播規(guī)律的MILP 模型.由于基于比特的分組密碼算法和序列密碼算法的輪函數(shù)都是由這些基本運(yùn)算構(gòu)成的, 在此基礎(chǔ)上可以建立針對(duì)任意加密輪數(shù)的可分路徑傳播模型.特別地, 對(duì)于給定輸入可分性質(zhì)k0和輸出可分性質(zhì)kr, 建立的MILP 模型可以覆蓋所有從k0到kr的可分路徑.

AND 運(yùn)算的MILP 模型[25].令(a1,a2,···,am)是經(jīng)過(guò)AND 的一條可分性路徑, 則下面的不等式描述了AND 運(yùn)算可分性的傳播規(guī)律:

4.3 基于二子集可分性的立方攻擊

在2017 年美密會(huì)上, Todo 首次將傳統(tǒng)的基于比特的可分性及其MILP 建模方法引入到序列密碼分析中, 提出了基于可分性的立方攻擊[5].在文獻(xiàn)[5] 中, 利用CBDP 和MILP 建?？梢耘袛嗄男┟荑€變?cè)怀霈F(xiàn)在給定立方集的超多項(xiàng)式中.下面的命題給出了CBDP 可分路徑與超多項(xiàng)式代數(shù)正規(guī)型的一種聯(lián)系.

命題1[5]設(shè)I是一個(gè)立方變?cè)南聵?biāo)集,kI ∈Fm2滿足vkI=∏i∈I vi.若不存在形如(ej,kI)f?→1 的可分路徑, 則xj不出現(xiàn)在pI(x) 的代數(shù)正規(guī)型中.

基于命題1, 對(duì)于給定的一組立方變?cè)疘, 可以建立描述從(ej,kI) 到1 經(jīng)過(guò)函數(shù)f的可分性傳播模型M, 若模型M無(wú)解, 則我們知道密鑰xj不出現(xiàn)在I的超多項(xiàng)式pI(x) 中.需要注意的是, 即使MILP 模型M有解, 變?cè)獂j也有可能不出現(xiàn)在pI(x) 中.主要原因有以下兩點(diǎn):

? 在CBDP 的MILP 建模中,常值視為常值變?cè)?這意味著只要單項(xiàng)式xjvkI的倍式出現(xiàn)在f(x,v)中, 模型M一定有解, 而實(shí)際中非立方變?cè)娜≈禃?huì)影響pI(x) 的具體代數(shù)正規(guī)型;

? 在CBDP 的MILP 建模中, 沒有處理異或運(yùn)算消項(xiàng)的問(wèn)題.

基于CBDP 和MILP 建模的立方攻擊步驟如下:

離線階段.選擇一個(gè)以I為下標(biāo)集的立方變?cè)? 利用MILP 模型得到一組不出現(xiàn)在pI中的密鑰變?cè)? 剩余的密鑰變?cè)洖榧螶.隨機(jī)設(shè)定一組非立方變?cè)娜≈礐, 計(jì)算超多項(xiàng)式pI({xj|j ∈J},C)的真值表, 計(jì)算復(fù)雜度為2|I|+|J|.若pI({xj|j ∈J},C) 是常值函數(shù), 則通過(guò)改變非立方變?cè)娜≈? 直到對(duì)應(yīng)的超多項(xiàng)式為非常值函數(shù).

在線階段.對(duì)于離線階段記錄的立方變?cè)疘, 設(shè)置非立方變?cè)娜≈? 使得超多項(xiàng)式pI(x) 是非常值函數(shù).在當(dāng)前密鑰下計(jì)算pI(x) 的函數(shù)值a, 建立關(guān)于密鑰的方程pI(x)=a.利用多個(gè)立方集, 可以建立關(guān)于密鑰的一組方程.

窮舉搜索階段.窮盡滿足方程解的剩余密鑰, 并逐個(gè)驗(yàn)證.

在上述攻擊中, 當(dāng)2|I|+|J|超過(guò)計(jì)算能力時(shí), 實(shí)際無(wú)法判斷超多項(xiàng)式pI({xj|j ∈J},C) 在給定非立方變?cè)≈禐镃時(shí)是否為常值多項(xiàng)式, 因此, 在文獻(xiàn)[5] 中提出如下兩個(gè)假設(shè):

假設(shè)1 (強(qiáng)假設(shè)) 對(duì)于給定的立方變?cè)聵?biāo)集I,存在很多非立方變?cè)馁x值使得I的超多項(xiàng)式pI(x)是平衡函數(shù).

假設(shè)2 (弱假設(shè)) 對(duì)于給定的立方變?cè)聵?biāo)集I,存在很多非立方變?cè)馁x值使得I的超多項(xiàng)式pI(x)不是常值函數(shù).

由于MILP 模型對(duì)于比較大維數(shù)的立方集, 例如70 維, 也可以快速求解集合J, 所以基于假設(shè)1 和假設(shè)2, 對(duì)于維數(shù)較大的立方集, 也可以給出密鑰恢復(fù)攻擊的理論分析.據(jù)此, 文獻(xiàn)[5] 中給出832 輪Trivium、183 輪Grain128a、872 輪Kreyvium 的理論攻擊, 立方集的維數(shù)分別是72、92 和64.隨后, 在2018 年美密會(huì)上, Wang 等人對(duì)傳統(tǒng)的基于比特可分性的MILP 建模方法進(jìn)行了一些技術(shù)上的改進(jìn)[6],同樣基于假設(shè)1 和假設(shè)2, 給出了839 輪Trivium、891 輪Kreyvium 和184 輪Grain-128a 的理論攻擊,立方集維數(shù)分別為78、113 和95.

值得注意的是, 上述假設(shè)對(duì)于Trivium 常常不成立, 例如當(dāng)集合J非空時(shí), 超多項(xiàng)式仍然可能是零常值, 這意味著任意非立方變?cè)娜≈? 超多項(xiàng)式都是零常值.文獻(xiàn)[7] 中通過(guò)對(duì)超多項(xiàng)式的準(zhǔn)確計(jì)算, 說(shuō)明了文獻(xiàn)[6] 中所給的833 輪–839 輪的5 個(gè)超多項(xiàng)式實(shí)際都是零常值, 從而與此相關(guān)的密鑰恢復(fù)攻擊均不成立, 應(yīng)是區(qū)分攻擊.此外, Wang 等人在文獻(xiàn)[8] 中也指出文獻(xiàn)[6] 的一些立方集的超多項(xiàng)式是零常值.

自2017 年Todo 等人將可分性和MILP 引入立方攻擊后, 如何基于可分性理論和MILP 建?；謴?fù)準(zhǔn)確的超多項(xiàng)式成為序列密碼立方攻擊的一個(gè)重要問(wèn)題.

2019 年, Ye 等人在文獻(xiàn)[7] 中提出一種基于CBDP 恢復(fù)超多項(xiàng)式的代數(shù)方法, 能夠恢復(fù)準(zhǔn)確的超多項(xiàng)式, 該技術(shù)思想在后續(xù)文獻(xiàn)[10] 的大規(guī)模超多項(xiàng)式恢復(fù)算法中也有應(yīng)用.文獻(xiàn)[7] 恢復(fù)超多項(xiàng)式的基本框架如下.首先, 選擇一個(gè)立方變?cè)疘.然后, 將輸出密鑰流比特表達(dá)成中間狀態(tài)變?cè)暮瘮?shù):

其中U ?{0,1}b,αi(x,v) 表示更新過(guò)程中某個(gè)內(nèi)部狀態(tài)比特變?cè)?可以是不同時(shí)刻).那么,I在f(x,v)中的超多項(xiàng)式滿足

4.4 基于無(wú)未知子集的三子集可分性的立方攻擊

2020 年歐密會(huì)上, Hao 等人在文獻(xiàn)[9] 中提出無(wú)未知子集的三子集可分性(three-subset division property without unknown subset, 3SDP/u), 從而較好解決了基于MILP 建模的超多項(xiàng)式恢復(fù)問(wèn)題.下面給出3SDP/u 的定義及其對(duì)應(yīng)的MILP 建模規(guī)則.

對(duì)于傳統(tǒng)基于CBDP 的MILP 建模, 目標(biāo)是找到一條傳播路徑或判斷沒有可分路徑[5,17].特別地,一個(gè)MILP 模型無(wú)解時(shí), 攻擊者可以知道某個(gè)項(xiàng)在超多項(xiàng)式中的系數(shù)為0; 而MILP 模型有解時(shí), 攻擊者不能確定該項(xiàng)在超多項(xiàng)式中的系數(shù).在3SDP/u 模型中, 給定初始可分性和常值, 一個(gè)可行解描述一條可分路徑, 可行解與可分路徑一一對(duì)應(yīng), 通過(guò)可分路徑的奇偶性可以準(zhǔn)確知道某個(gè)項(xiàng)在超多項(xiàng)式代數(shù)正規(guī)型中的系數(shù), 從而準(zhǔn)確恢復(fù)超多項(xiàng)式.具體地, 可行解為偶數(shù)的項(xiàng)在超多項(xiàng)式的代數(shù)正規(guī)型中系數(shù)為0, 即因?yàn)楫惢蜻\(yùn)算而消項(xiàng), 可行解為奇數(shù)的項(xiàng)在超多項(xiàng)式的代數(shù)正規(guī)型中系數(shù)為1, 即真正出現(xiàn)在超多項(xiàng)式代數(shù)正規(guī)型中的項(xiàng).因此, 所有奇數(shù)路徑的可行解即為超多項(xiàng)式的所有項(xiàng).利用新的建模技術(shù), Hao 等人給出了841 輪Trivium 和190 輪Grain-128AEAD 的密鑰恢復(fù)攻擊[9].

隨后, 在3SDP/u 模型基礎(chǔ)上, 為了能夠給出更高輪數(shù)的立方攻擊, 一系列針對(duì)大規(guī)模超多項(xiàng)式的恢復(fù)方法被提出.2021 年亞密會(huì)上, Hu 等人提出了嵌套單項(xiàng)式預(yù)測(cè)的恢復(fù)超多項(xiàng)式技術(shù)[10], 其也采用了和文獻(xiàn)[7] 類似的分治技術(shù), 即根據(jù)算法內(nèi)部更新函數(shù)的代數(shù)表達(dá)式, 將輸出比特表示為關(guān)于中間狀態(tài)比特的多項(xiàng)式, 通過(guò)恢復(fù)每個(gè)單項(xiàng)式的超多項(xiàng)式進(jìn)而恢復(fù)完整的超多項(xiàng)式.文獻(xiàn)[10] 與文獻(xiàn)[7] 存在兩點(diǎn)不同.第一, 文獻(xiàn)[10] 采用3SDP/u 的MILP 模型求每個(gè)中間狀態(tài)比特乘積αc11αc22···αcbb的超多項(xiàng)式, 而文獻(xiàn)[7] 采用CBDP 的MILP 模型判斷每個(gè)αc11αc22···αcbb的超多項(xiàng)式是否為零常值.第二, 通過(guò)設(shè)置時(shí)間閾值,文獻(xiàn)[10]提前結(jié)束很難求解的模型,即如果在給定時(shí)間內(nèi)關(guān)于某個(gè)中間狀態(tài)比特乘積αc11αc22···αcbb的MILP 模型未能求解, 則將該單項(xiàng)式進(jìn)一步展開, 表示為關(guān)于更早時(shí)刻中間狀態(tài)比特的多項(xiàng)式, 再建模計(jì)算每個(gè)單項(xiàng)式的超多項(xiàng)式.文獻(xiàn)[10] 恢復(fù)了超過(guò)一千萬(wàn)項(xiàng)的845 輪Trivium 超多項(xiàng)式.2021 年亞密會(huì)上, 在文獻(xiàn)[10] 方法基礎(chǔ)上, Hu 等人引入有效項(xiàng)(valuable terms) 的概念, 并提出了兩種篩選有效項(xiàng)的新技術(shù),非零比特可分性(non-zero bit-based division property,NBDP)和核心單項(xiàng)式預(yù)測(cè)(core monomial prediction, CMP)[11].兩種新技術(shù)在嵌套單項(xiàng)式預(yù)測(cè)技術(shù)中的應(yīng)用, 能夠避免在對(duì)超多項(xiàng)式?jīng)]有任何貢獻(xiàn)的中間項(xiàng)上浪費(fèi)計(jì)算資源, 進(jìn)而恢復(fù)了848 輪Trivium、895 輪Kreyvium 和192 輪Grain-128AEAD的準(zhǔn)確超多項(xiàng)式, 這是目前這些算法能夠恢復(fù)的最高輪數(shù)超多項(xiàng)式.

5 立方集的構(gòu)造

隨著恢復(fù)超多項(xiàng)式的方法越來(lái)越有效, 立方攻擊的另一個(gè)問(wèn)題, 即如何選擇立方集也越來(lái)越受關(guān)注.可分性的提出使得在立方集的構(gòu)造上有了新的突破, 一系列基于可分性的構(gòu)造立方集的方法被提出.2021年, Ye 等人將貪心比特集算法與基于可分性的代數(shù)次數(shù)估計(jì)方法相結(jié)合, 給出了用于恢復(fù)線性超多項(xiàng)式的立方集構(gòu)造算法[4].在構(gòu)造過(guò)程中, Ye 等人先啟發(fā)式地給出一個(gè)小維數(shù)的初始立方集, 再對(duì)其分兩階段添加IV 變?cè)? 從而成功構(gòu)造了包含線性超多項(xiàng)式的立方集.為方便描述擴(kuò)展的兩個(gè)階段, 首先給出以下兩個(gè)定義.

定義5[4]令I(lǐng)={vi1,vi2,···,vil}是一個(gè)有l(wèi)個(gè)IV 變?cè)牧⒎阶冊(cè)?如果一個(gè)IV 變?cè)猙滿足

則稱b是一個(gè)快速下降IV 變?cè)? 其中B={v0,v1,···,vm?1}I且ds(I) 是立方變?cè)疘在輸出中的超多項(xiàng)式的次數(shù).

定義6[4]令I(lǐng)={vi1,vi2,···,vil}是一個(gè)有l(wèi)個(gè)IV 變?cè)牧⒎阶冊(cè)?如果一個(gè)IV 變?cè)猙滿足

則稱b是一個(gè)緩慢下降IV 變?cè)? 其中B={v0,v1,···,vm?1}I且ds(I) 是立方變?cè)疘在輸出中的超多項(xiàng)式的次數(shù).

基于定義5 和定義6, Ye 等人提出了一個(gè)針對(duì)線性超多項(xiàng)式的立方集構(gòu)造方法.給定一個(gè)初始立方集I, 在第一階段中, 對(duì)于每次迭代選擇快速下降變?cè)獙?duì)集合I進(jìn)行擴(kuò)充, 使得超多項(xiàng)式的代數(shù)次數(shù)盡可能快地下降.然而, 僅通過(guò)添加快速下降變?cè)獰o(wú)法構(gòu)造具有線性超多項(xiàng)式的立方集.因此, 第二階段的目標(biāo)是確保超多項(xiàng)式的次數(shù)可以接近1, 而不是突然下降到0.在第二階段, 通過(guò)逐步添加緩慢下降IV 變?cè)?能以更高的概率構(gòu)造具有線性超多項(xiàng)式的立方變?cè)?成功構(gòu)造出候選立方集之后, Ye 等人再利用基于M?bius 的實(shí)驗(yàn)檢測(cè), 搜索線性超多項(xiàng)式.應(yīng)用于805 輪Trivium, 得到大量線性超多項(xiàng)式, 給出一個(gè)實(shí)際密鑰恢復(fù)攻擊.隨后, 在文獻(xiàn)[13] 中, Che 等人仍利用該方法構(gòu)造大立方集, 并提出了從大立方集中搜索有價(jià)值子立方集的方法.利用3SDP/u 對(duì)搜索得到的立方集逐個(gè)恢復(fù)超多項(xiàng)式, Che 等人給出了815 輪和820 輪Trivium 的實(shí)際密鑰恢復(fù)攻擊.

2021 年, Sun 基于實(shí)驗(yàn)觀察和分治技術(shù), 針對(duì)具有獨(dú)立線性變?cè)钠胶獬囗?xiàng)式(該變?cè)怀霈F(xiàn)在非線性項(xiàng)中), 提出了從大立方集中排除無(wú)效立方集的啟發(fā)式算法, 用來(lái)構(gòu)造具有平衡超多項(xiàng)式的立方集[12],給出了808 輪Trivium 的實(shí)際密鑰恢復(fù)攻擊, 并成功恢復(fù)了843 輪Trivium 的一個(gè)平衡超多項(xiàng)式.這是目前已知的最高輪數(shù)平衡超多項(xiàng)式, 大于843 輪的已知超多項(xiàng)式由于規(guī)模大, 無(wú)法準(zhǔn)確判斷其平衡性.

6 動(dòng)態(tài)立方攻擊

在立方攻擊的基礎(chǔ)上, 2011 年, Dinur 等人提出動(dòng)態(tài)立方攻擊[14].動(dòng)態(tài)立方攻擊是針對(duì)Grain 系列算法的重要攻擊方法.相比立方攻擊通過(guò)求解密鑰方程組來(lái)獲取密鑰信息, 動(dòng)態(tài)立方攻擊則是通過(guò)區(qū)分器來(lái)識(shí)別正確密鑰.在動(dòng)態(tài)立方攻擊中, 通過(guò)設(shè)置Key/IV 變?cè)谋磉_(dá)式條件, 達(dá)到簡(jiǎn)化輸出函數(shù)f(x,v) 代數(shù)正規(guī)型的目的; 若動(dòng)態(tài)條件中同時(shí)含有密鑰變?cè)虸V 變?cè)? 則可以恢復(fù)密鑰信息.

動(dòng)態(tài)立方攻擊將IV 變?cè)譃槿? 立方變?cè)?、常值、?dòng)態(tài)變?cè)? 其中每個(gè)動(dòng)態(tài)變?cè)梢粋€(gè)關(guān)于立方變?cè)兔荑€變?cè)谋磉_(dá)式確定.通過(guò)設(shè)置動(dòng)態(tài)變?cè)? 可以零化某些中間狀態(tài), 使得超多項(xiàng)式有可能呈現(xiàn)出不隨機(jī)性.在非常理想的情況下, 若密鑰猜測(cè)正確, 則超多項(xiàng)式可以檢測(cè)出不隨機(jī)性, 例如0 常值多項(xiàng)式;若密鑰猜測(cè)錯(cuò)誤, 則超多項(xiàng)式檢測(cè)為一個(gè)隨機(jī)多項(xiàng)式, 排除錯(cuò)誤密鑰.2011 年, Dinur 等人利用動(dòng)態(tài)立方攻擊, 分析了全輪Grain-128 算法, 并對(duì)攻擊進(jìn)行了實(shí)驗(yàn)驗(yàn)證[15].然而, 在實(shí)際情況中, 由于超多項(xiàng)式未知, 排除錯(cuò)誤密鑰的效果并不好.在文獻(xiàn)[15] 中, 對(duì)107 個(gè)正確密鑰進(jìn)行檢測(cè), 8 個(gè)正確密鑰的超多項(xiàng)式觀察到明顯0/1 偏差, 對(duì)正確密鑰攻擊成功的概率約為7.5%.由此可見, 文獻(xiàn)[15] 的動(dòng)態(tài)立方攻擊中超多項(xiàng)式的性質(zhì)對(duì)于正確密鑰和錯(cuò)誤密鑰的區(qū)分不大.因此, 動(dòng)態(tài)立方攻擊的研究中存在的突出問(wèn)題是: 排除錯(cuò)誤密鑰的概率建立在隨機(jī)假設(shè)之上, 隨機(jī)假設(shè)與實(shí)際情況是否相符不清楚.

對(duì)于上述問(wèn)題, Hao 等人在文獻(xiàn)[16] 中指出一個(gè)成功的攻擊不僅要評(píng)估正確密鑰的非隨機(jī)性, 還要評(píng)估錯(cuò)誤密鑰的隨機(jī)性.基于這一想法, Hao 等人考慮如何分析一個(gè)超多項(xiàng)式pI(x) 的偏差.他們將整個(gè)空間分成弱密鑰空間W和補(bǔ)集 ˉW.在弱密鑰空間W中, 超多項(xiàng)式恒為0; 在補(bǔ)集 ˉW中, 假設(shè)超多項(xiàng)式0/1 平衡.那么, 對(duì)于超多項(xiàng)式pI(x), 給定一個(gè)弱密鑰空間W, 則有

滿足對(duì)所有x ∈WΛ, 都有pI(x)=0, 則稱Λ 是一個(gè)分裂集.

分裂集Λ 定義了一類大小為2n?|Λ|的弱密鑰空間, 并且在假設(shè)條件下超多項(xiàng)式在該弱密鑰空間中的偏差為2?(|Λ|+1).在攻擊中, 對(duì)于正確密鑰條件, 超多項(xiàng)式等于0; 對(duì)于錯(cuò)誤密鑰條件, 通過(guò)MILP 模型構(gòu)造最小分裂集, 根據(jù)分裂集大小給出超多項(xiàng)式偏差的一個(gè)理論估計(jì).文獻(xiàn)[16] 對(duì)全輪Grain-128 給出一個(gè)新的動(dòng)態(tài)立方攻擊, 并評(píng)估成功概率為99.83%.

7 相關(guān)立方攻擊

2018 年, Liu 等人提出相關(guān)立方攻擊[17], 其思想是利用超多項(xiàng)式和密鑰表達(dá)式之間的相關(guān)性建立密鑰方程, 主要應(yīng)用到Trivium 算法.2023 年, Che 等人提出新的相關(guān)立方攻擊模型[18], 提高了對(duì)Trivium算法的攻擊效果.

7.1 數(shù)值映射

數(shù)值映射是文獻(xiàn)[17] 中實(shí)現(xiàn)相關(guān)立方攻擊的基本技術(shù), 也是Trivium 型序列密碼算法判斷代數(shù)次數(shù)上界的重要方法.

數(shù)值映射最早由Liu 在2017 年美密會(huì)上提出[26].設(shè)

是一個(gè)m元布爾函數(shù),D=(d0,d1,···,dm?1)∈Zm, 則函數(shù)h的數(shù)值映射DEG(h,D) 定義為

利用數(shù)值映射, 文獻(xiàn)[26] 中進(jìn)一步定義了合成函數(shù)的數(shù)值次數(shù).設(shè)g0,g1,···,gm?1是m個(gè)n元布爾函數(shù),h1=h(g0,g1,···,gm?1) 是一個(gè)合成函數(shù), 則h1的數(shù)值次數(shù)定義為DEG(h1,deg(G)), 其中G=(g0,g1,···,gm?1) 且deg(G)=(deg(g0),deg(g1),···,deg(gm?1)).顯然, 合成函數(shù)的代數(shù)次數(shù)總是小于等于其數(shù)值次數(shù), 即deg(h1)≤DEG(h,deg(G)).進(jìn)一步, 若已知deg(G)≤D=(d0,d1,···,dm?1),則也有deg(h1)≤DEG(h,D).利用這個(gè)不等式, 容易估計(jì)非線性迭代密碼的代數(shù)次數(shù).文獻(xiàn)[26] 中對(duì)Trivium-型序列密碼算法的代數(shù)次數(shù)進(jìn)行了一系列評(píng)估.2021 年, 針對(duì)數(shù)值映射中變量可能被重復(fù)計(jì)數(shù)的問(wèn)題, Ye 等人在文獻(xiàn)[27] 中給出了一種改進(jìn)的數(shù)值映射方法, 可以代替Liu 提出的數(shù)值映射, 得到更緊的代數(shù)次數(shù)上界.

7.2 利用基多項(xiàng)式分解的相關(guān)立方攻擊

在數(shù)值映射基礎(chǔ)上, Liu 等人于2018 年歐密會(huì)上提出相關(guān)立方攻擊[17].該攻擊利用數(shù)值映射給出超多項(xiàng)式的低次基多項(xiàng)式分解, 在基多項(xiàng)式中搜索與超多項(xiàng)式具有相關(guān)性的密鑰表達(dá)式.一個(gè)布爾函數(shù)的基多項(xiàng)式分解定義如下.

定義8 給定一個(gè)布爾函數(shù)h, 稱h=⊕ui=1hi·gi是h的一個(gè)分解, 并且G={g1,g2,···,gu}是h的一組基.

攻擊分為兩個(gè)階段: 預(yù)處理階段和在線階段.預(yù)處理階段, 對(duì)每個(gè)給定的立方集, 試圖找到超多項(xiàng)式的一組基并計(jì)算基多項(xiàng)式與超多項(xiàng)式的條件相關(guān)概率.因?yàn)榛贜FSR 的序列密碼是非線性迭代型密碼,所以文獻(xiàn)[17] 中提出前N0輪狀態(tài)比特中關(guān)于立方變?cè)淖畲蟠螖?shù)項(xiàng)的系數(shù), 很可能是一組基.在搜索基多項(xiàng)式時(shí), 選定N0, 計(jì)算前N0輪更新狀態(tài)中立方變?cè)畲蟠螖?shù)項(xiàng)的系數(shù).將這些關(guān)于密鑰變?cè)南禂?shù)表達(dá)式設(shè)置為0 后(除常值以外), 利用數(shù)值映射判斷第r輪超多項(xiàng)式是否為0.若超多項(xiàng)式等于0, 則這些系數(shù)表達(dá)式構(gòu)成超多項(xiàng)式的一組基.設(shè)I是一個(gè)具有低次分解基G的立方變?cè)?對(duì)于g ∈G, 估計(jì)在固定密鑰下的條件概率Pr(g= 0|pI(key,·)≡0) 和Pr(g= 1|pI(key,·)?≡0).在線攻擊階段, 通過(guò)超多項(xiàng)式的具體值, 選擇大于一定概率閾值的方程建立密鑰方程組.對(duì)于835 輪Trivium, 文獻(xiàn)[17] 平均可以恢復(fù)5 個(gè)密鑰比特, 在線攻擊復(fù)雜度244.文獻(xiàn)[27] 利用改進(jìn)的數(shù)值映射方法, 給出更多可用于對(duì)835 輪Trivium 進(jìn)行相關(guān)立方攻擊的立方集.

7.3 相關(guān)立方攻擊的新框架

給定立方集, 文獻(xiàn)[17] 的方法是先確定一組基多項(xiàng)式, 而后分析這些多項(xiàng)式和超多項(xiàng)式之間的條件相關(guān)性.然而, 基多項(xiàng)式是不唯一的, 可能一些具有較好相關(guān)性的低次多項(xiàng)式?jīng)]有被選到, 導(dǎo)致攻擊不成功.為了避免基的局限性以及更好地選擇一組相關(guān)性高的多項(xiàng)式, Che 等人在文獻(xiàn)[18] 中丟掉了基的概念, 提出了新的相關(guān)立方攻擊框架, 從更一般更直接的角度刻畫了在什么情形下密鑰表達(dá)式f(x,v) 和超多項(xiàng)式pI(x) 會(huì)具有好的相關(guān)性.

在立方攻擊中, 選定立方變?cè)疘后, 超多項(xiàng)式pI也可以視為關(guān)于密鑰和非立方變?cè)牟紶柡瘮?shù).若超多項(xiàng)式pI形如λ(x)g(x,v), 則在固定密鑰下, 可將pI看成關(guān)于IV 的黑盒多項(xiàng)式, 通過(guò)查詢pI的值來(lái)猜測(cè)λ(x) 的值.具體地, 若對(duì)于某組IV 有pI= 1, 則λ(x) = 1, 從而得到以概率1 成立的密鑰方程;若對(duì)于多組IV,pI始終等于0, 則λ(x) 以一定概率等于0.考慮到出現(xiàn)形如pI=λ(x)g(x,v) 的概率很小, 在文獻(xiàn)[18] 中, 作者將pI=λ(x)g(x,v) 擴(kuò)展為pI=λ(x)g(x,v)⊕h(x,v), 其中h是有明顯偏差的函數(shù).例如, 當(dāng)h以很大概率為0 時(shí),pI也可近似看成λ(x)g(x,v) 的形式, 仍可利用pI和λ(x) 之間的條件相關(guān)性來(lái)獲取密鑰信息.文獻(xiàn)[18] 搜索密鑰表達(dá)式的模型比文獻(xiàn)[17] 更全面, 搜索更細(xì)致, 并且搜索到的密鑰表達(dá)式完全包含了原模型中的密鑰表達(dá)式.在攻擊時(shí), 作者將可分性引入相關(guān)立方攻擊中, 借助MILP 建模技術(shù)對(duì)相關(guān)立方攻擊中可利用的立方集進(jìn)行搜索.對(duì)于844 輪Trivium, 平均能以245的計(jì)算復(fù)雜度恢復(fù)4 比特的密鑰信息, 通過(guò)實(shí)驗(yàn)可以充分驗(yàn)證.這是迄今為止對(duì)844 輪Trivium 密鑰恢復(fù)攻擊的最好結(jié)果.

8 總結(jié)

本文對(duì)立方攻擊的提出和發(fā)展進(jìn)行了系統(tǒng)的梳理和總結(jié).立方攻擊是序列密碼的一種重要攻擊方法.立方攻擊首次針對(duì)基于NFSR 序列密碼算法給出了建立低次密鑰方程的方法.搜索分組密碼積分區(qū)分器的可分性和MILP 建模方法引入立方攻擊后, 可用于攻擊的立方集的維數(shù)大大提高, 使得立方攻擊成為評(píng)估基于NFSR 序列密碼算法安全性的重要工具.三子集不含未知子集的MILP 建模方法首次較好解決了基于可分性立方攻擊中精確恢復(fù)超多項(xiàng)式的建模方法, 很大程度上增強(qiáng)了攻擊者恢復(fù)超多項(xiàng)式的能力.動(dòng)態(tài)立方攻擊和相關(guān)立方攻擊在已知超多項(xiàng)式局部信息時(shí)也可以攻擊密鑰, 攻擊思想對(duì)于處理大規(guī)模超多項(xiàng)式有一定價(jià)值.

目前, 超多項(xiàng)式的恢復(fù)技術(shù)已比較成熟, 隨著輪數(shù)的增長(zhǎng), 超多項(xiàng)式的規(guī)模太大是導(dǎo)致超多項(xiàng)式無(wú)法恢復(fù)的主要原因, 并且龐大的代數(shù)正規(guī)型對(duì)于密鑰恢復(fù)意義也不大.一般地, 代數(shù)次數(shù)越低, 超多項(xiàng)式的規(guī)模越小.因此, 如何選取低次超多項(xiàng)式的立方集是有待解決的關(guān)鍵問(wèn)題.同時(shí), 超多項(xiàng)式的次數(shù)與立方集維數(shù)之間的代數(shù)關(guān)系也是一個(gè)有意義的理論問(wèn)題.