Grain-v1 快速相關攻擊的改進*

張英杰, 胡 磊, 史丹萍, 王 鵬, 孫思維, 魏 榮,4

1. 中國科學院 信息工程研究所 信息安全國家重點實驗室, 北京100093

2. 中國科學院 數據與通信保護研究教育中心, 北京100093

3. 中國科學院大學 網絡空間安全學院, 北京100093

4. 北京衛星信息工程研究所, 北京100086

1 引言

流密碼算法是對稱密碼算法的重要分支, 包括同步流密碼算法和自同步流密碼算法. 其中, 同步流密碼算法是指將密鑰流與明文直接異或得到密文的流密碼算法, 其密鑰流僅與密鑰(Key) 和初始向量(IV)有關. 許多同步流密碼算法分為兩個階段: 初始化階段和密鑰流生成階段. 初始化階段的目的是將Key 和IV 充分混淆, 此階段不輸出密鑰流. 密鑰流生成階段將初始化階段結束后的狀態作為初始狀態, 通過不斷地更新中間狀態生成密鑰流.

LFSR 結構經常用于構造同步流密碼算法, 其狀態更新函數通常由一個或多個LFSR 和一個非線性函數構成. 基于Grain 結構的流密碼算法是一組典型的基于LFSR 結構的同步流密碼算法, 包括Grain-128a[1], Grain-v1[2], Grain-128[3]以及一些輕量級的流密碼算法等[4-6]. 其中, Grain-v1 是序列密碼征集eSTREAM 計劃的最終獲勝算法之一.

流密碼的相關攻擊是一種統計分析, 該分析方法與分組密碼的線性分析[7]類似, 但更具有針對性, 主要針對基于LFSR 結構的同步流密碼算法. 攻擊目標為密鑰流生成階段LFSR 的初始狀態. 相關攻擊最早可追溯到對非線性組合生成器的分析, 我國著名密碼學家肖國鎮教授曾提出Xiao-Massey 定理[8]來說明輸出序列與LFSR 的初始狀態之間具有某種相關性. Siegenthaler[9]最初提出可將相關攻擊應用于基于LFSR 結構的流密碼算法, 攻擊的時間復雜度為N2n,N為搜集的密鑰流規模,n為LFSR 的長度.

自從對流密碼的相關攻擊提出之后, 許多降低攻擊復雜度的方法應運而生[10]: 如快速相關攻擊[11],近似相關攻擊[12]和條件相關攻擊[13]等. 當相關攻擊的時間復雜度低于窮搜復雜度時, 就被稱為快速相關攻擊. Meier 和Staffelbach 等人[11]最先提出通過構造校驗等式進行快速相關攻擊. 隨后, 一些學者對傳統的快速相關攻擊方法進行了改進[14-26], 主要的改進策略為尋找低重量的校驗等式和提高恢復初始狀態的效率. 其中, 改進后的單通道算法[20]是一個非常有效的方法. 該算法通過將不同的校驗等式求和構造低重量的校驗等式, 并將猜測和恢復初始狀態的過程看作Walsh 變換, 利用快速Walsh 變換降低攻擊的時間復雜度. 當校驗等式涉及LFSR 初始狀態的n ?β比特時, 恢復n ?β初始狀態的時間復雜度為N+(n ?β)2n?β,N為搜集的密鑰流規模.

Todo 等人[27]在美密會2018 指出, 改進后的單通道算法在降低時間復雜度的同時可能會增加數據復雜度, 從而無法有效地攻擊Grain-128a. 為對Grain-128a 進行有效攻擊, 他們首先從線性分析的角度回顧了快速相關攻擊, 將構造低重量、高相關度的校驗等式轉化為尋找低重量、高相關度的線性掩碼. 隨后, 他們發現了基于LFSR 結構的流密碼算法的一種新性質, 并進一步指出基于Grain 結構的流密碼算法存在多個高相關度的線性逼近. 利用這兩個發現, 他們成功地攻擊了Grain-128a, Grain-128 和Grain-v1.隨后, Todo[28]和WANG 等人[29]分別對該方法進行了改進, 并將改進后的方法應用于對基于Grain 結構的輕量級流密碼算法的攻擊.

混合整數線性規劃(MILP) 是源于線性規劃的一種優化方法, 近年來該方法在密碼分析領域得到了廣泛的應用. 文獻[30] 首次將其應用于字節級差分(線性) 特征的搜索. 2013 年, 文獻[31,32] 對該方法進行了推廣, 首次將其應用于評估基于比特的密碼算法的安全性. 隨后, 文獻[33] 又將其進一步推廣, 使其能夠搜索高概率差分(線性) 路徑. 2016 年, 文獻[34] 利用MILP 模型首次對ARX 結構算法的差分和線性性質進行了刻畫, 文獻[35] 利用MILP 模型對可分性進行了刻畫, 文獻[36] 利用MILP 模型對不可能差分和零相關線性性質進行了刻畫. 次年的歐密會2017 上, 文獻[37] 利用MILP 模型對不可能差分進行了進一步刻畫.

在CRYPTO 2019 上, 文獻[38] 將基于MILP 的自動化分析方法應用于MORUS 認證加密算法的分析. 他們構建了一個搜索一般密鑰流生成器線性逼近的模型, 利用MILP 搜索MORUS 算法的線性逼近, 然后將這個線性逼近對應的布爾函數轉化為分離形式并得到它的相關度. 他們成功地發現了MORUS所有版本的高相關度線性逼近, 進而破解了MORUS 的所有版本. 在FSE 2020 上, Dhiman 等人將基于MILP 的自動化分析方法應用于對NIST 輕量級密碼算法競賽第二輪候選算法TinyJAMBU 的分析[39].他們充分考慮AND 運算之間的相關性, 添加約束對TinyJAMBU 的差分、線性特征進行了精確刻畫, 給出了TinyJAMBU 認證方案偽造攻擊最好的結果.

本文首先以一種便于理解的方式回顧了Todo 等人提出的快速相關攻擊方法. 之后, 基于NFSR 的狀態更新函數增加了搜索線性逼近的MILP 模型的約束, 從而改進了搜索校驗等式的方法. 我們利用改進后的搜索方法搜到了新的校驗等式, 與Todo 等人的結果相比, 新的校驗等式對應更多高相關度掩碼, 可將快速相關攻擊的時間和數據復雜度均降低為約原來的一半.

本文的組織結構如下: 第2 節介紹快速相關攻擊的基礎知識; 第3 節從線性分析的角度出發, 給出對基于Grain 結構的流密碼算法進行快速相關攻擊的基本框架; 第4 節基于MILP 構造校驗不等式, 搜索Grain-v1 的多個高相關度的線性掩碼, 并對Grain-v1 進行快速相關攻擊; 第5 節對全文進行總結.

2 預備知識

本節介紹快速相關攻擊的目標算法, LFSR 的性質和相關度的定義.

2.1 基于LFSR 結構的流密碼

快速相關攻擊[11]的目標算法是基于LFSR 的流密碼, 主要針對密鑰流生成階段. 令

為LFSR 的反饋多項式,s(t)= (st,st+1,··· ,st+n?1) 為LFSR 在t時刻的n比特狀態. 在t+1 時刻,LFSR 輸出st, 并按照如下方式更新狀態:

其中,F為LFSR 的狀態轉移矩陣,× 表示F2上的矩陣乘法. 更進一步, 可用初始狀態表示LFSR 在任意t時刻的狀態:

其中,Ft表示t個F相乘. 記TFt為Ft的轉置,At為TFt的第一行,TAt為At的轉置, 則

Todo 等人提出, LFSR 存在以下性質, 可利用該性質改進對Grain 結構的快速相關攻擊.

2.2 基于Grain 結構的流密碼

本文主要關注對基于Grain 結構的流密碼算法[1-6]的快速相關攻擊. Grain 結構如圖1 所示. 除LFSR 外, Grain 結構還包括一個NFSR, 其中LFSR 的更新與NFSR 無關, NFSR 的更新與LFSR 的輸出有關. 圖1 中s(t)和b(t)分別為LFSR 和NFSR 在t時刻的狀態. 其密鑰流由一個非線性的濾波函數h異或s(t)和b(t)的部分比特生成,h的輸入為s(t)和b(t)的部分比特, 記密鑰流生成函數為H.

圖1 基于Grain 結構的流密碼Figure 1 Overview of Grain-based stream cipher

2.3 相關度

3 Grain 結構的快速相關攻擊

本章從線性分析[7]的角度介紹對基于Grain 結構的流密碼算法的快速相關攻擊[11]. 快速相關攻擊是指時間復雜度低于窮搜復雜度的相關攻擊. 其一般思路為: 尋找LFSR 的初始狀態s(0)與密鑰流之間的強相關性, 在已知部分密鑰流的條件下恢復s(0). 我們可通過搜索相關度較高的線性跡尋找LFSR 的初始狀態s(0)與密鑰流之間的強相關性, 圖2 為搜索線性跡的基本模型[38].

其中, (s(U),b(U)) 為初始化階段的初始狀態; (s(0),b(0)) 為密鑰流生成階段的初始狀態, 若無特殊說明, 本文提到的初始狀態均指(s(0),b(0));zt為t時刻的密鑰流;F為狀態更新函數, 由LFSR 和NFSR的狀態更新函數f和g組成;βt?1=(βt?1,s,βt?1,b),αt=(αt,s,αt,b),γt=(γt,s,γt,b) 和λt為t時刻的線性掩碼, 下標中的s和b分別對應LFSR 和NFSR 的中間狀態,H為密鑰流生成函數.

圖2 Grain 結構的線性跡Figure 2 Linear trails for Grain structure

3.1 快速相關攻擊(FCA)

FCA 分為兩個階段: 離線階段和在線階段. 其中, 離線階段構造校驗等式, 在線階段實施攻擊.

3.1.1 離線階段: 構造校驗等式

離線階段的主要目標是通過尋找流密碼算法的高相關度線性掩碼, 構造具有高相關度的校驗等式. 最簡單地, 當|c(at ⊕zt)| 較大時, 令Γ=Γ0, 可按照如下方式構造校驗等式:

當f(x) 已知時, 我們可使用快速Walsh 變換計算c(et). 記校驗等式的相關度為c, 攻擊過程如下:

算法1 快速相關攻擊[20]Input: zt+i(i ∈Tz,t = 0,1,··· ,N): 密鑰流; n,F: LFSR 的狀態規模和狀態轉移矩陣;Γ: 線性掩碼; c: 相關度;Output: s(0)1 Lw = {}; /* 以字典形式存儲的函數*/2 foreach α ∈Fn2 do 3 f(α) = ∑t∈{0,1,···,N?1|?！罷F t=α}(?1)⊕i∈Tz zt+i;4 Lw[α] = f(α);5 end 6 foreach s ∈Fn2 do 7 ∑N?1 t=0 (?1)et = ?f(s) = ∑α∈Fn2 Lw[α](?1)〈s,α〉; /* 快速Walsh 變換*/8 if ∑N?1 t=0 (?1)et ～N(Nc,N) then s(0) = s;10 return s(0);11 end 12 end 9

3.2 使用多個線性掩碼和定理1 改進FCA

Grain 結構的LFSR 的狀態較大,n2n的值超過了算法的安全界. 在這種情況下, FCA 的復雜度還需要進一步降低. 一方面, 由于其密鑰流生成函數H存在多個相關度較大的線性逼近, 因此, 會存在多個不同的線性掩碼使得|c(et)| 較大; 另一方面, 根據定理1 可得到下述推論:

算法2 基于多個線性掩碼及推論1 的FCA [27]Input: zt+i(i ∈Tz,t = 0,1,··· ,N): 密鑰流; n,F: LFSR 的狀態規模和狀態轉移矩陣;Γ(0),··· ,Γ(mp?1): 相關度大于0 的線性掩碼; Γ(mp),··· ,Γ(m?1) 相關度小于0 的線性掩碼;th: 假設檢驗的閾值, 與Nc 有關; β: 忽略的比特數;Output: S: s(0) 的取值集合1 Lp, Lm, S = ?;2 cmax = 0;3 Lw,Lc, ˉS = {}; /* 以字典形式存儲的函數*/4 for i = 0,··· ,m ?1 do F?1 Γ(i) = [T Γ(i),F1 ×T Γ(i),··· ,Fn?1 ×T Γ(i)]?1 ;5 for t = 0,··· ,N ?1 do At = (TFt)row1; /* TFt 的第1 行*/6 foreach α ∈Fn?β 2 do 7 f(α) = ∑t∈{0,1,···,N?1|At[0,1,···,m?β?1]=α}(?1)⊕i∈Tz zt+i;8 Lw[α] = f(α);9 end 10 foreach s ∈Fn?β2 do 11 ?f(s) = ∑Lw[α](?1)〈s,α〉; /* 快速Walsh 變換*/12 if ?f(s) ≥th then Lp = Lp ∪{s} ; /* 相關度為正*/13 if ?f(s) ≤?th then Lm = Lm ∪{s} ; /* 相關度為負*/14 end 15 foreach s ∈Lp do α∈Fn?β 2 16 for i ∈{0,1,··· ,mp ?1} do Γ(i); /* ˉs 為s(0) 的可能取值*/18 ˉS = ˉS ∪{ˉs};19 Lc[ˉs] = Lc[ˉs]+1;20 end 21 end 22 foreach s ∈Lm do 17 ˉs = (s||0β)×F?1 23 for i ∈{mp,mp +1,··· ,m ?1} do 24 ˉs = (s||0β)×F?1Γ(i); /* ˉs 為s(0) 的可能取值*/25 ˉS = ˉS ∪{ˉs};26 Lc[ˉs] = Lc[ˉs]+1;27 end 28 end 29 foreach ˉs ∈ˉS do /* 將出現次數最多的ˉs 作為s(0) */30 if Lc[ˉs] ＞cmax then cmax = Lc[ˉs], S = {ˉs};31 else if Lc[ˉs] = cmax then S = S ∪{ˉs};32 end 33 return S;

3.3 基于MILP 搜索Tz

為了搜索多個相關度較大的線性掩碼, 我們首先需要搜索最優的Tz. Todo 等人提出可將基于混合整數線性規劃(MILP) 的方法用于搜索Tz. 結合文獻[38] 給出的方法, 我們給出R步的建模方式:

(1) 建立MILP 模型刻畫圖2 中線性特征的傳播規律, 模型的目標函數為最大化線性特征的概率, 模型的約束如下:

對模型進行求解, 得到Tz={t|λt=1}.

定義4 (無效線性特征) 使用上述方法搜索Tz時, 會出現Tz對應的線性特征的相關度不為0, 但c(et)=0 的情況. 我們稱這種線性特征為無效線性特征.

為保證攻擊的有效性, 在MILP 建模過程中需要將無效的線性特征排除. 通過多次實驗, 我們發現可以根據NFSR 的狀態更新函數增加約束將無效的線性特征排除. 由于涉及算法細節, 具體建模方法見4.2節.

當Tz已知時, 可通過計算⊕i∈Tz zt+i的線性逼近構造校驗等式, 進而搜索多個相關度較高的線性掩碼. 具體構造過程在4.3 節中給出.

4 Grain-v1 的快速相關攻擊

4.1 Grain-v1 算法描述

4.2 基于MILP 搜索Tz

4.3 構造校驗等式

令Γi為h在t+i時刻的輸入掩碼, 則

表1 h 函數的輸入掩碼及其相關度Table 1 Input linear mask and corresponding correlation of h function

表2 Γi[4] 給定時, Cg() 的取值Table 2 Summary of Cg() when Γi[4] is fixed

表2 Γi[4] 給定時, Cg() 的取值Table 2 Summary of Cg() when Γi[4] is fixed

Γ14[4] Γ21[4] Γ28[4] Γ45[4] Cg(ΓTz)0 0 0 0 2?19.7159 0 0 0 1 2?23.4500 0 0 1 0 2?19.6603 0 0 1 1 2?23.7260 0 1 0 0 ?2?25.1228 0 1 0 1 2?22.9025 0 1 1 0 ?2?24.3802 0 1 1 1 2?22.6875 1 0 0 0 ?2?21.9519 1 0 0 1 ?2?23.5233 1 0 1 0 ?2?21.8662 1 0 1 1 ?2?23.6420 1 1 0 0 2?24.9114 1 1 0 1 ?2?22.8544 1 1 1 0 2?24.5232 1 1 1 1 ?2?22.7302

表3 Γi[4] 給定時, Cg() 的取值Table 3 Summary of Cg() when Γi[4] is fixed

表3 Γi[4] 給定時, Cg() 的取值Table 3 Summary of Cg() when Γi[4] is fixed

Γ14[4] Γ21[4] Γ28[4] Γ45[4] Cg(ΓTz)0 0 0 0 2?17.5444 0 0 0 1 2?18.8880 0 0 1 0 2?17.6116 0 0 1 1 2?18.9524 0 1 0 0 2?20.8858 0 1 0 1 ?2?20.6941 0 1 1 0 2?20.9553 0 1 1 1 ?2?20.7608 1 0 0 0 ?2?20.2249 1 0 0 1 ?2?20.6946 1 0 1 0 ?2?20.3129 1 0 1 1 ?2?20.7603 1 1 0 0 ?2?20.8863 1 1 0 1 2?20.6946 1 1 1 0 ?2?20.9547 1 1 1 1 2?20.7603

從而可由推論1 構造校驗等式.

4.4 搜索多個線性掩碼并計算其相關度

表4 FCA 攻擊復雜度Table 4 Complexity of FCA

4.5 FCA 攻擊復雜度

我們發現, 雖然T1z對應的線性特征的相關度大于T2z, 但當Tz=T2z時, 可以找到更多高概率的線性掩碼, 使得快速相關攻擊的時間和數據復雜度較低. 利用T2z構造校驗等式, 可將對Grain-v1 快速相關攻擊的時間復雜度和數據復雜度由276.6935和275.1085降低為275.6724和274.0875.

5 結論

我們回顧了Todo 等人提出的基于線性分析的快速相關攻擊方法. 并基于NFSR 的狀態更新函數增加了搜索線性逼近的MILP 模型的約束, 從而改進了搜索校驗等式的方法. 我們利用改進后的搜索方法搜到了新的校驗等式, 與Todo 等人的結果相比, 新的校驗等式對應更多高相關度掩碼, 可將快速相關攻擊的時間和數據復雜度由276.6935和275.1085降低為275.6724和274.0875.

我們發現, 由于流密碼的密鑰流之間的強相關性, 相關度較高的線性特征不一定對應最優的校驗不等式. 接下來我們將基于這個發現, 進一步改進基于MILP 的搜索方法, 搜到更好或最優的校驗不等式.