田 甜, 戚文峰

信息工程大學, 鄭州 450001

1 引言

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

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

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

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

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

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

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

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

2 立方攻擊基本原理

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

集合CI稱為一個立方集(cube),{vi|i ∈I}稱為立方變元集,I稱為立方變元的下標集, 集合I的基數(shù)|I| 稱為CI的維數(shù), 多項式pI(x) 稱為I的超多項式(superpoly) 或CI的超多項式.

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

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

3 實驗立方攻擊

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

3.1 線性檢測和二次檢測

將f(x,v) 看作黑盒布爾函數(shù).設I是一個立方變元的下標集,pI是f(x,v) 關于I的超多項式.設a,b ∈Fn2, 通過查詢函數(shù)f(x,v) 的輸出, 可以計算出pI在變元x分別為a,b,a ⊕b,0 時的函數(shù)值, 驗證下式是否成立

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

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

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

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

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

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

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

3.2 M?bius 變換

在立方攻擊中, 利用M?bius 變換可以同時對立方變元集I的所有子立方變元集進行線性檢測, 這有效提高了檢測的效率, 從而增加了攻擊成功的可能性.

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

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

下面介紹M?bius 變換在立方攻擊中的應用.注意到在做線性檢測時, 關鍵是求得超多項式在給定密鑰下的函數(shù)值, 因此, 這里僅需討論如何同時獲得一個立方集全體子立方集的超多項式在給定密鑰下的函數(shù)值.設I={i1,i2,···,id}是一個立方變元下標集.給定密鑰x=a, 并且下標不在I中的IV 變元固定為常值0.那么, 在此條件下,f是關于立方變元的一個函數(shù), 其代數(shù)正規(guī)型可以表示為

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

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

算法1 M?bius 變換Input: h(x0,x1,··· ,xk?1) 的真值表S Output: h 的單項式系數(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 應用

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

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

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

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

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

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

4.2 基于比特的可分性

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

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

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

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

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

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

在2017 年美密會上, Todo 首次將傳統(tǒng)的基于比特的可分性及其MILP 建模方法引入到序列密碼分析中, 提出了基于可分性的立方攻擊[5].在文獻[5] 中, 利用CBDP 和MILP 建模可以判斷哪些密鑰變元不出現(xiàn)在給定立方集的超多項式中.下面的命題給出了CBDP 可分路徑與超多項式代數(shù)正規(guī)型的一種聯(lián)系.

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

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

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

? 在CBDP 的MILP 建模中, 沒有處理異或運算消項的問題.

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

離線階段.選擇一個以I為下標集的立方變元集, 利用MILP 模型得到一組不出現(xiàn)在pI中的密鑰變元, 剩余的密鑰變元記為集合J.隨機設定一組非立方變元的取值C, 計算超多項式pI({xj|j ∈J},C)的真值表, 計算復雜度為2|I|+|J|.若pI({xj|j ∈J},C) 是常值函數(shù), 則通過改變非立方變元的取值, 直到對應的超多項式為非常值函數(shù).

在線階段.對于離線階段記錄的立方變元集I, 設置非立方變元的取值, 使得超多項式pI(x) 是非常值函數(shù).在當前密鑰下計算pI(x) 的函數(shù)值a, 建立關于密鑰的方程pI(x)=a.利用多個立方集, 可以建立關于密鑰的一組方程.

窮舉搜索階段.窮盡滿足方程解的剩余密鑰, 并逐個驗證.

在上述攻擊中, 當2|I|+|J|超過計算能力時, 實際無法判斷超多項式pI({xj|j ∈J},C) 在給定非立方變元取值為C時是否為常值多項式, 因此, 在文獻[5] 中提出如下兩個假設:

假設1 (強假設) 對于給定的立方變元下標集I,存在很多非立方變元的賦值使得I的超多項式pI(x)是平衡函數(shù).

假設2 (弱假設) 對于給定的立方變元下標集I,存在很多非立方變元的賦值使得I的超多項式pI(x)不是常值函數(shù).

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

值得注意的是, 上述假設對于Trivium 常常不成立, 例如當集合J非空時, 超多項式仍然可能是零常值, 這意味著任意非立方變元的取值, 超多項式都是零常值.文獻[7] 中通過對超多項式的準確計算, 說明了文獻[6] 中所給的833 輪–839 輪的5 個超多項式實際都是零常值, 從而與此相關的密鑰恢復攻擊均不成立, 應是區(qū)分攻擊.此外, Wang 等人在文獻[8] 中也指出文獻[6] 的一些立方集的超多項式是零常值.

自2017 年Todo 等人將可分性和MILP 引入立方攻擊后, 如何基于可分性理論和MILP 建?；謴蜏蚀_的超多項式成為序列密碼立方攻擊的一個重要問題.

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

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

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

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

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

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

5 立方集的構造

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

定義5[4]令I={vi1,vi2,···,vil}是一個有l(wèi)個IV 變元的立方變元集.如果一個IV 變元b滿足

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

定義6[4]令I={vi1,vi2,···,vil}是一個有l(wèi)個IV 變元的立方變元集.如果一個IV 變元b滿足

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

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

2021 年, Sun 基于實驗觀察和分治技術, 針對具有獨立線性變元的平衡超多項式(該變元不出現(xiàn)在非線性項中), 提出了從大立方集中排除無效立方集的啟發(fā)式算法, 用來構造具有平衡超多項式的立方集[12],給出了808 輪Trivium 的實際密鑰恢復攻擊, 并成功恢復了843 輪Trivium 的一個平衡超多項式.這是目前已知的最高輪數(shù)平衡超多項式, 大于843 輪的已知超多項式由于規(guī)模大, 無法準確判斷其平衡性.

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

在立方攻擊的基礎上, 2011 年, Dinur 等人提出動態(tài)立方攻擊[14].動態(tài)立方攻擊是針對Grain 系列算法的重要攻擊方法.相比立方攻擊通過求解密鑰方程組來獲取密鑰信息, 動態(tài)立方攻擊則是通過區(qū)分器來識別正確密鑰.在動態(tài)立方攻擊中, 通過設置Key/IV 變元的表達式條件, 達到簡化輸出函數(shù)f(x,v) 代數(shù)正規(guī)型的目的; 若動態(tài)條件中同時含有密鑰變元和IV 變元, 則可以恢復密鑰信息.

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

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

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

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

7 相關立方攻擊

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

7.1 數(shù)值映射

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

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

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

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

7.2 利用基多項式分解的相關立方攻擊

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

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

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

7.3 相關立方攻擊的新框架

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

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

8 總結

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

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