王 娟， 周 鑫， 韓同壯

(黑龍江科技大學 電子與信息工程學院， 哈爾濱150022)

0 引 言

哈希函數(shù)是現(xiàn)代密碼學中一類重要的基礎(chǔ)密碼算法，它將任意長度的數(shù)據(jù)輸入經(jīng)過變化得到固定長度的哈希值，在密碼協(xié)議、數(shù)字簽名、完整性認證等領(lǐng)域具有廣泛應(yīng)用。作為消息摘要函數(shù)標準SHA-3的第二輪候選算法，BLAKE哈希算法[1]運算速度快且安全性高。近年來，其相關(guān)密碼攻擊正被逐漸重視。Aumasson等[2]給出BLAKE-256壓縮函數(shù)中間4輪的幾乎碰撞攻擊。Biryukov等[3]對BLAKE的7輪壓縮函數(shù)和8輪置換函數(shù)進行了攻擊，Dunkelman等[4]給出了BLAKE置換函數(shù)中間6輪的差分區(qū)分器。上述攻擊表明，BLAKE哈希算法仍存在一定的安全隱患。

混沌系統(tǒng)的運動特征表現(xiàn)為對初始狀態(tài)極度敏感性、確定的隨機性、混沌序列的遍歷性，這些特性恰好滿足哈希函數(shù)中壓縮函數(shù)的單向性、初值敏感性等要求。近年來，研究者們逐漸地使用混沌系統(tǒng)來構(gòu)建更安全的哈希算法，在對混沌哈希算法的研究中，最為常用的混沌系統(tǒng)多數(shù)為低維混沌系統(tǒng)，但隨著混沌研究的不斷進展，研究者發(fā)現(xiàn)低維混沌系統(tǒng)由于迭代方式簡單、滿映射區(qū)間小等原因已經(jīng)不足以支撐哈希算法的安全性，進而轉(zhuǎn)向研究并應(yīng)用高維混沌系統(tǒng)[5]。三維Lorenz混沌系統(tǒng)具有復(fù)雜的系統(tǒng)結(jié)構(gòu)使輸出更難預(yù)測，同時應(yīng)用3個混沌使應(yīng)用更加靈活，3個初值和3個參數(shù)構(gòu)成的解空間大大高于低維混沌，由于具有更高的維數(shù)和復(fù)雜程度使其具有更為優(yōu)異的動力學特性[6]。筆者為了進一步增強BLAKE哈希算法的安全性，使用優(yōu)化的輪函數(shù)和高維Lorenz混沌系統(tǒng)共同構(gòu)建壓縮函數(shù)，根據(jù)混沌系統(tǒng)對參數(shù)具有很高的敏感性，擴大壓縮函數(shù)混淆和擴散的范圍，增強算法的安全性。

1 預(yù)備知識

1.1 BLAKE哈希函數(shù)

BLAKE算法以安全性強、效率高等優(yōu)勢，于2012年被美國國家標準與技術(shù)研究所(National institute of standards and technology，NIST)征集并入選為SHA-3的最終決賽輪算法之一。BLAKE算法內(nèi)部采取的局部寬管道結(jié)構(gòu)如圖1所示，使用HAIFA迭代框架[7]，其主要思想是在壓縮過程中引入鹽值和計數(shù)值兩個額外的參數(shù)。該算法壓縮函數(shù)是基于ChaCha[8]核心函數(shù)設(shè)計，內(nèi)部的運算主要是異或、模加和循環(huán)移位。

圖1 BLAKE算法寬管道結(jié)構(gòu)Fig. 1 Wide pipeline structure of BLAKE algorithm

BLAKE算法家族有BLAKE-224、BLAKE-256、BLAKE-384和BLAKE-512四種哈希算法。各個算法的基本原理均相同，只是在消息摘要值的長度、部分輸入輸出參數(shù)、循環(huán)計算輪數(shù)和循環(huán)移位數(shù)等方面略有不同，摘要輸出的長度越長，則安全性越高、效率越低。從安全和效率綜合考慮后，文中主要研究的算法是BLAKE-256。

1.2 Lorenz混沌系統(tǒng)

Lorenz混沌系統(tǒng)是一個經(jīng)典的三維連續(xù)混沌系統(tǒng)，是氣象學家Lorenz在1963年研究氣象學時發(fā)現(xiàn)的，其微分方程形式的數(shù)學表達式為：

(1)

式中,a、b、c——Lorenz混沌系統(tǒng)的控制參數(shù)，一般采用的典型取值為a=10、b=28、c=8/3。在保證a和c不變的前提下，b>27.74時，Lorenz混沌系統(tǒng)處于混沌運動狀態(tài)。

2 BLAKE哈希算法

文中哈希算法使用Lorenz混沌迭代和BLAKE算法的輪函數(shù)作為主函數(shù)，使用鹽值和計數(shù)器值為參數(shù)作為輪函數(shù)和Lorenz系統(tǒng)的輸入，增加了哈希算法隨機性。并對初值和中間變量進行優(yōu)化，使其在引入混沌迭代情況下保障其算法效率，整個算法的流程如圖2所示。

圖2 基于Lorenz系統(tǒng)的哈希算法結(jié)構(gòu) Fig. 2 Structure of hash algorithm based on Lorenz system

首先將消息進行填充，使消息的長度為512比特的整數(shù)倍。填充規(guī)則有

M←M‖10000…00164，

(2)

式中：M——消息最后不足512比特的數(shù)據(jù)；

l——消息長度。

先在M后面添加1個1和若干個0，使其消息模512等于447，在添加一個1和64比特表示的消息長度，最后使消息長度為512比特的整數(shù)倍。

對算法中有16個中間變量Vi(0≤i≤15)進行賦值，通過下列方程得到

(3)

式中:hi——初始哈希值，(0≤i≤7)；

ci——常數(shù)，皆為固定數(shù)值，(0≤i≤7)；

ti——計數(shù)器，由消息原始長度與填充后長度的累加得到，(0≤i≤1)；

si——鹽值，隨機賦值生成，(0≤i≤3)。

初始化后得到的16個變量Vi作為輪函數(shù)G的輸入，總計循環(huán)14輪，分別為

G0(V0,V4,V8,V12)G1(V1,V5,V9,V13)G2(V2,V6,V10,V14)G3(V3,V7,V11,V15)G4(V0,V5,V10,V15)G5(V1,V6,V11,V12)G6(V2,V7,V8,V13)G7(V3,V4,V9,V14)，

(4)

式(4)中，每輪的Gi(a,b,c,d)有如下變換

(5)

式中：+——模加運算；

⊕——異或運算；

>>> ——右循環(huán)移位操作；

mi、cj——輸入的相應(yīng)消息塊或常量。

相比原BLAKE算法的壓縮結(jié)構(gòu)上，新輪函數(shù)G的前后操作不對稱，還增加了循環(huán)移位操作，更進一步的增強了輪函數(shù)G的擴散性和混淆性。

混沌迭代結(jié)構(gòu)，如圖3所示，經(jīng)過10輪的壓縮循環(huán)后，將Vi通過Lorenz混沌系統(tǒng)的多次迭代，得出的新值作為新的Vi值。

將Vi通過進制轉(zhuǎn)化為64個ASCII值，為了得到{0,1}之間的初值，對ASCII值進行如下變換

(6)

式中：n——迭代的輪數(shù)；

i——初值的序列數(shù)；

Vn(i)——第n輪迭代的第i個數(shù)。

圖3 混沌迭代結(jié)構(gòu)Fig. 3 Chaotic iterative structure

第一個值V0(0)作為Lorenz映射的參數(shù)b，初值以三個為一組作為Lorenz映射的初值輸入，并行混沌迭代50輪，其中第一組Lorenz混沌系統(tǒng)的輸出值(V50(1))與V0(0)異或得到V50(0)，然后將所有的值再進行如下逆變換

i=0,1,…,63，

(7)

式中：abs(t)——對t值取其絕對值；

mod——取模運算。

(8)

3 BLAKE哈希性能

將從哈希值的分布、初值敏感性、明文與摘要之間的混淆與擴散特性統(tǒng)計和抗碰撞測試等多個方面對所提算法的性能進行分析和討論。

3.1 哈希值分布

輸出哈希的均勻分布是哈希函數(shù)重要的安全功能之一。為了測試哈希函數(shù)的分布性，采用一條由隨機字符組成的消息；將其轉(zhuǎn)換為ASCII值并在圖4中進行描述。采用文中的算法得到其哈希值，在圖5中以十六進制格式顯示。從結(jié)果可以看出哈希值分布均勻，明文基本散布在某一有限的區(qū)域內(nèi)，而得到的哈希值卻不規(guī)則均勻分布在整個空間。實驗結(jié)果表明所提的算法有很好的分布性。

圖4 隨機字符的分布Fig. 4 Random character distribution

圖5 哈希值的分布Fig. 5 Distribution of hash value

3.2 初值敏感性

為了測試所得的哈希值對函數(shù)的初值敏感性，任選一段文本：“Chaotic motion is a complex long-term motion unique to deterministic nonlinear dynamic systems.”。按照以下6種情況進行測試：C1：計算給定消息的哈希值。C2：將單詞“a”改為“A”。C3：句末的“.”改為“，”。C4：單詞“l(fā)ong-term”改為“l(fā)ongterm”。C5：在單詞“to”前加個“3”。C6：句末增加一個空格。

對以上消息所得出的256比特值如圖6所示。由圖6可以看出，消息中的任何位置發(fā)生單個位更改，也會導(dǎo)致輸出的哈希值發(fā)生極大的變化。這證明所提出的方案對于輸入消息的改變具有很高的敏感性，很好地滿足了加密散列的單向性質(zhì)。

圖6 不同情況的哈希值Fig. 6 Hash values in different cases

3.3 混淆與擴散統(tǒng)計

對哈希函數(shù)的混淆性和擴散性測試主要是進行雪崩效應(yīng)測試，測試方案為：隨機選取一段消息并計算其哈希值，然后在消息中任意改變1比特，并計算改變后消息的值，比較消息改變前后的結(jié)果，得到相應(yīng)的變化比特數(shù)。這樣的測試重復(fù)進行N=10 000次，得到的變化比特數(shù)分布情況如圖7所示。結(jié)果表明，測試所得的變化比特數(shù)均介于101至158之間，且主要集中在理想值128附近。

圖7 哈希值變化比特數(shù)的分布Fig. 7 Hash value change bit number distribution map

表1 新算法的雪崩特性統(tǒng)計

Table 1 Statistics of avalanche characteristics of newalgorithm

NBminBmaxB-P%ΔBΔP%512105151128.4150.168.053.15 1 024103154128.1650.068.143.182 048103157128.2150.088.213.2110 000101158127.9849.998.053.14

在統(tǒng)計性能的基礎(chǔ)上，將文中提出的算法與最近的一些基于混沌的哈希算法進行了比較，結(jié)果如表2所示(由于哈希值不同，僅列出了 和 的比較結(jié)果)。從表中可以看出文中算法的 最接近理想值50，混淆和擴散性最好， 的值最小，雪崩特性最穩(wěn)定。

表2N=10 000次數(shù)下的統(tǒng)計性能比較

Table 2 Comparison of statistical performance underN=10 000 times%

概率MD5[9]Zhang's[10]Guo's[11]Li's[12]Wang's[13]BLAKE[1]文中算法P50.0249.9649.5350.2150.1150.1249.99ΔP4.424.513.925.814.513.573.15

3.4 抗碰撞

碰撞是指給定不同的明文，經(jīng)過相同的單向哈希算法得到的哈希值卻是相同的。算法的抗碰撞性能越好，表明哈希函數(shù)就越可靠。評估哈希函數(shù)的抗碰撞性可以通過計算兩個消息的哈希值之間的距離，計算公式為：

(9)

式中：dh——兩個哈希值之間單位字段的絕對差值；

ai、bi——兩個哈希值的第i個ASCII字符；

t(x)——將x對應(yīng)的ASCII字符轉(zhuǎn)化為十進制的值。

文獻[14]給出了dh的數(shù)學期望

(10)

測試N=10 000次時，與其他混沌哈希算法相比較的結(jié)果如表3所示。從結(jié)果來看，本算法單位字段的值為85.31，最接近于理論平均值85.33，表明新算法的抗碰撞性能最好，能夠有效抵抗偽造攻擊。

表3N=10 000次數(shù)下絕對距離的測試結(jié)果

Table 3 Test results of absolute distance atN=10 000 times

算法最大值最小值平均值單位字段的平均值MD5[9]4 1481 1802 60881.50Guo's[11]4 4481 1462 80287.56Li's[12]4 4601 4882 74285.69Wang's[13]4 4121 1662 80087.50Akhavan's[14]4 2981 2062 63882.44BLAKE[1]4 1921 4472 73485.44文中算法4 1091 4312 73085.31

4 結(jié)束語

提出了一種基于高維混沌系統(tǒng)的哈希算法，該算法采用BLAKE函數(shù)的輪函數(shù)和Lorenz混沌迭代作為壓縮函數(shù)，在循環(huán)壓縮中增加循環(huán)移位運算，保證壓縮結(jié)構(gòu)的前后不對稱，進一步增強算法的混淆性和擴散性。在Lorenz映射的初始狀態(tài)中引入中間變量，使每一輪混沌迭代都處于不同的運動狀態(tài)。最終的哈希值由每一輪混沌迭代后的中間變量、初始哈希、鹽值和計數(shù)器值計算得到。通過對該算法進行測試分析，結(jié)果表明該算法有著良好的分布性和敏感性，相比原BLAKE算法和其他混沌哈希算法，本文算法的混淆性和擴散性的指標更接近理想值，雪崩特性更穩(wěn)定，抗碰撞攻擊的能力也更強。