N-CDMA安全架构抗攻击性研究与改进＊

陈德宏 刘晓东 刘 梅

（安徽工业大学电气与信息工程学院，马鞍山，243032）

引 言

当今巨大的社会需求推动着移动通信迅猛发展。由于移动通信特有的无线属性，使信号更容易被第三方在空中截获，因而移动通信的信息安全问题越来越受到关注。深入研究移动通信系统的安全架构是从第二代移动通信系统（2G）开始的。作为2G技术代表之一，IS-95是一种基于窄带码分多址（Narrowband code division multiple access，N-CDMA）技术的北美数字蜂窝标准［1］，也是CDMA2000标准的技术基础。

在N-CDMA系统中，用于数字话音扰乱的密钥序列是由42位的长码掩码和一个42级的线性反馈寄存器共同作用产生的长周期伪随机m序列。破译者要想还原明文信息需要知道密钥序列的初始相位，不同用户的42位掩码决定密钥序列不同的初始相位。对于某个确定的手机号码，它有唯一的用户私人掩码，这个掩码并不通过无线信道传送，而只被用户的SIM卡与移动交换中心（Mobile switching center，MSC）共享存储［2］。在不知道用户42位私人掩码的情况下，破译者不得不详尽尝试42位私人掩码的各种可能。采用穷举的方法理论上是可行的，搜索42位私人掩码的最大复杂度为O（242），需要消耗巨量的时间，在实际破译中是没有意义的。因此，业内普遍认为N-CDMA系统提供了一种近乎完美的无线移动数字话音安全解决方案［3］。

一些研究表明，针对某些敌意的安全攻击，N-CDMA系统可能是脆弱的［4，5］。利用信道编码过程中卷积编码和码元重复导致的信息冗余度，文献［4］提出一种唯密文攻击N-CDMA加密话音安全的方法。用矩阵递推方法获取密文与密钥初始相位的之间关系表达式，并通过计算一系列线性等式能够求解密钥序列的初始相位。可是，这种方法也存在它的缺陷。首先，破译者需要截获不少于42帧时间达840 ms密文数据，其次，巨大计算量和算法复杂度也限制了它的实时破译效果，除此之外，虽然密钥序列可以通过求解的初始状态和一个等效的长码产生器产生，但是，用户的私人掩码并没有得到，每次为了从截获的密文中还原明文信息，破译者不得不重新求解密钥序列的初始相位。

本文通过对N-CDMA系统的前向业务信道结构的详细分析，发现在低速率帧时，块交织器会导致帧内明文周期反复。利用密钥序列是m序列以及明文数据周期反复的特性，采用一种新的唯密文攻击法来讨论N-CDMA系统的话音安全性。这种方法只需要20ms一个密文帧数据，就可以恢复出明文帧。为了彻底破译N-CDMA系统的安全架构，基于密钥序列与长码产生器状态之间的线性关系，提出了一种求解私人掩码的方法。

1 前向业务信道分析

N-CDMA信道包括控制信道和业务信道两类。其中控制信道传送信令信息，而业务信道传送数字压缩语音。业务信道又分为前向业务信道和反向业务信道。由于前向业务信道中采用Walsh码作为扩频码对信息进行扩频传输，与反向业务信道相比，破译者更容易从前向业务信道截取密文信息。图1是CDMA前向业务信道基带信号编码结构框图。

图1 前向业务信道基带信号编码结构Fig.1 Baseband signal encoding of forward traffic channel

图1中基站对语音压缩编码构成每帧20ms的数据流，为了提高容量和减少同道干扰，在N-CDMA中采用变速率语音编码器。速率分别为8.6，4.0，2.0和0.8kbps，也被称为速率1，1／2，1／4和1／8四种速率帧，对应每种速率，20ms信息帧比特为172／80／40／16比特。不同的帧速率取决于背景噪音的功率，在通话时数据以较高的速率传送，而停顿时选择较低速率。帧质量指示对8.6kbps和4.0kbps数据帧进行循环冗余度编码，每帧分别增加12比特和8比特用于帧质量指示。编码器尾比特的作用是使每帧数据卷积编码时编码器末尾状态复位至“0”，这样，4种速率帧到达卷积编码器输入端，速率分别为9.6，4.8，2.4和1.2kbps，再经过1／2卷积编码器，输出时速率分为19.2，9.6，4.8和2.4kbps。为了统一交织器的输入速率，4种数率帧要先进行符号重复，以保证交织符号率均为19.2ksps，不同速率的帧符号重复的次数也不相同。这4种速率在交织之前均变为19.2ksps的符号速率，即每20ms帧有384个符号。块交织的作用就是将突发性误码分散开来，便于卷积纠错。

块交织具体操作：

（1）对每帧码元重复后的384个符号，按行写入一个6×64输入矩阵。表1以前向业务速率1／8帧为例，交织器输入矩阵数据排列示意。表中Cn表示矩阵中符号的列地址为n，Rn表示行地址为n。阵列中的数字表示输入交织器符号在码元重复之前的序号，由于码元重复，表中同一序号连续出现8次。

（2）将输入矩阵的每行数据按位翻转地址交织打乱，送入输出矩阵并按列输出，见表2。所谓位翻转地址，即若交织前列二进制地址为：X1X2X3X4X5X6，则交织后列地址为：X6X5X4X3X2X1。

表1 速率1／8帧交织器输入矩阵数据排列示意Table 1 Interleaver input of rate 1／8

表2 速率1／8帧交织器输出矩阵数据排列示意Table 2 Interleaver output of rate 1／8

下面分析地址位翻转交织后，交织前连续出现的同一序号的分布特性。表3给出了除速率1之外的3种速率帧在位翻转前后相邻重复符号的变化规律。表3最后一列为一帧内连续出现的重复符号在位翻转后分布的位置间隔。

如表3所示，对于速率1／2的数据帧中的任意两个相邻的重复符号，其位比特翻转后列地址的唯一区别是列地址的最高位，而低5位（X5X4X3X2X1）是相同的，故地址的位置间隔是一个固定值32。对于速率1／4的数据帧中的任意4个相邻的重复符号，位翻转后列地址的前2位是不同的，而低4位（X4X3X2X1）是相同的，相同的符号其地址的位置间隔是定值16。同理，对于速率1／8的数据帧中的任意8个相邻的重复符号，位比特翻转后列地址前3位是不同的，而低3位（X3X2X1）是相同的，其地址的位置间隔是定值为8。因此，对于速率为1／2，1／4和1／8的数据帧，其交织输出矩阵中的每一行分别以32，16和8为周期排列。当6×64的交织矩阵按列输出后，每个数据帧中的384个符号分别变成以192（32×6），96（16×6）和48（8×6）为周期重复的数据流。表2中每间隔8列出现序号相同码元，显示了速率1／8时，数据帧呈现48反复的周期特征。

数据加扰的过程见图1所示。长码产生器以1.228 8Mcps速率产生长码序列，通过一个64分频器得到一个速率为19.2ksps密钥序列，密钥序列与交织后的明文模2加产生密文。图2是长码产生器的结构。

表3 3种速率帧位翻转交织后重复符号的位置关系Table 3 Position relations of repeating symbols of rate 1／2，1／4and 1／8

图2 长码产生器结构图Fig.2 Long code generator

图2可分为上下两部分，上半部分为一个按多反馈移位寄存器（Multi-return shift regiter generator，MSRG）结构和式（1）为特征多项式的42级m序列产生器。

下半部分为42级移存器状态输出与用户掩码相与再模2加产生长码序列。令M＝［m1，m2，…，m42］表示用户私人掩码，SI＝［si（1），si（2），…，si（42）］表示第i时刻线性反馈移位寄存器（Linear feedback shift registers，LFSR）的状态，则第i时刻长码输出di可以表示为

由于式（1）是一个本原多项式，因此LFSR各级输出都是同一平移等价m序列，根据m序列的线性组合特性，得到的长码也是同一平移等价m序列。由于不同移动用户的42位用户掩码是不同的，决定了各个移动用户长码产生器输出的长码序列在同一时刻具有不同的相位。长码产生器速率为1.228 8 Mcps，而要加密的明文信息的速率为19.2ksps。因此，用于加密的密钥序列是通过长码序列64分频得到的。第i时刻密钥码元ki可表示为

根据m序列的抽样特性可知，密钥序列与长码序列是同一平移等价m序列。结论：在序列是同一个m序列，唯一的区别是它们的相位是不同的且是由用户私人掩码决定的，N-CDMA安全保密的核心是用户42位私人掩码的安全。

2 一种有效的唯密文攻击方法

在图1中，密文是由明文信息和密钥序列模2加产生的，设第i时刻的明文为pi，密文为ci，则有

对于N-CDMA，密钥序列是一个m序列，并且产生该m序列的特征多项式是已知的。虽然破译者不知道用户的私人掩码，但是，只要能知道密钥序列的42比特的初始相位，就可以通过已知的特征多项式，产生后续的密钥序列，进而恢复用户的明文信息。一种有效的唯密文攻击方法就是消除明文的影响，试图从密文中得到密钥的初始相位。攻击的突破口就是选择具有特殊特征明文底码的密文作为攻击的素材。由第1节可知，对于速率1／2，1／4，1／8的数据帧，在块交织后每帧码元具有周期反复现象。对于1／2帧192码元周期反复一次，对于1／4帧有96码元周期反复3次，对于1／4帧有48码元周期反复7次，因此，可以认为对于这3种速率帧每帧384个码元均是192个周期反复一次发送。则有

由式（4，5），可得

根据m序列的移位相加特性：平移等价m序列的模2加，得到的序列仍然是平移等价m序列［6］，即

令r＝192，由式（6，7）转换为

从式（8）可知：利用密文帧前192码元与后192码元之间模2加，可以抵消明文的影响，可得到i时刻密文帧的密钥序列的平移了j个相位的等价m序列。如果知道了j，就可以利用ki＋j序列反推出该帧的密钥序列ki。因此，问题的关键是如何求出相移j。对于某个特定特征多项式产生的m序列，式（8）中的r和j存在固定一一对应关系且与初始相位i无关。令i＝0，则由式（8）得

密钥序列可以式（1）为特征多项式，用MSRG结构的移位寄存器产生器产生，也可由式（1）的对偶多项式，用简单移位寄存器（Simple shift register generator，SSRG）结构的移位寄存器产生器产生［7，8］。设第i时刻SSRG结构的移存器的输出码元为ki，则ki-41，ki-40，…，ki-1，ki是移存器此刻的状态。求解j的具体步骤如下：

步骤1：设计一个SSRG结构的m序列产生器，其特征多项式为式（1）的对偶多项式。以任意42位码元k-41，k-40，…，k-1，k0作为第0时刻移存器的初始状态，由初始状态和特征多项式通过简单计算可以得到第192时刻的移存器状态k151，k152，…，k191，k192。

步骤2：根据式（9），计算第j时刻，SSRG结构移存器的状态：kj-41，kj-40，…，kj-1，kj。

步骤3：计算SSRG结构的m序列产生器由状态k-41，k-40，…，k-1，k0到状态kj-41，kj-40，…，kj-1，kj之间的状态转移次数，即j的值。需要指出的是：在后续求解密钥序列初始状态的工作中，实际需要计算的是由kj-41，kj-40，…，kj-1，kj到k-41，k-40，…，k-1，k0的状态转移次数（记为j′）。由于该移存器的状态是以242-1周期构成状态转移圈，因此，j′＝242-1-j。

42级m序列的周期长达242-1，若编写软件用微型计算机在一个周期内计算两个状态转移的次数，可能需要数百小时。因而，基于FPGA设计了一个数字逻辑电路硬件电路，用于快速求解j′。这个数字逻辑电路工作主频为150MHz，内部包括一个SSRG结构的m序列产生器并能记录移存器的任意两种状态的转移次数。利用此高速硬件逻辑电路花费约90m求出j′值，j′值为28 483 522 265。

下面提出一种针对N-CDMA的唯密文攻击方法：

（1）破译者从前向业务信道截获无线电波，解调并用沃尔什码解扩频接收的信号，得到密文帧数据。设已知一个密文帧的384个码元：ci-41，ci-40，…，ci-1，ci，…，ci＋342。

（2）用密文帧前192位码元ci-41，ci-40，…，ci-1，ci，…，ci＋150与后192码元ci＋151，ci＋152，…，ci＋342模2加得到192个新码元ki＋j-41，ki＋j-40，…，ki＋j-1，ki＋j，…，ki＋j＋150。

（3）根据 Berlekamp-Massey算法［9］求解192个新码元ki＋j-41，ki＋j-40，…，ki＋j-1，ki＋j，…，ki＋j＋150的特征多项式。若得到的特征多项式不是式（1）的对偶多项式，则说明截获的素材密文帧是速率为1即底码明文不具备192周期反复特性，返回到步骤（1）重新选取一个新的密文帧，直到求解出的特征多项式为式（1）的对偶多项式。

（4）取42个码元ki＋j-41，ki＋j-40，…，ki＋j-1，ki＋j做为 SSRG 结构的m序列产生器的初始状态，以式（1）的对偶多项式为特征多项式，使该序列产生器状态转移284 835 222 265次得到一个新的移存器状态ki-41，ki-40，…，ki-1，ki。这个状态就是该密文帧的密钥初始状态。这一步的状态转移仍然可以采用FPGA硬件电路进行快速求解。

（5）利用求出密钥序列的初始状态ki-41，ki-40，…，ki-1，ki和设计的以式（1）的对偶多项式为特征多项式的SSRG结构m序列产生器，密钥序列可以等效重构ki-41，ki-40，…，ki-1，ki，…，ki＋342…。将重构的密钥序列与截获的密文帧模2加，即可破译出明文信息。

3 用户私人掩码的破解

第2节提出的唯密文攻击方法由于不知用户私人掩码，对于每次截获的密文需要花费一定时间重新求解等效密钥序列的初始相位，因此，它并不是一个实时破译系统。等效密钥序列的初始相位是由固化在用户移动电话的SIM卡的用户私人掩码唯一决定的，因此，只有彻底破解用户私人掩码，才能完全实时还原用户的加密信息。在文献［10］中，提出一种利用移存器的状态和长码密钥之间的线性关系，通过2元域的方程组求解用户掩码的方法。

从式（2）和（3）可知

式（10）也可以写成向量直积形式

式中：（m1，m2，m3，…，m42）表示用户42位私人掩码，ki表示第i时刻的密钥码元，向量S64i表示第64i时刻长码产生器的42位状态。为了求解42私人掩码，取42个时刻的密钥码元，根据式（11），可以列出一个42元一次方程组

在N-CDMA系统的同步信道总是不断地广播系统特定时刻的长码产生器的状态［11］，因此，破译者可以设计一个长码产生器与基站的长码产生器的状态严格同步。换句话说，破译者在从密文中求解出42位密钥码元的同时，可以已知长码产生器对应时刻的状态信息。

用增广矩阵法解这个方程组，用AX＝b表示等式（12），若矩阵A是可逆的，则AX＝b的增广矩阵（A，b）可通过行变换转换成（E，A-1b）形式，这里E是一个单位阵，A-1b就是方程组的解

注意这里的行变换是在伽罗华域GF（2）做模2加变换。式（13）右边矩阵最后一列即求解出的用户私人掩码。

4 N-CDMA安全架构的改进

以上的分析表明，针对敌意的安全攻击，N-CDMA给用户提供的话音保密非常脆弱。导致系统安全脆弱的原因，不是长码产生器的复杂度不够，而是长码产生器与前向业务信道之间不匹配造成。在图1中，信息被加密是在信道编码之后，而卷积编码、码元重复和块交织会导致明文信息出现冗余度和周期反复。已知的唯密文攻击方法均是利用N-CDMA系统的明文存在冗余度这个缺陷进行攻击的。文献［3，12，13］讨论了CDMA系统的几种新的加密方法。本文在不改变IS-95标准长码产生器结构的基础上，提出一种既加强了系统的安全性又兼顾了系统的兼容与可实施性的改进N-CDMA系统安全架构，见图3。在图3中，为了抵御针对明文冗余度的唯密文攻击，明文信息在信道编码之前被长码序列扰乱加密，这样，就很好地消除了明文信息帧的冗余及周期反复特性。由于卷积编码之前，信息帧有4种速率分别为：9.6，4.8，2.4，1.2kbps，因此，19.2kbps长码需要经过四次二分频与信息帧适配。在加扰之前进行加尾比特，目的是使4种信息帧的速率呈倍数关系。由于加扰后每帧尾比特不再为0，需要对每帧尾8位重新复位为0。

图3 改进后的前向业务信道基带编码结构Fig.3 Proposed enhancement scheme of scrambling

5 结束语

本文证明了N-CDMA移动通信系统是不安全的。需要指出的是：本文并没有用提出的唯密文攻击方法去攻击符合IS-95标准的真实通信系统，也无意破坏对现有的商业移动通信系统的安全架构。同时N-CDMA系统已经由IS-95标准演进为CDMA 2000 1x标准，在下一代移动通信系统中改进的加密算法已经提出［14］。本文的目的是以N-CDMA的安全架构为背景探讨新的密码分析方法，为3G乃至更新的移动通信系统的设计提供经验。

［1］ TIA／EIA-95-B.Mobile station-base station compatibility standard for dual-mode spread spectrum systems［M］.Washington，America：ANSI Publication Version，1998.

［2］ Gray V K.IS-95CDMA and CDMA2000［M］.Upper Saddle River，NJ：Prentice Hall，2000.

［3］ Li Tongtong，Ling Qi，Ren Jian.Physical layer built-in security analysis and enhancement algorithms for CDMA systems［J］.Eurasip Journal on Wireless Communications and Networking，2007，2007：1-8.

［4］ Zhang Muxiang，Carroll C，Chan A H.Analysis of IS-95CDMA voice privacy［C］∥Seventh Annual Workshop on Selected Areas in Cryptography.Ontario，Canada：Springer，2000：1-13.

［5］ Ryu D H，Jang S J.A security weakness of the CDMA（code division multiple access）cellular service［J］.International Journal of Computer Science and Network Security，2006，6（5B）：218-225.

［6］ 万哲先.代数与编码［M］.3版.北京：高等教育出版社，2007：220-220.

Wan Zhexian.Algebra and coding［M］.3Ed.Beijing：Higher Education Press，2007：220-220.

［7］ Kim S C，Lee B G.Parallel scrambling techniques for multibit-interleaved multiplexing environments［C］∥PROC ICC′93.Geneva：［s.n.］，1993：1526-1530.

［8］ Lee B G，Byoung-Hoon Kim.Scrambling techniques for CDMA communications［M］.New York：Springer International Series in Engineering and Computer Science，Kluwer Academic Publishers，2001.

［9］ Massey J.Shift-register synthesis and BCH decoding［J］.IEEE Transactions on Information Theory，1969，15（1）：122-127.

［10］陈德宏，刘梅.一种求解延迟型 m序列线性组合的新算法［J］.数据采集与处理，2014，29（3）：339-444.

Chen Dehong，Liu Mei.A new algorithm of multiplex problem for delayedm-sequence［J］.Journal of Data Acquisition and Processing，2014，29（3）：339-444.

［11］He Jiaming，Zeng Xingbin，Xu Bensong.A new CDMA long code fast computing method［C］∥The IEEE-Siberian Conference on Control and Communications.［S.l.］：IEEE，2003：146-151.

［12］Falahati A，Tafaroji M，Mashreghi M.Security enhancement in CDMA with a hidden direct sequence spread spectrum system［J］.IEEE Trans Magn Japan，2006，2：2524-2529.

［13］Krishna Bharathi L，Sudha G F.Security enhancement using mutual authentication in existing CDMA systems［J］.International Journal on Computer Science and Engineering，2010，2（2）：237-245.

［14］Mohammed A M，Mohamed M.Abd E，et al.Security analysis and enhancement of authentication in CDMA based on elliptic curve cryptography［J］.Research Journal of Information Technology，2012，4（3）：106-123.