SNOW 3G加密算法的BDD攻击

吴泳钢，古天龙，徐周波

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林　541004)



SNOW 3G加密算法的BDD攻击

吴泳钢，古天龙，徐周波

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004)

为了对SNOW 3G加密算法进行安全性分析，提出一种改进的BDD攻击。依据线性反馈移位寄存器的反馈多项式选择特定内部比特流构造第一类OBDD。利用猜测决定攻击的思想，猜测若干有限状态机的内部状态，并寻找其与SNOW 3G加密算法输出的密钥流之间的联系来推测密码器内部比特流，以此构造第二类OBDD。将2类OBDD进行交集操作得到SNOW 3G加密算法的初始密钥。分析结果表明，改进的BDD攻击优于原BDD攻击，对SNOW 3G加密算法的安全性更具威胁。

密码分析；BDD攻击；SNOW 3G加密算法；猜测决定攻击

随着通信技术的日益普及，人们对通信过程的保密性和完整性提出更高的要求。3G网络保留了2G网络的安全性优点，并且提出保证空中接口数据传输保密性和完整性的要求，使数据不被篡改和窃听。LTE系统沿用了第三代移动通信的安全策略，采用SNOW 3G加密算法，它不仅具有强大的抗攻击能力，而且能适应高速率通信。

在3GPP安全体系中，标准化算法包括保密性算法(UEA2)和完整性算法(UIA2)，这2种算法的核心是SNOW 3G加密算法。SNOW 3G加密算法属于流加密算法，即将明文的比特流与密钥生成器生成的密钥流进行异或操作，从而生成所需密文，实现加密。解密时将相同的密钥流与密文再进行一次异或操作，就可得到明文。SNOW 3G加密算法是基于线性反馈移位寄存器(linear feedback shift register，简称LFSR)的密钥流发生器。其主要原理是：由一个16级的线性反馈移位寄存器生成伪随机序列，该序列通过一个32 bit有限状态机进行变换，从而形成用于加密的密钥流。

SNOW 3G加密算法是现今移动通信的主流加密算法，对其安全性的研究一直都是一个热点。对SNOW 3G加密算法进行攻击，可以探究它对外部威胁的抵抗能力，确认它的安全性。文献[1]针对SNOW 3G加密算法进行线性区分攻击，所需的密钥流和计算复杂度皆为2274。文献[2]构造了一个Multiset区分器，并利用此区分器对SNOW 3G加密算法(简化版)进行区分攻击，计算复杂度为28。文献[3]对SNOW 3G加密算法进行了猜测决定攻击，计算复杂度为2320。

BDD攻击是2002年Krause[4]首先提出的，主要用于对基于LFSR密钥流生成器进行安全分析。其主要原理是利用BDD分析优化搜索路径，在图生成的同时排除一些不可能的情况，从而降低攻击所需要的算法复杂度，在蓝牙的E0加密算法、手机GSM网络的A5/1算法、自收缩序列生成器上均取得了良好的攻击效果。鉴于此，利用BDD攻击，同时结合猜测决定攻击算法的思想，对SNOW 3G加密算法进行攻击。相较于原BDD攻击，改进后的BDD攻击大大降低了计算复杂度和所需的密钥流，对SNOW 3G加密算法的安全性更具威胁。

1　相关知识

1.1SNOW 3G加密算法[5]

SNOW 3G加密算法是基于字的流密码加密算法，利用128 bit密钥和128 bit初始化变量，输出一串32 bit数据，用于加密明文流。SNOW 3G加密算法是从SNOW 2.0算法改进而来，能有效保护通信网络中的数据安全。SNOW 3G加密算法原理如图1所示。

图1　SNOW 3G加密算法原理Fig.1　Principle of SNOW 3G encryption algorithm

SNOW 3G加密算法由有限域GF(223)上的16级LFSR和有限状态机(FSM)两部分组成。LFSR由16个单元组成，每个单元包含32 bit数据，共512 bit。在每个时钟t，LFSR输出其内部状态st。LFSR内部状态的反馈多项式为：

(1)

式(1)基于有限域GF(223)上的本原多项式为：

其中：α为有限域GF(28)上的多项式

的一个根；β为在有限域GF(2)上的多项式

x8+x7+x5+x3+1

的一个根。FSM包括R1、R2和R3三个寄存器，大小均为32 bit，用于保存FSM的内部状态。记FSM的输出为ft，密钥发生器的输出为zt，t时刻R1、R2、R3的内部状态分别为R1,t、R2,t、R3,t，则存在输出规则：

zt=ft⊕st=(st+15□+R1,t)⊕R2,t⊕st，

(2)

其中“□+”表示模232整数加。R1、R2和R3的刷新变换规则为：

R1,t+1=(st+5⊕R3,t)□+R2,t，

(3)

R2,t+1=S1(R1,t)，

(4)

R3,t+1=S2(R2,t)，

(5)

其中S1、S2为32×32的S盒变换。

1.2OBDD

有序二叉决策图(ordered binary decision diagrams，简称OBDD)是布尔函数的一种有效图形、数学描述技术。

定义[6]对于从{0,1}n到{0,1}的布尔函数f(x1,x2,…,xn)和给定变量序π，在表示布尔函数族#f(x1,x2,…,xn)的二叉树图(BDD)中，若任一有向路径上的变量x1,x2,…,xn均以变量序π所规定的顺序依次出现，则称该BDD为布尔函数f(x1,x2,…,xn)的OBDD。

OBDD是一个有向无环图，节点分为根节点、终节点和内部节点3类。其中终节点有且仅有2个，用来表示布尔常量的0、1。每个非终节点都有2条输出的分支分别连接到下一节点，即0分支(虚线)和1分支(实线)。在OBDD任何一条路径上，每个变量都依照变量序π所限定的顺序出现一次。布尔函数f(x1,x2,x3)=(x1+x2)x3在变量序π：x1

图2　布尔函数f(x1,x2,x3)=(x1+x2)x3的OBDD表示Fig.2　OBDD for Boolean function f(x1,x2,x3)=(x1+x2)x3

1.3基于BDD的密码分析技术

由于BDD能对所有有序出现的输入变量进行合并，有效地将其简化，并可对所有满足要求的情况进行穷举，在密码分析领域具有较大的作用。BDD攻击通过给定的密钥流z，计算LFSRs的初始状态x。对于一个LFSR密钥流发生器，其生成规则为z=C(L(x))，其中L表示由一个或多个LFSR组成的线性比特流发生器，C:{0,1}n→{0,1}m为非线性压缩函数。非线性压缩函数的作用是将内部的线性比特流L(x)转化为非线性的密钥流z。一般来说，包含n个LFSR的发生器产生内部比特流的规则为L(x)=L0(x),L1(x),…,Lm(x)[7]。LFSR密钥流发生器结构如图3所示。

图3　LFSR密钥流发生器结构Fig.3　Structure of LFSR stream ciphers

从图3可看出，LFSR的初始状态包含在输出的内部线性比特流中，即L(x)的前几位包含LFSR的密钥x。通过给定的密钥流z，求满足z=C(L(x))的密钥x。此问题可等价为寻找一个最小的自由二元决策图 (free binary decision diagram，简称FBDD)来判断密钥x是否满足z=C(L(x))。

BDD攻击的具体步骤如下[8-9]：

1)对于任意的m≥n，用Tm表示一个最小的FBDD。此FBDD根据LFSRs的反馈多项式构造，用来判断内部比特流是否符合LFSR的反馈多项式。

2)对于任意的m≥1，用Qm表示另一个最小的FBDD。此FBDD根据LFSR输出的内部比特流L(x)构造，用来判断C(L(x))是否与密钥流z相符。

3)构造第3个FBDD，用Pm表示。其是Qm和Tm交集操作的结果，也就是Pm=SYNTH(Qm,Tm)，其中SYNTH为BDD的交集操作，m、n分别为BDD变量的个数和密钥x的个数。

BDD攻击伪代码[10]如下：

P←Qn;

form←n+1 tom*do:

P←(P∧Qm∧Tm);

returnz*thatP(z*)=1。

其中：m*为内部比特的长度；z*为LFSR的初始密钥。

2　SNOW 3G加密算法的BDD攻击

2.1攻击条件

在SNOW 3G加密算法中有5个表达式：LFSR的各状态之间的关系，即式(1)；FSM与LFSR之间的关系，即式(2)；SNOW 3G加密算法中的3个32位寄存器R1、R2、R3所包含的状态之间的转化关系，即式(3)、(4)、(5)。

SNOW 3G加密算法的内部状态由FSM的寄存器R1、R2、R3所决定。内部状态经过32 bit32 bit 的S盒变换和LFSR内部状态的混淆，使得FSM的当前状态与下一状态之间的关系变得十分复杂，因此引入猜测决定攻击的思想来应对这一问题。猜测决定攻击基本思想是：分析密码器中的数学原理、内部状态、输出密钥流三者之间的关系，并猜测若干的内部状态作为假设条件，以推导出其他的内部状态，从而得到在当前假设条件下输出的密钥流。该密钥流与已知的密钥流进行比对，可判定假设条件的正误。

BDD攻击是一种状态恢复攻击，即根据输出的密钥流恢复密钥发生器的初始状态。因此，以输出的密钥流作为已知条件，可获取密钥发生器前8个时钟输出的密钥流z0～z7。根据猜测决定攻击的思想，猜测前11个时钟R1的内部状态为R1,0～R1,10，将其作为假设条件。

2.2BDD生成过程

根据BDD攻击的步骤，先生成第一类OBDD，将其表示为T。此OBDD是以LFSR输出的特定内部状态st作为输入，st的选取依据式(1)的规定。若作为输入的st满足式(1)，则在T中代表该组取值的路径指向终节点1，否则，指向终节点0。也就是说，若t时刻st、st+2、st+11、st+16的某组取值满足LFSR的反馈多项式，则在OBDD中，该组取值的路径指向终节点1，否则指向终节点0。不同时刻存在不同的OBDD。

继续构建第2类OBDD，将其表示为Q，它是以LFSR的输出内部状态st为核心构成的。st由32 bit构成，共有232种状态。用OBDD结构保存这32 bit所有可能的组成。为了描述方便，将此OBDD结构称为基础链。当前时刻的基础链所包含的每条路径都连接相应的下一时刻的基础链。因此，可用前7个时钟的基础链s0～s6组成初始Q。

由式(4)可知，从R1的内部状态R1,t可得到t+1时刻R2的内部状态R2,t+1。因此，根据已知假设条件R1,0～R1,10的取值，可求得R2,0～R2,9。同理依据式(5)，从R2的内部状态R2,t可得到t+1时刻R3的内部状态R3,t+1。根据R2,0～R2,9的取值，求得R3,1～R3,9。至此就获得了攻击所需要的所有内部状态。

依据式(3)，从t时刻R2、R3的内部状态R2,t、R3,t与t+1时刻R1的内部状态R1,t+1，可求得t+5时刻LFSR输出的内部状态st+5。因此，由得到的R1、R2、R3内部的状态信息，可求得s7～s14的值，如表1所示。

表1　s7～s14推出过程

同样，根据式(2)，利用已知的密钥流z0～z7和R1、R2、R3内部的状态信息得到s15～s22的值，如表2所示。

表2　s15～s22推出过程

由s0～s6和s7～s22，可构造出完整的Q。对T、Q进行交集操作，最终得到P，即P=SYNTH(Q,T)。此交集的过程将大大简化OBDD，从而剔除不正确的路径，得到唯一一组路径s0～s6，使P的取值为1。验证过程如表3所示。

表3　验证过程

交集过程的简化原理为：选取s0与s1的一种可能情况，根据表3和式(1)，确定s2～s6的值，并判断选取的s0、s1与求解结果间是否存在矛盾，若矛盾，则抛弃该组取值，反之，则保留。步骤1中，已知s16、s11和选取的s0，其中s16是由s1决定的，s11为现有条件下确定的值，则由式(1)可知当前条件下s2的取值。以此类推，从步骤2～5求得现有条件下s3～s6的取值，然后，依据步骤6，求得s16。由式(2)可知，利用s16可推出s1，将其与选取的s1作比较，判断是否矛盾：

1)若矛盾，则表示此s1不是正确的LFSR的初值。

2)若不矛盾，则继续步骤7，判断s0的值是否矛盾。若矛盾，则表示此s0不是正确的LFSR初值；若不矛盾，则说明选取的s0和s1正确，此时OBDD的路径s0～s15就是要求取的LFSR初值。

2.3复杂度分析

本算法的计算复杂度由所合成的OBDD的空间复杂度决定。在整个BDD生成过程的每个阶段，所合成的OBDD被2个条件约束。

1)所有指向终节点1的路径的集合记为H，其与P的关系为：

其中m为OBDD包含的变量数目。假设时钟t>0，则：

2)由于P是T与Q交集操作的结果，可得到另一个约束：

其中|Q|为总节点数。

3　比较分析

根据现有的文献，针对SNOW 3G加密算法的攻击方法主要有线性区分攻击[1]、Multiset碰撞攻击[2]和猜测决定攻击[3]。将本BDD攻击与上述3种方法比较，结果如表4所示。

表4　4种攻击方法的比较

文献[1]和文献[2]的方法主要是构造区分器，并不以恢复线性反馈移位寄存器LFSR的内部状态为目的。BDD攻击是一种状态恢复攻击，因此主要与文献[3]比较。文献[3]的方法的计算复杂度为2320，所需的密钥流为9，本BDD攻击所需要的密钥流为8，计算复杂度为2362，虽然计算复杂度较高，但是利用BDD攻击，可直接得到所需攻击结果，不需要额外的操作。然而在文献[3]中，攻击得到的密钥流与已知的密钥流需要进行对比分析，这部分计算花销在文献[3]中并未提及。本BDD攻击结合了猜测决定攻击的思想，大大优化了Krause的算法，降低了计算复杂度和所需的密钥流。本BDD攻击在利用更少的密钥流的同时，可直接得到所需数据，在实际操作中更有优势。

4　结束语

对SNOW 3G加密算法的安全性进行了分析，以考察其安全性。通过改进的BDD攻击，利用少量的密钥流来获取SNOW 3G加密算法内部LFSR的初始状态。改进后的BDD攻击，结合了猜测决定攻击的思想，大大优化了Krause的算法，降低了计算复杂度。但是，本研究在计算复杂度方面还有提升的空间，主要体现在2个方面：1)寻找更加合适的结构来表示基础链；2)继续发掘FSM前后状态的变化规律。

[1]NYBERG K,WALLéN J.Improved linear distinguishers for SNOW 2.0[C]//Fast Software Encryption.Berlin:Springer Berlin Heidelberg,2006:144-162.

[2]BIRYUKOV A,PRIEMUTH-SCHMID D,ZHANG B.Multiset collision attacks on reduced-round SNOW 3G and SNOW 3G⊕[C]//Applied Cryptography and Network Security.Berlin:Springer Berlin Heidelberg,2010:139-153.

[3]关杰，丁林，刘树凯.SNOW3G与ZUC流密码的猜测决定攻击[J].软件学报，2013(6):1324-1333.

[4]KRAUSE M.BDD-based cryptanalysis of keystream generators[C]//Advances in Cryptology:EUROCRYPT 2002.Berlin:Springer Berlin Heidelberg,2002:222-237.

[5]ETSI/SAGE.Specification of the 3GPP confidentiality and integrity algorithms UEA2&UIA2[OL].(2006-12-18)[2016-3-18].http://cryptome.org/uea2-uia2/uea2-uia2.htm.

[6]古天龙，徐周波.有序二叉决策图及应用[M].北京：科学出版社，2009:22-51.

[7]STEGEMANN D.BDD-based cryptanalysis of the A5/1 keystream generator-experimental results[C]//The State of the Art of Stream Ciphers,2004:1-6.

[8]SHAKED Y,WOOL A.Cryptanalysis of the bluetooth E0 cipher using OBDD’s[C]//Information Security.Berlin:Springer Berlin Heidelberg,2006:187-202.

[10]GHASEMZADEH M,MEINEL C,SHIRMOHAMMADI M,et al.ZDD-based cryptanalysis of E0 keystream generator[C]//Proceedings of 3th International Conference on Mathematical Sciences,2008:1-6.

编辑：张所滨

BDD attack on SNOW 3G encryption algorithm

WU Yonggang, GU Tianlong, XU Zhoubo

(Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China)

In order to analyze the security of SNOW 3G encryption algorithm, an improved BDD attack method is proposed. The feedback polynomial of the linear feedback shift register is used to choose specific internal bit stream, which can construct the first kind of OBDD. Using the idea of guess and determine attack to guess internal state of finite state machine and find the connection between internal state and the keystream of SNOW 3G encryption algorithm for surmising the internal bit stream of cipher, which can construct the second kind of OBDD. The initial key of SNOW 3G encryption algorithm is obtained by the intersection operation of two kinds of OBDD. The analysis results show that the improved algorithm is better than original BDD attack and more threatening to SNOW 3G encryption algorithm.

cryptanalysis; BDD attack; SNOW 3G encryption algorithm; guess and determine attack

2016-03-18

国家自然科学基金(61262030,61572146,61363030)；广西自然科学基金(2015GXNSFAA139285,2014GXNSFAA118354)

古天龙(1964―),男，山西芮城人，教授，博士，研究方向为形式化方法、符号计算。E-mail:cctlgu@guet.edu.cn

TP309

A

1673-808X(2016)03-0199-05

引文格式： 吴泳钢，古天龙，徐周波.SNOW 3G加密算法的BDD攻击[J].桂林电子科技大学学报，2016,36(3):199-203.