朱 巍

(銳捷網(wǎng)絡(luò)股份有限公司，福建 福州 350002)

0 引言

單向Hash函數(shù)在數(shù)字簽名、身份認(rèn)證、動(dòng)態(tài)口令驗(yàn)證和完整性校驗(yàn)等領(lǐng)域中已經(jīng)得到了相當(dāng)廣泛的應(yīng)用。傳統(tǒng)的單向Hash方法有MD5、SHA-1、RIPEMD-160和SHA-256等[1-2]，它們大多數(shù)基于復(fù)雜度的假設(shè)，需要進(jìn)行大量的邏輯運(yùn)算[3-4]，另外相關(guān)研究發(fā)現(xiàn)，這些算法已經(jīng)并非足夠安全[5-7]。

基于神經(jīng)網(wǎng)絡(luò)的Hash構(gòu)造方法近些年來也引起了研究者的關(guān)注[8-12]。神經(jīng)網(wǎng)絡(luò)由于其內(nèi)部復(fù)雜性、混沌性、擴(kuò)散特性以及狀態(tài)或者結(jié)構(gòu)的時(shí)變性，已經(jīng)被廣泛地應(yīng)用于數(shù)據(jù)保護(hù)和加密算法中，并且隨著神經(jīng)網(wǎng)絡(luò)的單向特性(例如假設(shè)神經(jīng)網(wǎng)絡(luò)的輸出層維數(shù)小于隱含層維數(shù)，那么可以很容易地通過輸入得到輸出值，卻很難通過輸出值逆向推導(dǎo)出輸入)的不斷深入研究，在密碼學(xué)的單向Hash算法中，基于神經(jīng)網(wǎng)絡(luò)的方法也越來越多被提出。

然而目前大量基于神經(jīng)網(wǎng)絡(luò)的Hash方法并沒有針對身份認(rèn)證這一越來越廣泛的使用場景進(jìn)行優(yōu)化，依然采用空白填充的方法將用戶的密碼序列進(jìn)行對齊操作，這一步驟并不能增加信息的有效維度，并且加重了冗余計(jì)算，浪費(fèi)了密碼空間的復(fù)雜度[13-15]。另外，很多Hash方法中將原始字符序列的ASCII碼直接輸入到神經(jīng)網(wǎng)絡(luò)中，由于ASCII碼中存在很多‘0’的二進(jìn)制位[16]，并不能充分利用神經(jīng)網(wǎng)絡(luò)的輸入權(quán)值，并不利于最終Hash碼的魯棒性。

本文提出了一種基于非線性預(yù)處理和遞歸神經(jīng)網(wǎng)絡(luò)(RNN)的字符序列的Hash構(gòu)造方法，通過預(yù)先對字符序列進(jìn)行非線性處理，得到字符序列的目標(biāo)數(shù)值序列，并輸入到RNN中，經(jīng)RNN計(jì)算后得到最終的Hash值。通過理論分析和實(shí)驗(yàn)仿真，證明了本算法具有優(yōu)秀的混沌擴(kuò)散性質(zhì)、抗碰撞能力以及單向特性，因此具有良好的理論研究價(jià)值以及現(xiàn)實(shí)應(yīng)用意義。

1 Hash算法實(shí)現(xiàn)

1.1 非線性預(yù)處理

通過非線性預(yù)處理手段，可以將一維的字符序列映射到一個(gè)多維的混沌空間，有利于增強(qiáng)模型輸入的復(fù)雜性，從而獲得具有更加健壯的單向Hash函數(shù)構(gòu)造模型。

設(shè)用戶的字符序列X=[x1，x2,…，xN]T，其中N為序列的長度，序列中每個(gè)字符xi(1≤i≤N)均使用統(tǒng)一的字符編碼集U進(jìn)行二進(jìn)制編碼，例如ASCII編碼、UTF-8編碼等等。

Ci=normalize(Di)

1.2 RNN的構(gòu)建

圖1 網(wǎng)絡(luò)模型

RNN結(jié)構(gòu)如圖1所示。其中輸入層的節(jié)點(diǎn)數(shù)量為M(單個(gè)字符編碼長度)，輸出層的節(jié)點(diǎn)數(shù)量為期望得到的Hash碼的長度的1/k(k為預(yù)設(shè)的Hash碼增益長度系數(shù))，記為L，中間遞歸層的節(jié)點(diǎn)數(shù)量記為P，且需要保證P>L。

對輸入權(quán)值矩陣Win∈P×M、遞歸層反饋權(quán)值矩陣Wre∈P×P以及輸出權(quán)值矩陣Wout∈L×P，遞歸層偏置值Bre∈P×1，輸出層偏置值Bout∈L×1分別進(jìn)行隨機(jī)初始化。最后根據(jù)需要選定遞歸層和輸出層的激活函數(shù)，例如sigmod、tanh函數(shù)。

初始情況下，RNNN的隱含層神經(jīng)元狀態(tài)為0，經(jīng)過第一個(gè)輸入c1后，狀態(tài)為

S(1)=(Winc1+Bre)

(1)

從第二個(gè)輸入c2到最后一個(gè)輸入cN，隱含層神經(jīng)元狀態(tài)為

S(i)=(Winci+WreS(i-1)+Bre)

(2)

最終網(wǎng)絡(luò)N的輸出為

O(N)=(WoutS(N)+Bout)

(3)

1.3 Hash過程

Hash的具體實(shí)施步驟如下：

(1)初始化遞RNN，包括RNN的結(jié)構(gòu)規(guī)模、權(quán)值初始化以及隱含層神經(jīng)元狀態(tài)置0。

(2)設(shè)置Hash碼增益長度系數(shù)k，最終得到的Hash碼長度將為k倍的RNN輸出層維數(shù)，即kL。

(3)對密碼字符序列進(jìn)行非線性預(yù)處理，得到目標(biāo)數(shù)值序列。

(4)將每個(gè)密碼子夫的目標(biāo)數(shù)值序列依次輸入初始化好的RNN中，得到最終的網(wǎng)絡(luò)輸出O(N)。

(5)計(jì)算向量P=O(N)×10k，將P中每個(gè)元素值均轉(zhuǎn)換成十六進(jìn)制值，并取后位串聯(lián)組成最終的Hash碼。

2 實(shí)驗(yàn)

本文提出的算法采用MATLAB R2017a進(jìn)行了實(shí)驗(yàn)仿真，并且取得了較好的實(shí)驗(yàn)效果，其相關(guān)代碼可以從GitHub下載：https://github.com/JuiLangCHU/NP_ANN_HashAlgorithm。

這里假設(shè)有密碼文本如下：

密碼1：1b2FC1Pe6B94aZbD4740D7kd9L9B844f9g

密碼2：2b2FC1Pe6B94aZbD4740D7kd9L9B844f9g

密碼3：1b2FC1Pe6B94aZbD4840D7kd9L9B844f9g

密碼4：1b2FC1Pe6B94aZbD4740D7kd9L9B844f9h

其中密碼2與密碼1僅首部第一個(gè)字符不同(1→2)，密碼3與密碼1僅中間第18個(gè)字符不同(7→8)，密碼4與密碼1僅尾部最后一個(gè)字符不同(g→h)。4組密碼的Hash值如圖2所示。

圖2 4組密碼序列的Hash值0、1序列圖形

2.1 單向性分析

對于神經(jīng)網(wǎng)絡(luò)的最終輸出向量O，由于從小數(shù)點(diǎn)后第二位開始取若干位作為Hash碼，因此通過Hash值逆推網(wǎng)絡(luò)輸出的復(fù)雜度為o(24L)，L為神經(jīng)網(wǎng)絡(luò)的輸出層維度，可見當(dāng)網(wǎng)絡(luò)輸出層維數(shù)較大時(shí)，此步驟的計(jì)算復(fù)雜度相當(dāng)高。

圖4 改變密碼序列不同位置的一個(gè)字符時(shí)，Hash碼發(fā)生改變的比特?cái)?shù)量(總Hash碼長度為128)

另外，根據(jù)神經(jīng)網(wǎng)絡(luò)最終輸出公式(3)得:

WoutS(N)=f-1(O)-Bout

(4)

其中，Wout∈L×P，S∈P×1，令φ=f-1(O)-Bout∈L×1，對公式(4)展開，可以得到：

?

2.2 碰撞性分析

抗碰撞是指對于兩個(gè)不同的原始輸入序列，經(jīng)過Hash算法后得到的Hash值相同的概率非常小。實(shí)驗(yàn)中，對于1個(gè)密碼序列任意改變其中某一位置的一個(gè)字符，經(jīng)過本算法得到128 bit的Hash碼，并統(tǒng)計(jì)相同位置上對應(yīng)的Hash值相同的次數(shù)，經(jīng)仿真，統(tǒng)計(jì)結(jié)果分布如圖3所示，超過18個(gè)字符相等的Hash碼出現(xiàn)概率為0，說明算法具有良好的抗碰撞能力。

圖3 相同位置具有相同Hash值的統(tǒng)計(jì)次數(shù)

2.3 擴(kuò)散性和均衡性分析

隨機(jī)取一段密碼序列，并分別更改密碼序列的首部、中部、尾部以及隨機(jī)位置的一個(gè)字符，然后計(jì)算原始密碼以及字符發(fā)生變化之后的Hash值，實(shí)驗(yàn)中Hash碼的長度為128 bit。通過1 000次測試，計(jì)算得Hash碼發(fā)生變化的比特?cái)?shù)量分別為64.194、64.111、63.899、64.161，如圖4所示。

由此可見，即使是不同位置的密碼字符出現(xiàn)變化，對最終的Hash碼的影響幾乎是相同的，說明該Hash算法的平衡性非常均勻，并且最終Hash碼的比特變化數(shù)量均非常接近Hash碼總長度的50%，即64 bit，也說明了該Hash算法的混亂擴(kuò)散性比較出色，能夠敏銳地感知到原始密文序列出現(xiàn)的微小差異。

2.4 信息熵測試

為了度量一段消息中所含的信息容量，1948年由SHANNON C E提出了信息熵的概念，在信息論中，當(dāng)熵最大時(shí)，信息量最大。對于Hash函數(shù)而言，熵最大時(shí)，Hash值的分布也越混亂，信息復(fù)雜度越高。熵的數(shù)學(xué)度量模型為：

且滿足

0≤H(X)≤log|X|

其中|X|為取值個(gè)數(shù)。僅當(dāng)變量X符合均勻分布時(shí)，H(X)=log|X|，即此時(shí)H(X)為最大熵。

為此，計(jì)算序列Hash碼的信息熵，X為Hash碼中不同字符的集合。

由于這里Hash碼的取值為十六進(jìn)制的0至F，理論上的熵最大值為log216=4 bit。對比以上4組密碼序列的熵值(如表1所示)，可見已比較接近最大熵，表明其Hash碼的混亂程度也趨近最大。

表格1 不同密碼序列的信息熵值

3 結(jié)論

本文提出了一種基于非線性預(yù)處理和RNN相結(jié)合的密碼文本序列Hash算法，其中非線性預(yù)處理可以顯著地?cái)U(kuò)大遞歸神經(jīng)網(wǎng)絡(luò)輸入層中不同字符的輸入差異性，從而實(shí)現(xiàn)Hash構(gòu)造函數(shù)對于微小差異的序列具有高敏感性。結(jié)合RNN中的參數(shù)敏感性、非線性等特點(diǎn)，可以實(shí)現(xiàn)安全地抗攻擊的Hash構(gòu)造方法，相關(guān)實(shí)驗(yàn)分析也證明了其有效性。此外由于RNN中的參數(shù)取值靈活，網(wǎng)絡(luò)的規(guī)模也可以根據(jù)實(shí)際需要進(jìn)行調(diào)整，因此在Hash實(shí)現(xiàn)中不需要對網(wǎng)絡(luò)進(jìn)行訓(xùn)練。綜上所述，本文提出的算法具有高靈活性、易用性、擴(kuò)展性和用戶自定義配置性。

[1] RONALD L. RIVEST. The MD5 message-digest algorithm [R].MIT Laboratory for Computer Science and RSA Data Security, 1992.

[2] Federal information processing standards publication 180-1. secure hash standard [S]. 1995.

[3] Wang Shihong, Hu Gang. Coupled map lattice based hash function with collision resistance in single-iteration computation [J]. Information Sciences. 2012 Jul 15;195:266-76.

[4] WANG SHIHONG, LI DA, ZHOU HU. Collision analysis of a chaos-based hash function with both modification detection and localization capability [J]. Communications in Nonlinear Science and Numerical Simulation, 2012, 195(13):166-276.

[5] Wang Xiaoyun, Yao Fang. Crypt analysis of SHA-1 hash function [C].Proceedings of the 25th International Cryptology Conference, 2005:19-35.

[6] Xiao Di, Liao Xiaofeng, Wang Yong. Improcing the security of a parallel keyed hash function based on chaos map [J]. Physics Letter A, 2009:4346-4353.

[7] Yang Gang, Yi Junyan. Dynamics characteristic of a multiple chaotic neural network and its application[J]. Soft Computing, 2013:783-792.

[8] ABDOUN N, ASSAD S E, TAHA M A, et al. Secure Hash Algorithm based on Efficient Chaotic Neural Network [C]. 2016 International Conference on Communications. IEEE, 2016: 405-410.

[10] 陳軍, 韋鵬程, 張偉, 等. 基于RBF神經(jīng)網(wǎng)絡(luò)和混沌映射的Hash函數(shù)構(gòu)造 [J]. 計(jì)算機(jī)科學(xué), 2006, 33(8):198-201.

[11] 李國剛, 鐘超林, 藺小梅. OHNN新的分組Hash算法 [J]. 華僑大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,36(4):393-398.

[12] XIAO D, LIAO X, WANG Y. Parallel keyed hash function construction based on chaotic neural network [J]. Neurocomputing, 2009, 72(10):2288-2296.

[13] LIAN S, SUN J, WANG Z. Secure hash function based on neural network [J]. Neurocomputing, 2006,69(16):2346-2350.

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

[15] LIAN S, LIU Z, REN Z, et al. Hash function based on chaotic neural networks [C]. Circuits and Systems, 2006.ISCAS 2006.IEEE, 2006: 4.

[16] URBANOVICH P, PLONKOWSKI M, CHURIKOV K. The appearance of conflict when using the chaos function for calculating the hash code [J]. Network, 2012, 88(11b): 346-347.