Lorenz混沌系統(tǒng)的BLAKE哈希算法

王 娟， 周 鑫， 韓同壯

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

0 引 言

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

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

1 預(yù)備知識(shí)

1.1 BLAKE哈希函數(shù)

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

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

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

1.2 Lorenz混沌系統(tǒng)

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

(1)

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

2 BLAKE哈希算法

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

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

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

M←M‖10000…00164，

(2)

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

l——消息長(zhǎng)度。

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

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

(3)

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

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

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

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

初始化后得到的16個(gè)變量Vi作為輪函數(shù)G的輸入，總計(jì)循環(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)

式中：+——模加運(yùn)算；

⊕——異或運(yùn)算；

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

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

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

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

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

(6)

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

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

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

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

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

i=0,1,…,63，

(7)

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

mod——取模運(yùn)算。

(8)

3 BLAKE哈希性能

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

3.1 哈希值分布

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

圖4 隨機(jī)字符的分布Fig. 4 Random character distribution

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

3.2 初值敏感性

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

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

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

3.3 混淆與擴(kuò)散統(tǒng)計(jì)

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

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

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

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

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

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ù)就越可靠。評(píng)估哈希函數(shù)的抗碰撞性可以通過計(jì)算兩個(gè)消息的哈希值之間的距離，計(jì)算公式為：

(9)

式中：dh——兩個(gè)哈希值之間單位字段的絕對(duì)差值；

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

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

文獻(xiàn)[14]給出了dh的數(shù)學(xué)期望

(10)

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

表3N=10 000次數(shù)下絕對(duì)距離的測(cè)試結(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)移位運(yùn)算，保證壓縮結(jié)構(gòu)的前后不對(duì)稱，進(jìn)一步增強(qiáng)算法的混淆性和擴(kuò)散性。在Lorenz映射的初始狀態(tài)中引入中間變量，使每一輪混沌迭代都處于不同的運(yùn)動(dòng)狀態(tài)。最終的哈希值由每一輪混沌迭代后的中間變量、初始哈希、鹽值和計(jì)數(shù)器值計(jì)算得到。通過對(duì)該算法進(jìn)行測(cè)試分析，結(jié)果表明該算法有著良好的分布性和敏感性，相比原BLAKE算法和其他混沌哈希算法，本文算法的混淆性和擴(kuò)散性的指標(biāo)更接近理想值，雪崩特性更穩(wěn)定，抗碰撞攻擊的能力也更強(qiáng)。