一種改進的寬管道Hash結構模型

摘 要： 寬管道結構是由Lucks在2005年的亞洲密碼學會議上提出的改進MD結構Hash函數模型。寬管道結構由于迭代寬度大于輸出寬度，可能會產生內部碰撞，攻擊者可能使用離線攻擊并結合不動點攻擊的方法對寬管道結構的Hash函數造成安全威脅。在寬管道的結構模型基礎上，結合隨機Hash的思想，提出一種改進的Hash模型，稱為加鹽寬管道（SWP）模型。并從碰撞抵抗性的角度證明并驗證了新的SWP結構的安全性不弱于原始的SWP結構模型，并能抵抗任何離線攻擊。

關鍵詞： 寬管道結構； Hash函數； 隨機Hash； 碰撞抵抗

中圖分類號： TN711?34； TP309 文獻標識碼： A 文章編號： 1004?373X（2016）03?0086?04

An improved Hash model based on wide pipe structure

ZHAO Linsen1， XUE Ning2， LIU Jingmei2

（1. College of Electronic Engineering， Xi’an University of Post Telecommunications， Xi’an 710061， China；

2. National Key Laboratory of Integrated Service Networks， Xidian University， Xi’an 710071， China）

Abstract： A Hash function model of improved MD structure is proposed， which is based on wide pipe structure presented by Lucks on Asiacrypt Conference in 2005. Since the output width is large than the iteration width， the wide pipeline structure is easy to generate interior collision. The method of combining offline attack with fixed point attack is used by the attacker to form security threat for Hash function of wide pipe structure. Based on the wide pipe structure model， and in combination with the thought of random Hash， an improved Hash model of salt wide pipe （SWP） model is proposed. Proceeding from the aspect of collision resistivity， the fact that the security of the new SWP structure is better than that of the original SWP structure model is proved and verified. The structure can resist any offline attack.

Keywords： wide pipe structure； Hash function； random Hah； collision resistance

0 引 言

由于MD?x系列函數的成功破解[1?2]，嚴重威脅了被廣泛使用的基于MD結構Hash函數的安全性[3?4]，在2005年亞密會上，Lucks提出了改進MD結構的Hash模型——寬管道（Wide Pipe）[5]，此模型在[g]變換時采用壓縮產生截斷的寬度為Hash寬度的輸出，較MD結構有更強的多碰撞抵抗性和長消息的第二原像攻擊抵抗性。但寬管道結構由于迭代寬度大于輸出寬度，可能會產生內部碰撞，攻擊者可能使用離線攻擊并結合不動點攻擊的方法對寬管道結構的Hash函數造成安全威脅。本文在Lucks提出的寬管道模型的基礎上，在每一輪迭代時加入隨機的鹽值，使得寬管道模型具有隨機Hash的特點，從而對離線攻擊免疫。在通過分析新結構的碰撞抵抗性的基礎上，證明了新結構的碰撞抵抗性至少與原始寬管道結構模型相當，并在本文最后與較為常見的幾種Hash模型做了簡單的對比，分析了這種新模型的實用性。

1 改進的寬管道模型

針對Lucks提出的改進MD結構的Hash模型——寬管道（Wide Pipe），提出一種改進的寬管道結構模型，稱為加鹽寬管道SWP（Salted Wide Pipe）模型。該模型是在寬管道迭代結構的基礎上，加入隨機Hash思想，提出的Hash結構。主要思想是在算法的每一步迭代時加入一個隨機的[salt]值，稱為加鹽寬管道。在新的模型下算法的安全特性不弱于原始Wipe Pipe結構的安全特性，同時效率與原始Wipe Pipe結構相當。結構如圖1所示。

設填充后的消息為[M=m1||m2||…||ml，]壓縮函數[C：{0，1}m×{0，1}s×{0，1}w→{0，1}w，]選取一組值[（H0，salt）]作為迭代初值，最后使用壓縮函數[G：{0，1}w→{0，1}n]將中間鏈變量壓縮為[n]比特的輸出值。

（1） 對消息[M]填充分塊，記為[M=m0||m1||…||ml-1，]其中[l]為消息塊個數，[mi]的長度為[m]。

（2） 對分塊的消息迭代處理[hi=C（mi，salt，hi-1）]。

（3） 計算輸出值[H（M）=G（hl）]。

2 隨機預言機和碰撞分類

本節介紹隨機預言相關概念，然后對幾種碰撞簡單分類，并給出隨機預言模型下幾種函數的碰撞模型。

隨機預言機：如果函數[f：{0，1}a→{0，1}b]的輸出是均勻一致的，稱[f]為固定長度的隨機預言，一致是指函數[f]對同樣輸入產生同樣的輸出；如果[a]的大小是可選的（變化的），[a∈{0，1，2，…}，]稱[f]為變長隨機預言。如果隨機預言函數是可以訪問的，稱隨機預言函數是隨機預言機。完美的壓縮函數是固定長度的隨機預言機，可變長度的隨機預言是理想的Hash函數。

香農預言機：如果隨機預言函數[E：{0，1}n×{0，1}m→{0，1}n]是可逆的，稱[E]為香農預言。完美的分組密碼是香農預言，記[E]的逆函數為[E-1，]對于給定的輸入[x]和[M，]可以使用香農預言機輸出[y=E（x，M）；]給定[y]和[M，]可以使用預言機得到[x=E-1（y，M）]。

設Hash函數[H：{0，1}*→{0，1}n，]定義以下三個碰撞攻擊：

[K?]碰撞：對于[K≥2]，找出[K]個不同的消息[Mi，]滿足[H（M1）=H（M2）=…=H（Mk）。]

[K?way]（第二）原像碰撞：對于[K≥1]，給定[Y]（或給定[M，][Y=H（M）]），對于[K]個不同的消息[M1，M2，…，MK]，每一個消息[Mi]滿足[H（Mi）=Y]且[Mi≠Y]。

二次碰撞：給定一對碰撞[A]和[B，]滿足[H（A）=H（B），]找出另外一對碰撞[C]和[D，][C?{A，B，D}，]滿足[H（C）=H（D）]。

[K?]碰撞和[K?way]碰撞為Hash函數設計中需要考慮的兩種碰撞，原像和第二原像碰撞。二次碰撞是衡量Hash算法的另外一個指標，假設攻擊者很“幸運”的找到了Hash函數一對碰撞，二次碰撞抵抗性是衡量攻擊者通過已經找到的這對碰撞來獲得更多碰撞的計算復雜度。

對于[K?]碰撞、[K?way]碰撞、二次碰撞有下面的兩個結論：

結論1：找出隨機預言機[f：{0，1}m+n→{0，1}n]或[H：{0，1}*→{0，1}n]的一個[K?]碰撞的計算復雜度是[2（K-1）n/K]，找出一個[K?way]的計算復雜度[6]為[K2n。]

結論2：給出隨機預言機[f：{0，1}m+n→{0，1}n]或[H：{0，1}*→{0，1}n]的一對碰撞，找出二次碰撞的計算復雜度[6]為[2n2。]

3 SWP結構的碰撞分析

設[M=m0||m1||…||ml-1]和[N=n0||n1||…||nl-1]為兩個SWP的輸入消息，[hMi]和[hNi]表示消息[M]和[N]的鏈中間變量值。為方便分析，先引入下面的定義：

定義1 末尾碰撞（Final Collision）：[hMl]和[hNl]值不同，[C]的輸出值相同，即在最后的壓縮階段發生碰撞（[hMl≠hNl，][C（hMl）=C（hNl）]）。

定義2 內部碰撞（Internal Collision）：對于不同的消息[M]和[N，][hMi]和[hNi]的值相同，即[M≠N，][hMi=hNi，]這種碰撞發生在中間迭代過程。

定義3 [K?]末尾碰撞：對于[K?]碰撞消息[M1，M2，…，][MK]（即滿足[H（M1）=H（M2）=…=H（MN）]的消息），如果任意兩個消息[Mi，][Mj]是末尾碰撞的，稱[M1，M2，…，MK]為[K?]末尾碰撞。

3.1 [K?]碰撞抵抗性分析

定義壓縮函數[C]和[G]的級聯函數為[f：{0，1}w×][{0，1}s×{0，1}t→{0，1}n，][f（H，salt，M）=][G（C（H，salt，M））]。假設[C]是碰撞抵抗的，[f]是[K?]碰撞抵抗，并假設找到[C]的一對碰撞復雜度為[T，]找到[f]的一對碰撞為[T（K）]。

定理1 SWP的[K?]碰撞復雜度：找出一對SWP結構Hash函數[H]的[K?]碰撞的復雜度為[min{T，T（K）}]。

證明：任何一對[K?]末尾碰撞的是[f]的[K?]碰撞；如果函數[H]的[K?]碰撞不是末尾碰撞，則一定產生了內部碰撞；對于所有的[H0]和[salt，]找出一對內部碰撞等價于找出[C]的一對碰撞。所以找出[H]碰撞的難度至少和找出[C]的一對碰撞或找出[f]的一對碰撞的難度相當，復雜度為[min{T，T（K）}]。

定理2 SWP的[K?]碰撞抵抗性：考慮攻擊者可以任意選擇[H0]和[salt]。

（1） 如果[C]和[G]都是隨機預言函數，且兩者相互獨立，攻擊者找出一對[H]的[K?]碰撞的復雜度為[min{2w，2（K-1）n/K}]。

（2） [C]為隨機預言函數，[G]是[C]的[n]比特截斷輸出，攻擊者找出一對[H]的[K?]碰撞的復雜度為[min{2w2，2（K-1）n/K}]。

證明： 由第2節中的結論1知[T=2w2]。當[G]具有隨機預言性質且與[C]相互獨立時，[T（K）=2（K-1）n/K]；當[G]是[C]的[n]比特截斷時，可以把[f]看作[n]比特輸出的隨機預言函數，[T（K）=2（K-1）n/K]。結合前面的結論，找出一對[H]的[K?]碰撞的復雜度為[min{2w2，2（K-1）n/K}]。

3.2 [K?way]（第二）原像碰撞抵抗性分析

函數[f]如3.1中的定義，依然假設找出[C]的一對碰撞的復雜度為[T，]假設找出[f]的一個[K?way]碰撞的復雜度為[P（K）]。

定理3 [K?way]原像碰撞的復雜度：考慮攻擊者可以任意選取[H0]和[salt]。

（1） 攻擊者找到[H]的一個原像的復雜度為[P（1）]。

（2） 攻擊找到[H]的一個[K?way]原像的復雜度為

[min{T，P（K）}]。

證明：找出一個[H]的（第二）原像，等價于找出一個[f]（第二）原像。所以找出[H]的一個[K?way]等同于找出[H]的一個內部碰撞或找出[f]的[K?way]碰撞，而找出內部碰撞等價于獲得[C]的一個碰撞。

定理4 [K?way]（第二）原像碰撞抵抗性：假設[C]和[G]都是隨機預言函數，攻擊者可以任意選擇[H0]和salt。

（1） 找到[H]的一個碰撞的復雜度為[2n。]

（2） 找到[H]的[K?way]原像的復雜度為[min{2w2，K2n}。]

（3） 找到[H]的[K?way]第二原像的復雜度為

[min{2（w+s）/2，K2n}]。

證明：（1）和（2）可以直接由結論SWP的[K?]碰撞抵抗性得出。第二原像問題可以簡化為：給定隨機輸入[X∈{0，1}w，]尋找[Xi∈{0，1}w，]且滿足[G（Xi）=G（X）]。

隨機選擇消息[M，]設填充后的消息為[M1||M2||…||Ml，]設中間鏈變量為[H1，H2，…，Hl。]定義函數[G：{0，1}w→{0，1}n]：

[G（Hl）=G（X），G（X）=G（Hl），G（Z）=G（Z）， if Z∈{X，Hl}]

式中：[X]是隨機選取的，由于[C]滿足隨機預言性質，所以[Hl]也是隨機的，[G]也滿足隨機語言性質。對于攻擊者而言，并不能把[G]和[G]區分開來，用函數[G]代替[G，]并不影響原始Hash函數的第二原像碰撞抵抗性。記在[C]和[G]的作用下的SWP結構Hash函數為[H。]假設攻擊者成功找到[C]的[l]輪的第二原像[X，]即[HCl（X）=HCl（X）]，由Joux第二原像攻擊結論可知，這一過程時間復雜度為[2w2]。假設攻擊者找到[G]的第二原像，同理可以得出這個值也為[H]的第二原像，復雜度為[K2n。]注意到，[C（HCl（X））=C（HCl（X））]，所以[HCl（X）]為[C]的第二原像，由替換等價性可以得到第3條。

3.3 SWP結構的二次碰撞抵抗性分析

定理5 假設[C]和[G]是相互獨立隨機預言函數，或者[G]是隨機預言函數[C]的截斷輸出，找出SWP結構的二次碰撞復雜度至少為[2n2。]

證明：設函數[C：{0，1}2w×{0，1}m→{0，1}w]，且函數[C]和函數[C]滿足如下關系：

[C（h||s，m）=C（h，s，m）]

用[C]代替[C，]得出在[C]和[G]下的WP結構。由于salt是隨機選取的，[C]是滿足預言性質的Hash函數，函數[C]也滿足隨機預言性質。所以SWP結構二次碰撞抵抗性不弱于寬管道的抵抗性[Ο（2n2）]。

上述結果表明，新的SWP結構是抗原像、第二原像和抗二次碰撞的。

4 SWP結構與其他結構的比較

SWP結構是WP結構的一種隨機Hash的改進，可以把每一輪加入的salt看作原始鏈中間變量的一部分，SWP結構的執行效率與WP結構的效率相當。由第3節的結論知，SWP結構對碰撞（第二）原像攻擊抵抗性至少與寬管道的相當。

較傳統的MD結構，SWP結構采用了寬管道模型的思想，每一輪迭代的輸出長度大于Hash長度，然后對最后一輪的迭代輸出截取；這種多次壓縮的方法使找出原像或第二原像的復雜度大大增加。

與HAIFA結構[7]相比，在每一輪的輸入舍棄了部分變量，所以較HAIFA有更高的執行效率。

通過對WP結構引入加鹽操作，使WP結構具有了隨機Hash的性質，由于每一輪迭代之前不知道加入的slat值，所以SWP結構對所有離線攻擊或預計算的攻擊方式是免疫的，而這一特點是原始WP結構不擁有的。

SWP結構由于采用了寬管道的結構，可能產生內部碰撞，對不動點攻擊有弱抵抗性，可以在SWP結構的信息填充上面改進，如可以使用前綴填充的方法來預防這種攻擊。

5 結 論

計算能力的提升和日益成熟的密碼分析技術，使原始MD迭代結構的Hash函數的安全性受到很大威脅，如何設計出一種好的安全的Hash結構，受到密碼學愛好者的廣泛重視。本文在寬管道的結構模型基礎上，結合隨機Hash的思想，提出了一種改進的Hash模型——加鹽寬管道（SWP）模型，并從碰撞抵抗性的角度證明并驗證了新的SWP結構的安全性不弱于原始的SWP結構模型，較原始WP結構，SWP結構能夠抵抗離線攻擊。

參考文獻

[1] WANG X Y， LAI X J， FENG D G， et al. Cryptanalysis of the Hash functions MD4 and RIPEMD [C]// Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic. Aarhus： Springer Berlin Heidelberg， 2005： 1?18.

[2] WANG X Y， YU H B. How to break MD5 and other Hash functions [C]// Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic. Aarhus： Springer Berlin Heidelberg， 2005： 19?35.

[3] WANG X Y， YIN Y L， YU H B. Finding collisions in the full SHA?1 [C]// Proceedings of 25th Annual International Cryptology Conference. California： Springer Berlin Heidelberg， 2005： 17?36.

[4] WANG X Y， YU H B， YIN Y L. Efficient collision search attacks on SHA?0 [C]// Proceedings of 25th Annual International Cryptology Conference. California： Springer Berlin Heidelberg， 2005： 1?16.

[5] LUCKS S. A failure?friendly design principle for hash functions [C]// Proceedings of 11th International Conference on the Theory and Applications of Cryptology and Information Security. Chennai： Springer Berlin Heidelberg， 2005： 474?494.

[6] JOUX A. Multicollisions in iterated Hash functions： application to cascaded constructions [C]// Proceedings of 24th Annual International Cryptology Conference. California： Springer Berlin Heidelberg， 2004： 306?316.

[7] BIHAM E， DUNKELMAN O. A Framework for iterative Hash functions?HAIFA [C]// Proceedings of 2nd NIST Cryptographic Hash Conference. [S.l.]： IACR， 2007： 278?283.

[8] HALEVI S， KRAWCZYK H. Strengthening digital signatures via randomized hashing [C]// Proceedings of 26th Annual International Cryptology Conference. California： Springer Berlin Heidelberg， 2006： 41?59.