陳士偉，金晨輝

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

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

陳士偉1,2，金晨輝1

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

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

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

1 引言

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

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

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

3)抗第二原像性：對(duì)于給定的消息M1和對(duì)應(yīng)的雜湊值 h=H( M1)，找到另一個(gè)消息 M2≠M(fèi)1，使H( M2)=h在計(jì)算上是不可行的。

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

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

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

2 基本概念

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

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

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

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

2.2 “特洛伊”消息攻擊

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

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

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

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

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

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

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

3.1 算法描述

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

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

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

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

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

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

Step4搜索長(zhǎng)度為n塊的一個(gè)值y1，使

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

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

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

Step8輸出“特洛伊”消息

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

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

Step2輸出消息則

3.2 算法復(fù)雜性分析

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

1)第1階段

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

2)第2階段

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

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

4 結(jié)束語

本文通過分析聯(lián)接雜湊函數(shù)的特點(diǎn)，綜合利用Joux的多碰撞和“鉆石樹”結(jié)構(gòu)多碰撞，首次提出了對(duì)聯(lián)接雜湊函數(shù)的固定前綴“特洛伊”消息攻擊，其存儲(chǔ)復(fù)雜性為 2l + 2n?l+1+ n ?2k+1塊消息，時(shí)間復(fù)雜性為 O( n ? 2n+k+l?2l)次壓縮函數(shù)運(yùn)算，遠(yuǎn)低于理想的時(shí)間復(fù)雜性。這說明聯(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]陳士偉,金晨輝. 對(duì)強(qiáng)化MD結(jié)構(gòu)雜湊函數(shù)的一個(gè)新的“牧群”攻擊[J]. 電子與信息學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61272041）

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

陳士偉（1983-），女，河南唐河人，解放軍信息工程大學(xué)講師，主要研究方向?yàn)閷?duì)稱密碼算法分析。

金晨輝（1965-），男，河南扶溝人，解放軍信息工程大學(xué)教授，主要研究方向?yàn)槊艽a學(xué)與信息安全。