Grain-v1 快速相關(guān)攻擊的改進*

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

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

2. 中國科學(xué)院 數(shù)據(jù)與通信保護研究教育中心, 北京100093

3. 中國科學(xué)院大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 北京100093

4. 北京衛(wèi)星信息工程研究所, 北京100086

1 引言

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

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

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

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

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

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

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

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

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

2 預(yù)備知識

本節(jié)介紹快速相關(guān)攻擊的目標算法, LFSR 的性質(zhì)和相關(guān)度的定義.

2.1 基于LFSR 結(jié)構(gòu)的流密碼

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

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

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

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

Todo 等人提出, LFSR 存在以下性質(zhì), 可利用該性質(zhì)改進對Grain 結(jié)構(gòu)的快速相關(guān)攻擊.

2.2 基于Grain 結(jié)構(gòu)的流密碼

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

圖1 基于Grain 結(jié)構(gòu)的流密碼Figure 1 Overview of Grain-based stream cipher

2.3 相關(guān)度

3 Grain 結(jié)構(gòu)的快速相關(guān)攻擊

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

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

圖2 Grain 結(jié)構(gòu)的線性跡Figure 2 Linear trails for Grain structure

3.1 快速相關(guān)攻擊(FCA)

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

3.1.1 離線階段: 構(gòu)造校驗等式

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

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

算法1 快速相關(guān)攻擊[20]Input: zt+i(i ∈Tz,t = 0,1,··· ,N): 密鑰流; n,F: LFSR 的狀態(tài)規(guī)模和狀態(tài)轉(zhuǎn)移矩陣;Γ: 線性掩碼; c: 相關(guān)度;Output: s(0)1 Lw = {}; /* 以字典形式存儲的函數(shù)*/2 foreach α ∈Fn2 do 3 f(α) = ∑t∈{0,1,···,N?1|Γ×TF 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 結(jié)構(gòu)的LFSR 的狀態(tài)較大,n2n的值超過了算法的安全界. 在這種情況下, FCA 的復(fù)雜度還需要進一步降低. 一方面, 由于其密鑰流生成函數(shù)H存在多個相關(guān)度較大的線性逼近, 因此, 會存在多個不同的線性掩碼使得|c(et)| 較大; 另一方面, 根據(jù)定理1 可得到下述推論:

算法2 基于多個線性掩碼及推論1 的FCA [27]Input: zt+i(i ∈Tz,t = 0,1,··· ,N): 密鑰流; n,F: LFSR 的狀態(tài)規(guī)模和狀態(tài)轉(zhuǎn)移矩陣;Γ(0),··· ,Γ(mp?1): 相關(guān)度大于0 的線性掩碼; Γ(mp),··· ,Γ(m?1) 相關(guān)度小于0 的線性掩碼;th: 假設(shè)檢驗的閾值, 與Nc 有關(guān); β: 忽略的比特數(shù);Output: S: s(0) 的取值集合1 Lp, Lm, S = ?;2 cmax = 0;3 Lw,Lc, ˉS = {}; /* 以字典形式存儲的函數(shù)*/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} ; /* 相關(guān)度為正*/13 if ?f(s) ≤?th then Lm = Lm ∪{s} ; /* 相關(guān)度為負*/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 /* 將出現(xiàn)次數(shù)最多的ˉ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

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

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

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

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

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

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

4 Grain-v1 的快速相關(guān)攻擊

4.1 Grain-v1 算法描述

4.2 基于MILP 搜索Tz

4.3 構(gòu)造校驗等式

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

表1 h 函數(shù)的輸入掩碼及其相關(guān)度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 構(gòu)造校驗等式.

4.4 搜索多個線性掩碼并計算其相關(guān)度

表4 FCA 攻擊復(fù)雜度Table 4 Complexity of FCA

4.5 FCA 攻擊復(fù)雜度

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

5 結(jié)論

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

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