對SNOW 系列算法相關攻擊所需連續密鑰字最低個數的分析*

孫 瑩

（中國人民解放軍戰略支援部隊信息工程大學，河南 鄭州 450001）

0 引言

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

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

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

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

1 預備知識

1.1 符號及定義

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

表1 符號說明

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

1.2 SNOW 2.0 算法簡介

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

圖1 SNOW 2.0 序列密碼算法結構

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

SNOW-V 由LFSR 和FSM 部分組成，其中，LFSR 部分采用了兩個移存器串聯的模式，FSM 部分包含3 個記憶模塊，每個記憶模塊的規模為128 bit。其邏輯框架如圖2 所示。

圖2 SNOW-V 序列密碼算法結構

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

相較于SNOW-V，2021 年提出的SNOW-Vi 變更了LFSR 的刷新方式以及LFSR 抽頭位置，FSM則保持不變。SNOW 3G 的FSM 結構同樣采用3 個記憶模塊。當將σ變換替換為恒等變換，將位寬修改為32 bit，AES 輪函數替換為列混合和S 層組成的SP 結構，并增加一個密鑰字的白化過程，則SNOW-V 的FSM 部分轉變為SNOW 3G 的FSM。有關SNOW 3G 和SNOW-Vi 的詳細介紹可參考文獻[2]和文獻[3]。

2 SNOW 2.0 的單密鑰字與其LFSR 序列的相關免疫性

自2002 年SNOW 2.0 被提出以來，已經出現了許多相關攻擊方面的研究[4-9]。這些研究均圍繞著SNOW 2.0 兩個連續時刻密鑰字與其LFSR 序列的相關性展開，但還沒有理論解釋為何不采用單密鑰字和LFSR 序列來構造線性逼近作為相關攻擊區分器。對于非退化的LFSR 而言，其某一時刻的狀態即為LFSR 序列的一個極大線性無關組，因此考慮形式為α×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為自變量構造函數，f(x1,x2,y0,y1,…,y15)=(y15x1)x2⊕y0，則有：

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

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

上述結論表明，SNOW 2.0 的單個時刻密鑰字與LFSR 序列不存在線性相關性，因而至少需要兩個連續時刻的密鑰字，才能構造SNOW 2.0 的相關系數非零的相關攻擊區分器。

3 SNOW-V 和SNOW-Vi 連續兩個密鑰字與LFSR 序列的相關免疫性

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

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

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

它等價于：

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

函數f2的線性逼近方程為：

由上述mask 間的關系，逼近方程等價于：

記r=z⊕u3，由z與u3獨立知r與z獨立，因此由ρ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加運算的線性逼近(ξ2,0 →η1σ)和 對AES 輪函數的線性逼近(ξ→β)，因此ρ2=ρA(ξ2,0 →η1σ)ρE(ξ1→β)。

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

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

相較于SNOW-V，由于SNOW-Vi 并未對FSM部分進行變更，上述結論和推理對于SNOW-Vi 同樣成立。因此，對于SNOW-V 和SNOW-Vi，本文均得到兩個連續時刻密鑰字與其LFSR 序列相關免疫的結論。

4 結語

SNOW 系列序列密碼算法是加密通信領域十分重要的序列密碼算法，全面考察這些算法抵抗相關攻擊的能力是十分必要的。基于復合函數的Walsh譜理論，本文構造相應函數，將只包含密鑰字和LFSR 序列的線性逼近轉化為對相應函數的線性逼近，對SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法與LFSR 序列相關免疫的最大連續密鑰字的長度給出了明確的結論。這些結論從理論上給出了對SNOW2.0、SNOW-V 和SNOW-Vi 序列密碼算法的相關攻擊所需要的連續密鑰字的最低個數，為這些算法的相關攻擊研究提供了理論支撐。