CBC-MAC和Hash函數(shù)相關(guān)算法的安全性分析.pdf

1、Hash函數(shù)可以將任意長的消息壓縮為固定長的摘要,是一類重要的基礎(chǔ)密碼算法,有著廣泛的應(yīng)用,是數(shù)字簽名中的重要部件,用于抵抗存在性偽造攻擊,也可用于密鑰推導(dǎo),構(gòu)造消息認(rèn)證碼,偽隨機數(shù)生成器等。
　　 在此基礎(chǔ)上,我們對現(xiàn)有的一些MAC算法的迭代結(jié)構(gòu)進行總結(jié),提出了一種通用的模型gf1f2:｛0,1｝b1×｛0,1｝b2→｛0,1｝n,其中b1,b2≥n,f1:{0,1｝b1→｛0,1｝n和f2:{0,1｝b2→｛0,1｝n是兩個

2、映射,x∈{0,1}b1,y∈{0,1｝b2是相互獨立的。為了方便描述,將gf1f2簡記為g。函數(shù)g具有異或結(jié)構(gòu),通過轉(zhuǎn)換,可以利用Yuval的生日攻擊,對函數(shù)g求其第二原像。
　　 如果一個MAC算法,記為C,可以轉(zhuǎn)換為以下形式其中f置換,g(x,y)=f1(x)()f2(y),x和y相互獨立,mf是消息分組的級聯(lián)。對于任何大于兩個分組的消息,存在一個算法構(gòu)造它的第二原像,具有生日攻擊的復(fù)雜度。
　　 我們的第二原像攻

3、擊是Brincat和Mitchell攻擊[4]的擴展,不僅可以構(gòu)造CBC-MAC、EMAC、XCBC等算法的第二原像,也適用于MT-MAC、PMAC和基于三個密鑰的CBC模式的MAC等算法的第二原像攻擊。
　　 (2)SHA-3參賽算法Luffa的安全性分析
　　 本文給出了Luffa的偽碰撞,偽第二原像和偽原像攻擊。Luffa算法基于變種的sponge結(jié)構(gòu),其消息注入函數(shù)MI可看作是由初始值(IV)決定的消息擴展函數(shù),

4、將256比特的消息輸入擴展為整個狀態(tài)值w個256比特的字,然后對狀態(tài)值進行w個256比特的置換,其中w取決于Hash值的長度,對Luffa-224/256,Luffa-384,Luffa-512,w分別為3,4,5。IV是w個256比特的字,消息是256比特的字,因此MI將w+1個256比特的字壓縮為w個256比特的字。若將初始值看作是變量H=(H0,H1,H2),則MI的碰撞即為Hash函數(shù)的碰撞。因為M1是線性變換,將MI的輸出差分

5、置為零,我們可以求出輸入變量H和M差分關(guān)系。經(jīng)過計算發(fā)現(xiàn),改變5比特的IV,可以獲得Luffa-256的偽碰撞和偽第二原像。對Luffa-384,計算偽碰撞和偽第二原像需要改變7比特的IV。計算Luffa-512的偽碰撞和偽第二原像,IV在一個12比特的差分。這些攻擊可用于構(gòu)造利用密鑰作為初始值的MAC的相關(guān)密鑰攻擊。
　　 Luffa-256的偽原像計算是非常容易的,將初始值看作變量,可以直接對Hash函數(shù)求逆。Luffa-3

6、84/512的Hash值由兩次空迭代的輸出值級聯(lián)而成Z0‖Z1,直接求逆并不容易,因為它有兩個等式需要滿足。我們結(jié)合Luffa算法的特性和擴展的廣義生日攻擊給出了Luffa-384/512的偽原像攻擊。以Luffa-512為例,我們以最后一次迭代函數(shù)的線性變換MI的輸出X0,X1,X2,X3,X4作為輸入,根據(jù)Luffa函數(shù)的定義,我們可以得到兩個等式:
　　 因為等式(1)比較簡單,容易控制,我們可以進行分割攻擊。固定變量的一

7、部分比特,使等式的一部分比特關(guān)系成立,用另一部分控制使剩下的比特關(guān)系和等式(2)成立,經(jīng)過權(quán)衡我們可以讓等式(1)的低128比特成立,即當(dāng)i=0,l,2,3時,令Xi的低128比特是固定的常量CST,X4的低128比特是CST()l128(0xy○ Z0)。用這5個變量的高128比特滿足如下等式利用擴展的Wagner的廣義生日攻擊對等式(3)和(4)進行求解。對Luffa-384,尋找到一個偽原像需要264次迭代運算和267字節(jié)的存儲,

8、對Luffa-512,復(fù)雜度是2128次迭代運算和2132字節(jié)存儲。
　　 (3)有意義的MD4碰撞攻擊
　　 MD4算法是Rivest在1990年針對32位計算機設(shè)計的一個非常有效的Hash算法[7]。在1996年,Dobbertin給出了MD4全算法的碰撞攻擊,并構(gòu)造了純文本模式下的有意義的碰撞[8],但在碰撞開始的地方具有4個隨機的字。2005年,王小云等提出了模差分分析方法,可以有效構(gòu)造MD系列Hash函數(shù)的碰撞

9、,如MD4[9],RIPEMD[9],MD5[10],SHA-0[11]和SHA-1[12],而且這這些技術(shù)可以用于尋找MD4的變種的第二原像[10],引起人們對Hash函數(shù)的強烈關(guān)注。一些研究人員結(jié)合文件格式的冗余利用隨機碰撞構(gòu)造有意義的碰撞:如證書偽造[13],Ps文件[14],PDF,TIFF和MS Word97文檔[15]等有意義的碰撞的構(gòu)造。其主要方法是將隨機碰撞插入到文檔的控制命令中,(如PS文件的"if-then-else

10、',命令),這樣這些文檔的Hash值是一樣的,但顯示的內(nèi)容完全不一樣。這些碰撞在實際中都可能造成嚴(yán)重威脅。雖然MD4算法已經(jīng)被破解,但在一些需要追求壓縮效率的環(huán)境中,仍然可能被應(yīng)用。根據(jù)文件編碼格式構(gòu)造有意義的碰撞也是非常重要的。但這種有意義的碰撞比隨機碰撞構(gòu)造更為復(fù)雜,因為它對消息要求更苛刻。為了讓字符可以被計算機表示,利用字符編碼將每一個字符映射為一個可被計算機表示的數(shù)值,這些數(shù)值可以是單字節(jié)的形式也可以是多字節(jié)的形式。本文的分析是

11、基于單字節(jié)編碼方式的。
　　 我們研究了路線條件與消息字節(jié)相應(yīng)比特的對應(yīng)關(guān)系,當(dāng)消息字差分△-m4為±20+8k和±22+8k時,k=0,1,2,3,在第一輪只有一個條件對應(yīng)消息字節(jié)的第8比特,其他差分形式與第8比特關(guān)聯(lián)的比較多。因為與消息字節(jié)的第8比特關(guān)聯(lián),需要借助比特進位進行消息修改,修改成功后仍然有意義的概率比其他比特低,因此我們以消息差分△-m4=1為例,給出了句子結(jié)構(gòu)的構(gòu)造方式,在句子構(gòu)造的時候,可以選擇人名、價格、編

12、號等,使消息有足夠的自由度進行第一輪修改。然后從m0到m15,邊修改邊檢測,逐步確定消息字具體的值。
　　 1.先確定前6個字m0到m5,根據(jù)消息差分,確定存在差分的字符的形式如數(shù)字或字母。
　　 2.確定m6到m13八個字,利用簡單消息修改結(jié)合進位技術(shù),同時對句子進行檢測,避免出現(xiàn)不可視字符、無意義的單詞和不連貫的句子。
　　 3.利用m14,m15兩個字讓第2、3輪共38個條件成立,在搜索的過程中用m14,m

13、15進行高級消息修改降低尋找碰撞的復(fù)雜度。其中a5,6,a5,18,a5,29,d5,6,d5,13,c5,13和c5,18這7個條件可以通過高級消息修改使之以高概率成立。
　　 我們給出的構(gòu)造純文本文件的有意義MD4碰撞的方法,概率為2-33.77,并給出一個基于ISO Latin-1字符集的有意義的MD4碰撞。基于該碰撞敵手可以進行一些偽造和詐騙活動。
　　 (4)改進的44輪SHACAL-2的相關(guān)密鑰攻擊
　

14、　 SHACAL-2加密算法是NESSIEI程獲選的分組密碼算法之一,由Handschuh和Naccache設(shè)計[17],該算法基于NIST的Hash函數(shù)標(biāo)準(zhǔn)SHA-256[18]的壓縮函數(shù),明文作為鏈接變量,密鑰作為消息,因此其分組長度是256比特,密鑰長度是512比特。SHA-2的碰撞路線可以用于該分組算法的分析,SHA-2存在一些局部碰撞,可以利用局部碰撞構(gòu)造長的碰撞路線。Wagner在1999年提出了飛去來器(Boomeran

15、g)攻擊,使用兩個獨立的差分特征進行自適應(yīng)的選擇明密文攻擊,每個差分特征覆蓋密碼算法的一半。Kelsey等改進為選擇明文的攻擊,稱加強的飛去來器(Amplified Boomerang)攻擊[19](Biham等獨立提出,稱為矩形(Rectangle)攻擊[20])。
　　 我們采用相關(guān)密鑰三明治矩形攻擊,改進了44輪SHACAL-2的相關(guān)密鑰攻擊。我們將35輪的SHACAL-2分為3個部分E=E1()EM()E0,其中E0為前

16、24輪(0.24),EM為24-25輪,E1為25-35輪。以前的相關(guān)密鑰飛去來器攻擊,一般選取E0為前25輪,而我們只選擇前24輪為E0,然后利用中間輪EM進行擴充。因為利用第25輪的輸出差分不能轉(zhuǎn)換為E1的輸入差分,這是一種不可能的情況。但是利用第24輪的輸出差分可以直接轉(zhuǎn)換為E1的輸入差分,概率為1。第24輪的輸出差分是0,因為SHACAL-2的輪函數(shù)是非平衡的Feistel結(jié)構(gòu),只需要第25輪更新的字A25和E25滿足E1的輸入

17、差分。因為E1中ΔA25=0和△E25=0,所以當(dāng)一個對滿足E1的輸入差分的條件下,另一個對也滿足。
　　 我們利用模減差分和異或差分的混合表示方式以及采用差分集合代替單個差分提高差分路線E1的概率,在我們的分析中E0的輸入輸出差分都是異或差分,E1的輸入差分是異或差分,輸出差分是模減差分。我們給出了E1中差分路線成立的充分條件,在密鑰恢復(fù)的過程中,利用模減差分和差分路線的條件進行過濾,增加了密鑰過濾的強度。本文構(gòu)造的35輪相關(guān)