基于随机性测试的SNOW 2.0算法部件分析与改进

姚丹丹 张 筱 王 钊 姚 望 邱望洁 郑志明②



基于随机性测试的SNOW 2.0算法部件分析与改进

姚丹丹*①张 筱①王 钊①姚 望①邱望洁①郑志明①②

①(北京航空航天大学数学、信息与行为教育部重点实验室 北京 100191)②(北京航空航天大学软件开发环境国家重点实验室 北京 100191)

SNOW族算法是目前序列密码算法设计的一个主流方向。针对SNOW族算法现有的安全漏洞，该文以最具代表性的SNOW 2.0算法为研究对象，采用随机性测试方法对其多个域上模加、非线性S盒以及线性反馈移位寄存器(LFSR)3个核心部件进行分析，提出基于随机S盒和高性能LFSR等部件改进的多套改进方案，有效提升SNOW族算法的安全性和实现性能。

序列密码；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通信系统的安全性需求，基于SNOW 2.0的SNOW3G[4]和ZUC[5]被提出，并成为3GPP加密算法的核心部件。以上算法都是SNOW族的算法，由线性反馈移位寄存器(LFSR)和有限状态机(FSM)两部分连接而成，逻辑结构简洁，同时考虑到了32 bit输出的高效性及软、硬件的易实现性，充分利用了计算机资源。因此，以SNOW 2.0为代表的SNOW族算法成为序列密码设计的一个主流方向。

随着SNOW族密码算法的提出和广泛应用，其安全性成为密码分析学者研究的热点。已有研究成果表明，SNOW族算法存在代数攻击[6]、线性区分攻击[7]、侧信道攻击[8]以及差分错误攻击[9]等。这些攻击结果表明SNOW族算法的安全性有待提高。目前，提高算法安全性主要是通过密码攻击分析找出影响安全性的因素进而对算法提出改进，再对改进的效果进行分析，使得这种改进往往只能针对特定的攻击方法有效，具有一定的片面性。

算法的密钥流序列的随机性是衡量其安全性好坏的重要指标。密码检测技术为密码算法的设计、分析和评估提供客观的量化指标和技术参数，目前国际上运用比较广泛的密码检测分析工具是NIST发布的随机性检测SP 800-22标准[10]。通过对算法修改方案的随机性检测分析算法部件安全性能，可以从统计学角度科学地反应出算法部件设计的缺陷，避免传统密码攻击分析的片面性，同时可以找出随机性最好的部件组合。这是更科学、合理而且有效的改进方法，也符合序列密码的实际应用需求。

本文以SNOW族算法中最具代表性的SNOW 2.0为研究对象，其算法描述参见文献[2]。两个域上模加运算和非线性S盒是SNOW 2.0的FSM内部的核心部件，保证算法的非线性。LFSR作为SNOW 2.0的驱动部件，主要是产生大周期、高随机的初始序列。3个部件的综合使用须保证算法输出密钥流具有高随机性，不易被密码攻击手段攻破。因此，这3个部件的选取对算法的随机性和安全性有着重要的影响，本文将针对这3个部件进行研究并提出修改方案，依据SP 800-22标准[10]，对修改方案产生的密钥流序列进行测试并比较各个部件对算法密钥流随机性的影响，进一步结合密码理论分析方法对修改方案进行分析，从而得到伪随机性更强的序列密码算法。

2 随机性测试方法

测试序列的随机性，实质上是检验其是否是真随机的或与真随机的差距，假设检验是随机性测试技术的基本理论。本文采用的SP 800-22测试标准[10]包含15项测试，从不同角度检验被测序列在统计特性上相对于理想随机序列的偏离程度。这15项测试分别为单频数测试、块内频数测试、累计和测试、游程测试、基于块的最长1游程测试、二值矩阵秩测试、离散傅里叶变换(频域)测试、非重叠模板匹配测试、重叠模板匹配测试、Maurer’s的通用统计测试、近似熵测试、随机偏离测试、随机偏离方差测试、串行测试和线性复杂度测试。下文进行所有算法的测试时，15项测试结果均按以上顺序给出。根据部分测试的要求，下文进行全部测试时输入的每组测试序列的数据的长度是 1000000 bit。15项测试中有7项需要使用参数，下文中进行的测试均使用默认参数。

3 模加运算的随机性测试和分析

3.1 测试方案及数据分析

由图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的非线性，而只使用一个域上模加运算，FSM内部的非线性降低，输出密钥流就会不随机，可能遭受密码攻击，算法安全性随之降低。下文以SNOW2.0算法变为SNOW2.1算法为例来说明。

以上从理论分析角度证明了SNOW 2.0采用多种模加运算能够使其避免遭到密码攻击，增强了算法的安全性，这与上述通过随机性测试得到的多个域上模加混合运算能够增强算法随机性和安全性的结论相符。

4 S盒的随机性测试和分析

S盒是密码算法中重要的非线性部件，主要提供算法所必须的混淆作用，它的密码强度将直接影响整个算法的安全强度。SNOW 2.0的S盒由逆变换和仿射变换复合而成，具有一定的代数结构，容易遭受代数攻击[6]、区分攻击[7]等，因此需要找到性能更好的S盒来提高算法的安全性。

4.1 测试方案及数据分析

4.2 方案推广及分析

为进一步分析随机S盒增强算法随机性的幅度，将上述采用随机S盒的方案SNOW2S1和SNOW2S2的FSM中的多种模加运算改为会使算法非线性减弱的只有模2加运算，修改后的方案分别记为SNOW2S1.1和SNOW2S2.1。若随机S盒的使用能够弥补模加运算带来的非线性减弱，使得算法仍具有很高的随机性，则可充分说明随机S盒随机性能优越，能够显著增强算法随机性和安全性。

由图5知，SNOW2S2.1和SNOW2.1均有1项测试未通过，而SNOW2S1.1通过了全部测试，这表明采用随机S盒S1的 SNOW 2.0的修改方案比SNOW 2.0的算法随机性高，随机S盒的安全性能优于SNOW 2.0的S盒。

由图6知，只有SNOW2S1.1通过了全部测试，剩余4个修改方案都有1项测试未通过。因此，随机S盒S1对算法随机性的增强效果是5个S盒中最好的。

4.3 S盒代数结构分析

以上从S盒代数结构分析，进一步映证了随机S盒是所选S盒中随机性最好的，且比SNOW 2.0的S盒的随机性好，能够抵抗代数攻击，具有良好的安全性。可用5个S盒中随机性最好的随机S盒S1修改SNOW 2.0的S盒得到一个随机性和安全性更好的序列密码算法。

5 LFSR的随机性测试和分析

序列密码算法的驱动部件的设计是算法设计的重要环节，驱动部件的主要作用是产生极大周期和良好统计特性的初始序列，设计时应兼顾实现效率和资源消耗等优势。SNOW 2.0采用基于字的LFSR作为驱动部件，满足现代CPU基于字的特点，实现效率高。为使LFSR产生序列的周期达到最大，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 测试方案及数据分析

5.2 方案推广及分析

由图8知，SNOW2SBT32.1和SNOW2.1算法均有1项测试未通过，而SNOW2HHZ5.1算法通过了全部测试，表明本原多项式HHZ5比SNOW 2.0的反馈多项式随机性好，也是文中给出的7个多项式中随机性最好的一个，可以作为SNOW 2.0算法LFSR的改进，提高算法的安全性能。

值得指出的是，由HHZ-5的构造方式可知，在编程实现上，LFSR只有与和移位操作，大大节省了SNOW 2.0的LFSR中的复合域运算或查表操作的时间和资源占用，能够有力提高算法的整体性能。

6 结束语

本文面向SNOW族算法，提出一种利用序列密码随机性检测提升密码算法安全性的实验方法。以典型的SNOW 2.0算法为实验对象，对其多个域上模加、非线性S盒以及LFSR等核心部件提出改进方案，以NIST的随机性检测标准SP 800-22为实验手段，通过大量数值实验和理论分析，提出提升算法安全性的最优方案。通过对多种模加方案随机性测试的分析和比较，发现了模加混合运算的优越性，并通过密码分析验证了该类设计对安全性的提升价值；通过对多种S盒改进方案的随机性检测和理论分析，提出通过更换随机S盒提升SNOW 2.0 安全性的实质性方案；通过LFSR部件的随机性检测和筛选，提出随机性能大幅提升，且实现速度快、资源占用少的算法改进方案。本文提出的基于随机性测试的SNOW族算法改进方法，揭示了密码部件、随机性和算法安全性的客观关系，对SNOW 2.0算法的性能提升和SNOW族算法的后续设计有重要意义。

图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年生，博士，教授，研究方向为信息安全、实计算与动力系统以及计算复杂性等.

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

Yao Dan-dan①Zhang Xiao①Wang Zhao①Yao Wang①Qiu 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