王 勇，蔡國(guó)永

（1.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004；2.桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林541004）

0 引 言

現(xiàn)有的hash （又譯為哈希、雜湊、散列）函數(shù)具有固定的結(jié)構(gòu)和函數(shù)，這為密碼分析提供了便利，且近年來(lái)在hash函數(shù)分析方面取得較好的進(jìn)展，出現(xiàn)了非常有效的攻擊方法，特別是王小云提出一系列hash函數(shù)的攻擊方法，可以在現(xiàn)實(shí)中很快找到碰撞，許多研究對(duì)王小云的攻擊做了進(jìn)一步的改進(jìn)［1－5］。這促進(jìn)了新的hash算法的開(kāi)發(fā)研究。針對(duì)常見(jiàn)的MD 結(jié)構(gòu)算法存在較多的通用攻擊，比如長(zhǎng)度擴(kuò)展攻擊、多碰撞攻擊、長(zhǎng)消息第二原象攻擊、牧群 （集群）攻擊、木馬消息攻擊等，不過(guò)即使是通用攻擊依然是針對(duì)不變的算法，在SHA－3 競(jìng)賽規(guī)則中，明文禁止使用MD 引擎。針對(duì)于MD 結(jié)構(gòu)的局限性，產(chǎn)生了許多新的結(jié)構(gòu)，比如寬管道結(jié)構(gòu)［6］、雙管道結(jié)構(gòu)、Chop－MD 結(jié)構(gòu)、海綿結(jié)構(gòu)［7］等，最終Keccak算法勝出［8］。這些結(jié)構(gòu)依然是基于固定算法的。文獻(xiàn) ［9］提出了多重不確定的密碼體制的概念，即在密碼體制中增加更多的不確定因素，這會(huì)給密碼破譯帶來(lái)更大的困難，因?yàn)榇罅康拿艽a分析都是以許多因素是確定和已知作為前提條件的?，F(xiàn)在對(duì)hash的分析技術(shù)也是基于確定的算法，當(dāng)一個(gè)hash函數(shù)的算法是不確定的時(shí)候，密碼分析將很難著手。對(duì)于一個(gè)固定的函數(shù)，要保證這種單向性是比較困難的，因?yàn)樵瓌t上說(shuō)可以根據(jù)hash函數(shù)的結(jié)構(gòu)進(jìn)行逆推 （雖然它是單向的，原文和hash值是多對(duì)一的映射關(guān)系，但是在借助一些數(shù)學(xué)方法和計(jì)算工具的情況下，可能進(jìn)行成功的逆推，這提供了一個(gè)破解的入口），需要將算法設(shè)計(jì)得非常復(fù)雜。假如一個(gè)hash函數(shù)的算法是隨機(jī)的、不確定的，則密碼分析者很難著手。與傳統(tǒng)的確定函數(shù)相比，我們借鑒隨機(jī)變量，提出隨機(jī)函數(shù)的概念，即這個(gè)函數(shù)的表達(dá)式、結(jié)構(gòu)和形式是隨機(jī)的、不確定的，比如隨機(jī)函數(shù)y＝F（a，b，c），F(xiàn)（a，b，c）并沒(méi)有明確的形式，它的具體形式可能是f1（a，b，c）、f2（a，b，c）、f3（a，b，c）、f4（a，b，c）之中的一個(gè)函數(shù)，但是函數(shù)在具體的情況下卻是確定的。注意在這里的隨機(jī)函數(shù)的隨機(jī)指的是函數(shù)的形式是變化的、不確定的，理論上而言，hash函數(shù)都是可以攻破的，只是攻擊難度的問(wèn)題。鑒于確定的hash函數(shù)給予密碼分析者明確的靶子，為許多密碼分析創(chuàng)造了條件，從而影響安全性，在本文中采用隨機(jī)函數(shù)來(lái)設(shè)計(jì)hash 函數(shù)。hash 函數(shù)由復(fù)雜的運(yùn)算過(guò)程組成，但是它的關(guān)鍵部分都是集中在壓縮函數(shù) （或者利用分組密碼函數(shù)）中，所以這里討論的哈希函數(shù)主要指壓縮函數(shù)，明文一般指當(dāng)前分組的明文。

1 哈希函數(shù)的新設(shè)計(jì)原則

哈希函數(shù)設(shè)計(jì)主要是針對(duì)于現(xiàn)有的各種hash 分析方法，要求能夠抗擊各種攻擊，包括抗碰撞攻擊、抗原像攻擊、抗第二原像攻擊、抗生日攻擊等，其中抗生日攻擊主要是規(guī)定哈希值的長(zhǎng)度不能低于一定的值?？紤]到函數(shù)具體形式變化，所以我們可以將哈希值 （輸出參數(shù)）的決定因素歸結(jié)為函數(shù)和參數(shù) （輸入?yún)?shù)為明文，還有由此產(chǎn)生的中間參數(shù)）兩大部分。在本文中，從函數(shù)的具體形式變化的角度，我們給出新的設(shè)計(jì)原則，以增強(qiáng)哈希函數(shù)的安全性，主要原則包括如下幾點(diǎn)：

（1）打破前提條件原則。密碼分析往往存在前提條件，如果打破這些前提，則密碼分析很難進(jìn)行。顯然哈希函數(shù)的函數(shù)具體形式確定是密碼分析的必要條件，可以通過(guò)對(duì)哈希函數(shù)隨機(jī)化以破壞密碼分析的這一前提條件，采用隨機(jī)的、變化的函數(shù)來(lái)構(gòu)造哈希函數(shù)。當(dāng)然還有其它的前提條件可以被打破。

（2）函數(shù)具體形式f的單向性原則。對(duì)函數(shù)的具體形式f進(jìn)行隨機(jī)化，并且通過(guò)方案構(gòu)造出一種新的單向性，已知明文（輸入?yún)?shù)）m 可以很容易確定哈希函數(shù)的具體形式fi，而反過(guò)來(lái)，僅僅已知哈希值 （輸出參數(shù)）H 很難確定哈希函數(shù)的具體形式fi，這種單向性顯然增加了破譯難度。

（3）顧頭不顧尾原則。在基于隨機(jī)函數(shù)的哈希破譯中，函數(shù)具體形式fi和消息 （輸入?yún)?shù)）m 以及中間計(jì)算得到的參數(shù) （中間參數(shù)），對(duì)于破譯者而言是未知的，如果破譯者可以固定其中一個(gè)單獨(dú)去破譯另一個(gè)，則他可以各個(gè)擊破，好的哈希設(shè)計(jì)應(yīng)該是當(dāng)我們?nèi)フ{(diào)整其中一個(gè)的時(shí)候，另外一個(gè)也變化，比如調(diào)整輸入的消息的時(shí)候，函數(shù)的形式也發(fā)生了變化，這樣破譯者就顧頭不顧尾，顧尾不顧頭，破譯會(huì)很困難，明文修改會(huì)帶來(lái)哈希函數(shù)具體形式的變化，這也導(dǎo)致破譯哈希的明文 （消息）修改技術(shù)實(shí)現(xiàn)起來(lái)非常困難。

（4）對(duì)差分密碼分析的 “各說(shuō)各話”原則。一般對(duì)于差分密碼分析以相同的函數(shù)為前提條件之一，如果我們考慮差分的時(shí)候，兩個(gè)差分分析的明文的哈希函數(shù)的具體形式都不一樣，去進(jìn)行差分密碼分析必然是困難的，因?yàn)橐恍┹斎雲(yún)?shù)、中間參數(shù)的運(yùn)算方式、轉(zhuǎn)移軌跡都完全不一樣，想要進(jìn)行比特跟蹤都困難，如果通過(guò)差分進(jìn)行各種方式的比較，由于兩者各說(shuō)各話，驢頭不對(duì)馬嘴，所以不具有可比性，這使得差分分析非常困難。

（5）哈希函數(shù)不能或很難用數(shù)學(xué)方式來(lái)表示的 “難表達(dá)”原則。一個(gè)函數(shù)，如果能夠用數(shù)學(xué)方式表達(dá)，則密碼分析相對(duì)會(huì)容易一些，比如可以采用列出方程的方法，進(jìn)行代數(shù)等攻擊，而一個(gè)難于用數(shù)學(xué)方式表達(dá)的函數(shù)，則很難進(jìn)行攻擊。

（6）約束條件更多原則。在密碼分析中，受到的約束越多，參數(shù)進(jìn)行修改和調(diào)整的自由度就更小，在這樣的條件下進(jìn)行適應(yīng)性的修改以得到合適的消息 （原像）或者碰撞就會(huì)更加困難。約束條件更多可能是一個(gè)偽命題，但是我們可以只要求一定條件下或者說(shuō)在可行的密碼分析路徑下約束條件更多。

（7）在可以單一地進(jìn)行處理的求解單元下 “解更少”原則。從理論意義上來(lái)看解更少是一個(gè)偽命題，在哈希值長(zhǎng)度一定的情況下，在一定的明文消息空間中的解的數(shù)目平均而言是不變的。但是，在密碼學(xué)領(lǐng)域有許多要求從理論上看起來(lái)是偽問(wèn)題，在實(shí)際意義上卻可以認(rèn)為是成立的，比如偽隨機(jī)就是看起來(lái)是隨機(jī)的，其實(shí)并不隨機(jī)，公鑰密碼學(xué)和hash函數(shù)的單向性從理論意義上不成立，在無(wú)限的計(jì)算能力下并不是單向的，但是在實(shí)際限制下可以認(rèn)為是單向的。我們假設(shè)滿足hash值的消息稱(chēng)為破譯者可以得到的解。我們這里解更少原則就是要求單一地進(jìn)行處理的求解單元下，或者說(shuō)在可以不用逐一討論的情況下的解更少，它不能是把各種不同的函數(shù)的具體形式逐一討論。從另一個(gè)角度說(shuō)，是在具有可行性的現(xiàn)實(shí)密碼分析路徑下，比如滿足可用數(shù)學(xué)方式表達(dá)（但是不能是分類(lèi)討論這類(lèi)復(fù)雜、非單一的表達(dá)）的原則下，滿足條件的解更少。滿足條件的解更少，通過(guò)密碼分析能夠找到的解必然屬于這些解的子集，所以通過(guò)密碼分析找到的解一般會(huì)更少，找到解會(huì)更困難。

2 基于隨機(jī)函數(shù)的哈希函數(shù)的構(gòu)造方法

基于以上原則，我們來(lái)探討哈希函數(shù)構(gòu)造方法。通過(guò)對(duì)函數(shù)的具體形式進(jìn)行隨機(jī)化，將確定的函數(shù)f（m）變成隨機(jī)函數(shù)F（m），顯然是可以增強(qiáng)安全性的，但是，哈希函數(shù)值本身必須是確定的，而且不同的人都能按照某種公開(kāi)的計(jì)算規(guī)則來(lái)計(jì)算，所以對(duì)于不同的人在運(yùn)算某個(gè)具體消息的時(shí)候，函數(shù)F（m）的具體形式fi（m）不僅應(yīng)該是確定的，而且不同的人得到的i應(yīng)該是相同的，這里m 指當(dāng)前分組的明文消息，所以，應(yīng)該采用某種方式來(lái)確定函數(shù)的具體形式，我們可以構(gòu)造一個(gè)函數(shù)S 使得i＝S，利用這個(gè)函數(shù)的值來(lái)指定到底是哪個(gè)具體形式。這個(gè)函數(shù)的自變量可以采用公開(kāi)的參數(shù)、秘密的參數(shù) （比如密鑰），但是公開(kāi)參數(shù)顯然不符合安全性的考慮，這樣等于將hash的具體形式暴露給破譯者，如果采用密鑰來(lái)控制，則不符合hash函數(shù)公開(kāi)的特質(zhì)，則將hash 函數(shù)變成消息認(rèn)證碼 （MAC）。這意味著采用隨機(jī)函數(shù)構(gòu)造hash 似乎是矛盾的，不可能的。但是，我們考慮在密碼學(xué)中出現(xiàn)的許多單向性都具有這樣的特點(diǎn)：在理論上說(shuō)它是公開(kāi)的，但是實(shí)際上考慮到計(jì)算能力的限制，它又是保密的，比如無(wú)論是傳統(tǒng)的hash函數(shù)，還是公鑰密碼學(xué)，實(shí)際上他們都是可以破譯的，但是破譯計(jì)算量太大。這意味著我們可以利用類(lèi)似的單向性機(jī)制來(lái)消弭上面的這種矛盾。

對(duì)于安全的hash函數(shù)，在已知哈希值和算法的時(shí)候，明文 （消息）m 本質(zhì)上是可以推導(dǎo)的，但是通過(guò)哈希值計(jì)算明文的困難讓我們權(quán)宜地認(rèn)為它是未知的，所以，如果hash函數(shù)的具體形式由明文確定，即i＝S（m），哈希值H＝fi（m），則剛好滿足上面提到的 “已知明文可以很容易確定函數(shù)的具體形式，已知哈希值很難確定函數(shù)的具體形式”要求。因此，基于隨機(jī)函數(shù)的構(gòu)造方法可以是，首先設(shè)計(jì)不同的函數(shù)（當(dāng)然這些函數(shù)一般應(yīng)該滿足現(xiàn)有hash函數(shù)設(shè)計(jì)的原則），作為隨機(jī)函數(shù)的不同具體形式，給它們賦予不同的編號(hào)i，然后設(shè)計(jì)函數(shù)S，使得i＝S（m），這樣建立通過(guò)m 確定不同具體形式的映射關(guān)系，這樣得到明文消息m 的時(shí)候，可以確定哈希函數(shù)的具體形式，從而計(jì)算哈希值。

3 基于隨機(jī)函數(shù)的哈希函數(shù)的安全性分析

在以上設(shè)計(jì)中，由于函數(shù)具體形式未知，所以打破了密碼分析的基本條件，從而使得許多現(xiàn)有密碼分析方法無(wú)法進(jìn)行，滿足打破前提條件原則。

根據(jù)以上設(shè)計(jì)，哈希函數(shù)的生成者 （這里稱(chēng)為加密者）是可以很容易確定hash函數(shù)的具體形式的，但是，僅僅知道哈希值則不能確定哈希函數(shù)的具體形式，因此，這種設(shè)計(jì)滿足了函數(shù)具體形式的單向性原則。

進(jìn)一步，這種設(shè)計(jì)也容易滿足顧頭不顧尾原則，因?yàn)閔ash函數(shù)的具體形式與明文是相關(guān)的，中間參數(shù)與明文也是相關(guān)的，所以，改變中間參數(shù)一般會(huì)導(dǎo)致明文也會(huì)變化，明文變化一般也會(huì)導(dǎo)致哈希函數(shù)的具體形式發(fā)生變化，反之亦然，所以參數(shù)和函數(shù)兩者都是相關(guān)的，我們無(wú)法通過(guò)固定其中一個(gè)，試圖通過(guò)調(diào)整另外一個(gè)，達(dá)到破譯的目的。

哈希函數(shù)由明文確定，這意味著不同的明文一般有不同的哈希函數(shù)具體形式，差分密碼分析的對(duì)比的明文是不同的，而且尋找碰撞的目的本身就是要求不同的明文對(duì)應(yīng)相同的哈希值，所以，在這種情況下，函數(shù)的具體形式不同，導(dǎo)致現(xiàn)在采用的一些密碼分析方法的前提就失去了，比如，現(xiàn)在采用的一些密碼分析方法要求哈希函數(shù)是固定（相同）的，且是已知的，在這里采用隨機(jī)哈希函數(shù)，且函數(shù)由明文確定，導(dǎo)致了函數(shù)具體形式一般不同，這樣，由于不同函數(shù)下明文、中間參數(shù)的運(yùn)算方式不同、參數(shù)轉(zhuǎn)移軌跡都完全不一樣，想要進(jìn)行比特跟蹤會(huì)非常困難，要進(jìn)行比較和差分分析也不具有可比性。

“難表達(dá)”原則也很顯然是具備的，因?yàn)?，函?shù)的具體形式本身都是不確定的，采用某種數(shù)學(xué)方程來(lái)表示它必然困難，故很難采用代數(shù)方程攻擊之類(lèi)的方法。當(dāng)然這種難表達(dá)還使得到其它的密碼分析更加困難。

對(duì)于采用隨機(jī)函數(shù)的哈希函數(shù)，在討論的時(shí)候，我們沒(méi)有有效方法將不同的函數(shù)當(dāng)作一個(gè)函數(shù)統(tǒng)一處理，所以，分別討論不同的哈希函數(shù)的具體形式fi的時(shí)候，一方面明文消息m 運(yùn)算得到的哈希函數(shù)的具體形式應(yīng)該是fi，另外一方面，以明文m 作為輸入，用fi函數(shù)計(jì)算的結(jié)果應(yīng)該是給定的哈希值HASH，i＝S（m），HASH＝fi（m），即m需要滿足的條件更多，參數(shù)進(jìn)行修改和調(diào)整的自由度就更小，在這樣的條件下進(jìn)行適應(yīng)性的修改以得到合適的消息（原像、明文）或者碰撞就會(huì)更加困難。

在我們進(jìn)行上面討論的時(shí)候，由于約束條件越多，實(shí)際上就會(huì)導(dǎo)致 “解更少”，這是假定我們無(wú)法將隨機(jī)函數(shù)變成一個(gè)確定的函數(shù)的前提下，采取各個(gè)擊破的前提下。

可見(jiàn)，構(gòu)造的哈希函數(shù)在現(xiàn)實(shí)的角度上來(lái)看滿足我們提出的這些新原則。

下面我們從hash函數(shù)常見(jiàn)的攻擊方法著手逐一討論：

關(guān)于抗碰撞性攻擊：由于hash函數(shù)具有將任意長(zhǎng)度的消息轉(zhuǎn)化成固定長(zhǎng)度hash 值的性質(zhì)，消息的空間是非常大，而hash值的空間則很有限，所以必然是一種多對(duì)一的關(guān)系，即存在多個(gè)消息m1，m2，…，得到相同hash 值，這稱(chēng)為碰撞，在認(rèn)證的時(shí)候我們往往出示的是哈希值，有了碰撞就可能用m1假冒m2?？古鲎残怨粢笳业竭@種碰撞是困難的。在這里構(gòu)造的隨機(jī)哈希函數(shù)，由于不同的消息對(duì)應(yīng)不同的哈希函數(shù)，顯然尋找碰撞是非常困難的，我們以非常成功的差分密碼分析為例，現(xiàn)有的方法使用到了明文修改技術(shù)和比特跟蹤技術(shù)，本方法之所以能夠規(guī)避，①不同的消息對(duì)應(yīng)的哈希函數(shù)是不一樣的，所以，它們的參數(shù)的影響的軌跡和數(shù)值是不一樣的，這樣很難將它們放在一起進(jìn)行比較；②為了簡(jiǎn)化問(wèn)題，可能我們會(huì)假設(shè)碰撞消息的函數(shù)具體形式都是一樣的，這樣給差分的消息增加了約束條件，這樣滿足條件的解就會(huì)減少，甚至于沒(méi)有；③在王小云的哈希破譯中，采用了明文修改技術(shù)，在這里構(gòu)造的哈希函數(shù)，其函數(shù)的具體形式隨著明文變化而變化，一旦哈希函數(shù)的具體形式變化了，就很難對(duì)運(yùn)算進(jìn)行有效控制，出現(xiàn)顧頭不顧尾的局面。

關(guān)于抗第一原像攻擊：抗第一原像攻擊要求對(duì)于任意一個(gè)消息m，容易得到它的hash值h（m）；但反過(guò)來(lái)根據(jù)它的hash值h（m）很難推導(dǎo)出相應(yīng)的消息m，這里的消息m 稱(chēng)為h（m）的原像［10］。在這里，我們構(gòu)造的函數(shù)在已知m 的時(shí)候很容易計(jì)算哈希函數(shù)的具體形式fi，也很容易得出哈希值，但是已知哈希值的時(shí)候，是無(wú)法知道哈希函數(shù)的具體形式的，即使是我們限定是某個(gè)具體的哈希函數(shù)形式fi，fi是特定的m 才能得出的，所以會(huì)增加更多的約束條件，從而增加破譯難度。

關(guān)于抗第二原像攻擊：類(lèi)似于前面的分析，由于不同的原像的函數(shù)的具體形式不一樣，所以很難找到不同明文的哈希值是一樣的，我們也可以得出這樣的設(shè)計(jì)會(huì)增加破譯的難度。另一方面，對(duì)于確定且相同的函數(shù)，不同的原像之間可能存在關(guān)系，消息m1和消息m2的關(guān)系就可以用于破譯，但是，對(duì)于基于隨機(jī)函數(shù)的hash函數(shù)，不同的明文對(duì)應(yīng)于不同的hash函數(shù)，所以，消息m1和消息m2的關(guān)系就會(huì)很難利用于破譯。即使是我們限定兩個(gè)原像 （消息m1和消息m2）對(duì)應(yīng)于相同的hash函數(shù)具體形式，這會(huì)帶來(lái)更多的對(duì)兩個(gè)原像的限制，使得原像受到的約束條件更多，破譯更難。

在加密算法中，許多密碼分析基于統(tǒng)計(jì)特征，假如統(tǒng)計(jì)特征用于hash函數(shù)的破譯，也是存在困難的，原因在于本隨機(jī)函數(shù)F 的統(tǒng)計(jì)特征不是單個(gè)函數(shù)的統(tǒng)計(jì)特征，而且對(duì)于所有使用某個(gè)確定函數(shù)f 的明文消息m 和對(duì)應(yīng)的hash值H，由于并不是所有的明文都是使用該函數(shù)f，所以也只是該確定函數(shù)f 的明文消息和對(duì)應(yīng)hash值中的一部分的統(tǒng)計(jì)特征，因而我們使用隨機(jī)函數(shù)整體的統(tǒng)計(jì)特征，對(duì)這一部分也未必是有效的。

針對(duì)于其它的一些攻擊方法，由于我們這里打破了哈希函數(shù)形式是固定不變的這一前提，也會(huì)增加破譯的難度。

隨機(jī)函數(shù)是確定函數(shù)的一種推廣和隨機(jī)化，應(yīng)該說(shuō)確定函數(shù)是隨機(jī)函數(shù)的特例，將哈希函數(shù)的函數(shù)推廣到隨機(jī)函數(shù)，大大拓展了函數(shù)的形式和內(nèi)容，在這樣的更加寬闊的空間中必然存在更加優(yōu)秀的函數(shù)。

4 潛在的安全威脅分析

下面我們對(duì)破譯者可能采取的分析方法做一定的展望。

對(duì)于隨機(jī)函數(shù)，如果能夠想辦法確定函數(shù)的具體形式fi，則會(huì)更容易破譯，我們分析以下幾種可能性：①隨機(jī)函數(shù)的不同的具體形式的輸出值存在差異，某個(gè)輸出值或者某一部分輸出值明顯只能由某個(gè)隨機(jī)函數(shù)的具體形式fj得出，則可以確定哈希函數(shù)具體形式即為該函數(shù)fj，隨機(jī)函數(shù)退化為確定性函數(shù)，失去了前面討論的價(jià)值。②不同的隨機(jī)函數(shù)的運(yùn)算量、運(yùn)算速度不一樣，則在加密領(lǐng)域使用的能量攻擊、定時(shí)攻擊等邊信道攻擊也可能用于判定函數(shù)的具體形式。

退一步，即使是攻擊者不能知道函數(shù)的具體形式，但是他能夠知道函數(shù)的具體形式更可能是哪個(gè)，哪個(gè)的概率較大，也會(huì)帶來(lái)安全威脅。

密碼分析者還可能將F（m）的不同的具體形式f1（m）、f2（m）、f3（m）、…，統(tǒng)一為一個(gè)新的確定的函數(shù)g（m），注意到前面是m 確定了fi，這種隨機(jī)函數(shù)的統(tǒng)一是可能存在的，一旦能夠統(tǒng)一，則隨機(jī)函數(shù)可以退化為確定函數(shù)，從而喪失優(yōu)勢(shì)。

5 基于隨機(jī)函數(shù)的哈希函數(shù)的優(yōu)化思路

根據(jù)前面的分析，我們?cè)诖私o出一些優(yōu)化思路，以進(jìn)一步增強(qiáng)安全性和防范潛在的攻擊：①隨機(jī)函數(shù)的各個(gè)具體函數(shù)的輸入輸出空間 （所有可能值構(gòu)成的集合）應(yīng)該盡量是相同的，最好輸入輸出都遍歷所有可能的值，具有很好的遍歷性。②在運(yùn)算量、能耗等方面應(yīng)該具有很好的對(duì)等性，不能有太大的差異。③在消息等概率的情況下，隨機(jī)函數(shù)的各個(gè)具體形式出現(xiàn)的概率應(yīng)該是相近的，最好是等概率出現(xiàn)，即函數(shù)S 的值是等概率的。④哈希函數(shù)的各個(gè)具體形式應(yīng)該具有很大的差異，一方面可以防止統(tǒng)一為某個(gè)確定的函數(shù)，一方面使得密碼分析非常困難。⑤我們對(duì)比一個(gè)確定性hash函數(shù)，它的運(yùn)算量和隨機(jī)哈希函數(shù)的所有具體形式的運(yùn)算量都是類(lèi)似的，在采用同等運(yùn)算量的函數(shù)的情況下，本方法相比確定的函數(shù)，會(huì)存在一定的附加工作量，主要用于確定隨機(jī)函數(shù)的具體形式，這些工作量并不算大，要進(jìn)一步減少這部分工作量，可以盡量復(fù)用哈希函數(shù)運(yùn)算中的一些中間結(jié)果。為了減少運(yùn)算量，還可以將整個(gè)函數(shù)分為一些運(yùn)算部件，在一些部件中采用隨機(jī)函數(shù)部件，這樣通過(guò)乘積效應(yīng)放大隨機(jī)函數(shù)具體形式的數(shù)目，減少隨機(jī)函數(shù)設(shè)計(jì)的難度。

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

鑒于現(xiàn)有的大多數(shù)哈希函數(shù)的破譯均以知道哈希函數(shù)作為前提條件，因此去除和打破這些前提條件會(huì)帶來(lái)更好的安全性。本文打破這一前提，提出一種基于隨機(jī)函數(shù)的哈希函數(shù)的構(gòu)造方法，將傳統(tǒng)的確定函數(shù)推廣到了隨機(jī)函數(shù)，提出一些新的哈希函數(shù)的設(shè)計(jì)原則，并且論證本方法構(gòu)造的哈希函數(shù)符合這些原則，并且相對(duì)于現(xiàn)有的攻擊方法有很好的安全性。本文提出的這類(lèi)方法對(duì)設(shè)計(jì)確定函數(shù)的哈希函數(shù)同樣具有借鑒意義，比如顧頭不顧尾原則和難于表達(dá)原則?；陔S機(jī)函數(shù)的哈希函數(shù)體現(xiàn)了一種隨機(jī)變化的特點(diǎn)，這當(dāng)然是對(duì)于破譯不利的。即使是拋開(kāi)以上對(duì)具體密碼分析的討論，我們也可以很容易確定基于隨機(jī)函數(shù)的哈希函數(shù)中能夠選出更好的算法，因?yàn)閭鹘y(tǒng)的確定型hash函數(shù)只是隨機(jī)函數(shù)的一種特例，屬于其子集，在更加廣泛的隨機(jī)函數(shù)中自然能夠選出更好的函數(shù)。同樣在這一新的領(lǐng)域也會(huì)有新的問(wèn)題，比如如何選擇隨機(jī)函數(shù)的具體形式，讓它們搭配的更好。本文開(kāi)啟了一個(gè)新的領(lǐng)域，而對(duì)于這類(lèi)的哈希函數(shù)，傳統(tǒng)的攻擊方法并不能湊效 （除了暴力破解），需要有新的破譯方法，將會(huì)引出新的方向。而隨機(jī)函數(shù)也是傳統(tǒng)確定函數(shù)的一種推廣，也具有重要的研究?jī)r(jià)值。

［1］LI Lin.Cryptanalysis of the Hash functions RIPEMD－128and HMAC－MD4 ［D］.Jinan：Shandong University，2007 （in Chinese）.［黎琳.Hash函數(shù)RIPEMD－128和HMAC－MD4的安全性分析 ［D］.濟(jì)南：山東大學(xué)，2007.］

［2］WANG Yu，RUAN Yanhua，CHEN Jianhua.New attack on Haval－128 ［J］.Computer Engineering and Design，2008，29（20）：5159－5162 （in Chinese）.［汪玉，阮艷華，陳建華.新的Haval－128的碰撞攻擊 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（20）：5159－5162.］

［3］Liang Jie，Lai Xuejia.Improved collision attack on hash function MD5 ［J］.Journal of Computer Science and Technology，2007，22 （1）：79－87.

［4］Zhong Jinmin，Lai Xuejia，Duan Ming.Improved preimage attack on 3－pass HAVAL ［J］.Journal of Shanghai Jiao Tong University （Science），2011，16 （6）：713－721.

［5］ZHANG Shaolan.Design and security analysis on several cryptography Hash functions ［D］.Beijing：Beijing University of Posts and Telecommunications，2011 （in Chinese）. ［張紹蘭.幾類(lèi)密碼Hash函數(shù)的設(shè)計(jì)和安全性分析 ［D］.北京：北京郵電大學(xué)，2011.］

［6］Lucks Stefan.A failure－friendly design principle for hash functions ［G］.LNCS 3788：Advances in Cryptology－ASIACRYPT，2005：474－494.

［7］Guido Bertoni，Joan Daemen，Michael Peeters，et al.On the in differentiability of the sponge construction ［G］.LNCS 4965：Advances in Cryptology－EUROCRYPT，2008：181－197.

［8］Alshaikhli IF，Alahmad MA，Munthir K.Comparison and analysis study of SHA－3finalists［C］／／International Conference on Advanced Computer Science Applications and Technologies，2012：366－371.

［9］WANG Yong，HUANG Xionghua，CAI Guoyong.Information theory and coding ［M］.Beijing：Tsinghua University Press，2013：255－266 （in Chinese）. ［王勇，黃雄華，蔡國(guó)永.信息論與編碼 ［M］.北京：清華大學(xué)出版社，2013：255－266.］

［10］Sasaki Y，Aoki K.Finding preimage in full MD5faster than exhaustive search ［G］.LNCS 5479：Advances in Cryptology－EUROCRYPT，2009：134－152.