劉玉杰 劉建東 劉 博,2 鐘 鳴 李 博
1(北京石油化工學(xué)院信息工程學(xué)院 北京 102617) 2(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院 北京 100029)
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ù)算法。
將帳篷映射進(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ù)帳篷映射
利用耦合映像格子模型(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 模型耦合方式
多核處理技術(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)了并行。
執(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樹
壓縮函數(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值。
首先分別對(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個(gè)統(tǒng)計(jì)量來檢測(cè)算法的混亂與擴(kuò)散性質(zhì):
(1) 平均比特變化數(shù):
(4)
(2) 平均比特變化率:
(5)
(3) 比特變化數(shù)的均方差:
(6)
(4) 比特變化率的均方差:
(7)
表1 混亂與擴(kuò)散性質(zhì)統(tǒng)計(jì)結(jié)果
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ù)目分布
字符距離是一種用來檢驗(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 算法的平均字符距離
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é)果
當(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í)間
本文采用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à)值的,值得在未來信息安全中使用。