一種交叉處理的混沌多變量Hash算法構(gòu)造

張文婷,龍 敏

(長沙理工大學計算機與通信工程學院,長沙410014)

一種交叉處理的混沌多變量Hash算法構(gòu)造

張文婷,龍 敏

(長沙理工大學計算機與通信工程學院,長沙410014)

在現(xiàn)有的并行處理模式下,Hash函數(shù)由于明文分塊之間關聯(lián)性不大從而引起安全問題。為此,提出一種交叉處理的多變量混沌Hash算法,算法安全性基于二次多變量多項式方程組求解問題(MQ問題)的困難性和混沌理論的復雜性。其中64個壓縮函數(shù)可并行處理數(shù)據(jù),利用多變量代數(shù)理論構(gòu)造輸出函數(shù)進一步混亂與擴散,根據(jù)不同的需求調(diào)整Hash值的長度。對算法分別進行存儲空間分析、偽造攻擊分析、差分攻擊分析及統(tǒng)計實驗分析,結(jié)果表明,該算法彌補了傳統(tǒng)多變量多項式密碼的運行效率不足,且可以抵抗偽造攻擊、差分攻擊和統(tǒng)計攻擊。

Hash函數(shù);MQ問題;混沌映射;交叉處理;并行模式

1 概述

Hash函數(shù),也稱散列函數(shù)、湊雜函數(shù),用于將任意長度的消息壓縮為固定長度的消息摘要。Hash函數(shù)廣泛應用于數(shù)據(jù)完整性檢測、身份認證、數(shù)字簽名等領域。傳統(tǒng)的Hash函數(shù)采用Merkle-Damg?rd結(jié)構(gòu),如經(jīng)典的MD5[1]和SHA-1[2]算法。然而這類Hash函數(shù)的安全性能在文獻[3-4]中被證實不可靠,且串行處理的結(jié)構(gòu)導致效率不高,研究人員不再滿足于傳統(tǒng)Hash函數(shù)。

混沌是一種復雜的非線性動力學系統(tǒng),它具有初值敏感性、隨機性、長期不可預測性等性質(zhì),與密碼學上擴散與混亂的要求一致,因此誕生了混沌密碼學。近年來為了提高Hash算法的運行效率,新的混沌Hash算法越來越傾向于采用并行處理的模式。文獻[5]提出了一種時空混沌的可并行處理Hash函數(shù),文獻[6]也成功地找到了該算法的碰撞。文獻[7]利用分段線性函數(shù)和4維貓映射構(gòu)造了一種可并行處理Hash函數(shù),但文獻[8]發(fā)現(xiàn)了該算法難以抵抗偽造攻擊。盡管并行處理結(jié)構(gòu)效率很高,但這種并行處理的結(jié)構(gòu)導致明文的各分組之間聯(lián)系不強,很容易遭受攻擊。

有限域上MQ問題的求解是NP難解性問題,利用MQ問題構(gòu)造密碼可以抵抗量子計算機的威脅。2007年Billet等人首次將MQ問題應用到Hash函數(shù)中,提出了MQ-Hash[9]。然而這種基于多變量多項式方程組求解困難性的Hash函數(shù)存儲空間巨大,運行速度緩慢,實用價值不高。而文獻[10-11]也指出了直接利用MQ問題構(gòu)造的多變量Hash函數(shù)的不足。

本文基于混沌映射和多變量多項式方程組構(gòu)造了一種交叉結(jié)構(gòu)的Hash算法,該算法利用并行Hash算法和多變量Hash算法的優(yōu)點,抑制了兩者分別容易遭到偽造攻擊和差分攻擊的缺陷。

2 預備知識

2.1 混沌映射

混沌是一種類似無規(guī)則、隨機的運動,它對初值以及參數(shù)極其敏感,在長期內(nèi)不可預測。這些性質(zhì)都滿足密碼學中混亂與擴散的要求相符。本文采用Henon映射和分段線性映射來構(gòu)造Hash算法。

(1)Henon映射

其中,當α=1.4,β=0.3時為典型Henon映射,典型Henon映射是混沌映射。Henon映射是二維混沌映射,它由xi,yi共同確定迭代方程,本文算法選擇Henon映射生成密鑰流,加大了算法的密鑰空間。

(2)分段線性映射PLCM

當x∈[0,1],Q∈(0,0.5)時,系統(tǒng)處于混沌狀態(tài)。分段線性映射的分布均勻,且輸出軌道的自相關函數(shù)是δ形的。同時它的形式簡單,只有一個控制參數(shù),易于實現(xiàn)且速度上有優(yōu)勢。本算法選擇PLCM映射作為壓縮函數(shù)。

2.2 MQ問題

給定一個有限域F=GF(q)上n個變量m個方程二次多項式方程組可以表示為:

其中,1≤i≤m,ai,j,k,bi,j,ci∈GF(q)。則MQ問題為如下所述,給定方程組f=(f1,f2,…,fm),每個分量fi都是有限域GF(q)上隨機選擇的n個變量的二次方程。對于已知的y∈Fm,求解一個x∈Fn,滿足y=(f1(x),f2(x),…,fm(x)),叫做MQ問題。

MQ問題是NP難解性問題[12]。本文算法用二次多變量多項式結(jié)構(gòu)作為輸出函數(shù),將前面并行的壓縮函數(shù)隱藏起來,從而達到抵御偽造攻擊的目的。

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

3.1 消息填充

設明文的長度為m,Hash值的長度為n,明文被填充為512 bit的整數(shù)倍:在明文相應的二進制形式之后補充一個1,再補充若干個0。這段(100…0)2串的長度為l,滿足(m+l)mod 512=512-16-64=432。然后在右邊添加16 bit的Hash值長度n,最后再添加64 bit的消息明文長度m,如果m＞264,則取mmod 264。

消息填充結(jié)構(gòu)如圖1所示。

圖1 消息填充結(jié)構(gòu)

3.2 算法描述

算法運算在由不可約多項式y(tǒng)8+y4+y3+1定義的GF(28)上,Hash值長度可取192 bit,224 bit, 256 bit,384 bit等。為描述方便,下文輸出Hash值長度默認為192 bit。

(1)填充后的明文可分成s個512 bit的消息塊M1,M2,…,Ms。對于每個消息塊Mi(i=1,2,…,s)再分為64個子塊Mi=block1,i,block2,i,…,block64,i,其中每個blockj.i為8 bit。對于所有blockj,i(j=1, 2,…,64)經(jīng)下式線性變換后映射得到PLCM映射的參數(shù)Qj,i。

(2)算法的密鑰為Henon映射的一對初值(xx,yy)。迭代Henon映射50次后選取后32對迭代值(xxη,yyη)(η=19,20,21,…,50)進行下式變換得到PLCM映射的初值。

這 64個 PLCM 映射的初值分別為key1,key2,…,key64,而系統(tǒng)參數(shù)是變化的,每輪系統(tǒng)參數(shù)取相應的Qj,i,(j=1,2,…,64;i=1,2,…,s),共迭代2s次。因這64個PLCM是并行處理的,所以每一路的操作一樣,以PLCM1為例:PLCM1前s次迭代,參數(shù)依次為Q1,1,Q1,2,…,Q1,s;PLCM1后s次迭代,參數(shù)依次為Q1,s,Q2,s-1,…,Q1,1。這64個 PLCM構(gòu)成交叉結(jié)構(gòu),即每一輪PLCMj生成的迭代值作為下一輪PLCMj+1的初值,而PLCM64的迭代值則作為下一輪PLCM1的初值。最后這64個PLCM同時得到64個終值,作為二次多變量多項式結(jié)構(gòu)的輸入。2s輪迭代之間的交叉結(jié)構(gòu)如圖2所示。

圖2 壓縮函數(shù)的交叉結(jié)構(gòu)

(3)64個PLCM映射的終值作為二次多變量多項式方程組的 64個變量x1,x2,…,x64。此時GF(28)上64個變量24個方程的二次多變量多項式結(jié)構(gòu)可表示為:

每個fk(k=1,2,…,24)都為如下形式:

其中,ak,p,q,bk,p,ck都是從GF(28)上隨機選擇的元素。

這個二次多變量多項式結(jié)構(gòu)將64個變量壓縮為24個變量,而這24個變量級聯(lián)起來得到最終192 bit的Hash值。算法的整體結(jié)構(gòu)如圖3所示。

圖3 算法整體結(jié)構(gòu)

4 性能分析與仿真結(jié)果

算法的壓縮函數(shù)可定義為C=F(P(key,M)),其中,F為多變量多項式方程組;P為64路混沌映射;key為密鑰;M為消息明文。設每輪函數(shù)Pi的結(jié)果為ρi=(ρ1i,ρ2i,…,ρ64i),要找到一對M≠M′,使得C(M)=C(M′),做如下證明:設第i輪時ρi=ρi′,i-1是滿足ρi-1≠ρi-1′最大的情況,對于任意的ρi-1′計算得到ρi′=Pi(ρi-1′,Qi′),可推出Qi≠Q(mào)i′。假設第i輪后消息分組的值完全相同,則此后的迭代軌跡完全一致,在反向迭代至2s-i次時,再次使用Qi′作為參數(shù)計算得到 ρ2s-i+1′=P2s-i(ρ2s-i′,Qi′),由于Qi≠Q(mào)i′,ρ2s-i=ρ2s-i′而可推出 ρ2s-i+1≠ρ2s-i+1′。 那么對于往后2s-i+1至2s輪迭代,根據(jù)混沌的性質(zhì),其軌跡仍然將會截然不同,從而導致F的計算結(jié)果不同,即C(M)≠C(M′),因此可以認為算法是無碰撞的?；煦绲倪\動十分復雜,對初值極其敏感,對明文任意微小的改變都會導致迭代值極大的變化,即使在攻擊者已知P2s的最壞情況下,求解F也是不可行的,因為F是個NP難解性問題,從而保證了算法的單向性。

4.1 存儲空間

整個算法由混沌迭代和多變量多項式計算2個部分組成。第一部分所需存儲空間主要是PLCM映射的狀態(tài)值和系統(tǒng)參數(shù),而迭代64個PLCM映射2s次需64×2s×(2×8)bit。第二部分為有限域GF(28)上的二次多變量多項式方程組,其所需存儲空間主要是有限域GF(28)的乘法表和隨機系數(shù)。GF(28)有256個元素,每個元素8 bits,則乘法表需要256×256×8 bit。多變量多項式方程組有nm(n+l)/2個二次項,nm個一次項和m個常數(shù)項。表1列出不同Hash值長度情況下MQ部分所占存儲空間。

表1 二次多變量多項式結(jié)構(gòu)所占存儲空間

混沌部分所占空間由明文大小決定,多變量多項式部分的存儲空間則是固定的。因迭代Henon映射50次產(chǎn)生的密鑰流所占空間極小,此處計算忽略。因此,算法的存儲空間主要由明文大小和多變量多項式的隨機數(shù)決定。一段大小為512sbit(s為明文分組數(shù))的明文在Hash值長度為192 bit的情況下,多變量多項式結(jié)構(gòu)占114.27 KB混沌部分占0.25sKB,共計114.27+0.25sKB。顯然,與占用將近3.5 MB的MQ-Hash[9],本算法在存儲空間上具有明顯優(yōu)勢。這是因為MQ-Hash的采用的傳統(tǒng)的串行處理結(jié)構(gòu),每個壓縮函數(shù)中都要對當前明文分組進行一次多變量多項式計算,而本文的壓縮函數(shù)為并行的混沌映射而多變量多項式方程組為輸出函數(shù),對于任意長度的明文僅作一次多變量多項式計算。

4.2 抗偽造攻擊性

偽造攻擊是指給定一段消息,攻擊者不知其密鑰的情況下根據(jù)該消息的Hash值來構(gòu)造明文,從而達到攻擊的目的。文獻[6,8]中指出并行處理的結(jié)構(gòu)導致明文的各分組之間聯(lián)系不緊密,因而無法抵御偽造攻擊。因此,本算法在并行運算前,對明文的每個分組做了如下線性變化來加強各分組的聯(lián)系:

該變換由3個位置因素決定:當前消息塊的橫向坐標i、當前消息塊的縱向坐標j和消息塊的總數(shù)s,增減修改明文的任何數(shù)據(jù)都會不同程度地改變i,j,s,從而改變了Qi,j的值。同時算法又引進了交叉處理,當前混沌映射處理后得到的迭代值在下一輪中并不由自身處理,而是送給相鄰的混沌映射處理,這樣大大加強了明文不同分組之間的聯(lián)系,中間值微小的變化會在最終的Hash中放大,使得明文充分混淆。此外算法在并行的壓縮函數(shù)之后,用二次多變量多項式結(jié)構(gòu)作為輸出函數(shù)。對于文獻[6,8]中提出的將上下兩行Hash值交換后進行異或運算而產(chǎn)生相同結(jié)果的攻擊方法,由于本算法中多變量多項式結(jié)構(gòu)進一步對并行處理結(jié)構(gòu)的結(jié)果充分置亂,隱藏起壓并行處理結(jié)構(gòu)的內(nèi)部狀態(tài),從而不再可行。

4.3 抗差分攻擊性

MQ問題是NP難解性問題。但是解決MQ問題的復雜度取決于方程數(shù)m,變量數(shù)n和有限域的階q?，F(xiàn)已存在有效地解決超定多變量多項式方程(n＜m)的方法和置換多變量多項式方程(n=m)的方法,因此在利用多變量多項式構(gòu)造密碼時通常使用不定方程(n＞m)。本算法在選擇Hash值長度為192 bit,224 bit,256 bit,384 bit時,多變量多項式結(jié)構(gòu)均可表示為F64→F24,F64→F28,F64→F32和F64→F48的不定方程形式。相比求解復雜度為O(qm)的窮舉攻擊,文獻[13]中提出一種復雜度大大降低的解決不定方程系統(tǒng)的算法:設,當k滿足2k2＞m-2k時,該算法的復雜度為O(qm-k)?？梢娎迷撍惴ㄓ行蠼舛味嘧兞坎欢ǚ匠?對不定方程的取值要嚴格的限定,該算法僅適用于q,n,m很小的情況。按照文獻[13]的求解方法在不同的Hash值長度情況下解決本算法MQ問題部分的復雜度在表2列出,可見本文算法的二次多變量多項式結(jié)構(gòu)理論上不可解。

表2 二次多變量多項式結(jié)構(gòu)的求解復雜度

設Q為有限域F上m個方程n個變量的二次方程組為f1,f2,…,fm。對于任意給定的 δ=(δ1, δ2,…,δn)可在多項式時間O(mn2)內(nèi)找到一對輸入x=(x1,x2,…,xn),y=(y1,y2,…,yn)發(fā)生碰撞,其中,(x,y)=(x,x+δ)[9]。單獨使用二次多變量多項式來構(gòu)造密碼是不安全的,無法抵御差分攻擊。

差分攻擊的是針對分組通過分析明文對的差值對密文對的影響來恢復部分密鑰,而本文算法中明文的各分組在經(jīng)多變量多項式結(jié)構(gòu)處理前先經(jīng)過交叉的64組混沌映射處理,經(jīng)多輪迭代將初始值擴散到整個相空間,這種對明文充分的置亂很難從最終的迭代值中推算原始消息。而要在本文算法的二次多變量多項式結(jié)構(gòu)部分發(fā)現(xiàn)碰撞,必須要求前面的壓縮函數(shù)部分可逆,而壓縮函數(shù)采用的混沌映射的性質(zhì)確保了在輸入差分經(jīng)過數(shù)次迭代已均勻分布到所有比特位,因此,在二次多變量多項式結(jié)構(gòu)尋找碰撞是不可行的。

4.4 統(tǒng)計分析

4.4.1 擴散與混亂性質(zhì)測試

Shannon引入了擴散與混亂2個概念來評估密碼系統(tǒng)的性能。對于用二進制表示的Hash值,每1 bit只有0或者1兩種可能,因此理想的Hash值擴散效果應該是明文中1 bit變化會引起Hash值50%的變化。

其中,N為統(tǒng)計次數(shù);Bi為第i次測試變化的位數(shù);h為Hash值的長度。

取密鑰 xx=1.17,yy=-0.28。對初始文本“Hash function is an algorithm converts variable length message to a fixed length of digest,which is called hash value.Hash function has a wide range of application in information security,such as data integrity authentication, identity authentication and digitalsignature.”進 行1 000次測試,每次隨機改變文本中1 bit的值,并比較改變后的Hash值和原始文本的Hash值。不同Hash值長度下1 000次測試相應的平均變化比特數(shù)、平均變化概率P、均方差ΔB、均方差ΔP在表3中列出。

表3 雪崩測試統(tǒng)計結(jié)果

4.4.2 Hash值分布

安全的Hash算法的一個重要要求是Hash值均勻分布。本文對以下消息進行仿真實驗:“Hash function is an algorithm converts variable length message to a fixed length of digest,which is called hash value.Hash function has a wide range of application in information security, such as data integrity authentication,identity authentication and digital signature.”密鑰取 xx=1.17,yy=-0.28。通過仿真結(jié)果可以看到明文與Hash值的分布:圖4(a)為明文的ASCII碼值分布圖,ASCII碼值集中地分布在90～120這個范圍內(nèi);而圖4(b)為十六進制Hash值的分布圖,Hash值分布十分分散。由此可知,本文算法得到的Hash值有良好的擴散與混亂性能。

圖4 明文和Hash值的分布

4.4.3 敏感性分析

為測試本文算法對于明文和密鑰的敏感程度,在7種不同條件下對4.5.1中的文本進行仿真實驗。

文本1:原文。

文本2:將原文首字母H改為G。

文本3:將原文中as一詞改為is。

文本4:將原文末尾處句點改為逗號。

文本5:在原文末尾添加一位空格。

文本6:將 密 鑰yy取 值 由 -0.28改 為-0.280 000 000 000 000 1。

文本7:將 密 鑰xx取 值 由 1.17 改 為1.170 000 000 000 000 1。

仿真所得192 bit的Hash值長度的十六進制形式如下:

文本1:BAD4A890BF7240044C22B58E0A45A1C598 6D2E67E65A9939

文本2:27F08D4ECBC371221D35193A4D797391E4 CE56077B0A26D5(改變94位)

文本3:0BC2E9D74577C01E611F6480C51C63F43E CCC5DD136CFB7F(改變91位)

文本4:0F034E33295F561EF088BFF984B55ED96989 CC988750FE02(改變106位)

文本5:CEE066D48D20D8F2DA3C1924A69539735 C39FC711CA64547(改變96位)

文本6:400543850934F5EB02D3797DB6BB53CBE2 F06E62CF721A02(改變104位)

文本7:F093000A8363508DD75F621B782CEA4A6C 6D6397C30A546D(改變88位)

圖5所示為相應的Hash值二進制形式的圖形分布,可以看出對明文和密鑰的任何細微改變都會對Hash值產(chǎn)生巨大的影響,證明算法對明文和密鑰的敏感程度良好。

圖5 7種條件下二進制Hash值比較

5 結(jié)束語

本文結(jié)合混沌理論的復雜性和MQ問題的難解性,提出一種新的交叉迭代的Hash算法,算法占用空間小、處理速度快,另外,可根據(jù)不同需求調(diào)節(jié)Hash值長度。仿真實驗和理論分析證明本文算法滿足Hash算法的安全要求,且具有處理大容量數(shù)據(jù)的潛力。今后的工作重點是以該算法為基礎研究在云端進行消息認證的方法。

[1] Rivest L.The MD5 Message digest Algorithm[S]. RFC 1321,1992.

[2] NIST.FIPS PUB 180-2-1993 SecureHash Standard[Z].1993.

[3] Wang Xiaoyun,Yu Hongbo.How to Break MD5 and Other Hash Functions[C]//Proceedings of EUROCRYPT’05. Berlin,Germany:Springer-Verlag,2005:19-35.

[4] Wang Xiaoyun,Yu Hongbo.Finding Collisions in the Full SHA-1[C]//Proceedings of EUROCRYPT’05. Berlin,Germany:Springer-Verlag,2005:17-36.

[5] 趙 耿,徐 剛,閔樂泉.一種并行時空混沌單向Hash函數(shù)的構(gòu)造[J].微計算機信息,2011,27(5):232-236.

[6] 王 浩.混沌單向Hash函數(shù)的安全性分析研究[D].長沙:長沙理工大學,2013.

[7] Xiao Di,Liao Xiaofeng,Dong Shaojiang.Parallel Keyd Hash Function Construction Based on Chaotic Maps[J]. Physic Letters A,2008,17(7):2388-2393.

[8] Xiao Di,Liao Xiaofeng,Wang Yong.Improving the Sec Urity of a Parallel Keyd Hash Function Based on Chaotic Maps[J].Physic Letters A,2009,373(36):4346-4353.

[9] Olivier B,Matt R,Homas P.On Building Hash Functions from Multivariate Quadratic Equations[C]//Proceedings of ACISP’07.Berlin,Germany:Springer-Verlag,2007: 82-95.

[10] Ding Jintai,Yang Boyin.Multivariates Polynomials for Hashing[EB/OL].(2007-10-21).http://eprint.iacr. org/2007/137.pdf.

[11] Pierre-Alain F,Louis G,Jacques S.Differential CryptanaLysis for Multivariate Schemes[C]//Proceedings of EUROCRYPT’05.Berlin,Germany:Springer-Verlag,2005: 341-353.

[12] Garey T,Johnson D.Computers and Intractability,A Guide to the Theory of NP-completeness[M].New York,USA: [s.n.],1979:128-130.

[13] Nicolas C,Louis G,Jean-Daniel T.Solving Underdefined Systems ofMultivariate Quadratic Equations[C]// Proceedings of PKC’02.Berlin,Germany:Springer-Verlag, 2002:211-227.

編輯 索書志

Chaos Multivariate Hash Algorithm Construction of Cross Processing

ZHANG Wenting,LONG Min
(College of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410014,China)

Aiming at the defects of security in the existed parallel Hash funtions which are caused by the weak correlations between the plaintext block,a novel Hash function algorithm based on the difficulty of solving MQ problem and the complexity of chaotic theory is proposed.The algorithm works in a parallel and cross processing mode.The output function is constructed by multivariate polynomials equations to confuse the plaintext sufficiently.The output Hash size can be adjusted according to different requirements.Storage analysis,forge attack analysis,differential attack analysis and statistic analysis are carried on algorithm.Theoretical analysis and experimental results show that the parallel structure of the algorithm compensates the inefficiency of traditional multivariate polynomial cryptosystems,and it can resist forge attack,differential attack and statistic attack.

Hash function;MQ problem;chaotic mapping;cross processing;parallel mode

1000-3428(2015)01-0130-05

A

TP309

10.3969/j.issn.1000-3428.2015.01.024

國家自然科學基金資助項目(61001004);湖南省教育廳基金資助項目(11B002);湖南省海外名師基金資助項目(2013008);湖南省研究生科研創(chuàng)新基金資助項目(CX2013B376)。

張文婷(1989-),女,碩士研究生,主研方向:單向Hash函數(shù);龍 敏,教授、博士。

2014-03-03

2014-04-03 E-mail:yesterdayjuly@qq.com

中文引用格式:張文婷,龍 敏.一種交叉處理的混沌多變量Hash算法構(gòu)造[J].計算機工程,2015,41(1):130-134.

英文引用格式:Zhang Wenting,Long Min.Chaos Multivariate Hash Algorithm Construction of Cross Processing[J]. Computer Engineering,2015,41(1):130-134.