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

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

Abstract

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

CLC Number:

TP391

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.

Figures/Tables 9

符号	释义
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$ 被监听到的列向量信息

执行过程	结果
特殊矩阵密钥 $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

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

Metrics

Recommended 0

No Suggested Reading articles found!

内容	复杂度	解释
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 31

Related Articles 15

Metrics

Recommended 0

[1]	Yue ZHAO, Zan LI, Bing LI, Benjian HAO. TDoA localization-refused area analysis and node placement strategy research [J]. Journal on Communications, 2023, 44(1): 1-13.
[2]	Cuiran LI, Xuejie WANG, Jianli XIE, Anqi LYU. Routing algorithm for railway monitoring linear WSN based on improved PSO [J]. Journal on Communications, 2022, 43(5): 155-165.
[3]	Xiujuan DU, Lijuan WANG, Jingping LIU, Long JIN. Ranging localization method for nodes in underwater wireless sensor network based on zeroing neural dynamics [J]. Journal on Communications, 2022, 43(10): 177-185.
[4]	Aijing SUN, Shichang LI, Yicai ZHANG. WSN clustering routing algorithm based on PSO optimized fuzzy C-means [J]. Journal on Communications, 2021, 42(3): 91-99.
[5]	Tianjing WANG,Xiuqin LI,Guangwei BAI,Hang SHEN. Multi-target localization algorithm based on adaptive grid in wireless sensor network [J]. Journal on Communications, 2019, 40(7): 197-207.
[6]	Xiaochen HAO,Ning YAO,Lixia XIE,Jiaojiao WANG,Liyuan WANG. Research on WSN lifetime optimization game algorithm combined power and channel [J]. Journal on Communications, 2019, 40(4): 62-70.
[7]	Linlan LIU,Shengrong GAO,Jian SHU. Link quality prediction based on random forest [J]. Journal on Communications, 2019, 40(4): 202-211.
[8]	Xiaonian WU,Chuyun ZHANG,Runlian ZHANG,Yaping SUN. Clustering routing protocol based on improved PSO algorithm in WSN [J]. Journal on Communications, 2019, 40(12): 114-123.
[9]	Haoran LIU,Heyao ZHAO,Yujing DENG,Xingqi WANG,Rongrong YIN. Coverage control algorithm for wireless sensor networks based on non-cooperative game [J]. Journal on Communications, 2019, 40(1): 71-78.
[10]	Jian SHU,Manlan LIU,Yaqing SHANG,Yubin CHEN,Linlan LIU. Link quality prediction model based on Gaussian process regression [J]. Journal on Communications, 2018, 39(7): 148-156.
[11]	Junbin LIANG,Xiang ZHOU,Taoshen LI. Energy saving proactive neighbor discovery algorithm in mobile low-duty-cycle wireless sensor network [J]. Journal on Communications, 2018, 39(4): 45-55.
[12]	Xiaochen HAO,Liyuan WANG,Jinshuo LIU,Lixia XIE,Wenhuan ZHANG. Resource allocation optimization algorithm based on double populations differential evolution in WSN [J]. Journal on Communications, 2018, 39(4): 68-75.
[13]	Tian WANG,Yang LI,Weijia JIA,Guojun WANG,Shaoliang PENG. Research progress of sensor-cloud security [J]. Journal on Communications, 2018, 39(3): 35-52.
[14]	Chan JIANG,Taoshen LI,Junbin LIANG. Low-latency algorithm for improving data persistence in mobile low-duty-cycle wireless sensor network [J]. Journal on Communications, 2018, 39(3): 53-62.
[15]	Xiaoying ZHANG,Hui PENG,Hong CHEN. State-of-the-art survey of privacy-preserving data aggregation in wireless sensor networks [J]. Journal on Communications, 2018, 39(10): 130-142.