TinySBSec—新型轻量级WSN链路层加密算法

白恩健，朱俊杰

(1.东华大学信息科学与技术学院，上海201620;2.数字化纺织服装技术教育部工程研究中心，上海201620)

无线传感器网络(WSN)的相关研究中，对于节能算法的研究占据重要的地位。WSN链路层加密算法，作为节点调用最为频繁的一种功能，其节能性能对系统能耗的影响相当可观。在早前的一些研究中，讨论了对称密码与公钥密码的能耗差异，结果显然是对称密码算法更具节能优势。因此，在一些现行的WSN安全协议中，都采用对称加密算法作为链路层加密算法。如 TinySec［1］采用的 RC5 与 SkipJack、ContikiSec［2］采 用 的 AES 以 及 WSNSec［3］采 用 的SEA，这些都是对WSN的移植算法，针对性不强。TinyIBE［4］采用BF-IBE方案的基于身份的WSN公钥加密系统，利用椭圆曲线公钥加密算法极大地提高了WSN数据传输的安全性，且在密钥管理方面也更为简单，但牺牲了计算效率以及额外增加大量能耗，不能满足绝大部分WSN的应用要求。文献［5］提出的基于RC4序列密码和Group Key Update的WSN链路加密协议，由于WSN数据报文的数据部分，一般都是有着固定规律以及较高的重复率，且其长度有限，使序列密码的加密方法在WSN的应用中的安全性不能得到保证，尤其是文献［6］中给出了针对这类序列密码的分析手段。本文提出一种新型的WSN链路加密算法，该方案是依据TinySec数据包格式进行设计和优化的，采用序列密码(stream cipher)和混沌映射的密钥生成方案，并结合分组密码(block cipher)的密码分组链接模式(CBC)，拥有近似序列密码的计算效率和低功耗优势，并且克服了序列密码在WSN应用中的安全弱点。

1 算法设计

1.1 TinySec协议分析

TinyOS是一个基于组件(component-based)的开源操作系统，由UC Berkeley(加州大学伯克利分校)开发，专为存储器受限制的WSN设计。TinySec则同样是UC Berkeley为WSN开发设计的一款可运行于TinyOS的WSN链路加密协议。

该协议采用的是对称分组密码，加密算法可以是RC5或是SkipJack算法。其加密算法的工作模式为CBC模式，是一种拥有反馈机制的工作模式。每组密文不仅依赖于其明文，也依赖于上一密文分组(第1组密文依赖于初始向量IV)。

CBC模式的数学语言表示如下:

CBC模式能增加攻击者篡改消息的难度，以尽可能简单的运算，达到一定的安全性能，而且并不会增加太多额外的能量损耗。正是基于这一优点，其他的一些WSN链路层加密协议，如WSNSec和ContikiSec也使用CBC工作模式。

TinyOS的链路层协议有3种数据包结构:Tiny-OS packet format、TinySec-Auth packet format和 TinySec-AE packet format。其中 TinyOS packet format是TinyOS默认的数据包结构，没有加密和MAC(消息认证码)，只有CRC检验数据的完整性;TinySec-Auth是只带MAC认证的数据包结构，Data是未加密的明文;TinySec-AE则是既有MAC认证，同时Data也被加密保护的数据包结构。3种数据包结构如图1所示。

图1 TinyOS的3种数据包结构Fig.1 The TinySec packet formats

TinySec采用的RC5和SkipJack加密算法、CBCMAC以及CBC密码工作模式都没有明显的漏洞，且对资源的占用也控制的较好，似乎就是专为WSN量身定做的最合适的链路层加密协议。事实上，TinySec同样具有一些缺点，例如无密钥更新机制，需要人工进行密钥的更新。当然，这可以通过密钥管理协议进行完善，但对于WSN这种短报文且明文重复率较高的数据特点，需要经常更换密钥以保障数据的安全性，这便对系统的整体能耗增加了额外的负担。而本文提出的TinySBSec链路加密算法，则拥有一种子密钥的自动更新机制，来解决这一问题。

1.2 TinySBSec框架设计

TinySBSec采用序列密码与分组密码相结合的方式，从而简化节点进行加密/解密时的计算复杂度和计算量。从形式上讲，TinySBSec依然是一种分组密码算法，采用的是CBC工作模式，所以，TinySBSec的数据包结构，依然沿用TinySec-AE packet format如图1(c)所示，这样的设计尽可能的减小了对原TinyOS的其他协议算法的影响，具有更高的通用性。

虽然使用序列密码的加密方式能够极大的减少节点加密/解密的计算量，但却会导致严重的安全缺陷。为了解决序列密码在WSN链路层加密应用中的致命缺陷，本协议采用分组密码的形式，结合序列密码在产生子密钥和加密方面的优势，针对一些可能的安全漏洞进行了优化和设计。协议的加密/解密流程图如图2所示。

图2 TinySBSec加密/解密流程Fig.2 TinySBSec encryption/decryption process

从图2中可以得知，TinySBSec的加密和解密流程，相较标准的分组密码体制，增加了“交织/解交织”部分。需要说明的是，算法中引入交织并非是为了提供安全性上的增益，而是为了解决新算法在WSN应用中可能遇到的安全缺陷。考虑到WSN的消息内容有很强的“规范性”及“重复性”，若仅采用异或加密与分组密码的结合加密算法，将很容易遭到暴力破解。引入交织，结合CBC模式的特性，可以较有效的规避这一问题。

而且，每个分组进行加密时，所使用的密钥也是不同于标准分组密码那样的单一密钥，并且在不同的2个报文加密时，子密钥也会相应进行更新(非密钥管理方案形式的密钥更新)。

在进行TinySBSec协议的设计过程中，WSN的报文一般具有很强的“规范性”和“重复性”，而且种子密钥的长度一般不会很长。若单纯采用异或加密，会增加被暴力破解的风险。所以，TinySBSec采用明文交织和“伪一组一密”这2种技术，与分组密码CBC模式相结合，保证密码系统的安全性。

在加密前，明文先进行交织处理。交织这一概念源于通信原理，为了确保数据流在信道中某一块的丢失不会导致整个信息的无法还原，采用交织方法将原数据的块分散到传输信号的各个部分，在接收端再通过解交织以及纠错码进行信号还原。在这里，利用交织可以将数据位分散分布的特点，使得分析者在分析时，除非能猜测出完整的明文(或至少是明文的大部分位)，否则，无法通过简单的异或破解出加密密钥。而且，即使破译出了加密密钥，由于TinySBSec的子密钥自更新机制，破译者依然无法获得种子密钥T。

此外，TinySBSec的子密钥还具有自动更新机制，这进一步提高了密码的安全性，因为“一次一密加密系统”是最安全的一种加密方式，虽然本算法并非严格意义上的“一次一密”，但却能提供相当的功能，且不需要为此负担额外的密钥更新能耗，而这正适合WSN的链路层加密。以往的WSN链路加密协议不采用一次一密，是因为频繁的密钥更新，会给系统的计算和功耗带来极大的影响，不适合WSN这种轻量级的网络应用。而TinySBSec的子密钥自动更新，不需要通过WSN的密钥管理协议实现，恰好弥补了一次一密体制在WSN应用中的先天缺点。

TinySBSec采用CBC分组加密模式，加密/解密部分采用的是序列密码加密，因此加密及解密计算用异或表示，每组明文加密都采用独立的密钥Ki。加密及解密计算的数学表达式可以表述为

其中，C0=IV，i=1，2，…，29。TinySBSec采用 8 bit(即1byte)的分组长度，每个分组加密时都有对应的独立密钥，报文格式与TinyOS一样，默认支持最多为29 byte长的数据。

1.3 子密钥生成算法

TinySBSec是一种序列密码加密，分组密码链接形式的加密协议，其子密钥生成算法采用RC4框架的改进型序列密码算法。RC4算法原型具有易实现、速度快(大约是DES的10倍左右)、安全性好等优点，适合移植到WSN的应用中。通过结合在本文1.2节中提出的“伪一组一密”的CBC分组加密模式，作为序列密码的RC4也能在WSN中进行工作，并保证一定的安全性。而为了进一步保证TinySBSec的安全性能，本文对RC4算法进行进一步的修改，提高其序列输出的随机性，并且防止一些针对RC4算法特征的破解。

这种改进型的密钥序列生成算法采用128 byte长的种子密钥T，在RC4原型的伪随机子密码生成算法(PRGA)中，加入了Logistic混沌映射算法，以此增强子密钥序列的随机性。Logistic混沌映射模型如下:

改进算法中的Logistic初始值X0采用的是7位的无符号二进制数，其精度为1/128，即可精确到小数点后2位。在对算法进行改进的过程中，发现Logistic混沌映射在初始值X0变化很小时，其初始几轮迭代值差异很小，如图3所示。

图3 Logistic迭代情况Fig.3 Iteration of Logistic

从图3可见，在小数点后2位精度的情况下，初始值X0的微小变化导致的前4轮迭代值相差很小。所以，在算法中使用Logistic时，先进行4轮预迭代，以保证加入Logistic混沌映射的有效性。

改进后的子密钥序列生成算法如下:

其中，u=4即Logistic映射的控制参数μ，Len/8表示分组数量。

从算法中可以看到，PRGA中插入的Logistic映射的初始值X0，是由种子密钥T的第IV个元素的模16值确定的(因为种子密钥长为16 byte)。由于IV中包含计数器Ctr，所以IV的更新会带动初始值X0的更新，达到子密钥序列自动更新的效果。在最后产生子密钥时，加入Logistic迭代值，可以在增加输出子密钥序列随机性的情况下，避免破坏RC4原算法的结构，防止弱密钥情况的发生。

新算法充分利用了TinyOS数据报文的元素，实现了混沌映射在密钥生成算法中，保持加密/解密过程的同步。正如算法所描述的，PRGA中插入的Logistic映射的初始值X0，与初始向量IV(8 bit)有关。初始向量IV是消息头(IV=Dest||AM||Len||Src||Ctr)的8bit摘要。凭此，在解密时，节点能够有效地进行同步解密。

该算法的安全优势在于，克服了序列密码原本的周期性重复问题，且破译者进行破译时，无法获得必需的Logistic映射初始值X0，因为X0需要通过种子密钥T获得。从理论上讲，子密钥自更新机制对于暴力破解也有很强的防御能力，新的子密钥序列生成算法具有足够的安全性，并且比原RC4的PRGA算法更安全。

2 性能分析

2.1 算法安全性的理论分析

作为链路层加密算法，虽然WSN的应用特性要求算法需要有精简的计算负荷以及良好的节能效果，但算法提供的安全性能依然是必须考虑的重点。本节将从理论分析的角度，证明新算法具有足够的安全性能。

首先，新算法采用的是基于RC4算法以及Logistic映射的改进型密钥生成算法。RC4是具有极高非线性特性的算法，而且该算法在保证了足够安全性能的同时，提供了更快的计算速度(约为DES的10倍)，从而具有不错的节能效果。而Logistic映射本身也是一种离散非线性映射［7-8］，且映射值的插入是作为RC4密钥流输出的混沌偏移，并不会改变RC4算法的非线性结构，保证了算法整体的非线性能力。

其次，新算法中Logistic映射的初始状态量X0，是通过报文的IV以及通信种子密钥T计算而得。这使得X0本身也是保密的，确保了Logistic映射值作为RC4输出序列混沌偏移的有效性。

再者，WSN报文信息具有很强的“规范性”及“重复性”，且由于节点的硬件资源限制，加密通信采用的种子密钥长度必然受到限制。所以单纯地流密码加密方式，将使得WSN面对暴力破解时显得更为脆弱。而新算法巧妙地结合了CBC模式以及交织技术，可以有效抑制算法被暴力破解的风险。

最后，作为新算法中的重要组成部分，改进的密钥序列生成算法，通过引入Logistic映射值作为RC4输出序列的混沌偏移，解决了RC4输出序列的周期性问题，可以提供较RC4更好的随机序列输出能力。

2.2 密钥的安全性

TinySBSec采用的是流密码的加密方式，即按位异或，这种加密方式依赖于密钥序列的性能即随机性。所以，在对算法安全性进行验证时，可以通过对子密钥序列分布的随机性进行测试得出结论。

测试采用统计学的方法:卡方拟合检验［9］，对TinySBSec的安全性能进行验证。卡方拟合检验是在总体分布未知时，根据来自总体的样本，对总体分布的假设进行检验的一种方法。卡方拟合检验对于样本容量的要求是N≥50，且理论频数Ei≥5，测试中，样本容量N=1 305≫50、理论频数Ei=5.097 7＞5，符合卡方检验的样本要求。

对于密钥生成算法的随机性测试，可分为频数检验和跟随性检验。

2.2.1 频数检验

子密钥序列生成算法作为一种伪随机序列发生器，其生成密钥序列的“0”、“1”分布平衡性是评价算法性能的一个重要标准。频数检验是一种随机性检验，递差符号游程检验的变形。，该检验项目负责测试分组密钥的“0”、“1”的平衡性。

根据卡方拟合检验原理，理论频数(即期望)为Ei=Cin×F/2n，其中n=8 为分组长度，F=1 305 为样本个数(即测试分组数量)。统计F个8bit子密钥中汉明重量为 i(i=0，1，2，…，8)的个数，记为 Fi。将Fi与理论频数Ei进行卡方拟合检验，将其计算结果与自由度为n、显著性水平为5%的卡方阈值进行比较，若小于阈值，则接受密钥符合二项分布B(n，1/2)的假设，即证明密钥具有足够的“0”、“1”分布平衡性。

笔者随机产生种子密钥T，对子密钥序列进行卡方拟合检验，结果都符合卡方阈值要求。图4中列出了10组不同种子密钥T情况下对比RC4算法，2种算法卡方检验的结果比较。

图4 密钥频数检验Fig.4 Frequency test of Subkeys

可以看到，TinySBSec的伪随机性完全符合拟合要求，且比RC4算法的序列拥有更好的二项分布特性。

2.2.2 跟随性检验

对子密钥序列的跟随性检验同样采用卡方拟合检验，对每个分组子密钥的相邻元素进行模2加，得到1305组7位序列，统计其汉明重量为i(i=0，1，2，…，7)的分组个数，记为Gi，将其与理论频数Ei=Ci(n-1)×F/2n-1进行拟合检验，计算结果与自由度为n-1、显著性水平为5%的卡方阈值进行比较。

图5中显示了不同种子密钥T产生的子密钥序列与RC4算法产生序列的拟合结果对比，可以看到，新算法相较于RC4算法，在伪随机序列产生方面具有一定的优势。

图5 密钥跟随性检验Fig.5 Follow ing test of Subkeys

通过频数检验和跟随性检验，可以验证TinySBSec的子密钥生成算法，具有足够的安全性能，并且通过算法改进，达到了比RC4算法更好的效果。

2.3 加密算法的安全性

从结构上分析，TinySBSec采用的是分组密码CBC链接模式，该模式对于密文(除第1组外)有良好的扩散效果，并且计算速度高。而考虑到TinySBSec面对猜测报文部分字节的攻击，在分组前，明文经过周期为4的交织变换，将明文的单独字节分散，结合CBC模式的扩散效果，从而增加分析者的破译难度。

分析者破译密码算法时，将算法看做一个黑盒，所以，密码算法输出密文的随机性以及明/密文之间独立性，可以作为衡量算法安全性能的标准。密文的随机性测试与本文2.1节提到的密钥随机性测试相同，分为频数检验和跟随性检验2项。明密文的独立性则是计算各组对应明密文之间的距离D=W(pi⊕ci)，统计D中汉明重量为i的分组数，记为Hi，将 Hi与理论频数 Ei=Cin×F/2n进行拟合检验，计算结果与自由度为n、显著性水平为5%的卡方阈值比较，得出检验结果。表1中列出了对上述3个项目进行拟合的部分结果。

表1 不同屈服强度下工字梁的极限承载力Table 1 Ultimate bearing capacities of I beams at different yielding strengths

通过统计分析，TinySBSec生成的子密钥以及输出的密文，具有足够的伪随机特性，符合卡方拟合检验对二项分布的检验要求。而且，在子密钥生成算法中插入了Logistic迭代值作为混沌随机偏移，解决了原RC4算法的周期性问题，增加了子密钥序列的破译难度。

在算法结构上，改进的子密钥生成算法对于RC4的结构未作修改，不会造成结构上的漏洞，而且针对流密码形式的加密方式，做出了有效的算法调整和优化。

综合考虑以上的分析结果，TinySBSec是一个具有足够安全性能的加密算法，且算法轻量化，适合应用于WSN链路层加密。

4 结束语

TinySBSec作为针对WSN硬件特性进行设计的链路层加密算法，在算法结构上十分精简。子密钥生成算法以及CBC模式是构成算法的主要部分，CBC中加密函数F采用序列密码的加密方式，从而节省了大量的计算损耗。加密时，明文在分组加密之前进行交织，再结合CBC工作模式的扩散特性，解决了序列密码加密方式在WSN应用中，可能遇到的安全弱点，比如分析者通过对WSN中出现频次较高的字节位进行破译，由子密钥规律来分析种子密钥。此外，在子密钥生成算法中增加的Logistic混沌映射，也进一步增加了子密钥序列的随机性，同时解决了原RC4算法存在的输出序列周期性的问题，可以延长种子密钥的更新周期，从而达到节能的效果。

通过理论分析，可知密钥生成算法具有良好的非线性特性。经过一系列的统计学方法的测试，验证了TinySBSec的子密钥生成算法具有足够的伪随机特性，作为一种采用异或加密的算法，子密钥的伪随机性能越好，加密算法的安全性越高。而对加密算法输出密文的随机性以及明密文之间的独立性的卡方拟合检验测试，也证明了加密算法拥有足够的安全性能。

［1］KARLOFC，SASTRY N，WAGNER D.TinySec:a link layer security architecture for wireless sensor networks［C］//Proceedings of the Second ACM Conference on Embedded Networked Sensor Systems.Baltimore，USA，2004.

［2］CASADO L，TSIGASP.ContikiSec:a secure network layer for wireless sensor networks under the Contikioperating system［C］//The 14th Nordic Conference on Secure IT Systems.Oslo，Norway，2009.

［3］BANDIRMALI N，ERTURK I.WSNSec:a scalable data link layer security protocol for WSNs［J］.Ad Hoc Networks，2012，10(1):37-45.

［4］陈铁明，白素刚，蔡家楣.TinyIBE:面向无线传感器网络的身份公钥加密系统［J］.传感技术学报，2009，22(8):1193-1197.CHEN Tieming，BAI Sugang，CAI Jiamei.TinyIBE:an identity-based encryption for wireless sensor network［J］.Chinese Journal of Sensors and Actuators，2009，22(8):1193-1197.

［5］PU Chuanchin，CHUNG Wanyoung.Group key update method for improving RC4 stream cipher in wireless sensor networks［C］//ICCIT ＇07.［S.l.］，2007.

［6］TSUNOO Yukiyasu，SAITO Teruo，KUBO Hiroyasu，et al.a distinguishing attack on a fast s of tware-implemented RC4-Like stream cipher［J］.IEEE Transactions on Information Theory，2007，53(9):3250-3255.

［7］GRASSBERGER P，PROCACCIA I.Characterization of strange attractors［J］.Physical Review Letters，1983，50(5):346-349.

［8］FARMER JD，SIDOROWICH J J.Predicting chaotic time series［J］.Physical Review Letters，1987，59(8):845-848.

［9］亓民勇，董金新.基于卡方拟合优度检验的序列等概性测试组［J］.计算机工程与设计，2012，33(5):1757-1760.QIMinyong，DONG Jinxin.Test suite for sequence equal probability based on chisquare goodness of fit test［J］.Computer Engineering and Design，2012，33(5):1757-1760.