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

1、隨著信息化時代的到來,信息成為社會發(fā)展的重要資源,是當今世界發(fā)展的潮流和核心。而信息安全在信息社會中扮演著非常重要的角色,直接關系到國家安全,金融、商業(yè)、公安、軍事和政府等部門的正常運作,以及人們的日常生活。隨著信息產業(yè)的快速發(fā)展,全球對信息安全方面的要求進一步提高,特別是電子商務的興起,使得信息加密、認證技術以及安全傳輸協(xié)議等變得尤為重要。
　　 消息認證碼(Message Authentication Code,簡稱MAC碼

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

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

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

5、gy,NIST)開始對SHA函數(shù)進行標準化,在FIPSPUB180(Federal Information Processing Standards Publication)中給出了安全雜湊函數(shù)標準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系列還沒有實際的攻擊出現(xiàn),但是對SHA-2系列成功的碰撞攻擊將對數(shù)字簽名的安全性帶來災難性的后果。面對Hash函數(shù)的安全性現(xiàn)狀,NIST于2007年在全球范圍內開始新的雜湊函數(shù)標準的征集工作,預計在2012年評選出新的Hash函數(shù)標準算法,這個新算法將被稱為“SHA-3”[21,44]。
　　 雜湊函數(shù)的系列攻擊結果,也影響到其相關應用的安全性,密碼研究人員發(fā)現(xiàn)這些碰撞路線直接導致了一些MAC算法的有效差

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

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

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

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

11、AC碼易受到長度擴展攻擊,因為在Merkle-Damg(a)rd迭代結構中,我們有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、一個完整的消息塊。這種MAC碼的構造方式稱為LPMAC(Length Prefix MAC)[63]。
　　 王小云等的攻擊方法利用一條截斷的61步SHA-1碰撞路線,通過來識別第一輪的一個內部幾乎碰撞,確切的說,是發(fā)生在第14步的幾乎碰撞來進行區(qū)分攻擊。我們知道,SHA-1的碰撞路線中,第一輪的情況最為復雜,條件數(shù)也最多,通過這種方法,可以忽略前14步的條件,而用一個碰撞來代替,從而降低問題的難度。我們發(fā)現(xiàn)對于截斷的SHA-1

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

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

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

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

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