孫 瑩

（中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，河南 鄭州 450001）

0 引言

由于線性反饋移位寄存器（Linear Feedback Shift Register，LFSR）產(chǎn)生的序列周期長、統(tǒng)計(jì)特性好，在序列密碼設(shè)計(jì)中是一種常用的初始偽隨機(jī)數(shù)發(fā)生器?；贚FSR 和有記憶變換的前饋模型序列密碼的基本思想是，利用非線性變換對LFSR 的輸出序列進(jìn)行進(jìn)一步加工，破壞其線性制約性，從而獲得更好的偽隨機(jī)性。以SNOW 系列算法為典型代表，這類序列密碼算法由于具有良好的實(shí)現(xiàn)性能和安全性，在加密通信等方面占據(jù)著重要位置。SNOW 系列算法在實(shí)際中有著廣泛的應(yīng)用。2002 年，SNOW 2.0[1]由國際標(biāo)準(zhǔn)化組織（Internation Organization for Standardization，ISO）作為國際標(biāo)準(zhǔn)ISO/IEC 18033-4 發(fā)布。2018 年提出的SNOW-V[2]以及之后提出的升級版本SNOW-Vi[3]則參與了5G加密標(biāo)準(zhǔn)的評選。

對于這類序列密碼算法，相關(guān)攻擊是最強(qiáng)有力的分析方法之一。相關(guān)攻擊是一種已知明文攻擊，其基本思路是利用密鑰流輸出和LFSR 序列的相關(guān)性，通過分割窮舉LFSR 初態(tài)的方式對初始密鑰進(jìn)行還原。相比于采用無記憶變換作為濾波函數(shù)的序列密碼，這類基于有記憶變換和LFSR 的序列密碼算法需要多個(gè)時(shí)刻的密鑰字來構(gòu)造只包含密鑰字和LFSR 序列的線性逼近作為相關(guān)攻擊區(qū)分器，從而實(shí)施相關(guān)攻擊。以往關(guān)于SNOW 2.0 的相關(guān)攻擊研究中均給出了包含兩個(gè)連續(xù)時(shí)刻密鑰字的區(qū)分器構(gòu)造[4-8]，而對于完整版本的SNOW-V 和SNOWVi，已有的相關(guān)攻擊研究均是基于包含3 個(gè)連續(xù)時(shí)刻密鑰字的相關(guān)攻擊區(qū)分器展開[10-11]。這些分析結(jié)果逐步明確了這些算法具有抗相關(guān)攻擊的安全性，但并沒有從理論上解釋SNOW 2.0 的單密鑰字以及SNOW-V 的連續(xù)兩個(gè)時(shí)刻密鑰字是否與相應(yīng)的LFSR 序列存在相關(guān)性。

本文采用基于Walsh 譜理論的復(fù)合函數(shù)構(gòu)造方法，將SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法的相關(guān)攻擊區(qū)分器等價(jià)地轉(zhuǎn)化為相應(yīng)的復(fù)合函數(shù)的線性逼近問題。通過證明復(fù)合函數(shù)的線性逼近中包含的線性逼近單鏈的相關(guān)系數(shù)始終為零，對SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法與LFSR 序列相關(guān)免疫的最大連續(xù)密鑰字的長度給出了明確的結(jié)論。這些結(jié)論從理論上證明了對SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法的相關(guān)攻擊所需要的連續(xù)密鑰字的最低個(gè)數(shù)，從而為這些算法的相關(guān)攻擊研究提供了理論支撐。

本文其余部分組織如下：第1 節(jié)給出文中用到的符號及其定義，并簡要介紹SNOW2.0、SNOW-V和SNOW-Vi 序列密碼算法；第2 節(jié)證明SNOW 2.0的單密鑰字與其LFSR 序列的相關(guān)免疫；第3 節(jié)給出SNOW-V 和SNOW-Vi 連續(xù)兩個(gè)時(shí)刻密鑰字與LFSR 序列的相關(guān)免疫性；第4 節(jié)總結(jié)全文。

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

1.1 符號及定義

本文中將用到的符號及其定義如表1 所示。

表1 符號說明

引理1 說明，對于模232加運(yùn)算，輸入、輸出mask 的最高非零位在同一位置是其線性逼近的相關(guān)系數(shù)非零的必要條件。

1.2 SNOW 2.0 算法簡介

式中：矩陣乘法定義在由本原多項(xiàng)式z8+z4+z3+z4+1 ∈F2[z]定義的有限域上，z和z+1 分別為有限域上的2 倍乘和3 倍乘運(yùn)算；SR為美國高級加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）的S 盒。關(guān)于SNOW 2.0 序列密碼算法的更多細(xì)節(jié)可參考文獻(xiàn)[1]。

圖1 SNOW 2.0 序列密碼算法結(jié)構(gòu)

1.3 SNOW-V 及SNOW-Vi 算法簡介

SNOW-V 由LFSR 和FSM 部分組成，其中，LFSR 部分采用了兩個(gè)移存器串聯(lián)的模式，F(xiàn)SM 部分包含3 個(gè)記憶模塊，每個(gè)記憶模塊的規(guī)模為128 bit。其邏輯框架如圖2 所示。

圖2 SNOW-V 序列密碼算法結(jié)構(gòu)

式中：E(·)為子密鑰為零的AES 算法的輪函數(shù)；σ變換為基于8 比特字的置換，具體為σ={0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15}，其中0 和15 是兩個(gè)不動(dòng)點(diǎn)。第t時(shí)刻輸出的128 bit 密鑰字為。對于SNOW-V 序列密碼算法的更詳細(xì)介紹可參考文獻(xiàn)[2]。

相較于SNOW-V，2021 年提出的SNOW-Vi 變更了LFSR 的刷新方式以及LFSR 抽頭位置，F(xiàn)SM則保持不變。SNOW 3G 的FSM 結(jié)構(gòu)同樣采用3 個(gè)記憶模塊。當(dāng)將σ變換替換為恒等變換，將位寬修改為32 bit，AES 輪函數(shù)替換為列混合和S 層組成的SP 結(jié)構(gòu)，并增加一個(gè)密鑰字的白化過程，則SNOW-V 的FSM 部分轉(zhuǎn)變?yōu)镾NOW 3G 的FSM。有關(guān)SNOW 3G 和SNOW-Vi 的詳細(xì)介紹可參考文獻(xiàn)[2]和文獻(xiàn)[3]。

2 SNOW 2.0 的單密鑰字與其LFSR 序列的相關(guān)免疫性

自2002 年SNOW 2.0 被提出以來，已經(jīng)出現(xiàn)了許多相關(guān)攻擊方面的研究[4-9]。這些研究均圍繞著SNOW 2.0 兩個(gè)連續(xù)時(shí)刻密鑰字與其LFSR 序列的相關(guān)性展開，但還沒有理論解釋為何不采用單密鑰字和LFSR 序列來構(gòu)造線性逼近作為相關(guān)攻擊區(qū)分器。對于非退化的LFSR 而言，其某一時(shí)刻的狀態(tài)即為LFSR 序列的一個(gè)極大線性無關(guān)組，因此考慮形式為α×zt⊕(β0,β1,…,β15)×(st,st+1,…,st+15)0 的線性逼近，其中，α,β1,β2,…,β5∈為線性mask。由zt=(st+15R1t)⊕R2t⊕st，取R1t,R2t,st,st+1,…,st+15為自變量構(gòu)造函數(shù)，f(x1,x2,y0,y1,…,y15)=(y15x1)x2⊕y0，則有：

式中：ρf=Wf(0,0,β0,β1,…,β15→α)。該逼近方程與題設(shè)中的線性逼近完全一致，因此ρ=ρf。

性質(zhì)1 將SNOW 2.0 的只包含單個(gè)密鑰字的區(qū)分器轉(zhuǎn)化為了對函數(shù)f的線性逼近，使得本文可以從函數(shù)f的線性逼近的角度考察這一類線性逼近的相關(guān)系數(shù)。事實(shí)上，還可以對函數(shù)f的這一線性逼近進(jìn)行更加細(xì)致的推導(dǎo)。不取定輸入變量時(shí)，對函數(shù)f的線性逼近(0,0,β0,β1,…,β15)α的逼近 方程為：

上述結(jié)論表明，SNOW 2.0 的單個(gè)時(shí)刻密鑰字與LFSR 序列不存在線性相關(guān)性，因而至少需要兩個(gè)連續(xù)時(shí)刻的密鑰字，才能構(gòu)造SNOW 2.0 的相關(guān)系數(shù)非零的相關(guān)攻擊區(qū)分器。

3 SNOW-V 和SNOW-Vi 連續(xù)兩個(gè)密鑰字與LFSR 序列的相關(guān)免疫性

自2018 年SNOW-V 被提出以來，針對SNOW-V 及其各類變形版本的相關(guān)攻擊研究均圍繞連續(xù)3 個(gè)時(shí)刻密鑰字與其LFSR 序列的相關(guān)性展開[10-11]，但均未對不采用連續(xù)兩個(gè)時(shí)刻密鑰字與LFSR 序列的相關(guān)性進(jìn)行相關(guān)攻擊的原因作出理論解釋。由于為SNOW-V 的LFSR的一個(gè)極大線性無關(guān)組[10]，考慮SNOW-V 的包含連續(xù)兩個(gè)時(shí)刻密鑰字的相關(guān)攻擊區(qū)分器的形式為：

式中：ρf=Wf(0,0,0,a0,a1,a2,a3→α,β)。該逼近方程與題設(shè)中的線性逼近完全一致，因此ρ=ρf。

采用相同的方法，需要對這一復(fù)合函數(shù)的線性逼近過程中包含的線性逼近單鏈進(jìn)行更細(xì)致的考察。記f1的輸出mask 為(ξ1,ξ2,ξ3,ξ4,ξ5,ξ6)，f2的輸出mask 為(η1,η2,η3,η4)，則有：

它等價(jià)于：

上式轉(zhuǎn)化為ξ1×x⊕a1×u1⊕ξ2×(xu1)1ρ=0，亦即對模232加運(yùn)算的線性逼近(ξ1,a1→ξ2)，因此ρ1=ρA(ξ1,a1→ξ2)。

函數(shù)f2的線性逼近方程為：

由上述mask 間的關(guān)系，逼近方程等價(jià)于：

記r=z⊕u3，由z與u3獨(dú)立知r與z獨(dú)立，因此由ρ2≠0 知η3=a2，ξ2=α，a3=0。

由η1×σ(yr)=η1×σ(yr)T=(η1σ)·(yr)，可得(ξ2×y⊕0×r⊕(η1σ)×(yr))⊕(ξ1×x⊕β×E(x))0，即對模223加運(yùn)算的線性逼近(ξ2,0 →η1σ)和 對AES 輪函數(shù)的線性逼近(ξ→β)，因此ρ2=ρA(ξ2,0 →η1σ)ρE(ξ1→β)。

由引理1，當(dāng)ρA(ξ2,0 →η1σ)≠0 時(shí)有ξ2=η1=0，因此α=ξ2=0。再由ρ3=ρA(η1,η3→β)≠0 和ρ1=ρA(ξ1,a1→ξ2) ≠0 可知，η3=β=ξ1=a1=0，進(jìn)而有a2=η3=0。

綜上，對于ρ1ρ2ρ3≠0 的線性逼近單鏈，必有α=β=a0=a1=a2=a3=0，此時(shí)ρ=1，該線性逼近退化為平凡線性逼近0=0。因此，對任意不全為零的α,β,a0,a1,a2,a3，上述線性逼近的相關(guān)系數(shù)均為零。由定義1 知SNOW-V 的兩個(gè)連續(xù)時(shí)刻密鑰字與其LFSR 序列相關(guān)免疫。

相較于SNOW-V，由于SNOW-Vi 并未對FSM部分進(jìn)行變更，上述結(jié)論和推理對于SNOW-Vi 同樣成立。因此，對于SNOW-V 和SNOW-Vi，本文均得到兩個(gè)連續(xù)時(shí)刻密鑰字與其LFSR 序列相關(guān)免疫的結(jié)論。

4 結(jié)語

SNOW 系列序列密碼算法是加密通信領(lǐng)域十分重要的序列密碼算法，全面考察這些算法抵抗相關(guān)攻擊的能力是十分必要的?；趶?fù)合函數(shù)的Walsh譜理論，本文構(gòu)造相應(yīng)函數(shù)，將只包含密鑰字和LFSR 序列的線性逼近轉(zhuǎn)化為對相應(yīng)函數(shù)的線性逼近，對SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法與LFSR 序列相關(guān)免疫的最大連續(xù)密鑰字的長度給出了明確的結(jié)論。這些結(jié)論從理論上給出了對SNOW2.0、SNOW-V 和SNOW-Vi 序列密碼算法的相關(guān)攻擊所需要的連續(xù)密鑰字的最低個(gè)數(shù)，為這些算法的相關(guān)攻擊研究提供了理論支撐。