對聯(lián)接雜湊函數(shù)的“特洛伊”消息攻擊

陳士偉，金晨輝

(1. 解放軍信息工程大學三院，河南 鄭州 450002；2. 信息保障技術(shù)重點實驗室，北京 100072)

對聯(lián)接雜湊函數(shù)的“特洛伊”消息攻擊

陳士偉1,2，金晨輝1

(1. 解放軍信息工程大學三院，河南 鄭州 450002；2. 信息保障技術(shù)重點實驗室，北京 100072)

“特洛伊”消息攻擊是Andreeva等針對MD結(jié)構(gòu)雜湊函數(shù)提出的一種攻擊方法，首次將其應用于不同于MD結(jié)構(gòu)的一類雜湊函數(shù)，即聯(lián)接雜湊。結(jié)合聯(lián)接雜湊的特點，綜合利用Joux的多碰撞和深度為n?l的“鉆石樹”結(jié)構(gòu)多碰撞，構(gòu)造出了2n-bit聯(lián)接雜湊函數(shù)的長度為 n?2k塊的“特洛伊”消息，并據(jù)此首次提出了對其的固定前綴“特洛伊”消息攻擊，其存儲復雜性為 2 l + 2n?l+1+ n ?2k+1塊消息，時間復雜性為 O( n ? 2n+k+l?2l)次壓縮函數(shù)運算，遠低于理想的時間復雜性 O( n ?22n+k)。

雜湊函數(shù)；聯(lián)接雜湊；“特洛伊”消息攻擊；多碰撞；復雜性

1 引言

雜湊函數(shù)是密碼學領(lǐng)域中一類重要的密碼算法。它是將任意長度的消息轉(zhuǎn)化成固定長度的二元字符串的一類函數(shù)，雜湊的結(jié)果稱為雜湊值或摘要。若雜湊值的規(guī)模為n bit，則稱其為n-bit雜湊函數(shù)。一個雜湊函數(shù) H(M)需要滿足以下 3條基本的安全性原則。

1)抗碰撞性：找到滿足 H( M1)=H( M2)的一對碰撞消息在計算上是不可行的。

2)抗原像性：對于給定的雜湊值h，找到滿足H( M )=h的消息M在計算上是不可行的。

3)抗第二原像性：對于給定的消息M1和對應的雜湊值 h=H( M1)，找到另一個消息 M2≠M1，使H( M2)=h在計算上是不可行的。

雜湊函數(shù)的安全強度取決于雜湊值的規(guī)模，對于一個n-bit雜湊函數(shù)，如果找到產(chǎn)生相同雜湊值的一對碰撞消息的時間復雜性低于，或找到給定雜湊值的原像（或第二原像）的時間復雜性低于2n，則稱該雜湊函數(shù)是可破的。

雜湊函數(shù)主要包括2部分，即壓縮函數(shù)和迭代結(jié)構(gòu)，其中，迭代結(jié)構(gòu)是迭代壓縮函數(shù)的一種變換方式，比如雜湊函數(shù) MD5、SHA-0等所用的迭代結(jié)構(gòu)是強化的Merkle-Damgard[1,2]（簡稱MD）結(jié)構(gòu)。通常情況下，密碼學者們在壓縮函數(shù)是隨機函數(shù)或滿足某些性質(zhì)的條件下，分析迭代結(jié)構(gòu)的安全性，這類分析方法稱為對雜湊函數(shù)的一般攻擊。Merkle[1]和 Damgard[2]在壓縮函數(shù)滿足抗碰撞的條件下，證明了強化MD結(jié)構(gòu)也是抗碰撞的，因此它在最初的雜湊函數(shù)設計中是最常用的一種迭代結(jié)構(gòu)。然而，在假定壓縮函數(shù)是隨機函數(shù)的條件下，Joux[3]構(gòu)造出了MD結(jié)構(gòu)雜湊函數(shù)的2k-碰撞，即2k個不同的消息產(chǎn)生相同的雜湊值，其時間復雜性約為低于理想值之后，Kelsey和Schneier利用可擴展消息提出了對具有MD結(jié)構(gòu)的雜湊函數(shù)的長消息第二原像攻擊[4]，又利用“鉆石樹”結(jié)構(gòu)提出了對其的選擇目標強制前綴攻擊（即“牧群”攻擊）[5]。2011年，陳士偉等[6]提出了對強化MD結(jié)構(gòu)的改進“牧群”攻擊。在這些對MD結(jié)構(gòu)雜湊函數(shù)的有效攻擊被提出的同時,密碼學者們也開始嘗試著分析并設計一些不同于MD結(jié)構(gòu)的迭代結(jié)構(gòu)。2009年，Andreeva等[7]基于 Joux的?多碰撞構(gòu)造出了深度為l的“鉆石樹”結(jié)構(gòu)的方法，其時間復雜性約為并利用該方法將“牧群”攻擊應用于聯(lián)接雜湊、二次雜湊等與MD結(jié)構(gòu)不同的其他迭代結(jié)構(gòu)，進一步地將其轉(zhuǎn)化為第二原像攻擊。與此同時，他們提出了一種新的攻擊方法——“特洛伊”消息攻擊，但僅將其應用于 MD結(jié)構(gòu)雜湊函數(shù)。2013年的亞密會上，Kortelainen T等[8]提出了構(gòu)造n-bit雜湊函數(shù)的深度為d的“鉆石樹”結(jié)構(gòu)的新方法，其時間復雜性約為并提出了對MD結(jié)構(gòu)雜湊函數(shù)的 2類改進的“特洛伊”消息攻擊。但是，迄今為止，沒有文獻提出對具有不同于MD結(jié)構(gòu)的迭代結(jié)構(gòu)的雜湊函數(shù)的“特洛伊”消息攻擊。

聯(lián)接雜湊是不同于MD結(jié)構(gòu)的一種迭代結(jié)構(gòu)，它利用2個不同的雜湊函數(shù)對輸入消息進行雜湊，然后將2個雜湊的結(jié)果聯(lián)接作為雜湊值輸出，這是提高雜湊函數(shù)安全強度的一個簡單又有效的設計思想。本文將綜合利用“鉆石樹”結(jié)構(gòu)、Joux的多碰撞等多種技術(shù)，構(gòu)造出2n-bit聯(lián)接雜湊的長度為 2kn? 塊的“特洛伊”消息，并據(jù)此提出對其的“特洛伊”消息攻擊，其時間復雜性約為存儲復雜性為塊消息。

2 基本概念

下面介紹聯(lián)接雜湊函數(shù)和“特洛伊”消息攻擊的相關(guān)概念。

2.1 聯(lián)接雜湊函數(shù)

首先給出MD結(jié)構(gòu)雜湊函數(shù)的概念。

就聯(lián)接雜湊函數(shù)而言，對于任意的輸入消息，它是將2個基于不同壓縮函數(shù)的MD結(jié)構(gòu)雜湊函數(shù)的雜湊結(jié)果聯(lián)接之后作為雜湊值輸出。下面給出2n-bit聯(lián)接雜湊函數(shù) ConHFf1,f2的具體描述。

2.2 “特洛伊”消息攻擊

2009年，Andreeva等[7]提出了對雜湊函數(shù)的一種新的一般攻擊方法，即“特洛伊”消息攻擊，它本質(zhì)上是一類第二原像攻擊。其基本的攻擊思路是首先攻擊者A構(gòu)造一個“特洛伊”消息S并提供給受害者V，V從一個限定的集合中任意選擇前綴P構(gòu)成消息P||S傳遞給A。由于“特洛伊”消息 S是由攻擊者A構(gòu)造的，故如果S能夠滿足一些特定的性質(zhì)，則A就可以成功地給出消息P||S的一個第二原像。針對MD結(jié)構(gòu)雜湊函數(shù)H，Andreeva等給出了以下2類“特洛伊”消息攻擊。

1)碰撞?“特洛伊”攻擊：在S中引入一個限定的改變產(chǎn)生S′，使

2)牧群?“特洛伊”攻擊：在S幾乎不發(fā)生改變的條件下，找到 P′和 S′，使

2013年，Kortelainen T等[8]利用“鉆石樹”結(jié)構(gòu)和可擴展消息技術(shù)提出了對MD結(jié)構(gòu)雜湊的改進版本的“特洛伊”消息攻擊，即弱“特洛伊”攻擊和強“特洛伊”攻擊，其時間復雜性明顯低于文獻[5]中的攻擊方法。

然而，迄今為止，并沒有文獻對聯(lián)接雜湊抵抗“特洛伊”消息攻擊的能力進行分析。

3 對聯(lián)接雜湊函數(shù)的“特洛伊”消息攻擊算法

“特洛伊”消息攻擊中最關(guān)鍵的步驟在于“特洛伊”消息的構(gòu)造?！疤芈逡痢毕⒌某晒?gòu)造可以保證在攻擊過程中只需改變“特洛伊”消息的小部分比特，即可給出原消息的第二原像。而由聯(lián)接雜湊的描述可知，它是利用2個不同的MD結(jié)構(gòu)雜湊函數(shù)對同一消息進行雜湊，并將雜湊的結(jié)果聯(lián)接后輸出，故構(gòu)造出的“特洛伊”消息應該在2條雜湊路徑上保持一致。下面將利用Joux的多碰撞技術(shù)和“鉆石樹”結(jié)構(gòu)多碰撞技術(shù)提出對聯(lián)接雜湊的固定前綴的“特洛伊”消息攻擊，即對給定的單塊前綴 Pre，找到P′和S′，使并對該攻擊算法的計算復雜性進行分析。

3.1 算法描述

對聯(lián)接雜湊函數(shù)的固定前綴“特洛伊”攻擊分2個階段，即“特洛伊”消息構(gòu)造階段和固定前綴的第二原像攻擊階段。在“特洛伊”消息構(gòu)造階段，為了保證“特洛伊”消息在2條雜湊路徑上保持一致，首先在第 1條路徑上構(gòu)造長度為的多碰撞，然后以此多碰撞為基礎(chǔ)構(gòu)造出深度是n?l的“鉆石樹”結(jié)構(gòu)。接著，構(gòu)造出長度為n的多碰撞，然后在2n個多碰撞消息中選擇出1個使2條路徑上的消息一致。在固定前綴的第二原像攻擊階段，已構(gòu)造的具有2n?l個起始點的“鉆石樹”結(jié)構(gòu)多碰撞和長度為 l的多碰撞使能夠成功找到產(chǎn)生相同雜湊值的第二原像。下面給出算法的具體描述（如圖1所示）。

1)第1階段：“特洛伊”消息構(gòu)造階段

Step1在第1條雜湊路徑上,以IV1為初始值，計算并以ha為起始點，利用文獻[3]中 Joux的方法構(gòu)造長度為塊的多碰撞，產(chǎn)生的最終鏈接變量記為hb。

Step2在第2條雜湊路徑上，以IV2為初始值，計算隨機選擇2n?l個起始點，基于第 1條雜湊路徑上的長為的多碰撞，構(gòu)造出深度為n?l的“鉆石樹”結(jié)構(gòu)，產(chǎn)生的最終鏈接變量記為

圖1 對聯(lián)接雜湊函數(shù)的固定前綴“特洛伊”消息攻擊

Step3選擇長度為塊的一個值x0，并計算，以鏈接變量h01為起始點，構(gòu)造一個長度為n塊的多碰撞，產(chǎn)生的最終鏈接變量記為h02。

Step4搜索長度為n塊的一個值y1，使

Step5記由于對任意元素和固定的初始值 h，故從Step3構(gòu)造出的長度為n塊的多碰撞中的 2n個消息中一定能夠找到一個消息x1使則有

Step6類似于 Step3～Step5，找到滿足條件的第 i個消息xi，即：記在第1條雜湊路徑上，以h(i?1)i為起始點，構(gòu)造長度為n塊的多碰撞，產(chǎn)生的最終鏈接變量記為；搜索長度為n塊的消息yi使在第2條雜湊路徑上，從第1條雜湊路徑上產(chǎn)生的n塊長多碰撞中的2n個消息中找到一個消息xi使則有

Step7依此類推，直至找到 2k個具有類似性質(zhì)的消息

Step8輸出“特洛伊”消息

2)第2階段：輸出第二原像階段

Step1以為初始值，從第1階段的Step1中構(gòu)造的長度為 l塊的多碰撞中選擇消息，使等于“鉆石樹”的2n?l個起始點中的一個，并在“鉆石樹”結(jié)構(gòu)多碰撞中找到以此為起始點的消息M0。

Step2輸出消息則

3.2 算法復雜性分析

下面分2個階段給出聯(lián)接雜湊的“特洛伊”攻擊的時間復雜性和存儲復雜性分析結(jié)果。

1)第1階段

在Step1和Step2中，需存儲長為l塊的多碰撞和深度為n?l的“鉆石樹”結(jié)構(gòu)，共塊消息；Step5～Step7中，需存儲2k對長度為n的消息對共塊消息，故第1階段的存儲復雜性為

2)第2階段

Step1所需的時間復雜性為 2ll?次壓縮函數(shù)運算，且Step2的時間復雜性可忽略不計，故第2階段的時間復雜性為 2ll?，存儲復雜性可忽略不計。

綜合2個階段的分析結(jié)果可知，對聯(lián)接雜湊的固定前綴的“特洛伊”攻擊的時間復雜性約為次壓縮函數(shù)運算，存儲復雜性約為塊消息。由于“特洛伊”攻擊給出的第二原像的長度塊,故找到雜湊值規(guī)模為2n bit的聯(lián)接雜湊的相同長度的第二原像的理想計算復雜性為次壓縮函數(shù)運算，約為本文給出的“特洛伊”消息攻擊所需時間復雜性的2n倍。

4 結(jié)束語

本文通過分析聯(lián)接雜湊函數(shù)的特點，綜合利用Joux的多碰撞和“鉆石樹”結(jié)構(gòu)多碰撞，首次提出了對聯(lián)接雜湊函數(shù)的固定前綴“特洛伊”消息攻擊，其存儲復雜性為 2l + 2n?l+1+ n ?2k+1塊消息，時間復雜性為 O( n ? 2n+k+l?2l)次壓縮函數(shù)運算，遠低于理想的時間復雜性。這說明聯(lián)接雜湊函數(shù)不能抵抗“特洛伊”消息攻擊。

[1]MERKLE R. A certified digital signature[C]//Advances in Cryptology-CRYPTO 1989. LNCS 435,Heidelberg: Springer-Verlag,c1990:218-238.

[2]DAMGARD I. A design principle for hash functions[C]//Advances in Cryptology-CRYPTO 1989. LNCS 435,Heidelberg: Springerr-Verlag,c1990: 416-427.

[3]JOUX A. Multicollisions in iterated hash functions application to cascaded constructions[C]//Advances in Cryptology–CRYPTO 2004.LNCS 3152,Heidelberg: Springer-Verlag,c2004: 306-316.

[4]KELSEY J,SCHNEIER B. Second preimages on n-bit hash functions for much less than 2nwork[C]//Advances in Cryptology- EUROCRYPT 2005. LNCS 3494,Heidelberg: Springer-Verlag,c2005: 474-490.

[5]KELSEY J,KOHNO T. Herding hash functions and the nostradamus attack[C]//Advances in Cryptology–EUROCRYPT 2006. LNCS 4004,Heidelberg: Springer-Verlag,c2006: 183-200.

[6]陳士偉,金晨輝. 對強化MD結(jié)構(gòu)雜湊函數(shù)的一個新的“牧群”攻擊[J]. 電子與信息學報,2010,32(8): 1953-1955.CHEN S W,JIN C H. A new herding atlack on hash functions with strengthening Merke-Damgard(MD)construction[J]. Journal of Electronics amp; Information Technology,2010,32(8): 1953-1955.

[7]ANDREEVA E,BOUILLAGUET C,DUNKELMAN O,et al. Herding,second preimage and Trojan message attacks beyond Merkle-Damg?rd[C]//Selected Areas in Cryptography 2009. LNCS 5867,Heidelberg: Springer-Verlag,c2009: 393-414.

[8]KORTELAINEN T,KORTELAINEN J. On diamond structures and Trojan message attacks[C]//Advances in Cryptology–ASIACRYPT 2013,Part II,LNCS 8270. Heidelberg: Springer-Verlag,c2013: 524-539.

Trojan message attack on the concatenated hash functions

CHEN Shi-Wei1,2,JIN Chen-Hui1

(1. The Third College,PLA Information Engineering University,Zhengzhou 450002,China;2. Science and Technology on Information Assurance Laboratory,Beijing 100072,China)

The Trojan message attack was proposed by Andreeva,et al. aiming at the hash functions with MD structure.First it was applied on the hash function beyond MD structure,that was,concatenated hash. Utilizing the property of the concatenated hash,and combining the Joux’s multicollision and the “diamond” structure with the depth of n?l,a Trojan message of the length n?2kblocks for the 2n-bit concatenated hash was constructed,based on which a chosen-prefix Trojan message attack was first proposed. And the memory complexity of proposed attack is about 2 l + 2n?l+1+n ?2k+1blocks and the time complexity is about O( n? 2n+k+l?2l)computations of the compression function,much less than the ideal value O( n ?22n+k).

hash functions,concatenated hash,Trojan message attack,multicollsion,complexity

The National Natural Science Foundation of China(No.61272041)

TP918

A

2015-09-08；

2016-05-31

國家自然科學基金資助項目（No.61272041）

10.11959/j.issn.1000-436x.2016154

陳士偉（1983-），女，河南唐河人，解放軍信息工程大學講師，主要研究方向為對稱密碼算法分析。

金晨輝（1965-），男，河南扶溝人，解放軍信息工程大學教授，主要研究方向為密碼學與信息安全。