基于混沌神经网络和C-MD结构的带密钥哈希函数

doi:10.11959/j.issn.2096-109x.2023033

摘要/Abstract

摘要：

近年来，被广泛使用的MD5、SHA-1等哈希算法存在不同程度的安全隐患，现在通用的SHA-2算法迭代结构与SHA-1算法相同，使得其存在被攻破的可能性。而SHA-3由于其内部结构复杂，实现复杂度较高。设计并实现了基于混沌神经网络和C-MD（chaotic neural network-Merkle-Damgard）结构的带密钥哈希函数，为提高安全性改进了Merkle-Damgard结构，并提出C-MD结构，将该结构应用于哈希函数设计可以抵抗中间相遇攻击、多碰撞攻击以及针对长信息的第二原像攻击；使用混沌神经网络作为压缩函数，以提高哈希函数复杂度，增强函数的抗碰撞性，支持函数输出多种长度；设计一个明文预处理器，使用耦合映像格子产生与明文长度相关的混沌序列对明文进行填充，增强哈希函数抵抗长度扩展攻击的能力。仿真实验结果表明，提出的哈希函数效率优于 SHA-2、SHA-3 等的同类型混沌哈希函数，能够抵御第二原像攻击、多碰撞攻击和差分攻击等多种攻击方式，同时具有更好的抗碰撞性和映射均匀性。此外，提出的哈希函数可以输出不同长度的散列值，能够较好地应用在数字签名、密钥生成、基于哈希的消息认证码、确定性随机比特发生器等领域。

关键词: 哈希函数, 混沌神经网络, C-MD结构, 耦合映像格子

Abstract:

In recent years, widely used hash algorithms such as MD5 and SHA-1 have been found to have varying degrees of security risks.The iterative structure of the SHA-2 algorithm is similar to that of SHA-1, making it vulnerable to attacks as well.Meanwhile, SHA-3 has a complex internal structure and low implementation efficiency.To address these issues, a keyed hash function was designed and implemented based on chaotic neural network and C-MD structure.The approach involved improving the Merkle-Damgard structure by proposing the chaotic neural network Merkle-Damgard (C-MD) structure.This structure can be used to design a hash function that can withstand attacks such as the middle attack, multiple collision attack, and second pre-image attack for long information.Besides, the chaotic neural network was used as the compression function to increase the complexity of the hash function and improve its collision resistance, while also enabling it to output multiple lengths.Moreover, a plaintext preprocessor was designed, which used the coupled image lattice to generate chaos sequence related to the length of the plaintext to fill the plaintext, thus enhancing the ability of the hash function to resist length expansion attacks.Simulation results demonstrate that the proposed hash function performs faster than SHA-2, SHA-3 and the same type of chaotic hash function proposed by Teh et al.It can resist second pre-image attack, multi-collision attack and differential attack, while also exhibiting better collision resistance and mapping uniformity.In addition, the proposed Hash function can output Hash values of different lengths, making it suitable for use in digital signature, key generation, Hash-based message authentication code, deterministic random bit generator, and other application fields.

Key words: hash function, chaotic neural network, C-MD structure, coupled mapping lattice

中图分类号:

TP311

陈立全, 朱宇航, 王宇, 秦中元, 马旸. 基于混沌神经网络和C-MD结构的带密钥哈希函数[J]. 网络与信息安全学报, 2023, 9(3): 1-15.

Liquan CHEN, Yuhang ZHU, Yu WANG, Zhongyuan QIN, Yang MA. New hash function based on C-MD structure and chaotic neural network[J]. Chinese Journal of Network and Information Security, 2023, 9(3): 1-15.

图/表 20

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

表2

表3

对比实验（N=10 000） Table 3 Comparative experimental (N=10 000)"

算法	$\bar{B}$	P	?B	?P	B_min	B_max
MD5	64.03	50.02	5.660 0	4.42	40	82
文献[23]	63.88	49.91	5.750 0	4.50	—	—
文献[30]	63.99	49.99	5.660 0	4.40	40	85
文献[31]	63.92	43.94	7.430 5	5.80	—	—
文献[32]	64.02	50.01	5.640 0	4.40	—	—
文献[33]	64.00	50.00	5.440 0	4.25	—	—
文献[34]	63.91	49.94	5.617 2	4.39	—	—
文献[35]	63.15	50.11	5.770 0	4.51	—	—
文献[36]	63.88	49.91	5.660 0	4.41	42	84
C-MDhash (128 bit)	64.04	50.03	5.570 1	4.35	43	85
文献[37]	127.98	50.04	8.106 0	3.12	99	156
文献[38]	127.70	49.88	8.220 0	3.21	99	156
SHA-2 (256 bit)	128.81	50.03	8.109 3	3.56	100	155
SHA-3 (256 bit)	128.43	50.10	8.109 3	3.76	100	155
C-MDhash (256 bit)	127.99	50.00	8.075 2	3.15	99	157

表3

图10

图11

表4

表5

表6

表7

表8

表9

参考文献 42

[1]	LIN Z , GUYEUX C , YU S ,et al. On the use of chaotic iterations to design keyed hash function[J]. Cluster Computing, 2019,22(1).
[2]	ISLAM S H . Provably secure dynamic identity-based three-factor password authentication scheme using extended chaotic maps[J]. Nonlinear Dynamics, 2014,78(3).
[3]	CHAIN K , KUO W . A new digital signature scheme based on chaotic maps[J]. Nonlinear dynamics, 2013,74(4): 1003-1012.
[4]	DATCU O , MACOVEI C , HOBINCU R . Chaos based cryptographic pseudo-random number generator template with dynamic state change[J]. Applied Sciences. 2020,10(2).
[5]	WANG M , WANG X , ZHAO T ,et al. Spatiotemporal chaos in improved cross coupled map lattice and its application in a bit-level image encryption scheme[J]. Information Sciences, 2021,544: 1-24.
[6]	WANG Y , LIAO X , XIAO D ,et al. One-way hash function construction based on 2D coupled map lattices[J]. Information Sciences. 2008,178(5): 1391-1406.
[7]	WANG X , YU H . How to break MD5 and other hash functions[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2005. 19-35.
[8]	WANG X , YIN Y L , YU H . Finding collisions in the full SHA-1[C]// Annual International Cryptology Conference. 2005. 17-36.
[9]	GILBERT H , HANDSCHUH H . Security analysis of SHA-256 and sisters[C]// International Workshop on Selected Areas in Cryptography. 2003. 175-193.
[10]	HAWKES P , PADDON M , ROSE G G . On corrective patterns for the SHA-2 family[J]. IACR Cryptol.ePrint Arch.2004, 2004:207.
[11]	TUTUEVA A V , KARIMOV A I , MOYSIS L ,et al. Construction of one-way hash functions with increased key space using adaptive chaotic maps[J]. Chaos,Solitons ＆ Fractals, 2020,141:110344.
[12]	LI Y , XIAO D , DENG S ,et al. Parallel Hash function construction based on chaotic maps with changeable parameters[J]. Neural Computing and Applications. 2011,20(8): 1305-1312.
[13]	HE B , LEI P , PU Q ,et al. A method for designing hash function based on chaotic neural network[C]// International Workshop on Cloud Computing and Information Security (CCIS). 2013.
[14]	ROSENBLATT F . The perceptron:a probabilistic model for information storage and organization in the brain[J]. Psychological Review. 1958,65(6): 386.
[15]	LORENZ E N . Deterministic nonperiodic flow[J]. Journal of Atmospheric Sciences, 1963,20(2): 130-141.
[16]	HILBORN R C . Chaos and nonlinear dynamics:an introduction for scientists and engineers[M]. Oxford University Press on Demand, 2000.
[17]	DACHSELT F , SCHWARZ W . Chaos and cryptography[J]. IEEE Transactions on Circuits and Systems I:Fundamental Theory and Applications. 2001,48(12): 1498-1509.
[18]	TEH J S , SAMSUDIN A , AKHAVAN A . Parallel chaotic hash function based on the shuffle-exchange network[J]. Nonlinear Dynamics. 2015,81(3): 1067-1079.
[19]	XIAO D , LIAO X . A combined hash and encryption scheme by chaotic neural network[C]// International Symposium on Neural Networks. Springer, 2004. 633-638.
[20]	LIAN S , SUN J , WANG Z . Secure hash function based on neural network[J]. Neurocomputing, 2006,69(16-18): 2346-2350.
[21]	LIAN S , LIU Z , REN Z ,et al. Hash function based on chaotic neural networks[C]// 2006 IEEE International Symposium on Circuits and Systems. 2006.4.
[22]	YANG H , WONG K , LIAO X ,et al. One-way hash function construction based on chaotic map network[J]. Chaos,Solitons ＆Fractals. 2009,41(5): 2566-2574.
[23]	HUANG Z . A more secure parallel keyed hash function based on chaotic neural network[J]. Communications in Nonlinear Science and Numerical Simulation. 2011,16(8): 3245-3256.
[24]	ABDOUN N . Design,implementation and analysis of keyed hash functions based on chaotic maps and neural networks[R]. 2019.
[25]	KANEKO K . Pattern dynamics in spatiotemporal chaos:Pattern selection,diffusion of defect and pattern competition intermittency[J]. Physica D:Nonlinear Phenomena. 1989,34(1-2): 1-41.
[26]	CORON J , DODIS Y , MALINAUD C ,et al. Merkle-damg?rd revisited:how to construct a hash function[C]// Annual International Cryptology Conference. 2005. 430-448.
[27]	MERKLE R C . Secrecy,authentication,and public key systems[R]. Stanford University, 1979.
[28]	SHANNON C E . Communication theory of secrecy systems[J]. The Bell System Technical Journal. 1949,28(4): 656-715.
[29]	FEISTEL H . Cryptography and computer privacy[J]. Scientific American. 1973,228(5): 15-23.
[30]	LI Y , GE G , XIA D . Chaotic hash function based on the dynamic S-box with variable parameters[J]. Nonlinear Dynamics. 2016,84(4): 2387-2402.
[31]	XIAO D , LIAO X , DENG S . One-way hash function construction based on the chaotic map with changeable-parameter[J]. Chaos,Solitons ＆ Fractals. 2005,24(1): 65-71.
[32]	TEH J S , ALAWIDA M , HO J J . Unkeyed hash function based on chaotic sponge construction and fixed-point arithmetic[J]. Nonlinear Dynamics. 2020,100(1): 713-729.
[33]	TEH J S , TAN K , ALAWIDA M . A chaos-based keyed hash function based on fixed point representation[J]. Cluster Computing. 2019,22(2): 649-660.
[34]	XIAO D , LIAO X , DENG S . Parallel keyed hash function construction based on chaotic maps[J]. Physics Letters A. 2008,372(26): 4682-4688.
[35]	HUANG W , WANG L . A hash function based on sponge structure with chaotic map for spinal codes[C]// 2019 International Conference on Computer,Information and Telecommunication Systems (CITS). IEEE, 2019. 1-5.
[36]	ABDOUN N , EL ASSAD S , DEFORGES O ,et al. Design and security analysis of two robust keyed hash functions based on chaotic neural networks[J]. Journal of Ambient Intelligence and Humanized Computing, 2020,11(5): 2137-2161.
[37]	ALAWIDA M , SAMSUDIN A , ALAJARMEH N ,et al. A novel hash function based on a chaotic sponge and DNA sequence[J]. IEEE Access, 2021,9: 17882-17897.
[38]	ABDOUN N , EL ASSAD S , MANH HOANG T ,et al. Designing two secure keyed hash functions based on sponge construction and the chaotic neural network[J]. Entropy, 2020,22(9): 1012.
[39]	JOUX A . Multicollisions in iterated hash functions.Application to cascaded constructions[C]// Annual International Cryptology Conference. 2004: 306-316.
[40]	LUO Y L , DU M H . One-way hash function construction based on the spatiotemporal chaotic system[J]. Chinese Physics B. 2012,21(6): 60503.
[41]	LIU H , KADIR A , LIU J . Keyed hash function using hyper chaotic system with time-varying parameters perturbation[J]. IEEE Access. 2019,7: 37211-37219.
[42]	AHMAD M , KHURANA S , SINGH S ,et al. A simple secure hash function scheme using multiple chaotic maps[J]. 3D Research. 2017,8(2): 13.

条件	散列值
1	6BC35778C2CB3219D4DDE819655B04A521AA1A FE792638D0CB4E23240017DE0F
2	8148C288C3C6CF5B0A9E7FF0579F6A276237F313 C3393B210706B6641279B983
3	CFE8EB351410CA6C8CBA42037B950340BD9117D 4EAD2751613A2D1DC628CE85F
4	A0A84576903A0FB0B7945C7CFED47A6FF25A427 DD12CC343B72D5D2CCE78A238
5	7406B5B68EDDA9D39467E939E7B430DB4D497C9 1F1E0B03F509509DE5507AE96
6	F3D04C5A3C931EBF0AA8C83E9957425459BD7DF FF7AA4982425B8371A5653128

次数N	B	P	?B	?P	Bmin	B_max
256	127.50	49.81	7.9048	3.09	108	149
512	127.83	49.94	7.9852	3.12	106	150
1 024	128.02	50.01	8.2398	3.22	106	153
2 048	128.02	50.01	7.9457	3.10	104	153
10 000	127.99	50.00	8.0752	3.15	99	157

指标	P-value通过率	结果
Frequency	100%	Random
Frequency within a Block	100%	Random
Run	100%	Random
Longest Run of Ones in a Block	100%	Random
Binary Matrix Rank	100%	Random
Discrete Fourier Transform	100%	Random
Non-Overlapping Template Matching	100%	Random
Overlapping Template Matching	100%	Random
Maurer's Universal Statistical	100%	Random
Linear Complexity	100%	Random
Serial	100%	Random
Approximate Entropy	100%	Random
Cummulative Sums (Forward)	100%	Random
Cummulative Sums (Reverse)	100%	Random
Random Excursions	100%	Random
Random Excursions Variant	100%	Random

算法	Max	Min	Mean
MD5 (128 bit)	2 074	590	1 304
SHA-2 (256 bit)	3 819	1 789	2 707.10
SHA-3 (256 bit)	3 895	1 686	2 776.16
文献[13]	2 312	683	1 504
文献[30]	2 397	403	1 364
文献[31]	2 221	696	1 506
文献[32]	2 321	584	1 366
文献[33]	2 379	630	1 360.9
文献[34]	2 156	658	1 431.3
文献[36]	2 213	730	1 426.23
文献[37]	—	—	2 715
文献[38]	3 831	1 695	2 715.39
文献[40]	2 418	796	1 598.6
C-MDhash (128 bit)	2 168	517	1 380
C-MDhash (256 bit)	4 125	1 553	2 840.07

相同ASCII码数	碰撞次数理论值	碰撞次数实验值
0	8 822.2	8 851
1	1 107.8	1 027
2	67.3	114
3	2.6	8
4	0.1	0