基于隨機性測試的SNOW 2.0算法部件分析與改進

姚丹丹 張 筱 王 釗 姚 望 邱望潔 鄭志明②

?

基于隨機性測試的SNOW 2.0算法部件分析與改進

姚丹丹*①張 筱①王 釗①姚 望①邱望潔①鄭志明①②

①(北京航空航天大學數(shù)學、信息與行為教育部重點實驗室 北京 100191)②(北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 北京 100191)

SNOW族算法是目前序列密碼算法設計的一個主流方向。針對SNOW族算法現(xiàn)有的安全漏洞，該文以最具代表性的SNOW 2.0算法為研究對象，采用隨機性測試方法對其多個域上模加、非線性S盒以及線性反饋移位寄存器(LFSR)3個核心部件進行分析，提出基于隨機S盒和高性能LFSR等部件改進的多套改進方案，有效提升SNOW族算法的安全性和實現(xiàn)性能。

序列密碼；SNOW 2.0；隨機性測試；模加；S盒；線性反饋移位寄存器(LFSR)

1 引言

2000年由Patrik Ekdahl等人[1]設計的算法SNOW被宣布為NESSIE計劃的序列密碼候選算法。2002年，針對SNOW存在的弱點其作者提出了改進的算法SNOW 2.0[2]。2005年Berbain等人[3]采用SNOW 2.0的基本設計原理提出了SOSEMANUK。為適應3G通信系統(tǒng)的安全性需求，基于SNOW 2.0的SNOW3G[4]和ZUC[5]被提出，并成為3GPP加密算法的核心部件。以上算法都是SNOW族的算法，由線性反饋移位寄存器(LFSR)和有限狀態(tài)機(FSM)兩部分連接而成，邏輯結構簡潔，同時考慮到了32 bit輸出的高效性及軟、硬件的易實現(xiàn)性，充分利用了計算機資源。因此，以SNOW 2.0為代表的SNOW族算法成為序列密碼設計的一個主流方向。

隨著SNOW族密碼算法的提出和廣泛應用，其安全性成為密碼分析學者研究的熱點。已有研究成果表明，SNOW族算法存在代數(shù)攻擊[6]、線性區(qū)分攻擊[7]、側信道攻擊[8]以及差分錯誤攻擊[9]等。這些攻擊結果表明SNOW族算法的安全性有待提高。目前，提高算法安全性主要是通過密碼攻擊分析找出影響安全性的因素進而對算法提出改進，再對改進的效果進行分析，使得這種改進往往只能針對特定的攻擊方法有效，具有一定的片面性。

算法的密鑰流序列的隨機性是衡量其安全性好壞的重要指標。密碼檢測技術為密碼算法的設計、分析和評估提供客觀的量化指標和技術參數(shù)，目前國際上運用比較廣泛的密碼檢測分析工具是NIST發(fā)布的隨機性檢測SP 800-22標準[10]。通過對算法修改方案的隨機性檢測分析算法部件安全性能，可以從統(tǒng)計學角度科學地反應出算法部件設計的缺陷，避免傳統(tǒng)密碼攻擊分析的片面性，同時可以找出隨機性最好的部件組合。這是更科學、合理而且有效的改進方法，也符合序列密碼的實際應用需求。

本文以SNOW族算法中最具代表性的SNOW 2.0為研究對象，其算法描述參見文獻[2]。兩個域上模加運算和非線性S盒是SNOW 2.0的FSM內(nèi)部的核心部件，保證算法的非線性。LFSR作為SNOW 2.0的驅動部件，主要是產(chǎn)生大周期、高隨機的初始序列。3個部件的綜合使用須保證算法輸出密鑰流具有高隨機性，不易被密碼攻擊手段攻破。因此，這3個部件的選取對算法的隨機性和安全性有著重要的影響，本文將針對這3個部件進行研究并提出修改方案，依據(jù)SP 800-22標準[10]，對修改方案產(chǎn)生的密鑰流序列進行測試并比較各個部件對算法密鑰流隨機性的影響，進一步結合密碼理論分析方法對修改方案進行分析，從而得到偽隨機性更強的序列密碼算法。

2 隨機性測試方法

測試序列的隨機性，實質上是檢驗其是否是真隨機的或與真隨機的差距，假設檢驗是隨機性測試技術的基本理論。本文采用的SP 800-22測試標準[10]包含15項測試，從不同角度檢驗被測序列在統(tǒng)計特性上相對于理想隨機序列的偏離程度。這15項測試分別為單頻數(shù)測試、塊內(nèi)頻數(shù)測試、累計和測試、游程測試、基于塊的最長1游程測試、二值矩陣秩測試、離散傅里葉變換(頻域)測試、非重疊模板匹配測試、重疊模板匹配測試、Maurer’s的通用統(tǒng)計測試、近似熵測試、隨機偏離測試、隨機偏離方差測試、串行測試和線性復雜度測試。下文進行所有算法的測試時，15項測試結果均按以上順序給出。根據(jù)部分測試的要求，下文進行全部測試時輸入的每組測試序列的數(shù)據(jù)的長度是 1000000 bit。15項測試中有7項需要使用參數(shù)，下文中進行的測試均使用默認參數(shù)。

3 模加運算的隨機性測試和分析

3.1 測試方案及數(shù)據(jù)分析

由圖1知，SNOW2.1有1項測試未通過，SNOW2.11有兩項測試未通過，而SNOW 2.0全部通過了測試，SNOW 2.0的隨機性最強，修改模加運算后算法隨機性降低。因此，多個域上模加運算能夠提高算法的隨機性和安全性。

3.2 方案推廣及分析

圖1 SNOW2.0, SNOW2.1和SNOW2.11的通過率

圖2 SOSEMANUK, SOSEMANUK.1和SOSEMANUK.11的通過率

圖3 ZUC, ZUC.1和ZUC.11的通過率

由圖2和圖3知，SOSEMANUK和ZUC各有1項測試未通過，修改方案SOSEMANUK.1也有1項測試未通過，而剩下3個修改方案ZUC.1, SOSEMANUK.11和ZUC.11均有兩項測試未通過，故使用兩種模加混合運算的算法的隨機性是最強的。上述對SNOW 2.0, SOSEMANUK和ZUC的修改和測試可以充分說明采用多種模加混合運算能夠增強序列密碼算法的隨機性。

3.3 模加運算理論分析

以上測試分析表明多個域上模加運算能提高算法隨機性，使用單一域上模加運算密鑰流隨機性降低。這是由于多個域上模加運算能增強FSM的非線性，而只使用一個域上模加運算，F(xiàn)SM內(nèi)部的非線性降低，輸出密鑰流就會不隨機，可能遭受密碼攻擊，算法安全性隨之降低。下文以SNOW2.0算法變?yōu)镾NOW2.1算法為例來說明。

以上從理論分析角度證明了SNOW 2.0采用多種模加運算能夠使其避免遭到密碼攻擊，增強了算法的安全性，這與上述通過隨機性測試得到的多個域上模加混合運算能夠增強算法隨機性和安全性的結論相符。

4 S盒的隨機性測試和分析

S盒是密碼算法中重要的非線性部件，主要提供算法所必須的混淆作用，它的密碼強度將直接影響整個算法的安全強度。SNOW 2.0的S盒由逆變換和仿射變換復合而成，具有一定的代數(shù)結構，容易遭受代數(shù)攻擊[6]、區(qū)分攻擊[7]等，因此需要找到性能更好的S盒來提高算法的安全性。

4.1 測試方案及數(shù)據(jù)分析

4.2 方案推廣及分析

為進一步分析隨機S盒增強算法隨機性的幅度，將上述采用隨機S盒的方案SNOW2S1和SNOW2S2的FSM中的多種模加運算改為會使算法非線性減弱的只有模2加運算，修改后的方案分別記為SNOW2S1.1和SNOW2S2.1。若隨機S盒的使用能夠彌補模加運算帶來的非線性減弱，使得算法仍具有很高的隨機性，則可充分說明隨機S盒隨機性能優(yōu)越，能夠顯著增強算法隨機性和安全性。

由圖5知，SNOW2S2.1和SNOW2.1均有1項測試未通過，而SNOW2S1.1通過了全部測試，這表明采用隨機S盒S1的 SNOW 2.0的修改方案比SNOW 2.0的算法隨機性高，隨機S盒的安全性能優(yōu)于SNOW 2.0的S盒。

由圖6知，只有SNOW2S1.1通過了全部測試，剩余4個修改方案都有1項測試未通過。因此，隨機S盒S1對算法隨機性的增強效果是5個S盒中最好的。

4.3 S盒代數(shù)結構分析

以上從S盒代數(shù)結構分析，進一步映證了隨機S盒是所選S盒中隨機性最好的，且比SNOW 2.0的S盒的隨機性好，能夠抵抗代數(shù)攻擊，具有良好的安全性?？捎?個S盒中隨機性最好的隨機S盒S1修改SNOW 2.0的S盒得到一個隨機性和安全性更好的序列密碼算法。

5 LFSR的隨機性測試和分析

序列密碼算法的驅動部件的設計是算法設計的重要環(huán)節(jié)，驅動部件的主要作用是產(chǎn)生極大周期和良好統(tǒng)計特性的初始序列，設計時應兼顧實現(xiàn)效率和資源消耗等優(yōu)勢。SNOW 2.0采用基于字的LFSR作為驅動部件，滿足現(xiàn)代CPU基于字的特點，實現(xiàn)效率高。為使LFSR產(chǎn)生序列的周期達到最大，LFSR反饋多項式應為本原多項式。LFSR采用不同的反饋多項式會給算法的隨機性和安全性帶來影響，SNOW 2.0相比于SNOW1.0的一個顯著改進就是更改了反饋多項式。

圖4 SNOW2S1, SNOW2S2, SNOW2SS SNOW2SC1和SNOW2SC4的通過率

圖5 SNOW2S1.1, SNOW2S2.1和SNOW2.1的通過率SNOW2SC1.1和SNOW2SC4.1的通過率

圖6 SNOW2S1.1, SNOW2S2.1, SNOW2SS.1,

5.1 測試方案及數(shù)據(jù)分析

5.2 方案推廣及分析

由圖8知，SNOW2SBT32.1和SNOW2.1算法均有1項測試未通過，而SNOW2HHZ5.1算法通過了全部測試，表明本原多項式HHZ5比SNOW 2.0的反饋多項式隨機性好，也是文中給出的7個多項式中隨機性最好的一個，可以作為SNOW 2.0算法LFSR的改進，提高算法的安全性能。

值得指出的是，由HHZ-5的構造方式可知，在編程實現(xiàn)上，LFSR只有與和移位操作，大大節(jié)省了SNOW 2.0的LFSR中的復合域運算或查表操作的時間和資源占用，能夠有力提高算法的整體性能。

6 結束語

本文面向SNOW族算法，提出一種利用序列密碼隨機性檢測提升密碼算法安全性的實驗方法。以典型的SNOW 2.0算法為實驗對象，對其多個域上模加、非線性S盒以及LFSR等核心部件提出改進方案，以NIST的隨機性檢測標準SP 800-22為實驗手段，通過大量數(shù)值實驗和理論分析，提出提升算法安全性的最優(yōu)方案。通過對多種模加方案隨機性測試的分析和比較，發(fā)現(xiàn)了模加混合運算的優(yōu)越性，并通過密碼分析驗證了該類設計對安全性的提升價值；通過對多種S盒改進方案的隨機性檢測和理論分析，提出通過更換隨機S盒提升SNOW 2.0 安全性的實質性方案；通過LFSR部件的隨機性檢測和篩選，提出隨機性能大幅提升，且實現(xiàn)速度快、資源占用少的算法改進方案。本文提出的基于隨機性測試的SNOW族算法改進方法，揭示了密碼部件、隨機性和算法安全性的客觀關系，對SNOW 2.0算法的性能提升和SNOW族算法的后續(xù)設計有重要意義。

圖7 SNOW2HHZ1-SNOW2HHZ5, SNOW2SBT32和SNOWSBR128的通過率

圖8 SNOW2HHZ5.1, SNOW2SBT32.1和SNOW2.1的通過率

[2] Ekdahl P and Johansson T. A new version of the stream cipher SNOW[C]. Selected Areas in Cryptography, Springer Berlin Heidelberg, 2003: 47-61.

[3] Berbain C, Billet O, Canteaut a,.. New Stream Cipher Designs: Sosemanuk, A Fast Software-oriented Stream Cipher. [M]. Berlin: Springer Berlin Heidelberg, 2008: 98-118.

[4] ETSI/SAGE. Specification of the 3GPP confidentiality and integrity algorithms UEA2 & UIA2. Document 2: SNOW 3G specification[S]. 2005.

[5] Orhanou G, El Hajji S, Lakbabi A,.. Analytical evaluation of the stream cipher ZUC[C]. 2012 International Conference on Multimedia Computing and Systems (ICMCS), IEEE, Tangier, Morocco, 2012: 927-930.

[7] Nyberg K and Wallén J. Improved linear distinguishers for SNOW 2.0[C]. Fast Software Encryption. Springer Berlin Heidelberg, 2006: 144-162.

[8] Barenghi A and Trichina E. Fault Analysis in Cryptography: Fault Attacks on Stream Ciphers[M]. Berlin: Springer Berlin Heidelberg, 2012: 239-255.

[10] Rukhin A, Soto J, Nechvatal J,.. A statistical test suite for random and pseudorandom number generators for cryptographic applications[OL]. http://www.nist.gov. 2011, 10.

[11] Daemen Joan and Rijmen Vincent: AES proposal: rijndael; the latest revised version of the proposalis available on the internet[OL]. http://csrc.nist.gov/encryption/aes/rijndael/ Rijndael. pdf. 2011. 3.

[13] Xiong K J and Hu Z H. Cryptographic properties and quadratic equations of S-Box in SMS4[J]., 2012, 6/7: 54-57.

[14] Aoki K, Ichikawa T, Kanda M,.. Camellia: a 128-bit block cipher suitable for multiple platforms[OL]. http://info. isl.ntt.co.jp/camellia. 2012, 9.

[15] Zeng G, Han W, and He K. High efficiency feedback shift register: sigma-LFSR[J]., 2007, 2007: 114.

[16] Hawkes P and Rose G. Primitive specification and supporting documentation for SOBER-t32 submission to NESSIE[C]. Proceedings of the First Open NESSIE Workshop,Heverlee, Belgium, 2000: 13-14.

[17] Hawkes P and Rose G G. Primitive specification for SOBER- 128[J]., 2003, 2003: 81.

姚丹丹： 女，1990年生，碩士生，研究方向為密碼學與信息安全.

張 筱： 女，1984年生，博士，講師，研究方向為密碼學.

鄭志明： 男，1953年生，博士，教授，研究方向為信息安全、實計算與動力系統(tǒng)以及計算復雜性等.

Analysis and Improvement of the Components of SNOW 2.0 Based on Statistical Tests

Yao Dan-dan①Zhang Xiao①Wang Zhao①Yao Wang①Q(mào)iu Wang-jie①Zheng Zhi-ming①②

①(,,,100191,)②(,,100191,)

The SNOW family is a main trend of the design of the stream cipher. Because of the security vulnerabilities of the SNOW family, this paper selects SNOW 2.0 algorithm which is the most representative of the family as a research object. Three core components of SNOW 2.0 that are mold addition on more than one domain, nonlinear S-box and Linear Feedback Shift Register (LFSR) are analyzed using statistical tests. Several improved algorithms are proposed based on improving random S-box and improving high performance LFSR. The result enhances effectively the security and performance of SNOW family.

Stream cipher; SNOW 2.0; Statistical test; Mold addition; S box; Linear Feedback Shift Register (LFSR)

TN918.1

A

1009-5896(2014)01-0082-06

10.3724/SP.J.1146.2013.00283

2013-03-07收到，2013-07-27改回

國家863計劃項目(2011AA70110016)資助課題

姚丹丹 yd0519@yeah.net