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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文主要關(guān)注對(duì)基于Grain 結(jié)構(gòu)的流密碼算法[1-6]的快速相關(guān)攻擊. Grain 結(jié)構(gòu)如圖1 所示. 除LFSR 外, Grain 結(jié)構(gòu)還包括一個(gè)NFSR, 其中LFSR 的更新與NFSR 無關(guān), NFSR 的更新與LFSR 的輸出有關(guān). 圖1 中s(t)和b(t)分別為LFSR 和NFSR 在t時(shí)刻的狀態(tài). 其密鑰流由一個(gè)非線性的濾波函數(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]的角度介紹對(duì)基于Grain 結(jié)構(gòu)的流密碼算法的快速相關(guān)攻擊[11]. 快速相關(guān)攻擊是指時(shí)間復(fù)雜度低于窮搜復(fù)雜度的相關(guān)攻擊. 其一般思路為: 尋找LFSR 的初始狀態(tài)s(0)與密鑰流之間的強(qiáng)相關(guān)性, 在已知部分密鑰流的條件下恢復(fù)s(0). 我們可通過搜索相關(guān)度較高的線性跡尋找LFSR 的初始狀態(tài)s(0)與密鑰流之間的強(qiáng)相關(guān)性, 圖2 為搜索線性跡的基本模型[38].

其中, (s(U),b(U)) 為初始化階段的初始狀態(tài); (s(0),b(0)) 為密鑰流生成階段的初始狀態(tài), 若無特殊說明, 本文提到的初始狀態(tài)均指(s(0),b(0));zt為t時(shí)刻的密鑰流;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時(shí)刻的線性掩碼, 下標(biāo)中的s和b分別對(duì)應(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è)階段: 離線階段和在線階段. 其中, 離線階段構(gòu)造校驗(yàn)等式, 在線階段實(shí)施攻擊.

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

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

當(dāng)f(x) 已知時(shí), 我們可使用快速Walsh 變換計(jì)算c(et). 記校驗(yàn)等式的相關(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 = {}; /* 以字典形式存儲(chǔ)的函數(shù)*/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 使用多個(gè)線性掩碼和定理1 改進(jìn)FCA

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

算法2 基于多個(gè)線性掩碼及推論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è)檢驗(yàn)的閾值, 與Nc 有關(guān); β: 忽略的比特?cái)?shù);Output: S: s(0) 的取值集合1 Lp, Lm, S = ?;2 cmax = 0;3 Lw,Lc, ˉS = {}; /* 以字典形式存儲(chǔ)的函數(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)度為負(fù)*/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

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

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

對(duì)模型進(jìn)行求解, 得到Tz={t|λt=1}.

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

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

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

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

4.1 Grain-v1 算法描述

4.2 基于MILP 搜索Tz

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

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

表1 h 函數(shù)的輸入掩碼及其相關(guān)度Table 1 Input linear mask and corresponding correlation of h function

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

表2 Γi[4] 給定時(shí), 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] 給定時(shí), Cg() 的取值Table 3 Summary of Cg() when Γi[4] is fixed

表3 Γi[4] 給定時(shí), 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)造校驗(yàn)等式.

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

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

4.5 FCA 攻擊復(fù)雜度

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

5 結(jié)論

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

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