并行耦合動(dòng)態(tài)整數(shù)帳篷Hash函數(shù)設(shè)計(jì)

劉玉杰 劉建東 劉 博,2 鐘 鳴 李 博

1(北京石油化工學(xué)院信息工程學(xué)院 北京 102617) 2(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院 北京 100029)

0 引 言

Hash函數(shù)最早由Knuth在1950年提出，它是一種單向函數(shù)，用于將大數(shù)據(jù)塊壓縮為該數(shù)據(jù)的較小的固定大小表示形式，稱為消息摘要或Hash值[1-2]。作為現(xiàn)代密碼學(xué)的重要研究?jī)?nèi)容之一，Hash函數(shù)在信息安全領(lǐng)域中起著至關(guān)重要的作用，同時(shí)也是近幾年正興起的區(qū)塊鏈技術(shù)中的關(guān)鍵技術(shù)之一，密碼學(xué)家王小云因其所帶領(lǐng)的課題組成功碰撞了MD5等經(jīng)典加密算法獲得2019年未來科學(xué)大獎(jiǎng)“數(shù)學(xué)與計(jì)算機(jī)科學(xué)獎(jiǎng)”，Hash函數(shù)的研究再一次獲得了社會(huì)各界的關(guān)注。

安全是哈希函數(shù)的首要要求[3]，在MD5等傳統(tǒng)Hash算法被王小云教授課題組成功碰撞后，業(yè)界迫切需要尋找更加安全的Hash函數(shù)構(gòu)造方法。傳統(tǒng)的Hash函數(shù)構(gòu)造大多使用按位AND、OR、XOR和MOD等運(yùn)算符來對(duì)數(shù)據(jù)進(jìn)行雜湊處理，以增強(qiáng)其哈希輸出中的隨機(jī)性。文獻(xiàn)[4]提出了一種具有多項(xiàng)式函數(shù)的構(gòu)造方法，提升了部分性能，但是同樣避免不了使用上述運(yùn)算符。2002年出現(xiàn)了一種利用混沌模型構(gòu)造Hash函數(shù)的方法，其利用較少的運(yùn)算符就能充分使數(shù)據(jù)隨機(jī)性增強(qiáng)，成為一種新的研究思路，并且出現(xiàn)了較多的基于混沌映射的Hash算法?；煦缦到y(tǒng)具有良好的特征，與加密要求有很強(qiáng)的關(guān)聯(lián)性[5-6]。典型的混沌系統(tǒng)模型主要有連續(xù)系統(tǒng)模型和離散系統(tǒng)模型，帳篷映射就是一種經(jīng)典的離散混沌系統(tǒng)。將基于混沌的Hash函數(shù)構(gòu)造方法與傳統(tǒng)Hash函數(shù)構(gòu)造方法相結(jié)合，即將帳篷映射整數(shù)化，既能凸顯出基于混沌的Hash函數(shù)的優(yōu)良特性，又能避免出現(xiàn)因精度效應(yīng)導(dǎo)致的安全缺陷。同時(shí)通過添加動(dòng)態(tài)參數(shù)，成立動(dòng)態(tài)整數(shù)帳篷映射，這樣既可以避免整數(shù)帳篷映射的短周期行為，又保有其伸長(zhǎng)與折疊的非線性本質(zhì)。最后利用耦合映象格子對(duì)動(dòng)態(tài)整數(shù)帳篷映射進(jìn)行耦合，極大地提高了系統(tǒng)的混亂與擴(kuò)散性質(zhì)，進(jìn)而使其在應(yīng)用中具有更高的安全性[7]。

除安全性問題外，效率是Hash函數(shù)的另一個(gè)重要問題。Rivest在Crypto2008上提出了MD6算法，MD6算法的數(shù)據(jù)塊大小為512字節(jié)，(而MD5的數(shù)據(jù)塊大小是512比特)，鏈值長(zhǎng)度為1 024比特，可從其中摘出0～512比特的值作為最終Hash值，最重要的是MD6算法在其中增加了并行機(jī)制，非常適用于多核CPU，契合了時(shí)代的發(fā)展。另外SHA系列也是利用MD迭代結(jié)構(gòu)，其效率隨著文件大小的增加而迅速下降，所以目前研究方向是提出一種新穎的Hash函數(shù)，這種Hash函數(shù)在處理大量數(shù)據(jù)時(shí)可以保持較高的效率[8]。隨著信息時(shí)代的發(fā)展，產(chǎn)生巨大信息的同時(shí)，也要能夠快速地對(duì)大量數(shù)據(jù)進(jìn)行處理，多核處理器技術(shù)(CMP)的發(fā)展提供了快速運(yùn)算的可能。基于上述原因，本文采用MD6算法框架，利用多核處理器技術(shù)，設(shè)計(jì)出一種核心算法采用耦合動(dòng)態(tài)整數(shù)帳篷映象格子模型的新型并行Hash函數(shù)算法。

1 耦合動(dòng)態(tài)整數(shù)帳篷映象格子模型

1.1 動(dòng)態(tài)整數(shù)帳篷映射

將帳篷映射進(jìn)行整數(shù)化，并引入動(dòng)態(tài)參量，即得到動(dòng)態(tài)整數(shù)帳篷映射。它不僅解決了整數(shù)帳篷映射的短周期問題，還具備帳篷映射均勻分布的特性，性能優(yōu)良[7]。其數(shù)學(xué)描述如下：

(1)

gi=(xi+ki)mod 2n

(2)

F映射中(圖1)，ki為動(dòng)態(tài)變量，表示“帳篷”橫坐標(biāo)移動(dòng)的距離，控制其水平移動(dòng)。xi表示第i步迭代結(jié)果；2n為x(i)取值的整數(shù)集上界。迭代運(yùn)算中，隨著i值的變化，ki取不同的值，即ki的值與算法迭代步數(shù)有關(guān)，既保證了動(dòng)態(tài)性又保證了的算法的穩(wěn)定性，不會(huì)使得因動(dòng)態(tài)參數(shù)改變而使最終值改變。

圖1 動(dòng)態(tài)整數(shù)帳篷映射

1.2 耦合動(dòng)態(tài)整數(shù)帳篷映象格子模型

利用耦合映像格子模型(CML)將動(dòng)態(tài)整數(shù)帳篷映射進(jìn)行耦合，進(jìn)而獲得性能更好的密碼序列。CML所生成序列的復(fù)雜性直接影響其構(gòu)造出的密碼系統(tǒng)的安全性，而其又受到所選用的非線性函數(shù)、系統(tǒng)格子規(guī)模大小、耦合系數(shù)及非線性函數(shù)參數(shù)的取值等的影響[9]，將耦合映象格子系統(tǒng)的非線性函數(shù)選為動(dòng)態(tài)整數(shù)帳篷映射，耦合方式如下：

xi(n+1)=

(f[xi(n)]+f[xi-1(n)]+f[xi+1(n)])mod 2k

(3)

式中：xi(n+1)表示第i個(gè)格點(diǎn)的第n+1步迭代所得狀態(tài)值；f(·)表示格點(diǎn)的非線性函數(shù))；2k為格點(diǎn)取值的狀態(tài)數(shù)目。每一個(gè)格點(diǎn)既由上一步迭代的三個(gè)格點(diǎn)值所影響，又能對(duì)下一步迭代的三個(gè)格點(diǎn)產(chǎn)生影響，其過程如圖2所示。圖2中，實(shí)心點(diǎn)表示格點(diǎn)，空心點(diǎn)表示虛擬格點(diǎn)，虛擬格點(diǎn)為迭代計(jì)算提供邊界條件[9]。

圖2 模型耦合方式

2 多核并行計(jì)算技術(shù)

多核處理技術(shù)(CMP)是在一塊芯片上集成兩個(gè)及以上的處理器核，通過這種方式來增強(qiáng)芯片計(jì)算性能。CMP通過在兩個(gè)及以上的CPU核上分配工作負(fù)荷，并且依靠?jī)?nèi)存和輸入輸出的高速片上互聯(lián)和高帶寬管道對(duì)系統(tǒng)性能進(jìn)行提升。較之當(dāng)前的單核處理器，多核處理器能帶來更多的性能和生產(chǎn)力能效。因此針對(duì)多核處理器設(shè)計(jì)對(duì)應(yīng)的加密算法能夠使得雜湊算法更加快捷。

同時(shí)利用英特爾的超線程技術(shù)，把多線程處理器內(nèi)部的兩個(gè)邏輯內(nèi)核模擬成兩個(gè)物理芯片，舉例來說就是單個(gè)處理器就能夠模擬出兩個(gè)線程來實(shí)現(xiàn)并行，進(jìn)而兼容多線程操作系統(tǒng)和軟件。超線程技術(shù)充分利用空閑CPU資源，在相同時(shí)間內(nèi)完成更多的工作。通過超線程技術(shù)，可以將雙核心的處理器，模擬出4個(gè)線程處理器的效果。本文所有測(cè)試都是在Intel(R) Core(TM) i5- 6200U@2.30 GHz 2.40 GHz雙核處理器，利用超線程技術(shù)模擬出四個(gè)線程實(shí)現(xiàn)。

各種并行計(jì)算平臺(tái)的存在允許各種算法和操作的并行實(shí)現(xiàn)。一種流行的并行平臺(tái)是共享內(nèi)存并行機(jī)(SMPM)，它是一種多核共享內(nèi)存計(jì)算機(jī)，通常使用OpenMP(開放式多處理)API[10-11]。OpenMP采用Fork-Join模型，如圖3所示。

圖3 Fork-Join模型

OpenMP由Compiler Directives(編譯指導(dǎo)語(yǔ)句)、Run-time Library Functions(庫(kù)函數(shù))等組成，使用方式比較容易，很多研究人員做并行算法都會(huì)首先選擇使用。本文算法也是使用了openMP中的sections-section實(shí)現(xiàn)了并行。

3 并行Hash函數(shù)構(gòu)造

3.1 運(yùn)算模式

執(zhí)行模式的確定。參數(shù)L確定如圖4的Merkle樹的執(zhí)行模式。MD6中L默認(rèn)值為64，此時(shí)為一顆完整的Merkle樹，執(zhí)行模式為并行模式；如果L值等于0，則為串行模式，按順序串行執(zhí)行；如果L的值介于0和64之間，則進(jìn)行混合模式，首先從層次0到層次L，然后在每個(gè)層次內(nèi)按順序壓縮函數(shù)。本文中取L=64，以實(shí)現(xiàn)并行化。

數(shù)據(jù)填充。算法的輸入?yún)⒘繛殚L(zhǎng)度小于264比特的消息，算法中的計(jì)量單位是“字”，一個(gè)“字”等于8字節(jié)，圖4中每個(gè)節(jié)點(diǎn)的大小為16個(gè)“字”，所以進(jìn)行一次壓縮函數(shù)運(yùn)行需要64個(gè)“字”的初始輸入。要實(shí)現(xiàn)4個(gè)線程并行處理數(shù)據(jù)，進(jìn)行運(yùn)算的數(shù)據(jù)應(yīng)滿足其形成的節(jié)點(diǎn)數(shù)為4的次冪，即總字節(jié)數(shù)除以128后為4的次冪。所以算法先對(duì)初始數(shù)據(jù)進(jìn)行判斷，如果不能滿足上述情況，則用“0”進(jìn)行填充，以滿足條件。

算法運(yùn)算模式如圖4所示?？梢钥闯?，整棵樹被分成四個(gè)部分，每一個(gè)部分由一個(gè)線程執(zhí)行，最后將四個(gè)線程的結(jié)果匯總到一起進(jìn)行最后一次Hash計(jì)算并從中得到摘要值。利用openMP的fork-join模式，先劃分再匯總，以實(shí)現(xiàn)并行化提升效率。每個(gè)線程中的運(yùn)行方式相同，收到足夠的消息塊即512字節(jié)的數(shù)據(jù)即調(diào)用壓縮函數(shù)，逐級(jí)深入，整個(gè)過程只需要開辟一個(gè)很小的結(jié)構(gòu)體空間，存儲(chǔ)各級(jí)數(shù)和當(dāng)前需處理的數(shù)據(jù)等信息[13]。

圖4 Merkle樹

3.2 壓縮函數(shù)

壓縮函數(shù)的輸入是大小為80個(gè)“字”的數(shù)據(jù)塊，其具體表示如圖5所示。Q為一個(gè)15個(gè)“字”的向量，這一部分可以修改。U為節(jié)點(diǎn)ID號(hào)，其大小為1個(gè)“字”，指示分塊的位置，包括節(jié)點(diǎn)所在層次和在層次內(nèi)具體位置，大小分別為1個(gè)字節(jié)和7個(gè)字節(jié)。B是大小為64個(gè)“字”的數(shù)據(jù)塊，與4個(gè)16的“字”的節(jié)點(diǎn)相對(duì)應(yīng)。

圖5 壓縮函數(shù)的輸入

取系統(tǒng)格子規(guī)模L=16，對(duì)應(yīng)最終節(jié)點(diǎn)大小16個(gè)“字”。壓縮函數(shù)核心步驟如下[14]：

1) 將每個(gè)壓縮函數(shù)的輸入劃分成20×32字節(jié)的消息字m0，…，mp，…，m19。

2) 每個(gè)消息字按從高到低位劃分為4×8個(gè)字節(jié)：C1、C2、C3、C4。

3) 嵌入消息塊Mn。具體嵌入過程如下所示?？偣残枰M(jìn)行兩輪操作，每一輪操作執(zhí)行4次迭代過程。兩輪操作過后，每個(gè)消息字都被使用了4次，在每一輪中將消息塊與格點(diǎn)變量進(jìn)行混合。

第一輪：

第8×n次迭代：

xj,8×n=xj,8×n+mpj=0,…,4;p=0,…,4

第8×n+1次迭代：

xj,8×n=xj,8×n+1+mpj=0,…,4;p=5,…,9

第8×n+2次迭代：

xj,8×n=xj,8×n+2+mpj=0,…,4;p=10,…,14

第8×n+3次迭代：

xj,8×n=xj,8×n+3+mpj=0,…,4;p=15,…,19

第二輪：

第8×n+4次迭代：

第8×n+5次迭代：

第8×n+6次迭代：

第8×n+7次迭代：

4) 在對(duì)所有的消息塊進(jìn)行如上操作之后,接著對(duì)式(4)進(jìn)行r次迭代，取出最后一次迭代結(jié)果，即得到最后的16個(gè)“字”的輸出，然后在從中截取長(zhǎng)度為d的最終Hash值。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)敏感性分析

首先分別對(duì)以下幾種情況的消息文本進(jìn)行仿真實(shí)驗(yàn)：

T1:2.5Mbytes大小的消息文本。
T2：第一個(gè)大寫字母變?yōu)樾憽?br/>T3：中間一個(gè)句號(hào)變?yōu)槎禾?hào)。
T4：刪除末尾的一個(gè)字符。
T5：將中間的‘a(chǎn)’變?yōu)椤産’。

通過實(shí)驗(yàn)得到的各種情況十六進(jìn)制Hash值分別為：

T1:9c4b00e85d2d12a6e45d4cc43beccfa2。
T2：5d6d72613c163a7697b6eb8ec05579ee。
T3：a63b3d85950c8d42a87a931ac36eaef2。
T4：b050eadf93061e6a799470e9abaccd0e。
T5：f4841a6b5b442b169d8f81d42bb71e2e。

如果采用0，1序列來表示Hash值，上述各種情況對(duì)應(yīng)的結(jié)果如圖6所示。從仿真結(jié)果可以看出，明文消息文本的微小改變一定會(huì)對(duì)Hash值的生成產(chǎn)生極大的影響。

圖6 Hash值對(duì)明文消息敏感度的測(cè)試

4.2 混亂與擴(kuò)散性質(zhì)統(tǒng)計(jì)分析

一般用以下4個(gè)統(tǒng)計(jì)量來檢測(cè)算法的混亂與擴(kuò)散性質(zhì)：

(1) 平均比特變化數(shù)：

(4)

(2) 平均比特變化率：

(5)

(3) 比特變化數(shù)的均方差：

(6)

(4) 比特變化率的均方差：

(7)

表1 混亂與擴(kuò)散性質(zhì)統(tǒng)計(jì)結(jié)果

4.3 抗碰撞性分析

Hash函數(shù)的抗碰撞性是檢驗(yàn)其安全性的一個(gè)重要測(cè)試，如果能夠找到兩個(gè)不同的明文消息，其經(jīng)過算法處理后產(chǎn)生的Hash值相同，則稱為碰撞攻擊。方法如下：首先選取一段明文消息求出其Hash值，以ASCII字符來表示；然后改變明文中1 bit的值，得經(jīng)過計(jì)算得到一個(gè)新的Hash值。對(duì)兩個(gè)Hash值進(jìn)行比對(duì)，若兩個(gè)Hash值在相同位置上的ASCⅡ字符相同，則稱被擊中1次。測(cè)試結(jié)果如圖7所示，1 024次測(cè)試中有83次測(cè)試擊中1次，2次測(cè)試擊中2次，5次及以上是16次，碰撞率約為0.098 633。

圖7 相同位置上ASCII字符相同的數(shù)目分布

4.4 字符距離測(cè)試

字符距離是一種用來檢驗(yàn)兩個(gè)不同明文消息產(chǎn)生的Hash值是否相互獨(dú)立的統(tǒng)計(jì)量，定義如下：

(8)

式中：d為字符距離；H1[i]和H2[i]分別為用十進(jìn)制數(shù)來表示的兩個(gè)不同Hash值的第i個(gè)字節(jié)的值；s為所得的Hash值的字節(jié)長(zhǎng)度。如果兩個(gè)被檢驗(yàn)的Hash值獨(dú)立并且各字節(jié)取值服從均勻分布，所求得的平均字符距離值理論上應(yīng)為85.33。測(cè)試方法同抗碰撞檢驗(yàn)類似，在求得一段明文消息的Hash值后，隨機(jī)改變1比特明文，求得一個(gè)新的Hash值，比較兩個(gè)Hash值的字符距離。共進(jìn)行1 024次測(cè)試，得平均字符距離為85.89，同時(shí)通過表2與其他算法進(jìn)行對(duì)比，本算法的平均字符距離非常接近理論值，可以認(rèn)為更改原明文消息1 bit后，新的Hash值與原Hash值是相互獨(dú)立的。

表2 算法的平均字符距離

4.5 NIST隨機(jī)性測(cè)試

NIST測(cè)試套件是由15個(gè)測(cè)試組成的統(tǒng)計(jì)軟件包，這些是為了測(cè)試隨機(jī)(任意長(zhǎng)度)由基于硬件或軟件的密碼隨機(jī)或偽隨機(jī)數(shù)生成器產(chǎn)生的二進(jìn)制序列。測(cè)試關(guān)注于各種不同類型的已存在的非隨機(jī)序列。有些測(cè)試可以分成各種子測(cè)試。NIST測(cè)試主要檢測(cè)P_value的值與設(shè)定值α的大小比來判斷是否通過測(cè)試，α取值為0.01。若P_value≥α，則通過該項(xiàng)測(cè)試。測(cè)試結(jié)果如表3所示。本文提出的Hash函數(shù)算法生成的序列通過了其中13項(xiàng)測(cè)試，可以認(rèn)為生成的序列是一個(gè)比較理想的隨機(jī)序列。

表3 NIST隨機(jī)性測(cè)試結(jié)果

4.6 執(zhí)行效率測(cè)試

當(dāng)初始消息塊的長(zhǎng)度不能滿足被分成四塊后每塊形成的數(shù)據(jù)塊個(gè)數(shù)為4的次冪時(shí)，需要進(jìn)行數(shù)據(jù)填充，經(jīng)檢測(cè)此部分占用了大量時(shí)間去處理，這也是下一步需要改進(jìn)的地方。圖8顯示的是初始數(shù)據(jù)滿足條件時(shí)各線程運(yùn)行時(shí)間的對(duì)比?？梢钥闯鲈陂_啟1、2/3、4線程算法運(yùn)行時(shí)間是遞減的；在開啟2/3線程運(yùn)行時(shí)間相近是因?yàn)槎紴閷?塊數(shù)據(jù)分為兩步處理，因此執(zhí)行速度差別較小。

圖8 算法運(yùn)行時(shí)間

5 結(jié) 語(yǔ)

本文采用MD6架構(gòu)，利用merkle樹來實(shí)現(xiàn)并行化，壓縮函數(shù)核心為耦合動(dòng)態(tài)整數(shù)帳篷映射，結(jié)合傳統(tǒng)邏輯函數(shù)，使得帳篷映射整數(shù)化，并加入動(dòng)態(tài)參量，最后使用耦合映象格子模型，充分發(fā)揮了混沌系統(tǒng)的隨機(jī)性。同時(shí)利用merkle樹的結(jié)構(gòu)，并行化處理數(shù)據(jù)，使得雜湊速度在開啟多核情況時(shí)倍速增長(zhǎng)。對(duì)比文獻(xiàn)[9]可以用在對(duì)數(shù)據(jù)量較大的信息進(jìn)行雜湊處理。雖然由于數(shù)據(jù)填充部分使得在填充數(shù)據(jù)時(shí)可能會(huì)占用大量時(shí)間，但是算法通過了各項(xiàng)測(cè)試，可以說是有價(jià)值的，值得在未來信息安全中使用。