劉建東

(北京石油化工學(xué)院 信息工程學(xué)院，北京 102617)

1 引言

散列函數(shù)在現(xiàn)代密碼學(xué)中有著極其重要的用途，它不僅在安全通信中起著重要的作用，而且是許多密碼算法與密碼協(xié)議安全的前提條件。近幾年來(lái)，密碼學(xué)界對(duì)散列函數(shù)的設(shè)計(jì)與分析給予了廣泛的關(guān)注。在 2004年美密會(huì)上，王小云等宣布了包括MD4、MD5、HAVAL-128以及RIPEMD在內(nèi)的碰撞實(shí)例[1]。最為重要的是對(duì)MD5的破解不僅具有理論意義，而且在實(shí)際應(yīng)用領(lǐng)域也產(chǎn)生了巨大的影響。Lucks與Magnus已構(gòu)造出MD5的“有意義的碰撞”[2]。王小云等人對(duì)SHA-1的分析也已取得突破性成果，揭示出SHA-1的脆弱性[3]。

傳統(tǒng)的散列函數(shù)(MDx系和SHA系)的主要設(shè)計(jì)原則基于MD迭代結(jié)構(gòu)[4]，它們具有許多共同的設(shè)計(jì)準(zhǔn)則，各輪的混合運(yùn)算設(shè)計(jì)極為相似，全都采用了整數(shù)模加和邏輯函數(shù)(輪函數(shù))。如此眾多的散列算法在不長(zhǎng)的時(shí)間相繼被攻破，說(shuō)明其設(shè)計(jì)準(zhǔn)則存在缺陷。近年來(lái)，為獲得更安全的散列函數(shù)，利用混沌系統(tǒng)對(duì)變量和參數(shù)的變化的敏感特性構(gòu)造單向散列函數(shù)的研究已取得一些進(jìn)展[5～9]。但由于數(shù)字化混沌系統(tǒng)的動(dòng)力學(xué)特性退化問(wèn)題[10]及構(gòu)造方案本身的缺陷[11]，目前基于混沌理論的散列函數(shù)構(gòu)造方案還無(wú)法得到人們的信任。文獻(xiàn)[12]中首次將混沌散列函數(shù)的研究成果[13,14]與傳統(tǒng)的散列函數(shù)設(shè)計(jì)準(zhǔn)則相結(jié)合，設(shè)計(jì)了一種輸出長(zhǎng)度為160bit的散列函數(shù)。本文對(duì)文獻(xiàn)[12]提出的整數(shù)帳篷映射進(jìn)行了改進(jìn)，給出擴(kuò)展整數(shù)帳篷映射的定義，并對(duì)擴(kuò)展整數(shù)帳篷映射的均勻分布特性進(jìn)行了分析。在此基礎(chǔ)上,本文給出一種基于擴(kuò)展整數(shù)帳篷映射的具有動(dòng)態(tài)特性的散列函數(shù)設(shè)計(jì)方案(簡(jiǎn)稱 TDHA)。該方案各輪主要計(jì)算過(guò)程依然是整數(shù)模加和位運(yùn)算，為了提供良好的擴(kuò)散性，將擴(kuò)展整數(shù)帳篷映射作為各輪的主要非線性部件，由擴(kuò)展整數(shù)帳篷映射引發(fā)狀態(tài)變量?jī)?nèi)部及狀態(tài)變量之間的動(dòng)態(tài)強(qiáng)差分?jǐn)U散。該方案將傳統(tǒng)的散列函數(shù)中所使用的常數(shù)變?yōu)閯?dòng)態(tài)參數(shù)，利用擴(kuò)展整數(shù)帳篷映射的位邏輯判定功能，通過(guò)循環(huán)移位方式控制動(dòng)態(tài)參數(shù)的演化過(guò)程，增強(qiáng)了參數(shù)項(xiàng)與明文差分的關(guān)聯(lián)度。壓縮函數(shù)內(nèi)部采用了并行迭代結(jié)構(gòu)，有利于算法的軟硬件高速并行實(shí)現(xiàn)。另外，還對(duì)MD結(jié)構(gòu)進(jìn)行了改進(jìn)，使得壓縮函數(shù)之間不僅有狀態(tài)變量鏈接，還有相同數(shù)量的動(dòng)態(tài)鏈接參數(shù)，在無(wú)需擴(kuò)展中間狀態(tài)變量的情況下，提高了散列函數(shù)抵抗部分消息碰撞攻擊的能力。

2 基于整數(shù)帳篷映射的耦合映像系統(tǒng)

2.1 整數(shù)帳篷映射

帳篷映射的定義為[6]

該映射是混沌的。當(dāng)參數(shù)α=0.5時(shí)，帳篷映射為滿映射。帳篷映射的優(yōu)異特性之一是其具有均勻的分布函數(shù)，在實(shí)數(shù)域內(nèi)其性態(tài)是混沌的。將其由實(shí)數(shù)域運(yùn)算等價(jià)轉(zhuǎn)化為整數(shù)運(yùn)算(設(shè)整數(shù)的二進(jìn)制位數(shù)為k)：

其中 1＝2k-1。式(2)中的乘法運(yùn)算可用移位操作實(shí)現(xiàn)。映射F服從[0, 1]上的均勻分布。更為重要的是，整數(shù)帳篷映射保持了實(shí)數(shù)域帳篷映射的伸長(zhǎng)和折疊特性，其伸長(zhǎng)特性最終導(dǎo)致相鄰點(diǎn)的指數(shù)分離，即敏感的初始條件，其折疊特性則保持生成序列有界，且引起映射不可逆。然而，由于映射(2)定義在有限域內(nèi)，利用它生成的迭代序列必然進(jìn)入周期態(tài)，甚至出現(xiàn)一些周期長(zhǎng)度很小的周期點(diǎn)。例如k=4時(shí)，出現(xiàn)不動(dòng)點(diǎn)(10→10→…)；k=5時(shí)，出現(xiàn)周期長(zhǎng)度為2的短周期(12→25→12→…)。

2.2 擴(kuò)展整數(shù)帳篷映射

為了改進(jìn)整數(shù)帳篷映射的性態(tài)，給出擴(kuò)展整數(shù)帳篷映射,將其定義為

當(dāng)n為偶數(shù)時(shí)，

當(dāng)n為奇數(shù)時(shí)，

映射式(3)將生成的迭代序列的周期擴(kuò)展到2(k+1),并且避免了不動(dòng)點(diǎn)的出現(xiàn)。表1給出k=5時(shí)，從所有可能的初值出發(fā)，利用映射式(3)生成的迭代序列，其周期為12。從表中可以明顯看出其均勻分布的特性及拉伸與折疊的非線性特征。

表1 擴(kuò)展整數(shù)帳篷映像（k=5）

2.3 擴(kuò)展整數(shù)耦合帳篷映像系統(tǒng)

分析表1中的數(shù)據(jù)發(fā)現(xiàn)，映射式(3)生成的迭代序列共包含6個(gè)周期環(huán)，這些周期環(huán)是：

0→1→2→5→10→21→21→20→23→16→31→0→0,6→13→26→10→20→22→19→24→15→31→1→3→6,3→7→14→29→5→11→22→18→27→8→16→30→3,17→28→7→15→30→2→4→9→18→26→11→23→17,8→17→29→4→8,9→19→25→12→24→14→28→6→12→25→13→27→9。

在迭代過(guò)程中，通過(guò)施加擾動(dòng)，來(lái)打破擴(kuò)展整數(shù)帳篷映射所固有的周期環(huán)，則可以改善整數(shù)帳篷映射的遍歷性，使系統(tǒng)的迭代序列隨機(jī)化。為此，構(gòu)造如下的耦合映像系統(tǒng)模型：

式(4)中運(yùn)算符含義見(jiàn)下文中的說(shuō)明。該式采用耦合映像格子的并行迭代結(jié)構(gòu)及傳統(tǒng)散列函數(shù)中的模加耦合方式，繼承了耦合映像格子模型的混淆與擴(kuò)散特性，克服了耦合映像格子模型對(duì)格點(diǎn)序列分布特性的影響[14]。取p=5, j=0,…,4，圖1為式(4)在隨機(jī)選取一組初值時(shí)狀態(tài)變量經(jīng)12 000次迭代的結(jié)果，可看出時(shí)間序列具有均勻隨機(jī)的特性。

圖1 擴(kuò)展整數(shù)耦合帳篷映射時(shí)間序列分布

3 TDHA構(gòu)造

符號(hào)說(shuō)明：+為mod 232的加法運(yùn)算，～為逐比特邏輯反，⊕為逐比特邏輯異或，＜＜為左移位操作，＜＜＜為循環(huán)左移位操作，＞＞＞為循環(huán)右移位操作。

定義D=231，在GF(232)內(nèi)，擴(kuò)展整數(shù)帳篷映射(式(3))G:xn→xn+1可用 C語(yǔ)言中的三元運(yùn)算符(? :)描述為：

當(dāng)n為偶數(shù)時(shí)，

xn+1= xn＜D ? (xn＜＜1)+1 : ～xn＜＜1；

當(dāng)n為奇數(shù)時(shí)，

xn+1= xn＜D ? xn＜＜1 : (～xn＜＜1)+1。

由此可見(jiàn)，擴(kuò)展整數(shù)帳篷映射可用簡(jiǎn)單的邏輯判斷、邏輯取反及移位操作實(shí)現(xiàn)。若用匯編語(yǔ)言或硬件實(shí)現(xiàn)，則其操作可以進(jìn)一步簡(jiǎn)化為：當(dāng)n為偶數(shù)時(shí)，測(cè)試字的最高位是否為0，若為0,則左移一位加1，否則，則各位求反后，左移一位；當(dāng)n為奇數(shù)時(shí)，測(cè)試字的最高位是否為 0，若為 0，則左移一位,否則，則各位求反后，左移一位，再加1。編程實(shí)現(xiàn)時(shí)，n的奇偶性無(wú)需判定，只要在一次循環(huán)中包含2次映射即可(奇偶各一次)。在下面的散列算法設(shè)計(jì)中，擴(kuò)展整數(shù)帳篷映射的邏輯判定結(jié)果還將引起參數(shù)項(xiàng)k的動(dòng)態(tài)變化，將其統(tǒng)一用三元運(yùn)算符（? :）描述。下面給出構(gòu)造散列算法TDHA的一般過(guò)程。

1) 分割與填充。采用MD5算法的分割與填充方式。簡(jiǎn)要描述為:將任意長(zhǎng)度的明文消息 M 分割成 512bit的消息塊 M0,…,Mn,…,Mt，最后一個(gè)塊填充為:Mt=*…*10…0Length(M),其中 Length(M)表示M的長(zhǎng)度的二進(jìn)制形式，長(zhǎng)度為64bit，不足64bit時(shí)高位添一個(gè)介符1再補(bǔ)0。

2) 將每個(gè)消息塊Mn劃分成16個(gè)32bit的消息字 m0, m1,…,m15。

3) 5個(gè)32bit的初始向量：

5) TDHA算法：

② 作3輪計(jì)算，每一輪進(jìn)行4次迭代操作,每次迭代操作需要先進(jìn)行消息嵌入及映射變換，然后利用式(4)給出的耦合映像系統(tǒng)模型，進(jìn)行擴(kuò)散迭代。

第1輪：進(jìn)行4次迭代操作。

迭代操作1：

xi= mi+ xi, i=0,…,3。

x4= (m0⊕m1⊕m2⊕m3)+x4。

Gi= xi＜D?(xi＜＜1)+1:(ki+2mod5=ki+2mod5＞＞＞1,～xi＜＜1), i=0,…,4。

xi=Gi+((Gi-1mod5⊕Gi+2mod5)＜＜＜21)+

((Gi+1mod5⊕Gi+3mod5)＜＜＜11)+ ki, i=0,…,4。

迭代操作2：

xi= mi+4+ xi, i=0,…,3。

x4= (m4⊕m5⊕m6⊕m7)+x4。

Gi= xi＜D ? xi＜＜1:(ki+2mod5=ki+2mod5＞＞＞1, (～xi＜＜1)+1), i=0, …,4。

xi= Gi+ ((Gi-1mod5⊕Gi+2mod5)＜＜＜21)+((Gi+1mod5⊕Gi+3mod5)＜＜＜11)+ ki, i=0,…,4。

迭代操作 3：

xi= mi+8+ xi,i=0,…,3。

x4=(m8⊕m9⊕m10⊕m11)+x4。

Gi= xi＜D?(xi＜＜1)+1:(ki+2mod5=ki+2mod5＞＞＞1,～xi＜＜1), i=0,…,4。

xi= Gi+ ((Gi-1mod5⊕Gi+2mod5)＜＜＜21)+((Gi+1mod5⊕Gi+3mod5)＜＜＜11)+ ki, i=0,…,4。

迭代操作4：

xi= mi+12+ xi,i=0,…,3。

x4=(m12⊕m13⊕m14⊕m15)+x4。

Gi= xi＜D ? xi＜＜1 : (ki+2mod5=ki+2mod5＞＞＞1,(～xi＜＜1)+1) i=0,…,4

xi= Gi+ ((Gi-1mod5⊕Gi+2mod5)＜＜＜21)+((Gi+1mod5⊕Gi+3mod5)＜＜＜11)+ ki, i=0,…,4。

第2輪：映射變換及耦合擴(kuò)散迭代的方式與第1輪相同，因此，這里只給出4次迭代操作的消息嵌入情況。

迭代操作5：

xi= (m(15-(3i+1mod5)＜＜＜5)+ xi, i=0,…,4。

迭代操作6：

xi= (m(10-(3i+1mod5)＜＜＜5)+ xi, i=0,…,4。

迭代操作7：

xi= (m(5-(3i+1mod5)＜＜＜5)+ xi, i=0,…,4。

迭代操作8：

x0=( m0＜＜＜5)+ x0，

x1=(( m3⊕m15⊕m11⊕m7)＜＜＜5)+x1，

x2=(( m2⊕m14⊕m10⊕m6)＜＜＜5)+x2，

x3=(( m1⊕m13⊕m9⊕m5)＜＜＜5)+x3，

x4=(( m0⊕m12⊕m8⊕m4)＜＜＜5)+x4。

第3輪：消息嵌入情況(映射變換及耦合擴(kuò)散迭代的方式仍與第1輪相同)。

迭代操作9：

xi= (m(15-i)＜＜＜9)+ xi, i=0,…,3。

x4=(( m3⊕m14⊕m9⊕m4)＜＜＜9)+x4。

迭代操作10：

xi= (m(11-i)＜＜＜9)+ xi, i=0,…,3。

x4=(( m2⊕m13⊕m8⊕m7)＜＜＜9)+x4。

迭代操作11：

xi= (m(7-i)＜＜＜9)+ xi, i=0,…,3，

x4=(( m0⊕m15⊕m10⊕m5)＜＜＜9)+x4。

迭代操作12：

xi= (m(3-i)＜＜＜9)+ xi, i=0,…,3。

x4=(( m1⊕m12⊕m11⊕m6)＜＜＜9)+x4。

④ 對(duì)剩下的消息塊繼續(xù)②～③的操作，直到最后一塊。

⑤ 最后輸出160bit的散列值：x0|| x1|| x2|| x3||x4。

上述算法有以下特點(diǎn)。

1) 用擴(kuò)展整數(shù)帳篷映射取代傳統(tǒng)的邏輯函數(shù)。傳統(tǒng)的散列函數(shù)在混合運(yùn)算中采用了邏輯函數(shù)(輪函數(shù))。以MD5為例，在壓縮函數(shù)的設(shè)計(jì)中，為了實(shí)現(xiàn)消息的擴(kuò)散與混淆，主要采用了4個(gè)基本邏輯函數(shù)。在這些邏輯函數(shù)中，多個(gè)不同的輸入會(huì)產(chǎn)生相同的輸出，稱之為邏輯函數(shù)的值碰撞。以f1=f(A,B,C)=(A∧B)∨(∧C)為例，輸入為(0,0,0)、(0,1,0)、(1,0,0)、(1,0,1)時(shí)，輸出為 0；輸入為(0,0,1)、(0,1,1)、(1,1,0)、(1,1,1)時(shí)，輸出為1。由于邏輯函數(shù)的值碰撞，使壓縮函數(shù)內(nèi)部可能產(chǎn)生差分收斂性。王小云等正是利用邏輯函數(shù)的這一特性來(lái)控制差分的收斂，并結(jié)合整數(shù)模減差值表達(dá)式多樣性、左循環(huán)移位差值傳遞特性及比特修改與 2-block碰撞攻擊技術(shù)找到了MD5算法的碰撞實(shí)例。

擴(kuò)展整數(shù)帳篷映射具有均勻分布性及良好的非線性特征，并且實(shí)現(xiàn)簡(jiǎn)單，運(yùn)算速度快，但它是單變量間的1-1映射，不存在值碰撞問(wèn)題。另外，傳統(tǒng)的散列函數(shù)中，消息是不能注入邏輯函數(shù)的，否則，在邏輯函數(shù)中即可產(chǎn)生消息碰撞。而在TDHA算法中，帳篷映射不會(huì)導(dǎo)致消息碰撞，因而消息可直接注入擴(kuò)展整數(shù)帳篷映射中，即消息注入時(shí)就進(jìn)行了非線性變換，增強(qiáng)了算法的不可逆性。

2) 擴(kuò)展整數(shù)帳篷映射引發(fā)動(dòng)態(tài)強(qiáng)差分?jǐn)U散。傳統(tǒng)的散列函數(shù)(MD5、SHA-1等)的擴(kuò)散機(jī)制是由模32加和按位進(jìn)行的布爾操作的混合運(yùn)算實(shí)現(xiàn)的，每一比特的變化只有通過(guò)移位或進(jìn)位操作來(lái)影響其他的位。TDHA算法仍具有邏輯移位及模32加的擴(kuò)散機(jī)制，尤為重要的是，每一次映射變換除了能使?fàn)顟B(tài)變量左移一位之外，最高比特位的差分特性還將引發(fā)該狀態(tài)變量產(chǎn)生最大的擴(kuò)展碼字重量，稱這種現(xiàn)象為狀態(tài)變量?jī)?nèi)部的動(dòng)態(tài)強(qiáng)差分?jǐn)U散。在 3輪操作中，通過(guò)循環(huán)移位及耦合擴(kuò)散，每一消息比特差分均有機(jī)會(huì)觸發(fā)動(dòng)態(tài)強(qiáng)差分?jǐn)U散。此外，TDHA算法用動(dòng)態(tài)參數(shù)項(xiàng)取代了傳統(tǒng)散列函數(shù)中所使用的常數(shù)，消息差分可以引發(fā)動(dòng)態(tài)參數(shù)項(xiàng)產(chǎn)生不同的演化過(guò)程，這一過(guò)程發(fā)生在不同的狀態(tài)變量之間，因而我們稱之為狀態(tài)變量間的動(dòng)態(tài)強(qiáng)差分?jǐn)U散。

對(duì)壓縮函數(shù)的內(nèi)部結(jié)構(gòu)進(jìn)行密碼分析,目前最有效的方法是王小云等提出的模減差分分析方法。該方法構(gòu)造有效的差分路線的主要思想是去抵消由于消息差分引起的擴(kuò)散。差分攻擊的復(fù)雜度與壓縮函數(shù)中消息的差分?jǐn)U散程度成正比，因此差分?jǐn)U散程度越大，構(gòu)造的碰撞差分路線的導(dǎo)出條件就越多。TDHA算法引入動(dòng)態(tài)強(qiáng)差分?jǐn)U散機(jī)制，加速了差分?jǐn)U展，使只修改少數(shù)幾位就能產(chǎn)生一個(gè)碰撞的概率變得更小，對(duì)“差分路線”形成一道難以逾越的屏障。

3) 關(guān)于動(dòng)態(tài)參數(shù)項(xiàng)的說(shuō)明。在傳統(tǒng)散列函數(shù)中，一般均含有固定的常數(shù)項(xiàng)。以 MD5為例，除了4個(gè)初始狀態(tài)(A,B,C,D)外，另外還有64個(gè)常數(shù)Ti(Ti=232abs(sin(i),1≤i≤64)，在MD5算法的64步混合操作中，每步依次使用一個(gè)常數(shù)，因此，每步操作使用的常數(shù)是固定不變的。文獻(xiàn)[15]提出變參數(shù)概念，并對(duì) MD5算法進(jìn)行了改進(jìn)。方法是：構(gòu)造一個(gè)參數(shù)表T(T[0], …,T[256])，利用消息序列的前68個(gè)字節(jié)(不足時(shí)補(bǔ)0)生成一個(gè)68字節(jié)的索引序列I(I[0], …,I[67])，在索引序列I與參數(shù)表T之間利用一個(gè)映射，實(shí)現(xiàn)參數(shù)的動(dòng)態(tài)提取。該方法將MD5算法中的靜態(tài)常數(shù)項(xiàng)變成了動(dòng)態(tài)參數(shù)。但該算法存在以下幾個(gè)問(wèn)題：① 變參僅由消息序列的前68個(gè)字節(jié)決定，也就是說(shuō)，對(duì)68個(gè)字節(jié)以后的消息差分而言，并不引起參數(shù)項(xiàng)的變化；② 攻擊者可以從參數(shù)表T中先選定一組自己所期望的參數(shù)，然后根據(jù)映射關(guān)系逆推消息序列的前 68個(gè)字節(jié)，這樣，對(duì)攻擊者而言，又轉(zhuǎn)化為對(duì)固定常數(shù)項(xiàng)的MD5算法的攻擊；③ 為了實(shí)現(xiàn)參數(shù)可變，需要一個(gè)擴(kuò)展的參數(shù)表，新定義一個(gè)標(biāo)志數(shù)組，還需要生成一個(gè)索引序列，因而資源消耗較多。

設(shè)計(jì)散列函數(shù)的一個(gè)基本準(zhǔn)則是明文消息每比特的變化均能引起散列值中近 50%比特發(fā)生改變。因此，如果使參數(shù)項(xiàng)的取值與明文消息每比特的變化均相關(guān)，無(wú)疑對(duì)提高散列函數(shù)的安全性是極為有利的。TDHA算法只選定5個(gè)初始參數(shù)，利用擴(kuò)展整數(shù)帳篷映射的位邏輯判定功能，通過(guò)循環(huán)移位方式控制動(dòng)態(tài)參數(shù)的演化過(guò)程，增強(qiáng)了參數(shù)項(xiàng)與明文差分的關(guān)聯(lián)度，而編程實(shí)現(xiàn)又極為簡(jiǎn)單。表 2給出迭代過(guò)程中，參數(shù)的動(dòng)態(tài)演化過(guò)程。限于篇幅，表中只列出部分動(dòng)態(tài)參數(shù)值。從表2中的數(shù)據(jù)可看出，明文消息改變一個(gè)比特，就會(huì)引起動(dòng)態(tài)參數(shù)的演化過(guò)程發(fā)生很大變化。

4) 對(duì)MD結(jié)構(gòu)的改進(jìn)?；贛D結(jié)構(gòu)的散列函數(shù)一般形式如圖2所示。

圖2 基于MD結(jié)構(gòu)的散列函數(shù)

基于MD結(jié)構(gòu)的散列函數(shù)具有簡(jiǎn)單、高效和支持流處理技術(shù)等特點(diǎn)。但近年的研究發(fā)現(xiàn)，基于MD結(jié)構(gòu)來(lái)構(gòu)造散列函數(shù)存在嚴(yán)重的安全缺陷。由于MD結(jié)構(gòu)的散列函數(shù)采取迭代級(jí)聯(lián)方式，只要出現(xiàn)了碰撞而且余下的輸入一樣，那么散列值就一定相同，若消息 m和m′有相同的散列值，則對(duì)任意的X，有h(m||X)=h(m′||X)。針對(duì)這一安全隱患，甚至可以構(gòu)造出具有實(shí)際意義的碰撞實(shí)例。為了解決這種部分消息碰撞問(wèn)題，文獻(xiàn)[16]提出采用并行層疊方式來(lái)擴(kuò)展中間狀態(tài)。但這種改進(jìn)方式是以降低執(zhí)行效率為代價(jià)的。本文提出的TDHA算法，除了有5個(gè)32bit的字組成的160bit的中間狀態(tài)變量，另外還有 5個(gè)動(dòng)態(tài)演化參數(shù)，前級(jí)的輸出狀態(tài)H(160bit)及動(dòng)態(tài)參數(shù)演化結(jié)果K分別作為后級(jí)的初始向量及動(dòng)態(tài)參數(shù)的初始值(如圖3所示)，若消息m和m′有相同的散列值，但動(dòng)態(tài)參數(shù)演化結(jié)果K和K′不同，則對(duì)任意的X，顯然h(m||X)與h(m′||X)不會(huì)發(fā)生碰撞，只有消息 m和m′有相同的散列值，且動(dòng)態(tài)參數(shù)演化結(jié)果 K和K′也相同的情況下，對(duì)任意的 X，才會(huì)有 h(m||X)=h(m′||X)。顯然，由于引入動(dòng)態(tài)參數(shù),在無(wú)需擴(kuò)展中間狀態(tài)的情況下，提高了散列函數(shù)抵抗部分消息碰撞攻擊的能力。

表2 動(dòng)態(tài)參數(shù)的演化過(guò)程

圖3 TDHA的迭代結(jié)構(gòu)

5) TDHA算法秉承了傳統(tǒng)散列算法描述簡(jiǎn)單，易于實(shí)現(xiàn)的設(shè)計(jì)理念，借鑒并改進(jìn)了混沌密碼學(xué)研究中廣泛采用的帳篷映射模型，將其從實(shí)數(shù)域變換到整數(shù)域中，利用其拉伸與折疊的非線性本質(zhì)及均勻分布特性實(shí)現(xiàn)消息的混淆與擴(kuò)散。算法全部采用基于 32bit操作數(shù)的一些簡(jiǎn)單位操作，便于軟硬件高速實(shí)現(xiàn)。

6) 傳統(tǒng)散列函數(shù)的操作步只能用串行方式實(shí)現(xiàn)，TDHA算法的壓縮函數(shù)內(nèi)部的迭代結(jié)構(gòu)與MD5、SHA-1等不同，適應(yīng)于并行方式實(shí)現(xiàn)。

4 非線性擴(kuò)散特性的統(tǒng)計(jì)分析

密碼算法的混淆與擴(kuò)散程度可以通過(guò)非線性擴(kuò)散特性的統(tǒng)計(jì)檢測(cè)給出一個(gè)概率上的結(jié)論。用統(tǒng)計(jì)方法對(duì)密碼算法的非線性擴(kuò)散程度進(jìn)行分析通常要包括算法的完全性、雪崩效應(yīng)及嚴(yán)格雪崩準(zhǔn)則等方面。按文獻(xiàn)[17]的定義：完全性是指函數(shù)輸出值的每一個(gè)比特都與消息輸入的所有比特有關(guān)，雪崩效應(yīng)是指消息輸入中任意一個(gè)比特的改變都應(yīng)造成輸出平均半數(shù)比特的改變，嚴(yán)格雪崩準(zhǔn)則是指消息輸入中任意一個(gè)比特的改變都會(huì)造成輸出的每一個(gè)比特以1/2的概率發(fā)生改變。

設(shè)H是一個(gè)n bit輸入、m bit輸出的散列算法，輸入向量為x=(x1,…,xn)∈(0,1)n，僅改變x的第i bit后的輸入向量為x(i)∈(0,1)n。它們經(jīng)過(guò)壓縮映射后對(duì)應(yīng)的輸出向量分別記為 H(x)、H(x(i))∈(0,1)m。

(·)j表示向量的第 j bit，w(·)表示向量的漢明重量，#{·}表示集合的勢(shì)。設(shè)X為散列算法輸入的樣本空間，記 aij=#{x∈X| (H(x))j≠(H(x(i)))j}(其中i=1,2, …,n; j=1,2, …,m)表示X中的輸入向量x和x(i)對(duì)應(yīng)的輸出向量之間第j bit不同的個(gè)數(shù)；bij=#{x∈X|w(H(x(i))-H(x))=j}(其中 i=1,2,…, n;j=1, 2,…,m)表示X中的輸入向量x和x(i)對(duì)應(yīng)的輸出向量之間的差分漢明重量為j的個(gè)數(shù)。定義3個(gè)統(tǒng)計(jì)度量：

完備性程度的度量：

雪崩效應(yīng)程度的度量：

嚴(yán)格雪崩程度的度量：

若 H(·)是隨機(jī)變換，zα/2表示標(biāo)準(zhǔn)正態(tài)分布的α/2分位點(diǎn)，文獻(xiàn)[18]給出如下結(jié)論：

1) 測(cè)試的樣本量X至少應(yīng)為nm(zα/2)2；

2) p(dc)=1-2-#X≈1.0；

這里有必要指出：理想的散列函數(shù)應(yīng)該是從所有可能的輸入值到有限可能的輸出值集合的一個(gè)隨機(jī)映射。嚴(yán)格地講，像隨機(jī)映射這樣的散列函數(shù)是不存在的。因?yàn)樯⒘泻瘮?shù)是確定性的，而確定性和均勻輸出特性意味著輸出的熵大于其輸入的熵。但根據(jù)香農(nóng)熵理論，一個(gè)確定性函數(shù)決不可能放大熵。本文的設(shè)計(jì)目標(biāo)是使散列函數(shù)與隨機(jī)映射在概率分布上無(wú)法區(qū)分。一個(gè)實(shí)際的散列函數(shù)，測(cè)試其統(tǒng)計(jì)量dc、da、dsa，若落入其置信區(qū)間，則說(shuō)明散列算法滿足非線性擴(kuò)散的基本要求，即可以認(rèn)為散列函數(shù)具有很好的完全性和雪崩效應(yīng)，滿足嚴(yán)格雪崩準(zhǔn)則。

取輸入長(zhǎng)度n=512bit，輸出長(zhǎng)度m=160bit，在顯著水平α=0.05下，理論上得到如下結(jié)果：

1) zα/2=1.92, 選取樣本容量X為320 000；

2) dc=1.000 000；

3) E{da}=0.999 888，其置信區(qū)間為(0.999 876,0.999 900)；

4) E{dsa}=0.998 589；其置信區(qū)間為(0.998 577,0.998 601 2)。

在上述條件下，隨機(jī)選取320 000組512bit字(取自Visual C的Rand())的樣本集X作為TDHA算法的消息輸入，實(shí)際的測(cè)試結(jié)果如表3所示。

從表3可以看出，在顯著水平α=0.05的情況下，TDHA算法在迭代7拍之后統(tǒng)計(jì)量dc、da、dsa落入了各自的置信區(qū)間，從而滿足了散列算法非線性擴(kuò)散性的基本要求。需要指出的是，為便于軟硬件高速實(shí)現(xiàn)，TDHA算法采取了并行迭代結(jié)構(gòu)。而傳統(tǒng)的散列函數(shù)(MD5, SHA-1等)若改用并行結(jié)構(gòu)，則很難滿足擴(kuò)散性要求。

表3 TDHA算法擴(kuò)散性能的逐拍統(tǒng)計(jì)結(jié)果

5 抗碰撞性分析

散列函數(shù)的值域與定義域相比規(guī)模要小得多，是“多對(duì)一”映射。找出2個(gè)不同的消息，使其產(chǎn)生相同的散列結(jié)果稱為碰撞攻擊。通過(guò)以下的實(shí)驗(yàn)來(lái)定量測(cè)試本文算法的抗碰撞能力[9]：在明文空間中隨機(jī)選取一段明文求出其散列值，并以單字節(jié)字符的方式來(lái)表示，然后隨機(jī)地選擇并改變明文中1bit的值得到另一新的散列結(jié)果。定義2個(gè)散列值之間的距離為

其中，ei和ei′分別是最初的和新的散列值的第 i個(gè)字符，S為散列值對(duì)應(yīng)字符的個(gè)數(shù)，函數(shù) t(·)將 ei和ei′轉(zhuǎn)換成對(duì)應(yīng)的十進(jìn)制數(shù)。若2個(gè)散列值分別由2個(gè)獨(dú)立的均勻分布的隨機(jī)序列所組成，則理論上散列值的單位字符的平均距離為85.33[9]。

取輸入長(zhǎng)度n=512bit，隨機(jī)選擇輸入樣本，測(cè)試其輸出的單位字符的平均距離。經(jīng) 10萬(wàn)次統(tǒng)計(jì)測(cè)試，得到實(shí)際的測(cè)試結(jié)果如表4所示。

從表4可以看出，TDHA算法在迭代7拍之后，其輸出的單位字符的平均距離趨于穩(wěn)定，并且與理論值十分接近。這一測(cè)試結(jié)果表明，僅有1bit不同的2個(gè)明文所得到的2個(gè)散列值統(tǒng)計(jì)上由相互獨(dú)立的2個(gè)均勻隨機(jī)序列構(gòu)成。因此，依據(jù)本概率模型，無(wú)法將TDHA算法與隨機(jī)映射相區(qū)分。

表4 TDHA算法抗碰撞性的逐拍統(tǒng)計(jì)結(jié)果

6 TDHA算法的速度

TDHA與 SHA-1都輸出 160bit的散列值。SHA-1算法作4輪計(jì)算，共計(jì)80步混合操作，總共進(jìn)行224次循環(huán)移位，每步混合操作需要進(jìn)行一次邏輯函數(shù)計(jì)算；TDHA算法作3輪計(jì)算，共計(jì)60步混合操作，總共約進(jìn)行190次循環(huán)移位，每步混合操作需要進(jìn)行一次整數(shù)帳篷映射計(jì)算。表5給出了在P4、2.0GHz主頻條件下，3種散列函數(shù)(TDHA，MD5，SHA-1)用 C語(yǔ)言實(shí)現(xiàn)的速度測(cè)試結(jié)果。從表5可見(jiàn)，TDHA算法已接近MD5算法的速度，比SHA-1算法明顯要快。另外，TDHA算法的內(nèi)部迭代結(jié)構(gòu)使得它易于并行實(shí)現(xiàn)，多處理器環(huán)境下，在時(shí)間性能上有較大的提升空間。

表5 3種散列函數(shù)的速度比較

7 結(jié)束語(yǔ)

鑒于目前傳統(tǒng)散列函數(shù)的安全性受到嚴(yán)重威脅，本文主要對(duì)散列函數(shù)的設(shè)計(jì)思想進(jìn)行了一些新的探索，改進(jìn)了傳統(tǒng)散列函數(shù)的設(shè)計(jì)準(zhǔn)則,一方面提高了散列函數(shù)的性能，另一方面，也避免了散列算法設(shè)計(jì)總是走近親路線的現(xiàn)狀。作者希望這些探索能對(duì)新的散列函數(shù)標(biāo)準(zhǔn)的建立有一定指導(dǎo)意義。

現(xiàn)有的散列函數(shù)中，MD5是4輪，SHA-1是4輪，RIPEMD是5輪，HAVAL輪數(shù)可變(3到5輪)。本文之所以給出3輪的TDHA算法，除了兼顧算法的執(zhí)行效率外，同時(shí)也考慮到以下因素：人們?cè)谶M(jìn)行散列函數(shù)的分析與攻擊中，對(duì)于多輪的散列函數(shù)，總是首先采用降低輪數(shù)的辦法來(lái)進(jìn)行。對(duì)于大于 3 輪的散列函數(shù)，如果降低到 3輪后是不安全的，則該散列函數(shù)的安全性也是難以令人信服的，至少可以認(rèn)為其設(shè)計(jì)準(zhǔn)則存在某些缺陷。

非線性擴(kuò)散特性分析及抗碰撞性分析結(jié)果表明，本文給出的3輪TDHA算法已具有很強(qiáng)的安全性，用統(tǒng)計(jì)方法無(wú)法將其與真正的隨機(jī)函數(shù)相區(qū)分。TDHA算法實(shí)現(xiàn)簡(jiǎn)單，并且有明顯的執(zhí)行效率上的優(yōu)勢(shì)。在今后的改進(jìn)版本中，將對(duì)算法進(jìn)行優(yōu)化，通過(guò)引入消息擴(kuò)展機(jī)制及增加輪數(shù)的辦法，進(jìn)一步提高算法的安全性。

[1] WANG X Y, FENG D G, LAI X J, et al. Collisions for hash functions MD4, KD5, HAVAL-128 and RIPEMD[A]. Advances in Cryptology－CRYPTO 2004:The 24rd Annual International Cryptology Conference[C]. Berlin:Springer-Verlag, 2004.

[2] LUCKS S, DAUM M. The story of alice and her boss: hash functions and the the blind passenger attack[A]. Rump Session of Eurocrypt’05[C].2005.

[3] WANG X Y, YIN Y L, YU H B. Finding collisions on the Full SHA-1[A]. Advances in Cryptology--Crypto’05[C]. LNCS 3621, 2005.17-36.

[4] DAMGARD I. A design principle for hash functions[A]. Advances in Cryptology:CRYPTO89[C]. volume 435 of Lecture Notes in Computer Science. Springer- Verlag, 1989.416-427．

[5] WONG K W. A combined chaotic cryptographic and hash ing scheme[J]. Phys Lett A, 2003,307:292-298.

[6] YI X. Hash function based on chaotic tent maps[J]. IEEE Transactions on Circuits and Systems-Ⅱ: Express briefs,2005,52(6):354-357

[7] 劉軍寧, 謝杰成, 王普. 基于混沌映射的單向散列函數(shù)構(gòu)造[J]. 清華大學(xué)學(xué)報(bào), 自然科學(xué)版,2000,40(7): 55-58.LIU J N , XIE J C, WANG P .One way hash function construction based on chaotic mappings[J]. Journal of Tsinghua University, Science& Technology, 2000,40(7):55-58.

[8] XIAO D, LIAO X F, DENG S J. One-way hash function construction based on the chaotic map with changeable- parameter[J]. Chaos, Solitons and Fractals,2005,24:65-71.

[9] 盛利元, 李更強(qiáng), 李志煒. 基于切延遲橢圓反射腔映射系統(tǒng)的單向散列函數(shù)構(gòu)造[J]. 物理學(xué)報(bào), 2006,55(11):5700-5706.SHENG L Y, LI G Q, LI Z W. One-way hash function construction based on tangent-delay ellipse reflecting cavity-map system[J]. Acta Physica Sinica, 2006,55(11):5700-5706.

[10] LI S J, MOU X Q, et al. On the security of a chaotic encryption scheme: problems with computerized chaos in finite computing precision[J]. Computer Physics Communications, 2003, 153:52-58.

[11] 王繼志,王英龍，王美琴. 一類基于混沌映射構(gòu)造散列函數(shù)方法的碰撞缺陷[J]. 物理學(xué)報(bào)，2006,55(10):5048-5054.WANG J Z, WANG Y L, WANG M Q. The collision problem of one kind of methods for constructing one-way hash function based on chaotic map[J]. Acta Physica Sinica, 2006,55(10):5048-5054.

[12] LIU J D. One-way hash function construction based on integer coupled tent maps[A]. International Symposium on Computer Science and Technology[C]. Ningbo, China, 2007.

[13] 劉建東,余有明. 基于可變參數(shù)雙向耦合映像系統(tǒng)的時(shí)空混沌散列函數(shù)設(shè)計(jì)[J]. 物理學(xué)報(bào), 2007,56(3):1297-1304.LIU J D, YU Y M. A TCML-based spatiotemporal chaotic one-way散列 function with changeable-parameter[J]. Acta Physica Sinica,2007, 56(3): 1297-1304.

[14] 劉建東, 付秀麗. 基于耦合帳篷映射的時(shí)空混沌單向散列函數(shù)構(gòu)造[J]. 通信學(xué)報(bào)，2007,28(6):30-38.Liu J D, Fu X L. Spatiotemporal chaotic one-way hash function construction based on coupled tent maps[J]. Journal on Communications,2007,28(6):30-38.

[15] HSIEH T M, YEH Y S, LIN C H, et al. One-way hash function with changeable parameter[J]. Information Sciences, 1999,118:223-239.

[16] LUNCKS S. Design principles for iterated hash functions[EB/OL].E-print Archive. http://eprint.iacr.org/ 2004/253.pdf, 2004.

[17] WEISTER A F, TAVARES S E. On the design of S-boxes[A]. Advances in Cryptology-CRYPTO’85[C]. Berlin: Springer-Verlag, 1986.523-533.

[18] 朱明富, 張寶東, 呂述望. 分組密碼算法擴(kuò)散特性的一種統(tǒng)計(jì)分析[J].通信學(xué)報(bào), 2002,23(10):122-128.ZHU M F, ZHANG B D, LV S W. A statistical method of blockcipher on diffusion & propagation[J]. Journal on Communications,2002,23(10):122-128.