全動態密鑰流生成器DF-FCSR-8

潘臻，唐小虎

（西南交通大學 信息科學與技術學院，四川 成都 610031）

1 引言

在1994年，Klapper和Goresky提出了帶進位的反饋移位寄存器（FCSR）[1]，給出的分析結果表明，FCSR易于實現，生成速度快，其極大周期序列（l-序列）有良好的統計特性，在帶進位加的作用下，l-序列線性復雜度極高[1～4]，避免了使用LFSR的m-序列所受的B-M算法攻擊，使得近十多年利用 FCSR構造密鑰流生成器的方案被研究者所關注。但是由于FCSR基于2-adic理論，其生成序列的2-adic復雜度，利用有理數逼近算法[4]僅需要很短的序列段就可以將FCSR結構還原，因此要使用FCSR構造密鑰流生成器，需要提高其2-adic復雜度，而線性濾波是一個可行的辦法。在 2005年，Berger和Arnault利用FCSR主寄存器濾波的方法來產生密鑰流，得到了好的效果，從而提出了F-FCSR濾波密鑰流生成器族，且該生成器族序列生成速度快，生成序列統計特性好，線性復雜度高。同年在eSTREAM項目上他們提交了其設計的密鑰流生成器，其硬件密鑰流生成器F-FCSR-Hv2[5]最后通過了eSTREAM的評選，成為4個硬件方案之一。只是2008年Hell和Johansson在文獻[6]中以很小的代價攻破了 F-FCSR-Hv2，攻擊的關鍵是利用Galois表示的FCSR在運行中主寄存器會以一定的概率出現短暫的線性平移，而F-FCSR-Hv2濾波函數為線性函數，從而攻擊者可以列出足夠多的線性方程，以解線性方程的方法還原F-FCSR-Hv2生成器的狀態。

極高的生成速度，簡單的實現方式，良好的統計特性對于密鑰流生成器來說，是至關重要的，由于當前對F-FCSR流密碼族有效攻擊手段只有Hell-Johnson攻擊[6]，因此，如果某種改進方案能夠在保證其他良好性質的同時避免Hell-Johnson攻擊，將是對該密鑰流生成器族的成功改進，具有很好的意義。最近，Berger和Arnault提出了用環（ring）表示的FCSR進行濾波的方案[7]，并聲稱能抵抗文獻[6]的攻擊。而本文提出基于FCSR的全動態濾波密鑰流生成器DF-FCSR-8，利用一個FCSR來組成動態濾波函數，避免了文獻[6]中的攻擊和其他的攻擊。本文安排如下：第2節介紹FCSR自動機；第3節介紹F-FCSR和Hell-Johansson攻擊；第4節介紹DF-FCSR-8密鑰流生成器；第5節和第6節介紹DF-FCSR-8密鑰流生成器的性質和抵抗攻擊的能力；最后為結束語。

2 FCSR自動機

Galois表示下的FCSR自動機如圖1所示。其中，“田”表示帶進位加法，qn,qn-1,…,q1∈GF2將與反饋值進行乘法運算，運算結果作為對應位置帶進位加的一個輸入，由此得到的整數（且=1），滿足2n＜q＜2n+1，稱為FCSR的連接數。具體的FCSR由2個寄存器構成：

1) 主寄存器M=(mn-1,mn-2,…,m0)，由n個比特構成；

2) 進位寄存器C=(cn, cn-1,…,c1)，為方便起見，將其看做由n個比特構成且cn=0。

在單元級上，寄存器在時間t時的轉移函數表示如下：

其中，“⊕”表示異或，為方便表示，令mn( t)=m0( t)。但是需要注意的是，當qi=0時有ci最終會恒等于0，不會對FCSR的運行產生影響，只有在qi=1時ci才會起作用。因此實際中FCSR進位寄存器的數量為l=wt( q-1)-1，wt( x)表示數x的二進制展開中1的個數，也就是x的漢明重量。為了表示方便，也可以認為進位寄存器C包含n個單元ci(0≤i≤n-1)。為了便于理解，舉例如下：

例1：如果q=-347，那么有d=174=0xAE，n=8和l=4。則對應FCSR表示如圖2所示。

定理1[1]有理數α=p/ q和二元終歸周期序列=(a0, a1, a2,…)之間存在一一對應關系，對應規則為序列為有理數α的2-adic展開的系數序列，即。而其中奇整數為生成該序列的FCSR連接數。

定理2[1]如果p和q互素，-q＜p≤0，q為奇數，則α=p/ q 的2-adic展開序列周期為T=ordq(2)。

圖1 帶進位的反饋移位寄存器的Galois結構

圖2 FCSR舉例

定義2[1]如果FCSR自動機的連接數q滿足ordq(2)=|q|-1，稱該FCSR自動機為最優的，其生成序列為l-序列。

定義3[8]存在素數q，若2模q的階為q-1（i.e.2q-1≡1(modq)），則稱q為2-素數，當q=2r+1且r也為2-素數時，則稱q為強2-素數。

當FCSR的連接數q為2-素數，則生成的序列為極大周期序列，l-序列，其周期為q-1。下面的定理3為l-序列的線性復雜度的一些結論。

定理3[8]當FCSR的連接數為q=2p+1，其中，為2-素數，那么其FCSR生成序列的線性復雜度至少為m+2，其中，m為2模p的階。當q為強2-素數時，線性復雜度為p+1。

FCSR的主寄存器中寄存器單元所生成的序列稱為主寄存器序列，主寄存器第i個單元在時刻后的值構成的序列表示為Mi( t)=(mi( t+τ))τ≥0，其中，0≤i≤n-1。當序列從t=0時刻開始時，記為Mi=Mi(0)，而FCSR的生成序列M即為M0。

定理4[9]若有連接數為q=1-2d的最優FCSR自動機，令n為d的比特長度，那么對于所有的i,0≤i≤n-1，存在一個整數pi，使得主寄存器生成序列Mi為piq的2-adic展開。整數pi由如下公式給出：

其中，pn=p0。那么由定理2可知，FCSR主寄存器生成序列與FCSR序列具有相同的連接數和周期。

3 F-FCSR與Hell-Johansson攻擊

F-FCSR密鑰流生成器族[9]由FCSR自動機與濾波函數組成， FCSR自動機的主寄存器值通過濾波函數產生出密鑰流比特。

下面以F-FCSR-Hv2[5]為例，介紹F-FCSR密鑰流生成器族的具體實現。根據式(1)可知，當di=0時，有mi( t+1)=mi+1(t )，即主寄存器序列Mi( t+1)=Mi+1(t )，那么這2個序列將不適合同時參與濾波的異或運算，所以在文獻[5]中采用了固定的濾波器F（為二進制向量）等于d的二進制展開，這樣進位寄存器單元后的主寄存器單元都將參與濾波運算。該結構使用k=8個不同的子濾波器來增加吞吐量。F-FCSR-Hv2中的FCSR長度（主寄存器數目）為n=160，進位寄存器包含l=82個單元，FCSR的連接數為

F-FCSR-Hv2使用固定的濾波器

對應k=8個子濾波器為F7, F6,…,F0。令F對應比特串為(fn-1,fn-2,…,f1,f0)，Fi對應比特串為(fi,n/k-1,fi,n/k-2,…,fi,1,fi,0),0≤i＜k ，則存在如下對應關系(t≥0)：

對應8個子濾波器確定如下：

F7=(1101 0011 1011 1011 0100)2,

F6=(0011 0101 0010 0110 0101)2,

F5=(1001 1100 0100 1000 1010)2,

F4=(0111 0010 0010 0011 1100)2,

F3=(1111 0010 0011 1000 1001)2,

F2=(1011 1011 1010 1110 1111)2,

F1=(1001 1010 1101 1100 0001)2,

F0=(0011 0111 0100 1010 1010)2

令主寄存器向量(m152(t), m144(t),…,m8( t), m0( t ))用(t)表示，而( t),1≤i≤7表示主寄存器值(m152+i(t), m144+i(t),…,m8+i(t), mi( t ))。z( t)為F-FCSRHv2在時刻t的一個字節輸出，最高比特為z7( t)，最小比特為z0( t)，輸出字節z( t)則可表示為

其中，Fi,j(t)表示向量Fi( t)中的第j個元素，i,j(t)表示( t)中的第j個元素。圖3為F-FCSRHv2結構。

2008年，Hell和Johansson以很小的代價攻破了F-FCSR-Hv2[6]。他們認為F-FCSR流密碼族中，進位寄存器C變化并不是很隨機是其主要弱點。原因在于它們都有一個共同的輸入變量——反饋比特，當反饋比特為0時，C中為0的單元仍為0，為1的單元以50%的概率變為0。所以當反饋比特連續出現多個0時，會將進位寄存器變為常數0x2。設正整數20r＜ ，定義如下事件：

圖3 F-FCSR-Hv2結構

Et( r):C( t)=C( t+1)=…=C( t+r)=(0,0,…,0,1,0)

當Et( r)發生時，主寄存器出現線性平移的情況具體如下：

結合式(4)與式(5)可發現：zi( t+τ),0≤τ≤r ，僅與(τ+i)mod8(t )相關。那么令

其中，τ+τi≡i(mod8)對于任意的0≤τ≤r，0≤i≤7。則有

在這里Ri是由濾波器F決定的一個20×(r+1)的矩陣，=( t)為含有20個未知數的行向量。當分別求解這8個方程組時，每個方程組有20個未知數和r+1個方程。令矩陣Ri的秩為d(Ri)，若為20則可直接計算出主寄存器值，否則需要猜測20-d (Ri)個比特。所以正確解出這160個未知數的概率為

而Et( r)的出現條件為：需要lbl2≈6個反饋0使得C在時刻t變為漢明重量為1的常數，同時需要r個反饋0使C再保持為常數r次。Et( r)的發生概率為p=2-(r+lbl2)，因此一次實驗就能解出FCSR主寄存器值的概率為

由此，成功攻擊F-FCSR-Hv2的概率上限為2-25。同時由于反饋比特的作用，在求解方程前是可以事先確定r+2個比特，其值如下：

此時，成功的概率提高到2-23。真實情況的成功概率會比理想狀態稍低，文獻[6]給出的成功概率為2-24.7。

4 基于FCSR的全動態濾波密鑰流生成器DF-FCSR-8

由于FCSR本身具有很好的性質，F-FCSR密鑰流族的輸出密鑰流序列具有很好的統計特性，且吞吐量大，僅有Hell-Johansson攻擊，因此對其進行改進是很有利的。

由前面的敘述可知，F-FCSR密鑰流族被成功攻擊的原因如下：

1) Galois表示下的FCSR在反饋比特出現多個0的時候，其主寄存器會出現線性平移的情況；

2) 對FCSR主寄存器的濾波器為線性濾波器，且以字節為單位輸出。

情況1使得多次的濾波輸出有相同的主寄存器值，可以列出具有相同變量的多個方程；情況2使得列出的方程為線性方程，且每次可以列出的方程數量為8。這2種情況就會使得FCSR的主寄存器很容易被恢復。那么可以根據這2種情況來對F-FCSR密鑰流生成器進行改進。由于使用Galois表示的FCSR，主寄存器可能的線性平移是FCSR的固有性質，因此只能針對情況2進行改進。改進的可能方法如下：

1) 改變線性濾波的情況，使用非線性的濾波器；

2) 減少每次濾波的輸出比特數，如只輸出1bit[10]；

3) 隱藏濾波器，使攻擊者無法獲知濾波器的具體信息，從而使攻擊者無法列出對應的線性方程。

由于FCSR本身為非線性結構，若再使用非線性濾波器將會使得分析困難，無法保證生成序列的性質。而減少每次的濾波輸出，如F-FCSR流密碼族中最早提出的F-FCSR-SF1[10]，就是只輸出1bit，雖然會使得列出的線性方程組大大減少，無法還原FCSR主寄存器，但是高的吞吐率對于流密碼來說非常重要，減少輸出會使得密鑰流生成器性能大幅下降，喪失效率優勢而無法滿足要求。所以最好的改進方法為隱藏濾波器，Arnault等人在文獻[10]中提出過動態的濾波器方案F-FCSR-DF1和F-FCSR-DF8，這些方案的濾波器由初始密鑰確定，確定之后將不變，但是由于濾波器與密鑰的相關性，且濾波器在運行階段不會變化，文獻[11]針對F-FCSR-DF1進行了重同步攻擊，因此可以認為其安全性不夠。本文提出一種全動態的濾波方案，保持8個子濾波器，濾波器會隨著時刻的不同而不同，使得攻擊者無法獲取濾波器的信息，從而不能列出關于FCSR主寄存器的線性方程組來還原FCSR主寄存器值。

下面從靜態的F-FCSR出發，來構造一個全動態的濾波器DF-FCSR-8，其結構如圖4所示。

用到了2個FCSR：FCSR1和FCSR2，其中前者作為產生序列的源，而后者作為產生動態濾波器的組成部分，它們的級數都為128，選取FCSR1的連接數q1為強2素數，根據定理3和定理4可知，參與運算的主寄存器序列都具有極大的線性復雜度。選取FCSR2的連接數q2為2素數可以保證FCSR2的主寄存器狀態周期最大。q1和q2的值分別為

-q1= 0x199B63C90F4DE193F1FC89DFCD2C484BB

-q2= 0x1AC913013BC417DFF5FD97CF6D318A26B

且有gcd((|q1|-1)2,(|q2|-1)2)=1。

如同F-FCSR方案一樣，首先選取一個固定的濾波器，使得FCSR1中所有左邊有進位寄存器的主寄存器參與濾波運算，這個固定的濾波器記為Fa，其值為

Fa=d=(|q1|+1)/2

=(CCDB1E487A6F0C9F8FE44EFE6962425E)16

圖4 全動態濾波器結構

8個子濾波器Fa7,Fa6,…,Fa0表示如下：

Fa7=(1100 0001 1101 0000)2,

Fa6=(1101 1100 0111 1111)2,

Fa5=(0000 1100 0101 1100)2,

Fa4=(0110 1001 0001 0001)2,

Fa3=(1111 1111 1011 1001)2,

Fa2=(1010 0111 1111 0001)2,

Fa1=(0110 1101 1011 0111)2,

Fa0=(0100 0101 1000 1000)2

其次，為了獲得動態的濾波器，需要有一個動態變化的組件，FCSR或LFSR的主寄存器會不停地變化，所以本文選擇FCSR2的主寄存器（記為Fd( t)）與靜態濾波器Fa一起通過按位與運算構成一個動態的濾波器。

但是這樣可能會在某些時刻出現某些濾波器為全零的情況，從而無法保證生成序列的性質。為此，還必須再引入一個濾波器Fb，使得最終復合成的動態濾波器F( t)為

其中，“&”表示按位與操作，“|”為按位或操作。特別地，要求：

1)Fb中為1的位置在Fa中也必須為1；

2) 對于任意子濾波器Fbi而言，其中只包含2個為1的值，也就是Fbi,0≤i≤7的漢明重量為2；

3) 按8bit分段，每一段中有且僅有1位值為1。

條件1)確保只有FCSR1中左邊有進位寄存器的主寄存器才能參與濾波運算。同時考慮到2個FCSR主寄存器序列進行按位模2加之后的生成序列具良好的統計特性，且破壞了2-adic復雜度，這樣條件2)可以使每個子濾波輸出序列固定會有2個FCSR1的主寄存器序列參與運算，保證輸出序列的性質，條件3)使得固定參與模2加運算的FCSR1主寄存器序列均勻分布于FCSR1主寄存器中，極大降低了每次參與模2加運算的變量的相關性。

通過計算，選取了Fb如下：

Fb=(80801040 40200810 01200804 01020204)16

那么Fb的對應8個子濾波器為

Fb7=(1100 0000 0000 0000)2,

Fb6=(0001 1000 0000 0000)2,

Fb5=(0000 0100 0100 0000)2,

Fb4=(0010 0001 0000 0000)2,

Fb3=(0000 0010 0010 0000)2,

Fb2=(0000 0000 0001 0001)2,

Fb1=(0000 0000 0000 0110)2,

Fb0=(0000 0000 1000 1000)2

根據式(7)可得動態濾波器F( t)，對應8個子濾波器由式(3)確定，在t時刻的子濾波器分別為F7(t),F6(t),…,F0( t)。

FCSR的主寄存器向量(m120(t), m112(t),…,m8( t), m0( t))用(t)表示，而( t),1≤i≤7表示主寄存器值(m120+i(t), m112+i(t),…,m8+i(t), mi( t))。z( t)為DF-FCSR-8在時刻t的一字節輸出，最低比特為z0( t)，最高比特為z7( t)，那么輸出字節z( t)可表示為

其中，Fi,j(t)表示向量Fi( t)中的第j個元素，(t)表示( t)中的第j個元素。

對于密鑰流生成器來說，K和初始化向量(IV)的設置過程是必不可少的，下面介紹全動態濾波密鑰流生成器DF-FCSR-8的K與IV的設置過程：密鑰K和初始化向量IV的長度皆為128bit，KL為密鑰的低64bit，KH為密鑰的高64bit；IVL為IV的低64bit，IVH為IV的高64bit，約定高位在左。

2) 將FCSR1和FCSR2的進位寄存器1C，2C都初始化為0：

3) 運行DF-FCSR-8密鑰流生成器32次，每次運行得到一個字節輸出Si(0≤i≤31)；

4) 利用得到的這些字節重新初始化主寄存器：

5) 將FCSR1和FCSR2的進位寄存器重新初始化為0：C1:=0,C2:=0；

6) 運行DF-FCSR-8生成器132個時鐘（將這一步的輸出丟棄）。

5 F-FCSR-8密鑰流生成器抗Hell-Johansson攻擊的分析

對于DF-FCSR-8密鑰流發生器來說Hell-Johansson攻擊將會困難得多。下面敘述對聯合的F-FCSR流密碼發生器的可能攻擊。

聯合的DF-FCSR-8中FCSR1主寄存器單元數共為128n=，對DF-FCSR-8定義如下事件：

Et1( r):C1( t)=C1( t+1)=…=C1( t+r )=(0,0,…,0,1,0)

事件Et1( r)發生時，FCSR1主寄存器變化情況由式(5)確定，但是由于DF-FCSR-8的濾波函數F( t)隨時間變化，且Fd( t)為秘密的，那么攻擊者無法完全確定F( t)的值，僅僅知道，Fb中為1的位置上F( t)也為1，Fa中為0的位置上F( t)也為0，由Fb中有16個1，Fa中有59個0，最終可以確定16+59=75bit，剩下53bit。若要正確列出線性方程組，有2種方法：

1) 對每個時刻下的濾波函數進行猜測，則正確列出t時刻下的線性方程組的概率為2-53，那么事件Et1( r)發生時，正確列出8(r+1)個線性方程組的概率為2-53(r+1)。

2) 對產生動態濾波器的FCSR2主寄存器M?2(t)進行猜測，以便獲得每個時刻下的濾波器，由于FCSR與密鑰相關，且無法得到主寄存器的相關信息，那么猜測正確的概率為2-128。

圖5 DF-FCSR-8隨機性測試通過率

當事件Et1( r)發生時，就可以列出8(r+1)個方程，如果能列出正確的線性方程組，根據第3節的分析可以得到，能解出FCSR主寄存器的概率如下：

在使用第一種方法的情況下，正確列出線性方程組的概率為2-53(r+1)，聯合起來，要恢復FCSR主寄存器，一次實驗的成功概率如下：

可以看出，成功概率與r成反比，在r=1時，成功概率就小于2-225，所以采用第一種方法是不可行的。

而對于方法2來說，猜測出所有時刻濾波器值的概率就為2-128，而在此基礎上，一次實驗的成功概率如下：

則一次實驗成功的概率下界為2-254+7·15=2-149，所以采用第二種方法也不可行。

6 DF-FCSR-8的其他密碼分析

本文利用美國國家技術與標準局NIST推出的STS軟件包（版本1.6）[12]對DF-FCSR-8的生成序列進行了測試。參數與文獻[9]中的測試參數相同，默認置信水平α=0.01下為：Block Frequency tests：20 000；Overlapping and Nonoverlapping Template tests：9；Universal test：7(with 1 280 initialization)Approximate Entropy and Serial tests：10；Linear Complexity test：2 000。測試了1 000組長度為610 bit的生成序列，結果表明全動態濾波密鑰流生成器DF-FCSR-8生成序列具有良好的隨機性。測試通過率如圖5所示，密鑰流生成器的生成序列通過率都在99%左右，偏差在1%之內。因此認為DF-FCSR-8密鑰流生成器的密鑰流具有良好的統計特性。

同時，在一個動態子濾波器中，會有固定的2個輸入序列，通過將其他動態輸入進行模2加的結果看成一個輸入序列，這樣可以將每個子濾波器看成3個輸入變量的線性函數。那么根據類似于文獻[9]的分析，可得全動態濾波密鑰流生成器DF-FCSR-8的生成序列在復雜度上類似于隨機序列，同時也能夠抵抗相關攻擊和代數攻擊。

7 結束語

本文分析了基于FCSR濾波的密鑰流生成器F-FCSR。研究了F-FCSR的線性弱點以及F-FCSR-Hv2被攻破的原因的基礎上，提出了全動態濾波密鑰流生成器DF-FCSR-8。該密鑰流生成器利用一個FCSR來生成動態的濾波器，使得濾波器會隨著時鐘脈沖變化，攻擊者無法獲得濾波器，從而使利用FCSR出現線性平移而進行的Hell-Johansson攻擊無效。其生成序列也通過了美國技術與標準局（NIST）的STS 軟件包的16 項隨機性測試。最后討論了改進流密碼生成器抵抗相關攻擊和代數攻擊的能力，結果表明DF-FCSR-8彌補了F-FCSR方案的缺陷，保證了原有的良好性質，生成簡單，速度快，統計特性良好。所以認為DF-FCSR-8密鑰流生成器是成功的。

[1] KLAPPER A, GORESKY M. 2-adic shift register[A]. Fast Software Encryption[C]. Combridge, UK, 1993. 174-178.

[2] GORESKY M, KLAPPER A. Feedback register based on ramified extensions of the 2-adic number[A]. Advances in Cryptology-eurocrypt’94[C]. Perugia, Italy, 1994. 215-222.

[3] KLAPPER A, GORESKY M. Feedback shift registers, 2-adic span and combiners with memory[J]. Journal of Cryptology, 1997, 10(1):111-147.

[4] GORESKY M, KLAPPER A. Fibonacci and galois representations of feedback-with-carry shift registers[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2826-2836.

[5] ARNAULT F, BERGER T P, LAURADOUX C. Update on F-FCSR stream cipher[DB/OL]. http://www.ecrypt.eu.org/stream/,2008.

[6] HELL M, JOHANSSON T. Breaking the F-FCSR-H stream cipher in real time[A]. Advances in Cryptology - ASIACRYPT 2008[C]. Melbourne, Australia, 2008. 557-569.

[7] ARNAULT F, BERGER T P, LAURADOUX C, et al. A new approach for FCSRs[A]. Selected Areas in Cryptography[C]. Springer,2009. 433-448.

[8] SEO C, LEE S, SUNG Y. A lower bound on the linear span of FCSR[J].IEEE Transactions on Information Theory, 2000,43(4): 691-693.

[9] ARNAULT F, BERGER T P. Design and properties of a new pseudorandom generator based on a filtered FCSR automaton[J] .IEEE Transactions on Computers, 2005, 54(11): 1374-1383.

[10] ARNAULT F, BERGER T P. F-FCSR: design of a new class of stream ciphers[A]. Fast Software Encryption 2005[C]. Springer, Berlin,2005. 83-97.

[11] JAULMES E, MULLER F. Cryptanalysis of the F-FCSR stream cipher family[A]. SAC 2005[C]. Springer, Berlin, 2000.20-35 .

[12] RUKHIN A, SOTO J, NECHVATAL J, et al. A statistical test suite for random and pseudorandom number generator for cryptographic applications[EB/OL]. http://csrc.nist. gov/rng/SP800-22b.pdf,2004.