對SNOW 系列算法相關(guān)攻擊所需連續(xù)密鑰字最低個數(shù)的分析*

孫 瑩

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

0 引言

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

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

本文采用基于Walsh 譜理論的復合函數(shù)構(gòu)造方法，將SNOW 2.0、SNOW-V 和SNOW-Vi 序列密碼算法的相關(guān)攻擊區(qū)分器等價地轉(zhuǎn)化為相應的復合函數(shù)的線性逼近問題。通過證明復合函數(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ù)密鑰字的最低個數(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ù)兩個時刻密鑰字與LFSR 序列的相關(guān)免疫性；第4 節(jié)總結(jié)全文。

1 預備知識

1.1 符號及定義

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

表1 符號說明

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

1.2 SNOW 2.0 算法簡介

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

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

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

SNOW-V 由LFSR 和FSM 部分組成，其中，LFSR 部分采用了兩個移存器串聯(lián)的模式，F(xiàn)SM 部分包含3 個記憶模塊，每個記憶模塊的規(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 是兩個不動點。第t時刻輸出的128 bit 密鑰字為。對于SNOW-V 序列密碼算法的更詳細介紹可參考文獻[2]。

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

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

自2002 年SNOW 2.0 被提出以來，已經(jīng)出現(xiàn)了許多相關(guān)攻擊方面的研究[4-9]。這些研究均圍繞著SNOW 2.0 兩個連續(xù)時刻密鑰字與其LFSR 序列的相關(guān)性展開，但還沒有理論解釋為何不采用單密鑰字和LFSR 序列來構(gòu)造線性逼近作為相關(guān)攻擊區(qū)分器。對于非退化的LFSR 而言，其某一時刻的狀態(tài)即為LFSR 序列的一個極大線性無關(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→α)。該逼近方程與題設中的線性逼近完全一致，因此ρ=ρf。

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

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

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

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

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

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

它等價于：

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

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

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

記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 輪函數(shù)的線性逼近(ξ→β)，因此ρ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，上述線性逼近的相關(guān)系數(shù)均為零。由定義1 知SNOW-V 的兩個連續(xù)時刻密鑰字與其LFSR 序列相關(guān)免疫。

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

4 結(jié)語

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