基于对称矩阵分解的无线传感网密钥恢复攻击

纪祥敏，赵波，刘金会，贾建卫，张焕国，向騻



基于对称矩阵分解的无线传感网密钥恢复攻击

纪祥敏1,2，赵波1，刘金会3，贾建卫4，张焕国1，向騻5

（1. 武汉大学国家网络安全学院空天信息安全与可信计算教育部重点实验室，湖北 武汉 430072； 2. 福建农林大学计算机与信息学院，福建 福州 350002；3. 陕西师范大学计算机科学学院，陕西 西安 710119； 4. 华为技术有限公司，陕西 西安 710075；5. 长江工程监理咨询有限公司，湖北 武汉 430015）

密钥协议是保障无线传感网络（WSN, wireless sensor network）安全性的关键技术之一。Parakh等基于矩阵分解提出一种传感网密钥协议，然而研究表明该协议存在安全隐患。利用对称矩阵和置换矩阵性质，提出针对该协议的密钥恢复攻击方法。在截获节点行、列向量信息基础上，进行初等变换，构造线性代数攻击算法，求解出等价密钥，计算复杂度为(6)。实验结果表明，在多项式计算复杂度内，该方法可恢复出上述协议的等价密钥，内存开销在可接受范围内。此外，为了抵抗线性代数攻击，通过引入随机扰动矩阵，给出一种密钥协商修正方案，并进行了正确性与安全性分析。

密钥协议；密钥恢复；矩阵分解；齐次线性方程组求解；无线传感网络

1 引言

当前，无线传感网络发展迅速，广泛应用于商业、军用和航空等领域。由于WSN的无线通信特性，缺乏固定基础设施，容易遭受节点俘获攻击、黑洞攻击等各种攻击，比传统无线网络面临更大的安全挑战与威胁[1-9]。

在诸多安全问题中，密钥管理是WSN安全的基础，密钥管理包括传感器节点密钥的生成、分发和维护。密钥分发协议是密钥管理的重要内容，密钥分发协议旨在2个传感器节点之间分配密钥，实现所有传输消息的认证和加密，从而达到基站数据中继或正常执行分布式计算时安全通信目的。密钥分发协议是保证WSN安全性的关键所在，目前，众多研究者针对WSN密钥分发协议展开了大量研究，并在协议设计、协议安全分析等多个方面取得了较为重要的研究成果[10-20]。

由于传感器设备资源有限，已有的解决方案大部分基于对称密钥加密，在加、解密效率和功耗等方面都具有一定优势。但是，在分发过程中攻击者容易截获共享密钥；同时，随着WSN分布式节点的增加，每个节点存储密钥数量激增，从而导致管理复杂，难以抵御节点脆弱性攻击[16]。

为了克服这些不足，Shim等[13]设计了基于非对称加密算法的WSN密钥分发协议，旨在提高协议安全性，增加对节点攻击的抵抗力，满足一定的部署灵活性与可扩展性。

文献[21]在传感器上实现了许多非对称加密算法，并声称该方案具有实用性，但是与对称加密算法相比消耗功率更大。文献[22]提出一种混合方案，将整个传感器网络划分为簇，由网络簇头管理各节点通信，实现公钥加密和数据聚合，而单个传感器仅使用对称密钥进行加密。文献[23]使用中央密钥管理服务器建立密钥。文献[24]讨论了基于散列链的密钥分发机制。

文献[25]提出基于排列的多项式方案，通过加大多项式重构困难度，抵御基于Lagrange插值方法攻击，然而该方案无法应对大范围节点共谋攻击。对此，文献[26]给出相应攻击方法，研究表明文献[25]方案无法突破门限，也未能应对大范围节点攻击。基于全同态加密，文献[26]提出了对偶密钥建立方法，在加密环境中实现共享密钥生成，防止相关多项式信息被捕获，在一定程度上解决大范围节点捕获攻击问题。

文献[27]提出一种基于椭圆曲线数字签名算法（ECDSA, elliptic curve digital signature algorithm）的WSN密钥协议。该方案应用椭圆曲线加密在网关到簇头、簇头到节点之间建立安全通信链路，以ECDSA进行簇头身份验证，密钥存储在传感器节点内存中，数量不增加，定期更新，防止一般性安全问题。

显然，上述研究在一定程度上解决了密钥分发过程中的一些安全性问题，但仍然存在一定的安全性弱点与计算效率低等问题。因为基于矩阵的非交换结构具有抗攻击潜力和计算效率高优点，所以，近年来，基于矩阵的密钥协议设计和分析成为了研究热点之一[28]。

2015年，Parakh等[16]基于矩阵分解提出了PK传感网密钥协议，每个传感器预装少量种子信息，通过矩阵行与列的乘法运算产生密钥，应用矩阵交换属性分发密钥。该算法不依赖于数学运算的困难性，计算复杂度为线性。

然而，通过本文研究发现，在弱密钥产生过程中，PK传感网密钥协议方案容易受到潜在的线性代数攻击。在WSN环境，这种攻击对密钥协议破坏性极大，容易造成共享密钥泄露，从而导致潜在的安全隐患。在线性代数攻击方面，文献[28-29]对具有非交换结构的非对称密码协议进行线性代数攻击，只需多项式时间可以获得某些给定密钥的等价密钥，并给出了理论证明。文献[30]将线性方程组攻击算法应用到一般矩阵群环上的HKKS协议，并给出了一些修正建议。

本文创新之处在于，利用对称矩阵和置换矩阵性质，提出一种针对PK传感网密钥协议的密钥恢复攻击方法。在有限域上，通过构造线性代数攻击算法，在可接受的内存开销范围内，求解等价密钥，证明原方案在弱密钥产生过程中存在不安全因素。此外，应用随机产生的扰动矩阵，给出一种修正方案并进行正确性分析，旨在提高原协议密钥协商的安全性。这对于WSN环境密钥交换协议的安全设计与分析的一般理论研究具有重要意义和应用价值。

2 PK传感网密钥协议

本节简要列出涉及密钥协议分析的一些基本数学符号表示含义，如表1所示；同时，给出初等矩阵与初等变换定义，并对PK传感网密钥协议[16]方案进行概述。

表1 密钥协议分析基本数学符号表示

定义1 初等矩阵：在有限域上，初等矩阵定义为由单位矩阵经过一次矩阵初等变换得到的矩阵。

定义2 初等变换主要有下列3种变换，即换法初等变换、倍法初等变换及消法初等变换，具体如下。

1) 换法初等变换：交换矩阵中任意两行的位置。

2) 倍法初等变换：以一非零数乘矩阵的某一行（列）。

以上3种初等变换统称为初等行（列）变换。

换法初等变换对应的初等矩阵如式(1)所示，称为换法变换矩阵。

一次换法变换矩阵具有如式(2)所示的性质。

多次换法矩阵的乘积是一个0-1矩阵。

针对计算资源受限的WSN环境，Parakh等[16]提出PK传感网密钥协议。该方案在传感器上预存少量部署信息，经配置后生成会话密钥，在通信范围内可与相邻传感器交换密钥[16]。具体算法描述如下。

预部署阶段主要涉及对称矩阵分解，由基站执行以下预部署计算。

3 密钥恢复攻击

3.1 密钥恢复攻击总体框架

图2 密钥恢复攻击的总体框架

密钥恢复攻击主要包括4个步骤。

因此，满足如下关系式

证毕。

根据性质1，可得

进而存在

因此，可得

根据有限域上矩阵的初等变换矩阵，可以得到一个唯一的等式关系，如式(4)所示。

因此，可以得到齐次线性方程组，如式(5)所示。

进而，

因为

所以，假设不成立。因此，

证毕。

若上述齐次线性方程组的秩小于−1，那么本文的攻击方法只能在安全水平小于80 bit的情况下才能攻破，否则不能攻破。

3.2 算法描述与有效性分析

算法1

输入

4) 求解齐次线性方程组式(5)为

表2 算法1的计算复杂度分析

3.3 攻击实例

假设未知信息为

截获信息为

可得

因为

于是求解对称矩阵密钥为

4 实验与分析

为了验证算法1破解分析PK传感网密钥协议的有效性与可行性，分别从时间复杂度与空间复杂度两方面进行实验测试。为此，采用Java作为编程语言对算法1进行编程实现，具体实验环境：处理器为AMD A10-4600M，内存8 GB，操作系统为Windows 7 （64-Bit）sp1。开发平台为Eclipse Java EE IDE的Mars Release (4.5.0版本)，Java（TM）SE 运行时环境为1.7版本。

图3 密钥矩阵恢复流程

表3 密钥矩阵恢复结果

4.1 时间复杂度测试

表4 算法1实验结果

由表4可见，随着有限域值与密钥矩阵维度的提升，实验计算复杂度相应增加，攻击时间随之递增。当有限域值均为216，矩阵维度为3时，攻击时间仅为0.004 s；矩阵维度为5时，计算复杂度相应增加，攻击时间增达1.383 s，而有限域值增至220时攻击时间增为2.5倍；在矩阵维度提升为10时，攻击时间快速增达13 530.850 s。显然，相对于有限域值，密钥矩阵维度的提升对密钥矩阵恢复攻击时间影响更为显著。但是总体而言，在多项式时间计算复杂度[28-31]内，算法1均能恢复出密钥矩阵，得出共享密钥。

4.2 空间复杂度测试

在某些密码破解算法中，随着目标数据维度的升高，空间复杂度呈几何指数增长，从而在高维数据破解时，空间复杂度上升到一定阶段对于常规计算机难以承受，这样有可能在针对高维数据分析时不具备可行性。因此，本文从内存开销角度对算法1进行空间复杂度测试。

同时，随着对称矩阵维度的提高，内存开销峰值如式(8)所示，呈现平缓的线性递增过程，并没有呈现几何指数激增趋势。

可见，在空间复杂度方面，采用算法1针对PK传感器网络密钥协议进行密钥恢复攻击具有计算可行性。

图4 密钥矩阵恢复内存开销峰值统计

实验结果表明，在多项式计算复杂度内，提出的密钥恢复攻击方法可得到PK协议的共享密钥，内存开销在可接受范围内，这说明线性代数攻击对于PK传感网密钥协议的弱密钥攻击是可行的。

5 安全性解决方案

5.1 系统建立

5.2 共享密钥协商

在WSN有效通信范围内，任意传感器节点与通过邻域探测发现彼此，并且按照图5方式协商密钥。

至此，节点、得到相同的等价密钥。

至此，节点、获得共享密钥为

5.3 正确性证明

基于随机扰动矩阵的密钥协商算法给定之后，我们给出相应的正确性证明，具体如下。

证毕。

5.4 安全性分析

6 结束语

针对PK协议在弱密钥生成过程中存在安全问题，本文提出一种密钥恢复攻击方法。通过构造齐次线性方程组，求解等价密钥，计算复杂度为(6)。本文采用的攻击方法正确、有效。与现有其他攻击方法相比，线性代数攻击方法新颖，攻击所需的数据量少，同时本文提出的攻击算法直观、易于分析理解，并且攻击计算复杂度较低。此外，为了抵抗本文攻击方法，给出一种基于随机扰动矩阵的密钥协商方案，以解决PK协议在WSN环境应用中潜在的安全隐患，为构造面向WSN计算环境的密钥安全协议提供一种途径。

随着WSN快速发展，其信息安全与隐私性受到越来越多关注。由于WSN设备计算能力、存储空间和能量有限，如何设计适用于资源受限设备的轻量级安全密钥分发方案是进一步研究的内容。

[1] 张焕国, 韩文报, 来学嘉,等. 网络空间安全综述[J]. 中国科学:信息科学, 2016, 46(2):125-164.

ZHANG H G, HAN W B, LAI X J, et al. Survey on cyberspace security[J]. Science China Information Sciences, 2016, 46(2): 125-164.

[2] 罗军舟, 杨明, 凌振, 等. 网络空间安全体系与关键技术[J]. 中国科学:信息科学, 2016, 46(8):939-968.

LUO J Z, YANG M, LING Z, et al. Architecture and key technologies of cyberspace security[J]. Science China Information Sciences, 2016, 46(8): 939-968.

[3] 陈帅, 钟先信, 巫正中, 等. 无线传感器网络混沌分组密码研究[J]. 中国科学:信息科学, 2009, 39(3):357-362.

CHEN S, ZHONG X X, WU Z Z, et al. Chaos block cipher for wireless sensor network[J]. Science China Information Sciences, 2009, 39(3): 357-362.

[4] 曾建电, 王田, 贾维嘉, 等. 传感云研究综述[J]. 计算机研究与发展, 2017, 54(5):925-939.

ZENG J D, WANG T, JIA W J, et al. A survey on sensor-cloud[J]. Journal of Computer Research and Development, 2017, 54(5): 925-939.

[5] 付帅, 马建峰, 李洪涛,等. 无线传感器网络中匿名的聚合节点选举协议[J]. 通信学报, 2015, 36(2):88-97.

FU S, MA J F, LI H T, et al. Anonymous aggregator election protocol for wireless sensor networks[J]. Journal on Communications, 2015, 36(2):88-97.

[6] ARAFATH M S, KHAN K U R. Opportunistic sensor networks: A survey on privacy and secure routing[C]//International Conference on Anti-Cyber Crimes. IEEE, 2017:41-46.

[7] HAMZA T, KADDOUM G, MEDDEB A, et al. A survey on intelligent MAC layer jamming attacks and countermeasures in WSN[C]//2016 IEEE 84th Vehicular Technology Conference (VTC-Fall). IEEE, 2016: 1-5.

[8] TEJASWINI B S, BHAT G J. Survey on various attacks and message authentication schemes in WSN[J]. International Journal of Scientific Research Engineering & Technology (IJSRET),2015,4(3): 148-152.

[9] RAYMOND D R, MARCHANY R C, BROWNFIELD M, et al. Effects of denial-of-sleep attacks on wireless sensor network MAC Protocols[J]. IEEE Transactions on Vehicular Technology, 2009, 58(1): 367-380.

[10] GANDINO F, FERRERO R, REBAUDENGO M. A Key distribution scheme for mobile wireless sensor networks: q-s-composite[J]. IEEE Transactions on Information Forensics & Security, 2017, 12(1):34-47.

[11] HAYOUNI H, HAMDI M, KIM T H. A survey on encryption schemes in wireless sensor networks[J]. J Chem Eng Data, 2014, 3(1):91-92.

[12] RAVI K, KHANAI R, PRAVEEN K. Survey on pairing based cryptography for wireless sensor networks[C]//International Conference on Inventive Computation Technologies. IEEE, 2016: 1-4.

[13] SHIM K A. A survey of public-key cryptographic primitives in wireless sensor networks[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1):577-601.

[14] MALEH Y, EZZATI A. A lightweight symmetric cryptography scheme for Identifying compromised node in WSN[J]. Indonesian Journal of Electrical Engineering and Computer Science ,2016, 2(2):431-451.

[15] YAGAN O, MAKOWSKI A M. Wireless sensor networks under the random pairwise key pre-distribution scheme: can resiliency be achieved with small key rings[J]. IEEE/ACM Transactions on Networking, 2016, 24(6):3383-3396.

[16] PARAKH A, KAK S.New key agreement techniques for sensor networks[J].Infocommunications Journal,2015,7(1):15-21.

[17] SINGH A, AWASTHI A K, SINGH K. A key agreement algorithm based on ECDSA for wireless sensor network[C]//Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics. 2016:143-149.

[18] CHAPHEKAR P P. Survey of key distribution schemes for wireless sensor networks[J]. Computer Science, 2014, 1(1): 1-14.

[19] CHEN C Y, CHAO H. A survey of key distribution in wireless sensor networks[J]. Security and Communication Networks, 2015, 7(12): 2495-2508.

[20] CASOLA V, BENEDICTIS A D, DRAGO A, et al. Analysis and comparison of security protocols in wireless sensor networks[C]// IEEE, Symposium on Reliable Distributed Systems Workshops. 2011: 52-56.

[21] JR M A S, BARRETO P S L M, MARGI C B, et al. A survey on key management mechanisms for distributed wireless sensor networks[J]. Computer Networks, 2010, 54(15): 2591-2612.

[22] RUJ S,SAKURAI K. Secure and privacy preserving hierarchical wireless sensor networks using hybrid key management technique[C]// Global Communications Conference. 2014:402-407.

[23] SALZO S,VILLA S. SPIKE: a novel session key management protocol with time-varying secure cluster formation in wireless sensor networks[C]// Eleventh International Conference on Privacy, Security and Trust. 2013:151-160.

[24] BECHKIT W, CHALLAL Y, BOUNABDALLAH A. A new class of Hash-Chain based key pre-distribution schemes for WSN[J]. Computer Communications, 2013, 36(3):243-255.

[25] 陈燕俐, 杨庚. 适合于无线传感器网络的混合式组密钥管理方案[J]. 通信学报, 2010, 31(11): 56-64.

CHEN Y L, YANG G. Hybird group key management scheme for wireless sensor networks[J]. Journal on Communications, 2010, 31(11): 56-64.

[26] 张永, 温涛, 郭权,等. WSN中基于全同态加密的对偶密钥建立方案[J]. 通信学报, 2012,33(10):101-109.

ZHONG Y, WEN T, GUO Q, et al. Pair-wise key establishment for wireless sensor networks based on fully homomorphic encryption[J]. Journal on Communications, 2012, 33(10): 101-109.

[27] SINGH A, AWASTHI A K, SINGH K. A key agreement algorithm based on ECDSA for wireless sensor network[C]// Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics. Springer India. 2016: 143-149.

[28] LIU J H, ZHANG H G, JIA J W, et al. Cryptanalysis of an asymmetric cipher protocol using a matrix decomposition problem[J]. Science China Information Sciences, 2016, 46(5): 1-11.

[29] LIU J H, ZHANG H G, JIA J W. A linear algebra attack on the non-commuting cryptography class based on matrix power function[C] //International Conference on Information Security and Cryptology. 2016: 343-354.

[30] 刘金会, 张焕国, 贾建卫, 等. HKKS密钥交换协议分析[J]. 计算机学报, 2016, 39(3): 516-528.

LIU J H, ZHANG H G, JIA J W, et al. Cryptanalysis of HKKS key exchange protocols[J]. Chinese Journal of Computers, 2016,39(3): 516-528.

[31] 张焕国, 毛少武, 吴万青, 等. 量子计算复杂性理论综述[J]. 计算机学报, 2016, 39(12): 2403-2428.

ZHANG H G, MAO S W, WU W Q, et al. Overview of quantum computation complexity theory[J]. Chinese Journal of Computers, 2016, 39(12): 2403-2428.

WSN key recovery attack based on symmetric matrix decomposition

JI Xiangmin1,2, ZHAO Bo1, LIU Jinhui3, JIA Jianwei4, ZHANG Huanguo1, XIANG Shuang5

1. Key Laboratory of Aerospace Information Security and Trusted Computing，Ministry of Education, School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China 2. College of Computer Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China 3. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China 4. Huawei Technologies Co., Ltd., Xi’an 710075, China 5. Yangtze River Engineering Supervision Consulting Co., Ltd., Wuhan 430015, China

The key protocol is one of the crucial technologies to ensure the security for wireless sensor network（WSN）. Parakh, et al. proposed a key agreement for WSN based on matrix decomposition. However, the study revealed that the protocol had security risks. A key recovery attack scheme against this protocol was proposed by using the properties of symmetric matrix and permutation matrix. Based on intercepting the row and column vector of the node, elementary transformation was performed to construct a linear algebraic attack algorithm and the equivalent key was obtained. The computational complexity is(6). Experimental results show that the method can recover the equivalent key of the above protocol within the polynomial computational complexity and the memory consumption is within an acceptable range. In addition, an improved scheme for key agreement was proposed to resist the linear algebraic attack by using a random disturbance matrix, and the correctness and security analysis were also carried out.

key protocol, key recovery, matrix decomposition, homogeneous linear equations solving, wireless sensor network

TP391

A

10.11959/j.issn.1000-436x.2018221

纪祥敏（1971−），男，福建尤溪人，武汉大学博士生，主要研究方向为云安全、可信计算与信息安全。

赵波（1972−），男，山东青岛人，武汉大学教授、博士生导师，主要研究方向为可信计算、虚拟化安全、嵌入式系统安全等。

刘金会（1989−），女，河南睢县人，博士，陕西师范大学讲师，主要研究方向为抗量子计算密码、数字签名。

贾建卫（1988−），男，河南温县人，博士，华为技术有限公司工程师，主要研究方向为密码学、信息安全。

张焕国（1945−），男，河北元氏人，武汉大学教授、博士生导师，主要研究方向为密码学、信息安全等。

向騻（1984−），男，湖北荆州人，博士，长江工程监理咨询有限公司(湖北)高级工程师，主要研究方向为云安全、信息安全。

2017−11−02；

2018−07−22

赵波，zhaobo@whu.edu.cn

国家重点基础研究发展计划（“973”计划）基金资助项目（No.2014CB340600）；国家高技术研究发展计划（“863”计划）基金资助项目（No.2015AA016002）；国家自然科学基金重点项目资助项目（No.61332039）；中央高校基本科研业务费基金资助项目（No.GK201803061）；中国博士后科学基金面上项目基金资助项目（No.2018M631121）；福建省自然科学基金资助项目（No.2016J01285）

The National Basic Research Program of China (973 Program)(No.2014CB340600),The National High Technology Research and Development Program of China (863 Program) (No.2015AA016002), The Major Program of National Natural Science Foundation of China (No.61332039), The Fundamental Research Funds for the Central Universities (No.GK201803061), The Postdoctoral Science Foundation Project of China (No.2018M631121), The Natural Science Foundation of Fujian Province (No.2016J01285)