基于非線性預處理和神經(jīng)網(wǎng)絡的字符序列單向Hash算法

朱 巍

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

0 引言

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

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

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

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

1 Hash算法實現(xiàn)

1.1 非線性預處理

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

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

Ci=normalize(Di)

1.2 RNN的構(gòu)建

圖1 網(wǎng)絡模型

RNN結(jié)構(gòu)如圖1所示。其中輸入層的節(jié)點數(shù)量為M(單個字符編碼長度)，輸出層的節(jié)點數(shù)量為期望得到的Hash碼的長度的1/k(k為預設的Hash碼增益長度系數(shù))，記為L，中間遞歸層的節(jié)點數(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ù)需要選定遞歸層和輸出層的激活函數(shù)，例如sigmod、tanh函數(shù)。

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

S(1)=(Winc1+Bre)

(1)

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

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

(2)

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

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

(3)

1.3 Hash過程

Hash的具體實施步驟如下：

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

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

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

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

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

2 實驗

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

這里假設有密碼文本如下：

密碼1：1b2FC1Pe6B94aZbD4740D7kd9L9B844f9g

密碼2：2b2FC1Pe6B94aZbD4740D7kd9L9B844f9g

密碼3：1b2FC1Pe6B94aZbD4840D7kd9L9B844f9g

密碼4：1b2FC1Pe6B94aZbD4740D7kd9L9B844f9h

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

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

2.1 單向性分析

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

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

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

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

(4)

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

?

2.2 碰撞性分析

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

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

2.3 擴散性和均衡性分析

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

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

2.4 信息熵測試

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

且滿足

0≤H(X)≤log|X|

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

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

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

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

3 結(jié)論

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

[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)絡和混沌映射的Hash函數(shù)構(gòu)造 [J]. 計算機科學, 2006, 33(8):198-201.

[11] 李國剛, 鐘超林, 藺小梅. OHNN新的分組Hash算法 [J]. 華僑大學學報(自然科學版), 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.