基于縮減輪數(shù)SHA-1的LPMAC的區(qū)分攻擊和SHA-0-MAC的部分密鑰恢復(fù)攻擊.pdf

1、隨著信息化時(shí)代的到來,信息成為社會發(fā)展的重要資源,是當(dāng)今世界發(fā)展的潮流和核心。而信息安全在信息社會中扮演著非常重要的角色,直接關(guān)系到國家安全,金融、商業(yè)、公安、軍事和政府等部門的正常運(yùn)作,以及人們的日常生活。隨著信息產(chǎn)業(yè)的快速發(fā)展,全球?qū)π畔踩矫娴囊筮M(jìn)一步提高,特別是電子商務(wù)的興起,使得信息加密、認(rèn)證技術(shù)以及安全傳輸協(xié)議等變得尤為重要。
　　 消息認(rèn)證碼(Message Authentication Code,簡稱MAC碼

2、)是保證消息完整性和進(jìn)行數(shù)據(jù)源認(rèn)證的基本算法,它將密鑰和任意長度的消息作為輸入,輸出一個(gè)固定長度的標(biāo)簽,使驗(yàn)證者可以能夠校驗(yàn)消息的發(fā)送者是誰,以及消息傳輸過程中是否被篡改。這在網(wǎng)絡(luò)交互中是非常重要的,因此它被廣泛應(yīng)用于各種安全協(xié)議中,如IPSec、SSL/TLS、SSH、SNMP等。
　　 目前,消息認(rèn)證碼主要有三種構(gòu)造方法--基于分組密碼(Block Ci-pher)[3,12]、雜湊函數(shù)(Hash Function)[4,5

3、7]或者泛雜湊函數(shù)族[5,13]。本文側(cè)重于對基于雜湊函數(shù)的MAC碼的安全性進(jìn)行研究。
　　 雜湊函數(shù)(Hash Function)將任意比特長的輸入消息壓縮成固定長的輸出。這個(gè)輸出稱為該消息的消息摘要(Message Digest),也稱雜湊值(Hash Value)。對雜湊函數(shù)的攻擊主要有:原像攻擊[2]、第二原像攻擊[33,66]、碰撞攻擊[10,11]及長度延展攻擊等。現(xiàn)代抗碰撞雜湊函數(shù)可以提供數(shù)據(jù)完整性保護(hù),是數(shù)字簽名

4、中的關(guān)鍵技術(shù),并被用于構(gòu)造偽隨機(jī)數(shù)生成器及消息認(rèn)證碼等[18]。一系列的雜湊函數(shù)已經(jīng)被開發(fā)出來,如MD4[53],MD5[54],SHA-0[38],SHA-1[39]以及SHA-2[40]函數(shù)族(可產(chǎn)生224,256,384和512比特雜湊值),所有這些都遵循MD(Merkle-Damg(a)rd)[20,37]結(jié)構(gòu)。1993年,美國國家標(biāo)準(zhǔn)技術(shù)局(NationalInstitute of Standards and Technolo

5、gy,NIST)開始對SHA函數(shù)進(jìn)行標(biāo)準(zhǔn)化,在FIPSPUB180(Federal Information Processing Standards Publication)中給出了安全雜湊函數(shù)標(biāo)準(zhǔn)SHA-0的規(guī)范說明。后續(xù)版本FIPS180-1將SHA-0替換為SHA-1,FIPS180-2添加了SHA-2函數(shù)族。近幾年來,王小云等提出一系列Hash函數(shù)的碰撞攻擊成果,發(fā)現(xiàn)了MD4,MD5,SHA-0,SHA-1的碰撞攻擊[58-60

6、,62]。盡管SHA-2系列還沒有實(shí)際的攻擊出現(xiàn),但是對SHA-2系列成功的碰撞攻擊將對數(shù)字簽名的安全性帶來災(zāi)難性的后果。面對Hash函數(shù)的安全性現(xiàn)狀,NIST于2007年在全球范圍內(nèi)開始新的雜湊函數(shù)標(biāo)準(zhǔn)的征集工作,預(yù)計(jì)在2012年評選出新的Hash函數(shù)標(biāo)準(zhǔn)算法,這個(gè)新算法將被稱為“SHA-3”[21,44]。
　　 雜湊函數(shù)的系列攻擊結(jié)果,也影響到其相關(guān)應(yīng)用的安全性,密碼研究人員發(fā)現(xiàn)這些碰撞路線直接導(dǎo)致了一些MAC算法的有效差

7、分攻擊[30,52],基于雜湊函數(shù)的MAC碼的安全性成為研究熱點(diǎn)。對MAC碼算法的攻擊方法主要有以下幾種:
　　 ●區(qū)分攻擊[61,63,67](區(qū)分MAC算法和隨機(jī)函數(shù)的R型區(qū)分攻擊/Distinguishing-R Attacks以及區(qū)分MAC算法基于的具體密碼元件和基于隨機(jī)函數(shù)的H型區(qū)分攻擊/Distinguishing-H Attacks)；
　　 ●偽造攻擊[8,19](攻擊者可計(jì)算隨機(jī)消息M的有效MAC值C的

8、存在性偽造/Existential Forgery,攻擊者可選擇消息M并計(jì)算有效MAC值C的選擇性偽造/Selective Forgery,對任給的消息M,都可計(jì)算有效MAC值C的一般性偽造Universal Forgery)；
　　 ●密鑰恢復(fù)攻擊[22,64,68](恢復(fù)密鑰k,從而可以任意進(jìn)行偽造。如果不能恢復(fù)全部的密鑰,則恢復(fù)部分密鑰的攻擊稱為部分密鑰恢復(fù)攻擊。通過恢復(fù)部分密鑰,猜測剩余的密鑰比特,可以極大的降低攻擊的復(fù)

9、雜度)。
　　 在導(dǎo)師的悉心指導(dǎo)下,本論文對基于SHA系列雜湊函數(shù)的MAC碼的安全性進(jìn)行分析,并有如下結(jié)果:
　　 (1)基于63步(8-70)SHA-1的LPMAC的區(qū)分攻擊
　　 在深入分析SHA-1碰撞路線中差分向量選取和碰撞概率的關(guān)系的基礎(chǔ)上,結(jié)合王小云等在FSE2009提出的新型區(qū)分器[63],適當(dāng)選取碰撞路線起始點(diǎn),將基于61步SHA-1的LPMAC的區(qū)分攻擊擴(kuò)展到63步(8-70),復(fù)雜度為2157

10、次查詢,成功率為0.70。
　　 MAC碼又稱帶密鑰的雜湊函數(shù),根據(jù)密鑰介入方式的不同,分為密鑰前置(Secret Prefix Method),或者密鑰后置(Secret Surfix Method),以及密鑰封裝(Envelope Method)等[57],秘密前置MAC碼,即將密鑰等秘密信息級聯(lián)在明文消息之前,然后進(jìn)行雜湊操作的MAC碼,是早期廣泛使用的一類MAC碼,其最初的形式為:MACk(m)=H(k‖m),但是這種M

11、AC碼易受到長度擴(kuò)展攻擊,因?yàn)樵贛erkle-Damg(a)rd迭代結(jié)構(gòu)中,我們有HIV(m1‖m2)=HH(m1)(m2),從而,如果敵手通過某種渠道獲得了消息m1的MAC值,那么他可以在不知道秘密密鑰k的情況下,偽造m1‖m2的MAC值。解決這一問題的一種方案是將消息的長度也放到秘密前置中,即:MACk(m)=H(k‖l‖padding‖m),其中“l(fā)”表示消息的長度,“padding”為消息填充,使得“k‖l‖padding”成為

12、一個(gè)完整的消息塊。這種MAC碼的構(gòu)造方式稱為LPMAC(Length Prefix MAC)[63]。
　　 王小云等的攻擊方法利用一條截?cái)嗟?1步SHA-1碰撞路線,通過來識別第一輪的一個(gè)內(nèi)部幾乎碰撞,確切的說,是發(fā)生在第14步的幾乎碰撞來進(jìn)行區(qū)分攻擊。我們知道,SHA-1的碰撞路線中,第一輪的情況最為復(fù)雜,條件數(shù)也最多,通過這種方法,可以忽略前14步的條件,而用一個(gè)碰撞來代替,從而降低問題的難度。我們發(fā)現(xiàn)對于截?cái)嗟腟HA-1

13、算法,如果不從SHA-1的第一步開始,而是從第一輪的某一步開始的話,則有可能將該方法應(yīng)用于基于更多輪數(shù)的截?cái)嗟腟HA-1的LPMAC。
　　 首先,我們對SHA-1的碰撞攻擊進(jìn)行研究。根據(jù)王小云等對安全雜湊函數(shù)(SHA-體制)的碰撞攻擊,SHA-1的碰撞路線是由一些局部碰撞構(gòu)成。局部碰撞可以分為兩種情形:單一局部碰撞和復(fù)合局部碰撞。
　　 ●單一局部碰撞是指對兩個(gè)明文M,Mˊ,雖然在以后的相鄰6步操作內(nèi)所對應(yīng)的擴(kuò)展明文塊

14、不同,但在計(jì)算H(M),日(Mˊ)的第ⅰ步操作后,輸出值相同。
　　 ●復(fù)合局部碰撞是指多個(gè)單一局部碰撞復(fù)合而成的碰撞,在不同的輪函數(shù)內(nèi),其性質(zhì)有所不同。
　　 第一圈的一個(gè)單一局部碰撞成立的概率為1/25,即需要5個(gè)條件來保證碰撞的發(fā)生。對于第二圈來說,所需條件數(shù)為2個(gè),第三圈為4個(gè),第四圈為2個(gè)。而復(fù)合碰撞攻擊的情況稍微復(fù)雜,第一圈兩個(gè)相鄰的單一碰撞不可能構(gòu)成復(fù)合局部碰撞,而第三圈的某些復(fù)合局部碰撞成立所需要的條件數(shù)

15、低于相應(yīng)幾個(gè)單一碰撞所需條件數(shù)之和,第二和第四圈的復(fù)合局部碰撞成立所需的條件數(shù)則與相應(yīng)單一碰撞所需條件數(shù)之和相等。
　　 然后,編程搜索適當(dāng)?shù)牟罘窒蛄?Disturbance Vector),我們發(fā)現(xiàn),差分向量應(yīng)滿足第一圈的條件數(shù)盡量少,同時(shí)避免不能構(gòu)成復(fù)合碰撞的情況,并且總的條件數(shù)盡量少,則有可能將該方法用于基于更多輪數(shù)的SHA-1的LPMAC。通過設(shè)定不同的初始值,按照SHA-1的消息擴(kuò)展獲得一定長度的差分向量列表,然后對這

16、些差分向量進(jìn)行篩選。由于在王小云等的方法中,第14步之后的條件數(shù)不能超過40,因此這限制了可用的差分向量的篩選。我們通過比較最終確定了一段適合的差分向量,它與王小云等所采用的差分路線中使用的差分向量的初始值相同,但整條路線作了平移。這樣使得整條路線可以達(dá)到63步,條件數(shù)為37個(gè)。確定了幾乎碰撞路線,按照王小云等的區(qū)分器,成功進(jìn)行區(qū)分攻擊,其復(fù)雜度為2157次查詢,成功的概率為0.70。
　　 (2)基于65步(12-76)SHA

17、-1的LPMAC的區(qū)分攻擊
　　 通過進(jìn)一步分析SHA-1的差分路線的特點(diǎn),發(fā)現(xiàn)可以單條路線取代兩條路線構(gòu)造新的區(qū)分器,使原本不能超過40個(gè)條件的制約擴(kuò)展為不超過80個(gè)條件,從而將基于SHA-1的LPMAC的區(qū)分攻擊由63步擴(kuò)展到65步(12-76),復(fù)雜度由2157次查詢降低為280.9次查詢。
　　 王小云等的方法有效的避免了SHA-1中第一輪的復(fù)雜情況,但所利用的區(qū)分器需要兩對消息同時(shí)滿足差分路線,極大限制了碰撞路