一種基于Rule30+ 細(xì)胞自動機(jī)的流密碼設(shè)計方法*

郭曉威, 郭亞軍

華中師范大學(xué) 計算機(jī)學(xué)院, 武漢430079

1 引言

細(xì)胞自動機(jī)首先由馮諾伊曼[1]提出, 這是一種研究復(fù)雜系統(tǒng)的理論模型. 在1986 年, S. Wolfram 通過簡化細(xì)胞自動機(jī)的行為, 首個提出使用細(xì)胞自動機(jī)來設(shè)計流密碼[2]. 這種流密碼的設(shè)計基于Rule30, 能夠輸出隨機(jī)性質(zhì)良好的密鑰流, 同時安全性可以歸結(jié)于NP 問題. MS 攻擊[3]由Meier 等人在1992 年提出, 這是一種針對該結(jié)構(gòu)的攻擊方式, 它根據(jù)結(jié)構(gòu)中存在的線性相關(guān)性進(jìn)行攻擊, 并指出需要超過1000 長度的Rule30 細(xì)胞自動機(jī), 才能實(shí)現(xiàn)其計算上的安全. 目前基于細(xì)胞自動機(jī)設(shè)計流密碼主要包含兩種思路,一種是設(shè)計更復(fù)雜的規(guī)則, 如CARPenter[4], 它選擇了一種5 鄰域規(guī)則的細(xì)胞自動機(jī)來作為流密碼的非線性部分. 另一種是設(shè)計更復(fù)雜的結(jié)構(gòu), 如CAR30[5]或者CASTREAM[6]. 之所以會不斷有學(xué)者嘗試使用細(xì)胞自動機(jī)設(shè)計流密碼, 這主要是基于兩個原因. 首先, 細(xì)胞自動機(jī)的結(jié)構(gòu)具備并行特性, 這種性質(zhì)能夠很好的由硬件在較小的開銷下實(shí)現(xiàn). 第二, 一個設(shè)計良好的流密碼往往能夠作為偽隨機(jī)數(shù)發(fā)生器使用, 基于細(xì)胞自動機(jī)能夠設(shè)計出性能良好的偽隨機(jī)數(shù)發(fā)生器[7–9]和真隨機(jī)數(shù)發(fā)生器[10]. 并且, 細(xì)胞自動機(jī)一個獨(dú)特的優(yōu)勢在于規(guī)則編碼, 編碼后的規(guī)則可以使用編輯距離來判斷兩個規(guī)則是否相似, 并且表征能力良好.這種特性使得在確定了適應(yīng)度函數(shù)后, 可以通過進(jìn)化算法去自動的生成所需要的規(guī)則或者規(guī)則集[11,12].

Rabbit[13]和Grain-v1[14]是ESTREAM 項目[15]中進(jìn)入了final list 的兩種流密碼設(shè)計結(jié)構(gòu). 前者是一種基于復(fù)雜系統(tǒng)理論設(shè)計的流密碼算法, 它包含513 個內(nèi)部狀態(tài), 具有很好的安全性, 但在效率上與后者相比略顯不足. 它的一個啟發(fā)意義在于, 純粹的基于復(fù)雜系統(tǒng)理論模型是可以設(shè)計出一個符合現(xiàn)代流密碼安全性要求的算法的. 后者是ESTREAM 硬件組的優(yōu)勝者, 它的結(jié)構(gòu)包含一個線性模塊, 非線性模塊和輸出函數(shù), 各個模塊間滿足一定的依賴關(guān)系. 這種結(jié)構(gòu)層次非常清晰, 符合這種設(shè)計思路的流密碼都可以歸屬為Grain Family. Grain 算法自提出以來經(jīng)過了好幾次的修改, 比如Grain-v1 被認(rèn)為無法抵抗線性逼近攻擊[16], 于是Grain-128[17]通過修改結(jié)構(gòu)中線性結(jié)構(gòu)與非線性結(jié)構(gòu)的反饋函數(shù)以及輸出函數(shù),解決了相關(guān)性問題. 我們注意到, Grain 算法的安全性很大程度的依賴于結(jié)構(gòu)中的反饋函數(shù)以及輸出函數(shù),這使得當(dāng)密鑰長度發(fā)生變化時, 結(jié)構(gòu)中所有的函數(shù)都需要重新設(shè)計. 將細(xì)胞自動機(jī)引入到Grain 型結(jié)構(gòu)的設(shè)計中, 可以使得流密碼在具備相當(dāng)安全性的情況下, 同時具備對任意長度密鑰的適配性.

在上文提到的CAR30[5]就是一種屬于Grain Family 結(jié)構(gòu), 同時具備適應(yīng)任意長度密鑰的流密碼設(shè)計, 當(dāng)設(shè)計需要適配新密鑰長度的時候, 只需要修改結(jié)構(gòu)中對應(yīng)的內(nèi)部狀態(tài)數(shù), 而不需要像Grain 一樣重新設(shè)計流密碼算法. CAR30 中包含3 個128 bit 長的細(xì)胞自動機(jī), 一共384 個內(nèi)部狀態(tài). CAR30 的問題在于, 硬件的開銷較大, 在該設(shè)計思路下很難快速的產(chǎn)生密鑰流. 這主要是因?yàn)樗惴ㄔ趫?zhí)行過程中包含循環(huán)操作, 引入循環(huán)操作本身會帶來額外的硬件開銷. 并且, 由于不同模塊間的循環(huán)操作不能很好的并行進(jìn)行, 還需要加入同步的控制信號. 這使得算法無法以時鐘周期為單位輸出密鑰流, 從而在設(shè)計層面上限制了產(chǎn)生密鑰流的速度.

本文提出一種新的流密碼設(shè)計思路, 算法屬于Grain Family 結(jié)構(gòu). 我們對Rule30 進(jìn)行了改進(jìn), 稱之為Rule30+. Rule30+ 依然屬于一種簡單的規(guī)則, 之所以本文沒有使用5 鄰域規(guī)則, 這主要是因?yàn)? 鄰域規(guī)則的引入會帶來較大的硬件開銷, 與流密碼目前的定位不太符合. 基于該規(guī)則設(shè)計非線性模塊使得算法能夠解決Rule30 所引發(fā)的線性相關(guān)性問題, 即能夠抵抗MS 攻擊. 同時較CAR30 有著更小的硬件開銷與更快的密鑰流產(chǎn)生速度.

論文的組織如下, 首先在第2 節(jié)中介紹與算法設(shè)計相關(guān)的預(yù)備知識. 在第3 節(jié)中會給出Rule30+ 的介紹和算法的詳細(xì)設(shè)計與偽碼實(shí)現(xiàn), 隨后在第4 節(jié)和第5 節(jié)分別對算法的隨機(jī)性和安全性進(jìn)行分析, 最后在第6 節(jié)給出算法的硬件開銷與結(jié)論.

2 相關(guān)知識

2.1 一維細(xì)胞自動機(jī)

細(xì)胞自動機(jī)是一個具有時間與空間概念的動態(tài)系統(tǒng), 它由多個細(xì)胞構(gòu)成, 細(xì)胞的排列方式可以是1 維的, 比如向量, 也可以是2 維的, 如矩陣, 或是是高維的. 我們使用c0,c1,c2,··· ,cn?1來表示細(xì)胞自動機(jī),n 為細(xì)胞的個數(shù), 在一維細(xì)胞自動機(jī)中等于向量長度. 對于細(xì)胞而言, 在給定的時刻t, 它都會擁有狀態(tài)要sti和狀態(tài)轉(zhuǎn)移函數(shù)f(ci), f(ci) 用于確定t+1 時刻下該細(xì)胞的狀態(tài), 即有st+1i= f(ci). 本論文中探討的是在GF(2) 下的一維細(xì)胞自動機(jī), 此時細(xì)胞狀態(tài)的取值只能是0 或者1. 為了方便之后的敘述, 我們記t 時刻下長度為l 的細(xì)胞自動機(jī)狀態(tài)(st0,st1,··· ,stl?1) 為St. 記細(xì)胞ci自t 時刻起所產(chǎn)生的狀態(tài)序列(sti,st+1i,··· ,st+k?1i) 為Cti, 且有Cti的長度為len(Cti)=k. 在接下來比較的過程中, 對于起始時間相同的Cti間的對比, 會將其簡寫為Ci, 或稱之為第i 列.

2.2 一維細(xì)胞自動機(jī)的相關(guān)概念

2.2.1 細(xì)胞半徑

細(xì)胞半徑用來確定一個細(xì)胞存在多少“鄰居”, 當(dāng)細(xì)胞半徑為d 時, 一個細(xì)胞有2d+1 個鄰居. 具體的來說, 對于ci,cj, 如果|i ?j|≥d, 那么我們可以認(rèn)為兩個細(xì)胞是相鄰的. 當(dāng)d=1 時, 即是一般意義上的相鄰. 當(dāng)且僅當(dāng)兩個細(xì)胞處于相鄰關(guān)系時, 細(xì)胞之間才可能會有關(guān)聯(lián)性, 這種關(guān)聯(lián)性體現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)上, 細(xì)胞是自相鄰的.

2.2.2 規(guī)則

規(guī)則是在指定細(xì)胞半徑下用來描述細(xì)胞狀態(tài)轉(zhuǎn)移函數(shù)的一種概念, 一般可以用一個具體的狀態(tài)轉(zhuǎn)移函數(shù)描述規(guī)則. 特別的, 對于細(xì)胞半徑為1 的一維細(xì)胞自動機(jī), 一般以數(shù)字作為規(guī)則的代號. 比如本文開頭提到的Rule30, 這是一種細(xì)胞半徑為1 的規(guī)則, 一共有256 種這樣的規(guī)則.

2.2.3 混合和簡單細(xì)胞自動機(jī)

“簡單” 指細(xì)胞自動機(jī)中, 所有細(xì)胞都服從相同的規(guī)則. 相對的, 當(dāng)至少存在兩個細(xì)胞, 它們服從不同的規(guī)則的時候, 那么就稱這種細(xì)胞自動機(jī)是混合細(xì)胞自動機(jī), 混合細(xì)胞自動機(jī)可以是細(xì)胞間規(guī)則不同, 也可以是一個細(xì)胞在不同時刻下, 或是在其他條件下, 服從不同的規(guī)則.

2.2.4 邊界條件

一維細(xì)胞自動機(jī)的細(xì)胞排列為向量, 這使得第一個元素和最后一個元素在細(xì)胞半徑為1 時, 均只有兩個鄰居. 為了使得細(xì)胞自動機(jī)中所有的細(xì)胞都具有相同的鄰居數(shù)量, 需要引入邊界條件. 常見的邊界條件包括0 邊界, 1 邊界, 循環(huán)邊界和鏡像邊界. 一般而言, 邊界條件是對稱的, 即左, 右兩側(cè)選用相同的邊界條件.

表1 是一個關(guān)于規(guī)則30 的描述, Status 代表的是鄰居的狀態(tài), Next 代表的是下一個時刻細(xì)胞的狀態(tài).以101 為例, 它代表對于指定細(xì)胞c, 當(dāng)左側(cè)細(xì)胞狀態(tài)為1, 本身狀態(tài)為0, 右側(cè)細(xì)胞狀態(tài)為1 時, 下一個時刻細(xì)胞c 的狀態(tài)為0. 可以看到,Next 行中8 個狀態(tài)所組成的二進(jìn)制數(shù)(00011110), 轉(zhuǎn)化為十進(jìn)制就是30.

表1 Rule30 狀態(tài)轉(zhuǎn)移表Table 1 Status transform table of Rule30

2.2.5 線性細(xì)胞自動機(jī)和非線性細(xì)胞自動機(jī)

對于線性細(xì)胞自動機(jī), 可以使用線性變化T 來描述不同時刻下細(xì)胞自動機(jī)狀態(tài)的關(guān)系, T 由細(xì)胞自動機(jī)所服從的規(guī)則確定. 如果細(xì)胞自動機(jī)的狀態(tài)變化不能用上述的表達(dá)式來進(jìn)行描述, 那么就稱為非線性細(xì)胞自動機(jī). 例如, 對于0 邊界, 規(guī)則90 的細(xì)胞自動機(jī), 有

3 設(shè)計思路

3.1 Rule30+ 及其性質(zhì)

在給出流密碼的詳細(xì)設(shè)計之前, 我們先介紹Rule30+. Rule30+ 的更新函數(shù)與Rule30 類似, 兩者的狀態(tài)轉(zhuǎn)移方程如下. 另外, 本文中涉及的加法均為模2 加法.

對比Rule30 的更新規(guī)則, Rule30+ 不同的地方在于對最后一個細(xì)胞的依賴上. 之所以進(jìn)行修改的原因有兩點(diǎn), 第一, 規(guī)則中包含的邏輯操作數(shù)量會極大的影響硬件開銷, 這使得修改主要在依賴關(guān)系上. 第二,通過修改依賴關(guān)系使得細(xì)胞的狀態(tài)轉(zhuǎn)移只與其中一側(cè)的細(xì)胞相關(guān), 所以只存在一個擴(kuò)散方向, 這樣能夠解決Rule30 中的線性相關(guān)性問題. 另外, 由于改變的僅是依賴關(guān)系, 這使得Rule30+ 能同Rule30 一樣保證狀態(tài)的0/1 產(chǎn)生的頻率. 隨后, 在邊界條件的設(shè)置上, 有X0和X1需要應(yīng)用邊界條件.

以下是Rule30+ 的性質(zhì), 這些性質(zhì)可以直接根據(jù)狀態(tài)轉(zhuǎn)移方程得出.

3.2 詳細(xì)設(shè)計

這一節(jié)中我們將給出算法的具體設(shè)計, 算法一共由256 個內(nèi)部狀態(tài), 即256 bit. 其中線性部分使用119 bit, 非線性部分使用137 bit. 密鑰的長度為128 bit, IV 的長度為112 bit. 對于線性部分, 我們使用si來表示第i 個位置的狀態(tài), 同理對應(yīng)非線性部分, 我們使用bi來表示第i 個位置的狀態(tài). 下面, 我們將按照非線性模塊、線性模塊、輸出函數(shù)三個部分對流密碼的結(jié)構(gòu)進(jìn)行說明.

對于流密碼的非線性部分, 我們基于Rule30+ 進(jìn)行設(shè)計, 稱之為CA30+, 其狀態(tài)轉(zhuǎn)移方程同(2), 其中邊界條件b?1,b?2的設(shè)置如下

當(dāng)且僅當(dāng)算法處于初始化階段時, a=1, 且Zt代表此時的輸出. 其中, b?1用于保證CA30+ 對CA90 直接的依賴關(guān)系. 而之所以b?2的變換取決于CA90, CA30+ 以及Zt, 原因如下. 第一, 包含CA90 的狀態(tài)能夠改善b?2在統(tǒng)計意義上的隨機(jī)性, 同時使得b136依賴更多CA90 的狀態(tài). 第二, 雖然CA90 在初始化階段中邊界條件與Zt相關(guān), 但在已知IV 的情況下, 由于CA90 的擴(kuò)散需要時間, 這使得攻擊者仍可以推斷出一部分s60序列, 于是在初始化階段中引入Zt, 可以使得攻擊者無法確定Zt+s60的值. 第三, 由引理2 可知, 若b?1,b?2的變化僅與CA90 相關(guān), 那么存在時刻t, 使得CA30+ 的狀態(tài)在t 時刻后僅與CA90 相關(guān), 而與密鑰的選取無關(guān). 這使得b?2的變換需要引入CA30+ 狀態(tài)的影響. 另外, 其中需要引入的CA30+ 狀態(tài)數(shù)與CA30+ 的長度有關(guān), 其最終關(guān)聯(lián)的狀態(tài)數(shù)應(yīng)在log2l 左右, l 為CA30+ 的長度, 同時其位置應(yīng)滿足均勻分布.

對于線性部分, 一般的設(shè)計思路是使用Rule90 和Rule150 在零邊界下設(shè)計一個滿周期細(xì)胞自動機(jī)[18], 這種情況下對細(xì)胞自動機(jī)的長度沒有限制. 事實(shí)上, 線性反饋移位寄存器(LFSR) 和90–150 細(xì)胞自動機(jī)產(chǎn)生的隨機(jī)序列具有相當(dāng)?shù)碾S機(jī)性能, 并且較之前者, 有更大的線性復(fù)雜度, 同時在長度較大的情況下, 更容易在硬件中實(shí)現(xiàn)[19]. 本文基于Rule90 在鏡像-零邊界下設(shè)計線性部分, 稱之為CA90. 這主要是因?yàn)镽ule90 較Rule150 有更小的硬件開銷和更快的運(yùn)算速度. 這種方式的問題在于對細(xì)胞自動機(jī)的長度進(jìn)行了限制, 只有滿足特定條件的長度才能成為滿周期細(xì)胞自動機(jī), 119 bit 就是一個滿足上述要求的長度[20]. 以下是Rule90 和Rule150 的狀態(tài)轉(zhuǎn)移方程

對于本文所使用的Rule90, 其狀態(tài)轉(zhuǎn)移方程同式(5), 它們的不同點(diǎn)在于處理邊界值的情況. 以下是0 邊界Rule90 和本文使用的Rule90 在鏡像邊界上的狀態(tài)轉(zhuǎn)移方程.

其中, 當(dāng)算法處于初始化階段時, a=1, 在密鑰流輸出階段, a=0.

最后在輸出函數(shù)部分, 本文使用的輸出函數(shù)為

之所以輸出函數(shù)較Grain-128[17]顯得比較“簡單”, 這主要是因?yàn)樵贕rain-128 中的非線性部分, t+n 時刻下新產(chǎn)生的內(nèi)部狀態(tài)已經(jīng)在非線性反饋移位寄存器中(NFSR) 中存在了n 個時鐘周期了, n 為NFSR的長度, 這使得攻擊者可以追溯t 時刻下NFSR 的情況, 并利用兩者的相關(guān)性去推斷出線性結(jié)構(gòu)的內(nèi)部狀態(tài). 對于本文中的非線性狀態(tài)b136, 它是經(jīng)過多次不可逆狀態(tài)轉(zhuǎn)移方程的迭代后完成的, 具有很高的線性復(fù)雜度, 這是本文選擇該輸出函數(shù)的原因.

如圖1 和圖2 所示,流密碼的運(yùn)行階段分為兩個部分,一個是初始化階段,另外一個是密鑰流輸出階段.在初始化階段, 算法首先將Key 和IV 分別裝載到CA30+ 和CA90 中. 設(shè)ki代表Key 的第i 位, 同理, vi代表IV 的第i 位. 設(shè)密鑰長度為lk, 初始化向量的長度為li, CA30+ 的長度為l30, CA90 的長度為l90, 于是有bi+1= ki(0 ≤i < lk), 以及si= vi(0 ≤i < li). 隨后, 將b0,si(li≤i ≤l90) 置為1, 將bj(lk≤j ≤l30) 置0. 另外, 在初始化階段, 算法不產(chǎn)生密鑰流. 最后執(zhí)行輪數(shù)r = 256 后(r 應(yīng)至少大于算法中包含的內(nèi)部狀態(tài)數(shù)), 完成初始化操作. 在密鑰流輸出階段, 算法在每個單位時鐘周期下都會產(chǎn)生1 bit 的密鑰.

圖1 初始化階段Figure 1 Initial mode

圖2 密鑰流輸出階段Figure 2 Output mode

3.3 算法偽碼

算法總體結(jié)構(gòu)如偽碼1所示, 偽碼2代表一個時鐘周期下, 算法完成具體的操作. 每完成一次Round 函數(shù), 都會更新一次變量Output 的值. 算法首先分為初始化階段, 密鑰流輸出兩個階段. 在初始化階段將Key 和IV 載入到CA30+ 和CA90 中. 對于算法中涉及到的運(yùn)算操作, 這些操作是以bit 為單位進(jìn)行的.特別的, 對于軟件環(huán)境下的算法實(shí)現(xiàn), 可以通過以byte 為單位事先建立代換表和置換表的方式, 來加快算法的執(zhí)行速度, 使用該方法需要額外占用2 KB 的內(nèi)存空間.

偽碼1 流密碼結(jié)構(gòu)Load Key, IV to CA30+ and CA90.#Initial Mode for i in 0 to 255 do Round();end#Output Mode for i in 0 to LengthOfKeyStream do Round();Add Output To KeyStream;end偽碼2 函數(shù)Round#CA30+for j in 0 to 136 do# when j = 0 or j = 1, need to call boundary condition CA30+Temp[j] = CA30+[j ?1] XOR (CA30+[j ?2] And CA30+[j]);end#CA90+for j in 0 to 118 do# when j = 0 or j = 118 need to call boundary condition if on Initial Mode then CA90Temp[j] = CA90[j ?1] XOR CA90[j +1];# when j = 118 will do CA90Temp[118] = CA90[117] XOR Output;end else CA90Temp[j] = CA90[j ?1] XOR CA90[j +1];end end Swap Temp and CA;Output = CA30+[136] XOR CA90[71];

4 隨機(jī)性分析

4.1 NIST 隨機(jī)性測試

本文使用NIST 隨機(jī)性測試[21]作為算法隨機(jī)性的檢測工具. 它是一種常見的隨機(jī)性檢測方式, 一共包含15 項測試, 分別是頻度檢驗(yàn)(Frequency)、塊內(nèi)頻度檢驗(yàn)(Block Frequency)、游程檢驗(yàn)(Runs)、塊內(nèi)最長游程檢驗(yàn)(Longest Run)、二元矩陣秩檢驗(yàn)(Rank)、離散傅里葉變化檢測(FFT)、非重疊模塊匹配檢驗(yàn)(Non Overlapping Template)、重疊模塊匹配檢驗(yàn)(Overlapping Template)、通用統(tǒng)計檢驗(yàn)(Universal)、近似熵檢驗(yàn)(Approximate Entropy)、隨機(jī)游動檢驗(yàn)(Random Excursions)、隨機(jī)游動狀態(tài)頻度檢測(Random Excursions Variant)、序列檢測(Serial) 和線性復(fù)雜度檢測(Linear Complexity).

4.2 測試的參數(shù)選取和結(jié)果概述

本節(jié)將對算法的隨機(jī)性檢驗(yàn)結(jié)果進(jìn)行分析, 我們選用了一種基于混沌理論設(shè)計的偽隨機(jī)數(shù)發(fā)生器, 在下文中稱為WQ 算法[22], 作為隨機(jī)性的對照. 本文調(diào)用以系統(tǒng)時間為種子的隨機(jī)函數(shù)為算法生成了Key和IV, 隨后使用算法生成了長度為20 MB 的字節(jié)流, 編碼的方式為二進(jìn)制. 在NIST 隨機(jī)性測試的參數(shù)選取上, 我們將20 MB 的字節(jié)流劃分成了20 段, 每一段之間獨(dú)立的進(jìn)行NIST 隨機(jī)性測試, 關(guān)于具體到每個測試的參數(shù), 我們采用測試中的默認(rèn)參數(shù). 最后得出結(jié)果如表2 所示. P-Value 為該檢測經(jīng)過歸一化的決策指標(biāo), 當(dāng)P-Value>0.01 時, 認(rèn)為通過該檢驗(yàn), 且值越大, 代表效果越好. WQP-Value 代表WQ 算法在該檢驗(yàn)下的P-Value 值. Compare 列代表兩者的測試效果對比. 此時我們可以看到, 對于本文所提出的算法, 算法通過了15 項檢驗(yàn), 且在15 項檢驗(yàn)中有7 項檢驗(yàn)弱于WQ 算法, 有5 項檢驗(yàn)強(qiáng)于WQ 算法,具有相當(dāng)?shù)碾S機(jī)性. 因而, 本文提出的流密碼能夠產(chǎn)生隨機(jī)性良好的密鑰流序列.

表2 NIST 隨機(jī)數(shù)測試的結(jié)果Table 2 Result of NIST random test

4.3 結(jié)果分析

隨機(jī)序列的熵、線性復(fù)雜度和長1/0 序列的分布是流密碼的設(shè)計中比較重要的隨機(jī)性指標(biāo), 這分別對應(yīng)于近似熵檢驗(yàn)、線性復(fù)雜度檢驗(yàn)、塊內(nèi)最長游程檢驗(yàn). 本節(jié)將對這三個檢驗(yàn)的結(jié)果以及P-Value 值較小的重疊模塊匹配檢驗(yàn)測試進(jìn)行分析, 這是因?yàn)閷τ诩?xì)胞自動機(jī)所產(chǎn)生的隨機(jī)序列, 時間越相近, 關(guān)聯(lián)度越大. 我們將首先介紹近似熵檢驗(yàn), 并以(01101001)2為為例, 說明該檢驗(yàn)的執(zhí)行過程.

圖3 左右兩側(cè)分布表明了近似熵檢測中P-Value 和近似熵的分布情況. 左側(cè)的橫軸代表字節(jié)段的編號, 由0 到19, 縱軸代表P-Value 值. 右側(cè)的縱軸表示近似熵的取值, 其中maxValue 代表近似熵可以取得的以e 為log 底數(shù)的最大值. 本小節(jié)中圖都將以該形式出現(xiàn). 由此我們可以看到, 各個字節(jié)段的近似熵始終穩(wěn)定在一個區(qū)間, 這說明各個字節(jié)段之間隨機(jī)性質(zhì)相似. 另外, 由于隨機(jī)序列的長度有限, 并且很難保證在任意長度下, 0/1 的產(chǎn)生數(shù)量完全相等, 這使得序列的熵值必然存在誤差. 本文字節(jié)段長度的量級為106, 偏差的量級為10?5, 誤差在合理的范圍內(nèi). 算法通過了該檢驗(yàn).

圖3 近似熵檢驗(yàn)Figure 3 Approximate entropy test

對于線性復(fù)雜度檢驗(yàn), 有如下步驟

圖4 的左側(cè)是線性復(fù)雜度檢驗(yàn)的P-Value 分布情況, 右側(cè)為P-Value 取最大值和最小情況下的頻數(shù)分布情況, 其中, 橫軸表示標(biāo)號為Cx的區(qū)間. 且有P-Valuemax= 0.978891, P-Valuemin= 0.035101.由此可以看到, 雖然直觀上來看, 兩者的分布情況近乎完全一致, 然而P-Value 卻有很大的區(qū)別, 這說明P-Value 對數(shù)據(jù)的分布情況非常敏感, 將閾值設(shè)為0.01 是嚴(yán)格的, 本文提出的算法通過了該檢測.

對于塊內(nèi)最長游程檢測, 其關(guān)

注點(diǎn)在于塊內(nèi)最長的1 序列. 該檢測的步驟如下:

(1) 將序列切分成m 個長度為n=10000 的子塊.

(2) 為每一個子塊計算其1 序列長度的最大值mi.

(3) 設(shè)Ci為1 序列長度最大值為i 的字塊數(shù), 使用C10?,C11,C12,C13,C14,C15,C16+記錄不同1序列最大長度的子塊數(shù)量, 最后使用P-Value 判斷統(tǒng)計量Ci是否服從卡方分布.

圖4 線性復(fù)雜度檢驗(yàn)Figure 4 Linear complexity test

該檢測的依據(jù)在于, 一個序列如果是隨機(jī)生成的, 那么對于長度2n的子塊, 出現(xiàn)長度為n 的最長1序列是合理且概率最高的. 圖5 說明了P-Value 和以及當(dāng)P-Value 取最小值和最大值時, 頻數(shù)Ci的分布情況, 且有P-Valuemax=0.992 138, P-Valuemin=0.04 771. 其中, 橫軸代表的是長1 序列的長度, 縱軸代表出現(xiàn)的頻數(shù). 其中橫軸的邊界, 即刻度為10 和16 時, 代表小于等于10 或者大于等于16 的頻數(shù). 從圖5 可以看出, 兩者存在區(qū)別的地方在于1 序列最大值大于12 的位置. 但總的來說, 兩者在分布上基本一致, 并且眾數(shù)相同, 因而我們認(rèn)為兩者的隨機(jī)性質(zhì)相似. 算法通過了該檢驗(yàn).

圖5 塊內(nèi)最長1 序列Figure 5 Longest run test

重疊模塊匹配檢驗(yàn)是本文沒有通過的隨機(jī)性檢驗(yàn), 它的過程與模式匹配類似. 以下是它的具體步驟.

(1) 檢驗(yàn)首先將切分成N 個長度為M 的子塊, 設(shè)定模式的長度為m. 在檢驗(yàn)中為模式設(shè)置了初值.

(2) 模式的匹配過程可以認(rèn)為是窗口的滑動過程, 每完成一次匹配操作, 窗口將右移一位. 其中, vi代表第i 個子塊模式匹配成功的次數(shù).

(3) 設(shè)Ci代表匹配成功次數(shù)等于i 的子塊數(shù)量, 使用C0,C1,C2,C3,C4,C5+記錄匹配成功次數(shù)的分布情況. 其中5+ 代表匹配成功次數(shù)大于等于5 的子塊數(shù)量. 在該檢驗(yàn)中, P-Value 表征Ci分布是否服從卡方分布.

圖6 代表P-Value 的分布,以及當(dāng)P-Value 取最大值和最小值時,Ci的分布情況.其中P-Valuemax=0.874 100, P-Valuemin=0.002 812. 雖然對于右側(cè)顯示的頻數(shù)分布中, 決策指標(biāo)P-Value 相差很大, 但是在兩者的頻數(shù)分布上沒有明顯區(qū)別, 算法通過了該檢驗(yàn).

5 安全性分析

5.1 流密碼分析概述

目前常見的流密碼分析方法包括窮舉攻擊、代數(shù)攻擊、相關(guān)攻擊、差錯攻擊、區(qū)分攻擊、選擇IV 攻擊、滑動攻擊、立方攻擊、時間-空間交換攻擊(Time-Memory Trade-off Attack)、猜測并確定攻擊(Guess and Determine Attack)[24]. 本文我們將基于部分密碼分析方法以及針對Rule30 設(shè)計MS 攻擊[3]進(jìn)行安全性分析.

圖6 重疊模塊檢測Figure 6 Overlapping template test

5.2 MS Attack

MS Attack[3]是分析Rule30 的一種方法. 它的思路如下, 它通過猜測一部分細(xì)胞自動機(jī)的內(nèi)部狀態(tài),并利用結(jié)構(gòu)中存在的線性相關(guān)性來恢復(fù)細(xì)胞自動機(jī)的狀態(tài), 最后根據(jù)密鑰流驗(yàn)證猜測的內(nèi)部狀態(tài)是否正確. 它被認(rèn)為能夠攻擊基于Rule30 設(shè)計的非線性結(jié)構(gòu), 以下是采用MS 攻擊對Rule30 進(jìn)行分析的步驟說明.

由MS 攻擊對Rule30 攻擊步驟我們可以看到, 如果按照窮舉法猜測St, 它的狀態(tài)空間大小為22k+1,而利用MS 攻擊, 則可以將需要窮舉的狀態(tài)空間大小縮小為2k. 我們注意到,MS 攻擊中對Rule30 的攻擊沒有指定Rule30 的邊界條件, 這意味著通過調(diào)整Rule30 的邊界條件使得它能抵抗MS 攻擊是不可行的.

對于Rule30+, 為了使得它能夠抵抗MS 攻擊, 一個核心問題就是阻斷上述步驟2 和步驟3 中所描述的bti(i < k) 的鏈?zhǔn)酵茖?dǎo)過程. 在MS 攻擊對Rule30+ 攻擊的場景中, 我們采用與上述Rule30 相同的符號表示, 即是在已知任意時刻下b2k的情況下, 希望能夠恢復(fù)某時刻t 下細(xì)胞自動機(jī)狀態(tài)St. 下面我們來說明Rule30+ 是如何通過阻斷鏈?zhǔn)酵茖?dǎo)過程, 從而能夠抵抗MS 攻擊的.

(1) 在猜測部分的選取上, 可以選擇b0,b1,··· ,bk或者bk+1,bi+2,··· ,b2k?1, 前者離b2k較遠(yuǎn), 在在邊界條件未知的情況下, 無法利用已知條件b2k, 因而排除. 于是在猜測部分的選取上, 只能選取后者.

另外, 在上述步驟中, 我們出于符號統(tǒng)一的原因假定了細(xì)胞自動機(jī)的長度為奇數(shù). 需要說明的是, 無論其長度是偶數(shù)或是奇數(shù), 并不影響最后的結(jié)論, 即Rule30+ 能夠抵抗MS 攻擊. 除此之外, 我們也能夠看到, Rule30 和Rule30+ 細(xì)胞自動機(jī)的安全性問題可以歸結(jié)于求某指定時刻t 下的狀態(tài)St, 這意味著它的復(fù)雜度很大程度上取決于它的長度, 而不是初態(tài)的生成方式. 所以, 當(dāng)需要Rule30+ 細(xì)胞自動機(jī)適應(yīng)更大長度密鑰的時候, 只需要增大它的長度即可.

5.3 猜測決定攻擊

猜測決定攻擊的思路如下, 它通過猜測加密算法的一部分的內(nèi)部狀態(tài), 隨后試圖尋找到某種方式去確定猜測的內(nèi)部狀態(tài)是否正確. 比如對于一個包含2k 個內(nèi)部狀態(tài)的加密算法, 猜測決定攻擊首先選定其中k 個內(nèi)部狀態(tài), 對其進(jìn)行猜測, 隨后試圖尋找到一種多項式時間復(fù)雜度的方式去驗(yàn)證猜測是否正確, 如果能夠找到, 那么只需要對剩下的內(nèi)部狀態(tài)繼續(xù)進(jìn)行猜測即可. 于是, 猜測決定攻擊可以將破解該加密算法的時間開銷由22k降到2k+1. 事實(shí)上, 我們可以看到猜測決定攻擊的關(guān)鍵在于“決定”, 即尋找到驗(yàn)證猜測正確的方法. 注意到, 我們在MS 攻擊一節(jié)中已經(jīng)說明了, 即使已知一半的CA30+ 中的內(nèi)部狀態(tài), 也是不能還原CA30+ 狀態(tài)的. 而如果不能還原CA30+ 的狀態(tài), 就無法產(chǎn)生密鑰流, 從而使得驗(yàn)證無法進(jìn)行. 于是,本文提出的算法能夠抵抗猜測決定攻擊.

5.4 代數(shù)攻擊

表3 回溯次數(shù)與參數(shù)個數(shù)的對應(yīng)表Table 3 Corresponding table of number of backtracking times and number of parameters

5.5 時間/空間交換攻擊

時間/空間交換攻擊是一種以空間換時間的攻擊思路,比如事先存儲部分密鑰與密鑰流,該攻擊的時間復(fù)雜度與加密算法的內(nèi)部狀態(tài)數(shù)有關(guān). 本文中使用的加密算法一共有256 個內(nèi)部狀態(tài), 因而其時間復(fù)雜度不會小于O(2128).

5.6 滑動攻擊

滑動攻擊主要針對的是使用輪函數(shù)的加密算法, 尤其是在輪函數(shù)F 較為簡單的情況下. 它的核心在于尋找到一組(X,Y), 使得Y =F(key,X) 成立. 此時, 由于輪函數(shù)F 較為簡單, 且X,Y 均已知, 這使得我們可以很容易的從中得到key. 需要說明的是, 對于(X,Y) 的尋找主要是通過生日攻擊的思路進(jìn)行的, 這使得滑動攻擊需要存儲足夠多的(X,Y). 于是, 滑動攻擊本質(zhì)上仍屬于時間/空間交換攻擊, 這意味著它的時間復(fù)雜度不會小于O(2128).

5.7 線性逼近

線性逼近屬于相關(guān)攻擊, 它的核心思路在于尋找出流密碼所產(chǎn)生的密鑰流與它結(jié)構(gòu)中線性部分的關(guān)系, 其中一個關(guān)鍵的步驟在于利用偏差使用線性結(jié)構(gòu)的內(nèi)部狀態(tài)代替非線性變量, 偏差越大, 該方法越有效. 對于本文提出的流密碼結(jié)構(gòu), 非線性結(jié)構(gòu)與線性結(jié)構(gòu)的關(guān)系源于b?2,b?1, 而尋找到b136與線性部分的關(guān)系需要展開Rule30+ 一共68 次, 于是我們認(rèn)為尋找到一種同時包含bi和si的等式去表達(dá)b136是很困難的, 所以我們認(rèn)為算法能夠抵抗線性逼近攻擊.

5.8 選擇IV 攻擊

選擇IV 攻擊是假定攻擊者可以選擇任意IV, 運(yùn)行流密碼, 根據(jù)密鑰流和IV 的性質(zhì)來恢復(fù)密鑰的方法. Grain Family 這種結(jié)構(gòu)天然的對該攻擊具有抵抗力, 這是因?yàn)殡m然IV 是已知的, 但由于在算法初始化階段中, 密鑰會參與線性部分的變化, 這使得在完成初始化操作后, 無法利用線性變化這種方法得知線性結(jié)構(gòu)的內(nèi)部狀態(tài). 事實(shí)上, 屬于Grain Family 的流密碼能夠抵抗選擇IV 攻擊.

5.9 立方攻擊

立方攻擊屬于選擇IV 攻擊, 它的攻擊思想在于將加密系統(tǒng)看作是一個n + m 輸入1 輸出的, 在GF(2) 域上的多變量多項式p. 其中, n 為密鑰的長度, m 為IV 的長度. 隨后通過選擇不同的IV, 以及在該IV 下的1 bit 密鑰流去構(gòu)建密鑰與密鑰流的代數(shù)關(guān)系. 立方攻擊中最為在意的指標(biāo)是d, d 代表p 的維度(degree), 它表示p 中長度最大的項由多少個變量相乘得到. 比如p(x1,x2,x3) = x1x2+x3+x1, 那么此時d = 2. 立方攻擊在d 較小的時候有效, 且攻擊的時間開銷不會小于2d. 對于本文所提出的流密碼算法, 如果使用立方攻擊進(jìn)行分析, 那么首先應(yīng)當(dāng)確定多項式p 的維度d. 由于多項式p 的輸入為密鑰和IV, 輸出為密鑰流, 這意味著p 需要能夠描述初始化階段, 事實(shí)上, 表3 給出了回溯次數(shù)0 < n < 8 下, 維度d 的變化情況. 由此可以看到, 每對Rule30+ 進(jìn)行一次回溯, 都會增加所對應(yīng)多項式的維度. 而我們知道, 算法在初始化階段需要運(yùn)行256 次, 這就意味著需要回溯Rule30+256 次. 這就使得多項式的維度d至少不會小于CA30+ 的長度. 由立方攻擊的時間開銷不會小于2d可知, 使用立方攻擊對該算法進(jìn)行攻擊的時間開銷不會小于2137.

5.10 差錯攻擊

差錯攻擊是一種在算法的運(yùn)行階段, 采用某種物理手段引發(fā)結(jié)構(gòu)中某個比特的值發(fā)生變化, 隨后通過觀察原密鑰流與引入錯誤的密鑰之間的差別, 進(jìn)而推斷出算法內(nèi)部狀態(tài)的攻擊方法. 事實(shí)上, 細(xì)胞自動機(jī)這種結(jié)構(gòu)對差錯攻擊存在著天然的抗性, 當(dāng)細(xì)胞自動機(jī)的細(xì)胞半徑為1 時, 任意一個細(xì)胞的狀態(tài)發(fā)生變化,都會影響到下一個時刻周圍兩個細(xì)胞的狀態(tài)變化. 當(dāng)差錯經(jīng)由擴(kuò)散函數(shù)影響到密鑰流時, 細(xì)胞自動機(jī)已經(jīng)運(yùn)行了多次, 這個時候細(xì)胞自動機(jī)的內(nèi)部狀態(tài)已經(jīng)發(fā)生了很大的變化, 從而使得攻擊者無法根據(jù)密鑰流之間的區(qū)別推斷出算法的內(nèi)部狀態(tài).

6 硬件開銷

本小節(jié)我們主要討論算法的硬件開銷, 我們分別統(tǒng)計了Grain-128, CAR30, 以及本文所提出算法在相同密鑰長度情況下的邏輯門的開銷, 具體如表4 所示. 對于細(xì)胞自動機(jī)而言, 其邏輯門開銷主要取決于其所使用的規(guī)則和長度. 在規(guī)則上, 這主要表現(xiàn)包含的邏輯運(yùn)算操作數(shù)量. 對于Rule30+ 和Rule30 而言, 兩者具有相同的邏輯運(yùn)算數(shù)量, 這意味著在相同邊界條件下和長度下, 兩者具有相同的邏輯門開銷.

表4 邏輯門開銷Table 4 Cost of logic gate

在開銷的量化方式上, 我們與Grain-128 中相同. 即異或運(yùn)算的開銷為2.5, D 觸發(fā)器為8, 與操作與或操作為1. 于是, Rule30(+) 包含一個異或操作和一個或操作, 其開銷為3.5, Rule90 包含1 個異或操作,因而邏輯門開銷為2.5, Rule150 包含2 個異或操作, 因而邏輯門開銷為5. CAR30 中的線性部分是長度為128 bit 的90–150 滿周期細(xì)胞自動機(jī), 由于它沒有說明具體使用的規(guī)則向量, 我們假定其線性部分包含10 個的Rule150, 其余均為Rule90. 可以看到本文提出的算法其硬件開銷位于Grain-128 和CAR30 之間, 且與Grain-128 相比開銷相差不大. 對于CAR30, 其算法包含循環(huán)操作, 并且需要額外的同步信號, 因而其真實(shí)的硬件開銷將更大.

7 結(jié)論

本文提出了一種新的規(guī)則Rule30+, 并基于該規(guī)則提出了一種新的流密碼算法. 本算法的特點(diǎn)在于,首先具備產(chǎn)生隨機(jī)性良好的密鑰流序列的特點(diǎn). 第二, 較同類算法相比具有更小的硬件開銷和更快的密鑰產(chǎn)生速度. 第三, 經(jīng)過簡單調(diào)整, 即增加CA30+ 的長度和b?2中涉及的CA30+ 狀態(tài)數(shù), 算法就可以適配任意長度的密鑰.