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

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

通信学报 ›› 2018, Vol. 39 ›› Issue (10): 87-96.doi: 10.11959/j.issn.1000-436x.2018221

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

纪祥敏^1,²,赵波¹(),刘金会³,贾建卫⁴,张焕国¹,向騻⁵

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

修回日期:2018-07-22 出版日期:2018-10-01 发布日期:2018-11-23
作者简介:纪祥敏（1971-），男，福建尤溪人，武汉大学博士生，主要研究方向为云安全、可信计算与信息安全。|赵波（1972-），男，山东青岛人，武汉大学教授、博士生导师，主要研究方向为可信计算、虚拟化安全、嵌入式系统安全等。|刘金会（1989-），女，河南睢县人，博士，陕西师范大学讲师，主要研究方向为抗量子计算密码、数字签名。|贾建卫（1988-），男，河南温县人，博士，华为技术有限公司工程师，主要研究方向为密码学、信息安全。|张焕国（1945-），男，河北元氏人，武汉大学教授、博士生导师，主要研究方向为密码学、信息安全等。|向騻（1984-），男，湖北荆州人，博士，长江工程监理咨询有限公司(湖北)高级工程师，主要研究方向为云安全、信息安全。
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目(2014CB340600);国家高技术研究发展计划（“863”计划）基金资助项目(2015AA016002);国家自然科学基金重点项目资助项目(61332039);中央高校基本科研业务费基金资助项目(GK201803061);中国博士后科学基金面上项目基金资助项目(2018M631121);福建省自然科学基金资助项目(2016J01285)

WSN key recovery attack based on symmetric matrix decomposition

Xiangmin JI^1,²,Bo ZHAO¹(),Jinhui LIU³,Jianwei JIA⁴,Huanguo ZHANG¹,Shuang XIANG⁵

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

Revised:2018-07-22 Online:2018-10-01 Published:2018-11-23
Supported by:
The National Basic Research Program of China (973 Program)(2014CB340600);The National High Technology Research and Development Program of China (863 Program)(2015AA016002);The Major Program of National Natural Science Foundation of China(61332039);The Fundamental Research Funds for the Central Universities(GK201803061);The Postdoctoral Science Foundation Project of China(2018M631121);The Natural Science Foundation of Fujian Province(2016J01285)

摘要/Abstract

摘要：

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

关键词: 密钥协议, 密钥恢复, 矩阵分解, 齐次线性方程组求解, 无线传感网络

Abstract:

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 O(N⁶).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 words: key protocol, key recovery, matrix decomposition, homogeneous linear equations solving, wireless sensor network

中图分类号:

TP391

纪祥敏,赵波,刘金会,贾建卫,张焕国,向騻. 基于对称矩阵分解的无线传感网密钥恢复攻击[J]. 通信学报, 2018, 39(10): 87-96.

Xiangmin JI,Bo ZHAO,Jinhui LIU,Jianwei JIA,Huanguo ZHANG,Shuang XIANG. WSN key recovery attack based on symmetric matrix decomposition[J]. Journal on Communications, 2018, 39(10): 87-96.

图/表 9

表1

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

符号	释义
p	素数
$Z_{p}$	有限域{0,1,2",p-1}
$Z_{P}^{n \times n}$	实数域 $Z_{p}$ 上的n×n矩阵
$P^{T r}$	矩阵 $P$ 的转置
$K$	对称矩阵密钥
$\tilde{K}$	矩阵 $K$ 中元素的排列组合
$r o w_{i} (X)$	矩阵 $X$ 的行分配给 i节点
$c o l_{j} (Y)$	矩阵 $Y$ 的列分配给 j节点
$X^{'}$	矩阵 $X$ 被监听到的行向量信息
$Y^{'}$	矩阵 $Y$ 被监听到的列向量信息

表1

图1

图2

表2

图3

表3

密钥矩阵恢复结果"

执行过程	结果
特殊矩阵密钥 $K^{'}$	$(\begin{matrix} 4 & 3 & 1 \\ 2 & 0 & 4 \\ 0 & 2 & 3 \end{matrix})$
初等矩阵 $P^{2}$	$(\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix})$
初等矩阵 $P$	$(\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$
密钥 $K$	$(\begin{matrix} 2 & 3 & 0 \\ 3 & 1 & 4 \\ 0 & 4 & 2 \end{matrix})$
执行总时间	0.004 s

表3

表4

图4

图5

参考文献 31

[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.

内容	复杂度	解释
3)	O(N³)	一个矩阵乘法
4)	O(N⁶)	N²个方程、N²个变量的齐次线性方程组
7)	O(N⁶)	2N²个方程、N²个变量的齐次线性方程组
9)	O(N³)	3个N阶矩阵相乘

有限域q	矩阵维度	计算复杂度	攻击时间/s
2¹⁶	3	2^{17.509 8}	0.004
2¹⁶	4	2^{20.000 0}	0.553
2¹⁶	5	2^{21.931 5}	1.383
2¹⁸	5	2^{22.271 3}	3.150
2²⁰	5	2^{22.575 5}	3.538
2²⁰	6	2^{24.156 3}	259.035
2²⁰	10	2^{28.575 8}	13 530.850

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

WSN key recovery attack based on symmetric matrix decomposition

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 31

相关文章 15

Metrics

推荐阅读 0

[1]	解元, 邹涛, 孙为军, 谢胜利. 面向高混响环境的欠定卷积盲源分离算法[J]. 通信学报, 2023, 44(2): 82-93.
[2]	李骜, 冯聪, 牛宇童, 徐士彪, 张英涛, 孙广路. 面向视角非对齐数据的多视角聚类方法[J]. 通信学报, 2022, 43(7): 143-152.
[3]	邱飞岳,陈博文,陈铁明,章国道. 稀疏诱导流形正则化凸非负矩阵分解算法[J]. 通信学报, 2020, 41(5): 84-95.
[4]	吴宾,陈允,孙中川,叶阳东. 联合成对排序的物品推荐模型[J]. 通信学报, 2019, 40(9): 193-206.
[5]	舒坚,刘满兰,郑巍. 基于AdaBoost的链路质量预测机制研究[J]. 通信学报, 2017, 38(Z1): 39-45.
[6]	常振超,陈鸿昶,黄瑞阳,于洪涛,刘阳. 基于非负矩阵分解的半监督动态社团检测[J]. 通信学报, 2016, 37(2): 132-143.
[7]	徐琨,刘宏立,詹杰,马子骥. 容忍恶意攻击的无线传感网络安全定位算法[J]. 通信学报, 2016, 37(12): 95-102.
[8]	于淼,杨武,王巍,申国伟. 面向微博的多实体稀疏关系数据联合聚类[J]. 通信学报, 2016, 37(1): 151-159.
[9]	荣辉桂,莫进侠,常炳国,孙光,龙飞. 基于Shamir秘密共享的密钥分发与恢复算法[J]. 通信学报, 2015, 36(3): 265-274.
[10]	陈权,高宏. 低占空比无线传感器网络中基于动态切换的实时路由协议[J]. 通信学报, 2015, 36(10): 224-234.
[11]	刘建华,童维勤. RFID系统中面向服务的动态资源配置优化机制[J]. 通信学报, 2012, 33(8): 93-105.
[12]	魏祥麟,陈鸣,张国敏,黄建军. NMF-NAD：基于NMF的全网络流量异常检测方法[J]. 通信学报, 2012, 33(4): 54-61.
[13]	宋海欣,范修斌,武传坤,冯登国. 立方攻击成功率分析[J]. 通信学报, 2012, 33(10): 143-148.
[14]	孙欣尧,王雪,王晟. 无线传感网络协同概率多模识别方法[J]. 通信学报, 2011, 32(6): 141-147.
[15]	郑世慧,张国艳,杨义先,李忠献. 基于混沌的带密钥散列函数安全分析[J]. 通信学报, 2011, 32(5): 146-152.