基于隨機函數的哈希函數

王 勇，蔡國永

（1.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林541004；2.桂林電子科技大學 計算機科學與工程學院，廣西 桂林541004）

0 引 言

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

1 哈希函數的新設計原則

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

（1）打破前提條件原則。密碼分析往往存在前提條件，如果打破這些前提，則密碼分析很難進行。顯然哈希函數的函數具體形式確定是密碼分析的必要條件，可以通過對哈希函數隨機化以破壞密碼分析的這一前提條件，采用隨機的、變化的函數來構造哈希函數。當然還有其它的前提條件可以被打破。

（2）函數具體形式f的單向性原則。對函數的具體形式f進行隨機化，并且通過方案構造出一種新的單向性，已知明文（輸入參數）m 可以很容易確定哈希函數的具體形式fi，而反過來，僅僅已知哈希值 （輸出參數）H 很難確定哈希函數的具體形式fi，這種單向性顯然增加了破譯難度。

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

（4）對差分密碼分析的 “各說各話”原則。一般對于差分密碼分析以相同的函數為前提條件之一，如果我們考慮差分的時候，兩個差分分析的明文的哈希函數的具體形式都不一樣，去進行差分密碼分析必然是困難的，因為一些輸入參數、中間參數的運算方式、轉移軌跡都完全不一樣，想要進行比特跟蹤都困難，如果通過差分進行各種方式的比較，由于兩者各說各話，驢頭不對馬嘴，所以不具有可比性，這使得差分分析非常困難。

（5）哈希函數不能或很難用數學方式來表示的 “難表達”原則。一個函數，如果能夠用數學方式表達，則密碼分析相對會容易一些，比如可以采用列出方程的方法，進行代數等攻擊，而一個難于用數學方式表達的函數，則很難進行攻擊。

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

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

2 基于隨機函數的哈希函數的構造方法

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

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

3 基于隨機函數的哈希函數的安全性分析

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

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

進一步，這種設計也容易滿足顧頭不顧尾原則，因為hash函數的具體形式與明文是相關的，中間參數與明文也是相關的，所以，改變中間參數一般會導致明文也會變化，明文變化一般也會導致哈希函數的具體形式發(fā)生變化，反之亦然，所以參數和函數兩者都是相關的，我們無法通過固定其中一個，試圖通過調整另外一個，達到破譯的目的。

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

“難表達”原則也很顯然是具備的，因為，函數的具體形式本身都是不確定的，采用某種數學方程來表示它必然困難，故很難采用代數方程攻擊之類的方法。當然這種難表達還使得到其它的密碼分析更加困難。

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

在我們進行上面討論的時候，由于約束條件越多，實際上就會導致 “解更少”，這是假定我們無法將隨機函數變成一個確定的函數的前提下，采取各個擊破的前提下。

可見，構造的哈希函數在現實的角度上來看滿足我們提出的這些新原則。

下面我們從hash函數常見的攻擊方法著手逐一討論：

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

關于抗第一原像攻擊：抗第一原像攻擊要求對于任意一個消息m，容易得到它的hash值h（m）；但反過來根據它的hash值h（m）很難推導出相應的消息m，這里的消息m 稱為h（m）的原像［10］。在這里，我們構造的函數在已知m 的時候很容易計算哈希函數的具體形式fi，也很容易得出哈希值，但是已知哈希值的時候，是無法知道哈希函數的具體形式的，即使是我們限定是某個具體的哈希函數形式fi，fi是特定的m 才能得出的，所以會增加更多的約束條件，從而增加破譯難度。

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

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

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

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

4 潛在的安全威脅分析

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

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

退一步，即使是攻擊者不能知道函數的具體形式，但是他能夠知道函數的具體形式更可能是哪個，哪個的概率較大，也會帶來安全威脅。

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

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

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

6 結束語

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

［1］LI Lin.Cryptanalysis of the Hash functions RIPEMD－128and HMAC－MD4 ［D］.Jinan：Shandong University，2007 （in Chinese）.［黎琳.Hash函數RIPEMD－128和HMAC－MD4的安全性分析 ［D］.濟南：山東大學，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］.計算機工程與設計，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）. ［張紹蘭.幾類密碼Hash函數的設計和安全性分析 ［D］.北京：北京郵電大學，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）. ［王勇，黃雄華，蔡國永.信息論與編碼 ［M］.北京：清華大學出版社，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.