Hash函數(shù)MD5攻擊技術(shù)研究

1、西安電子科技大學(xué)碩士學(xué)位論文 Hash函數(shù)MD5攻擊技術(shù)研究 姓名：陳少暉 申請(qǐng)學(xué)位級(jí)別：碩士 專(zhuān)業(yè)：密碼學(xué) 指導(dǎo)教師：毛明20100101摘要Hash函數(shù)是信息安全領(lǐng)域中一個(gè)非常重要的基本工具，它在數(shù)字簽名、身份 認(rèn)證等領(lǐng)域中有著廣泛的應(yīng)用。MD5算法作為Hash函數(shù)大家庭中的一員，是MD 結(jié)構(gòu)的典型代表，廣泛應(yīng)用于信息安全領(lǐng)域。因此，通過(guò)對(duì)MD5算法的解析可以 掌握Hash函數(shù)的基本分析方法，對(duì)其他Hash函數(shù)的分析有著重要的參考意義。本論文對(duì)MD5算法的攻擊技術(shù)進(jìn)行了深入的分析和研究。首先系統(tǒng)總結(jié)了對(duì) 該算法進(jìn)行碰撞攻擊的整體思想，運(yùn)用了比特跟蹤技術(shù)對(duì)差分路徑進(jìn)行分析和控 制，利用消息修

2、改技術(shù)提高搜索到產(chǎn)生碰撞的明文對(duì)的概率；其次通過(guò)介紹初始 結(jié)構(gòu)和過(guò)渡結(jié)構(gòu)的構(gòu)建，詳細(xì)解析了對(duì)MD5進(jìn)行原像攻擊的技術(shù)和方法；最后對(duì) Hash函數(shù)進(jìn)行了歸納總結(jié)和進(jìn)一步的研究與探索。關(guān)鍵詞：雜湊函數(shù)MD5碰撞攻擊原像攻擊AbstractHash function is a very important and basic tool in the field of information security, widely applied in the areas of the digital signature and identity authenticationMD5 algorithm，as

3、 a member of Hash function family,is a typical representative of MD structure and wide used in information securityTherefore，it is helpful to get the basic analysis method of Hash functions to attack other Hash functions through the research of MD5 algorithmAttack technology of MD5 algorithm is anal

4、yzed and researched deeply in thispaperFirst of all，the main idea of collision attack of MD5 is summarizedThe bit-tracking technology is used to analyze and control the differential pathsMeanwhile， the message modification technology is taken advantage of to improve the possibility of searching the

5、messages for collisionSecondly,the construction of the initial structureand the skipping steps is proposed and the technology and method of preimage attack ofMD5 is analyzed in detailFinally,the performances of the Hash functions are summed up and the further research direction iS introducedKeywords

6、：Hash function MD5 Collision attack Preimage attack創(chuàng)新性聲明秉承學(xué)校嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)和優(yōu)良的科學(xué)道德，本人聲明所呈交的論文是我個(gè)人在 導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo) 注和致謝中所羅列的內(nèi)容以外，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成 果；也不包含為獲得西安電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的 材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中做了明確的說(shuō) 明并表示了謝意。申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切的法律責(zé)任。本人簽名：2纏絲垡日期蘭型!：蘭：<關(guān)于論文使用授權(quán)的

7、說(shuō)明本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究生 在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬西安電子科技大學(xué)。本人保證畢業(yè) 離校后，發(fā)表論文或使用論文工作成果時(shí)署名單位仍然為西安電子科技大學(xué)。學(xué) 校有權(quán)保留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)校可以公布論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存論文。(保密的論文在 解密后遵守此規(guī)定)本人簽名：日期絲么生：蘭：笪導(dǎo)師簽名：日期絲么!1 2 1董第一章緒論第一章緒論弟一早珀T匕11論文的研究背景Hash函數(shù)在數(shù)字簽名系統(tǒng)中扮演著重要的角色?！癏ash函數(shù)"一詞最初來(lái)源于 計(jì)算機(jī)科學(xué)，表示可以將

8、任意長(zhǎng)度的字符串壓縮成固定長(zhǎng)度的字符串的函數(shù)， Hash函數(shù)的輸出結(jié)果，稱(chēng)為Hash值，又稱(chēng)為消息摘要、指紋等。通俗地講，Hash函數(shù)用于壓縮消息，是將任意長(zhǎng)的消息映射為固定長(zhǎng)度的Hash 值。消息的Hash值可以看作是數(shù)字指紋：像實(shí)際生活中指紋可以驗(yàn)證一個(gè)人身份 的唯一性一樣，Hash函數(shù)可用于驗(yàn)證一個(gè)消息的唯一性。也就是說(shuō)，給定某一消 息和Hash值，我們可以判斷此消息與Hash值是否匹配。此外，類(lèi)似于我們?cè)谙?疑犯數(shù)據(jù)庫(kù)里比較一系列犯罪現(xiàn)場(chǎng)出現(xiàn)的指紋一樣，我們可以從有限的消息中檢 測(cè)某些Hash值與哪些原始消息相匹配。然而，對(duì)于給定的Hash值不可能恢復(fù)出 其原始消息。Hash函數(shù)有三個(gè)

9、安全特性，包括抗碰撞攻擊、抗原象攻擊和抗第二 原象攻擊。由于這些特性，Hash函數(shù)在公鑰密碼、數(shù)字簽名、完整性檢驗(yàn)、身份 認(rèn)證等領(lǐng)域中有著廣泛的應(yīng)用。目前，Hash函數(shù)主要有MDx系列和SHA系列，MDx系列包括MD41。、 MD5121、HAVALl31、RIPENDl4】等；SHA系列包括SHA0t51、SHA1【6l、SHA-256、 SHA-384frl等，這些Hash算法體現(xiàn)了目前主要的Hash函數(shù)設(shè)計(jì)技術(shù)。本論文是對(duì)MD5算法攻擊技術(shù)的研究和探索。MD5算法是由MD4算法發(fā)展而來(lái)的，其中MD表示消息摘要(Message Digest)。MD4算法是較早出現(xiàn)的Hash函數(shù)算 法，它使

10、用了基本的算術(shù)和布爾運(yùn)算，其設(shè)計(jì)原則采用了迭代結(jié)構(gòu)的思想。在MD4 算法公布后，許多Hash函數(shù)算法相繼提出，包括MD5、HAVAL、RIPEMD、 RIPEMD128、RIPEMD160、SHA-0和SHA1等，它們的大多數(shù)算法也是基于MD4算法的設(shè)計(jì)原則。RIPEMD算法是歐洲計(jì)劃RIPE的組成部分。RIPEMD128算法是1996年由Hans Dobbertin，Antoon Bosselaers和Bart Preneel提出來(lái)，用于替代實(shí)際應(yīng) 用中的RIPEMD算法。在近十幾年里，對(duì)于Hash函數(shù)的分析取得了一些進(jìn)展。1996年，HDobbertin給 出了一個(gè)對(duì)MD4算法完整算法的攻

11、擊【8l，該攻擊以2拋的概率找到一個(gè)碰撞，他同 時(shí)給出了如何找到有意義消息碰撞的方法；1998年，HDobbertin證明了MD4算法 的前兩圈不是單向函數(shù)【91，這一結(jié)論意味著對(duì)于尋找第一原像和第二原像存在有效 的攻擊。對(duì)于RIPEMD算法，HDobbertin能夠以231的復(fù)雜性找到兩圈RIPEMD的碰2 Hash函數(shù)MD5攻擊技術(shù)研究撞【lo】。隨著MDx系歹lJHash函數(shù)的發(fā)展，對(duì)于這些函數(shù)的安全性分析也不斷深入。 BdenBoer和AB0sselaers找到了針對(duì)MD5算法的一種偽碰撞【1l】11，即同一明文在不· 同初始值下得到相同Hash值。在1996年歐洲密碼大會(huì)上

12、，HDobbertin公開(kāi)了另一 種形式的偽碰撞【12】，即在兩個(gè)不同的初始值下的不同消息的一個(gè)碰撞。在1998年 國(guó)際密碼大會(huì)上，EChabatld和AJoux證明了用差分攻擊方法可以以2姐的概率找到 SHA0的一個(gè)碰撞【l引。一些針對(duì)Hash函數(shù)的更為有效的攻擊方法出現(xiàn)在2004年。Eli Biham和Raft提出了對(duì)SHA0算法的幾乎完全碰捌14】。AAoux給出了一個(gè)由4個(gè)明文塊構(gòu)成的SHA0 的碰撞【15l。在這些成果中，最為顯著的是在2004年國(guó)際密碼學(xué)大會(huì)上，王小云等 人宣布的對(duì)于一系YlJHash函數(shù)的碰撞結(jié)果，包括MD4161、MD5171、HAVAL-12818l和RIPE

13、MD算法，其中可以找至IJMD4和RIPEMD算法碰撞的復(fù)雜性分別低于28和218。王小云提出了一套新的針對(duì)MDx系列的Hash函數(shù)的分析技術(shù)，同時(shí)給出了得 到滿(mǎn)足差分路線(xiàn)的充分條件的方法，以及如何使用明文修改技術(shù)來(lái)提高碰撞攻擊 的成功概率。2005年，王小云等應(yīng)用此技術(shù)對(duì)MD5171、SHA-0191、SHA-120l算法 進(jìn)行碰撞攻擊，取得了很好的效果，在普通的個(gè)人電腦上就可以找到相關(guān)碰撞的 實(shí)例。這一攻擊技術(shù)對(duì)現(xiàn)有的Hash函數(shù)提出了嚴(yán)峻的挑戰(zhàn)，促進(jìn)了新的Hash算法 的開(kāi)發(fā)研究：美國(guó)NIST于2007年開(kāi)始在全球征集新的Hash算法。截至2008年11月， 一共提交了64個(gè)入選算法；2

14、008年12月有51個(gè)算法被NIST接收作為第一輪的候選 算法；2009年7月，NIST公布了進(jìn)入第二輪的14個(gè)算法；2010年將公布進(jìn)入最終一 輪的5個(gè)算法；最終將于2012年選出獲勝算法并命名為SHA-3。12 Hash函數(shù)設(shè)計(jì)原則Hash函數(shù)的算法是公開(kāi)的，對(duì)于每一個(gè)給定的消息串，計(jì)算輸出的Hash值是容 易的；但是從Hash值反推算出輸入的明文是困難的。實(shí)際應(yīng)用中，安全的Hash函 數(shù)必須符合以下三個(gè)設(shè)計(jì)原則：1抗碰撞性攻擊：由于Hash函數(shù)具有壓縮的性質(zhì)，所以必然存在多個(gè)消息串對(duì) 應(yīng)同一Hash值的可能，這就是所說(shuō)的碰撞的出現(xiàn)。實(shí)際應(yīng)用中由于Hash函數(shù)的抗 碰撞性，導(dǎo)致現(xiàn)實(shí)中很難找

15、到兩個(gè)不同的消息串對(duì)應(yīng)同一個(gè)Hash值的情況。2抗第一原像攻擊：對(duì)于任意一個(gè)消息串a(chǎn)，容易得到它的Hash值h(a)；但是從 它I拘Hash值h(a)很難推出相應(yīng)的消息串a(chǎn)，此時(shí)消息串a(chǎn)稱(chēng)之為h(a)的原像。抗第一 原像攻擊使得Hash函數(shù)具有單向性的特點(diǎn)。3抗第二原像攻擊：對(duì)于某一給定的消息串a(chǎn)，很難找到另一不同的消息串b， 使得h(a)=h(b)。抗第二原像攻擊使得Hash函數(shù)可以應(yīng)用于數(shù)字簽名和身份認(rèn)證領(lǐng) 域。第一章緒論3對(duì)Hash函數(shù)最重要的碰撞攻擊是生日攻擊。生日攻擊的名字起源于生日悖論， 嚴(yán)格來(lái)說(shuō)，它并不是一個(gè)真正的悖論，只是一個(gè)概率問(wèn)題。生日悖論乜¨：設(shè)M是一個(gè)集合，且

16、M中互不相同元素的個(gè)數(shù)為t(t>lO)，從M中隨機(jī)選取樣本容量為k>118柝)的樣本，則樣本中含有兩個(gè)相同元素的概率大于1 一o，一生日攻擊乜¨：設(shè)H：X_y是一個(gè)隨機(jī)函數(shù)，并且Y是一個(gè)具有t個(gè)值的集合，則隨機(jī)選取k(k>118也)個(gè)x，其中xEX，至少找到一對(duì)碰撞的概率大于妄。生日攻擊方法沒(méi)有利用Hash函數(shù)的結(jié)構(gòu)和任何代數(shù)弱性質(zhì)，它只依賴(lài)于消息摘 要的長(zhǎng)度，且PHash值的長(zhǎng)度。這種攻擊對(duì)Hash函數(shù)提出了一個(gè)必要的安全條件， 即消息摘要必須足夠的長(zhǎng)。如同密鑰的搜索方法作為分組密碼的衡量標(biāo)準(zhǔn)一樣， 抵抗生日攻擊的能力被用于衡量單向Hash函數(shù)安全性的重要標(biāo)準(zhǔn)之一

17、。應(yīng)用中的Hash函數(shù)，對(duì)以上三種抗攻擊特性都有嚴(yán)格的規(guī)定：對(duì)11比特摘要 的Hash算法，碰撞攻擊的復(fù)雜度至少為2以；第一原象攻擊的復(fù)雜度至少為24；針 對(duì)長(zhǎng)度小于2。比特的消息，第二原象攻擊的復(fù)雜度至少為2詘。13 MD5的研究歷程和意義MD5算法是MD4算法的改進(jìn)算法。Ron Rivest于1990年提出MD4單向散列 函數(shù)，對(duì)于輸入的消息，算法產(chǎn)生128位散列值。該算法首次公布之后，Ben den Boer 和Antoon Bosselaers對(duì)算法三輪中的后兩輪進(jìn)行了成功的密碼分析。在一個(gè)不相 關(guān)的分析結(jié)果中，Ralph MerKle成功地攻擊了前兩輪。盡管這些攻擊都沒(méi)有擴(kuò)展 到整個(gè)

18、算法，但Rivest還是改進(jìn)了其算法，MD5算法就此產(chǎn)生。目前，對(duì)MD5算法的研究主要集中在碰撞攻擊和第一原像攻擊方面。在碰撞攻擊方面，王小云在2004年利用明文修改技術(shù)，用兩個(gè)明文塊產(chǎn)生了 完全碰撞，將計(jì)算復(fù)雜度分別降低到239和232；2005年，來(lái)學(xué)嘉對(duì)文獻(xiàn)x71所列 的產(chǎn)生碰撞的充分條件進(jìn)行了修正【捌；2008年，馮登國(guó)等探索出一條新的差分路 徑【231，利用類(lèi)似隧道技術(shù)大大提高了產(chǎn)生碰撞的效率，可以在1秒鐘內(nèi)產(chǎn)生一組 碰撞的明文對(duì)陋J。在第一原像攻擊方面， DeD等人在2007年對(duì)MD5的前26步進(jìn)行了原像攻 擊【251，這是研究人員第一次對(duì)MD5進(jìn)行成功的原像攻擊；在2008年的A

19、CISP上， Sasaki等對(duì)MD5中間的44步進(jìn)行了攻擊261，計(jì)算復(fù)雜度為296；在2008年的SAC 上，Aumasson等對(duì)MD5前47步進(jìn)行了攻擊【271，復(fù)雜度為2102，Aoki等以低于2128 的復(fù)雜度找到了對(duì)MD5的完全原像攻擊【281；2009年，Sasaki和Aoki【29】把對(duì)MD5 的第一原像攻擊的計(jì)算復(fù)雜度降低到21強(qiáng)4。MD5算法作為Hash函數(shù)大家庭中的一員，是MD結(jié)構(gòu)的典型代表。在相當(dāng)長(zhǎng)4 Hash函數(shù)MD5攻擊技術(shù)研究的時(shí)間內(nèi)，MD5算法都廣泛應(yīng)用于信息安全領(lǐng)域，具有其他算法所不可比擬的應(yīng) 用優(yōu)勢(shì)。因此，通過(guò)對(duì)MD5算法的解析可以掌握Hash函數(shù)的基本分析方

20、法，對(duì) 其他Hash函數(shù)的分析有著重要的參考意義。14研究的主要內(nèi)容本論文研究的主要內(nèi)容是針對(duì)MD5算法的結(jié)構(gòu)特點(diǎn)，對(duì)其進(jìn)行碰撞攻擊和第 一原像攻擊的研究，分析總結(jié)其攻擊的思路和方法，在此基礎(chǔ)上對(duì)其攻擊的核心 環(huán)節(jié)進(jìn)行深入的探索，逐步形成了一套完整的MD5分析研究體系，對(duì)今后新的 Hash算法的學(xué)習(xí)研究有著重要的借鑒意義。研究的主要內(nèi)容如下：1MD5的碰撞攻擊 總結(jié)了碰撞攻擊的整體思想和關(guān)鍵步驟，從差分的引入，差分路徑的控制和充分條件的推導(dǎo)等方面，展示了MD5算法產(chǎn)生碰撞的全過(guò)程，用比特跟蹤技術(shù)詳細(xì) 記錄了在算法迭代過(guò)程中差分的繼承、產(chǎn)生和消除，研究了消息修改技術(shù)的實(shí)際 應(yīng)用，并從程序上得以驗(yàn)

21、證。2MD5的第一原像攻擊 根據(jù)MD5消息字的排列特點(diǎn)，引入“中立字”的概念，構(gòu)建“初始結(jié)構(gòu)"和“過(guò)渡結(jié)構(gòu)”，將整個(gè)MD5算法分為兩個(gè)部分，再將兩個(gè)部分分別對(duì)應(yīng)兩個(gè)“中 立字"，有效降低了攻擊的計(jì)算復(fù)雜度；對(duì)原像攻擊進(jìn)行了整體規(guī)劃和布局，在攻 擊過(guò)程中設(shè)計(jì)了程序的限制性搜索功能。15論文的章節(jié)安排本論文共分為五章，結(jié)構(gòu)如下：第一章介紹了論文的研究背景， Hash函數(shù)的發(fā)展歷程，MD5的研究意義和本 文的研究?jī)?nèi)容。第二章介紹了相關(guān)的基礎(chǔ)知識(shí)： MD5算法，三種差分的異同，循環(huán)左移的不同結(jié)果。 第三章對(duì)MD5的碰撞攻擊進(jìn)行了詳細(xì)的解析：介紹了碰撞攻擊的總體思路，利用比特跟蹤技術(shù)

22、對(duì)差分路徑進(jìn)行分析和控制，利用明文修改技術(shù)對(duì)產(chǎn)生碰撞的明文對(duì)進(jìn)行搜索，最后對(duì)MD5的碰撞攻擊進(jìn)行了總結(jié)。 第四章對(duì)MD5的原像攻擊進(jìn)行了詳細(xì)的解析：先介紹了預(yù)備知識(shí)，然后對(duì)原像攻擊最主要的兩個(gè)結(jié)構(gòu)：初始結(jié)構(gòu)和過(guò)渡結(jié)構(gòu)的構(gòu)建進(jìn)行了分析，最后對(duì)MD5的原像攻擊進(jìn)行了總結(jié)。第一章緒論5第五章對(duì)全文進(jìn)行了總結(jié)并對(duì)將來(lái)的研究提出了展望。第二章相關(guān)的基礎(chǔ)知識(shí)7第二章相關(guān)的基礎(chǔ)知識(shí)目前，應(yīng)用中的大多數(shù)Hash函數(shù)的設(shè)計(jì)都采用了迭代結(jié)構(gòu)，每次處理一個(gè)固 定長(zhǎng)度的消息分組。迭代結(jié)構(gòu)的典型代表是MD結(jié)構(gòu)，該結(jié)構(gòu)是基于壓縮函數(shù)的 迭代：廠：o，1)”×o，畸“-o，1)”其中咒>m1式(2-1)一個(gè)

23、Hash函數(shù)的任意有限長(zhǎng)度的輸入X在被壓縮之前，首先被劃分長(zhǎng)度為b 比特的消息分組五，這個(gè)過(guò)程包含了消息的填充，也就是在最后的一個(gè)消息分組 的后面附加若干個(gè)額外的比特，使得填充后的消息的長(zhǎng)度恰好為b比特的整數(shù)倍。 為了安全和便于應(yīng)用，通常填充信息包含了填充前消息的長(zhǎng)度。每一個(gè)消息塊鼉作 為壓縮函數(shù)f的輸入，f的輸出為一個(gè)n比特的中間結(jié)果。f可以看成是一個(gè)具有 兩個(gè)輸入變量的函數(shù)：前一個(gè)迭代輸出的中間結(jié)果以及輸入的消息分組t，讓皿代 表第i個(gè)迭代的輸出結(jié)果。一個(gè)輸入為X'-IlX2··x的Hash函數(shù)迭代過(guò)程如下：H。=，式(22)4,=，(Hil；毛)，1sf sf

24、； 式(2-3)h(x)=g(只) 式(2-4)日H稱(chēng)為第i一1個(gè)迭代和第i個(gè)迭代之間的鏈接變量，風(fēng)是一個(gè)預(yù)先定義的初 始值。在最后一步使用一個(gè)輸出變換函數(shù)g，把n比特的鏈接變量映射成m比 特的輸出結(jié)果g(H)。在很多Hash算法中，g經(jīng)常被定義成恒等映射g(皿)=q。21MD5算法211整體結(jié)構(gòu)描述 MD5算法采用迭代型Hash函數(shù)的一般結(jié)構(gòu)，算法如圖21所示。算法的輸入為任意長(zhǎng)的消息(圖中為k比特)，分為512比特長(zhǎng)的消息分組，輸出為128比特的消息摘要。8 Hash函數(shù)MD5攻擊技術(shù)研究 填充(1至tJ512bit)消息長(zhǎng)度(K mod 264)匠卜512bit斗41-512bit

25、9;互128-IVcVq CVLl圖21 Hash函數(shù)一般結(jié)構(gòu)消息處理過(guò)程如下：1對(duì)消息的填充。對(duì)消息的填充，使得其比特長(zhǎng)在模512下為448，即填充后 消息的長(zhǎng)度為512的某一倍數(shù)減去64，留出64比特以備第2步使用。步驟1是必 須的，即使消息長(zhǎng)度已經(jīng)滿(mǎn)足要求，仍需要填充。例如，消息長(zhǎng)為448比特，則 需要填充512比特，使其長(zhǎng)度變?yōu)?60，因此填充的比特?cái)?shù)大于等于1，小于等于512。填充的方法是確定的：第1位為1，后面的位都為O2附加消息的長(zhǎng)度。用步驟1留出的64比特以littleendian方式來(lái)表示消息被 填充前的長(zhǎng)度。如果消息的長(zhǎng)度大于264，則以2“為模數(shù)取模。Littleendi

26、an方式是指數(shù)據(jù)的最低有效字節(jié)(byte)(或者最低有效位)的優(yōu)先 順序存儲(chǔ)數(shù)據(jù)，即將最低有效字節(jié)(或者最低有效位)存于第地址字節(jié)(或者位)。 相反的存儲(chǔ)方式稱(chēng)之為big-endian方式。前兩步執(zhí)行完后，消息長(zhǎng)度為512的倍數(shù)(設(shè)為L(zhǎng)倍)，因此可將消息表示為分組長(zhǎng)為512比特的一系列分組KXl：，而每一分組有可表示為16個(gè)32比特長(zhǎng)的字，這樣消息中的總字?jǐn)?shù)為N=Lxl6，因此消息又可按字表示為M0，1， N1】。3對(duì)MD緩沖區(qū)初始化。算法使用128比特長(zhǎng)的緩沖區(qū)以存儲(chǔ)中間結(jié)果和最 終Hash值，緩沖區(qū)可以表示為4個(gè)32比特長(zhǎng)的寄存器似，B，C，D)，每個(gè)寄存器都 以littleendian方

27、式存儲(chǔ)數(shù)據(jù)，其初值(以存儲(chǔ)方式)為A=01234567，B=89ABCDEF, C=FEDcBA98，D=76543210，實(shí)際上為A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476。4以分組為單位對(duì)消息進(jìn)行處理。每一分組K(q=0， ，L-1)都經(jīng)一壓縮函 數(shù)處理，壓縮函數(shù)是整個(gè)MD5算法的核心，共有4個(gè)不同的布爾函數(shù)，分別為F 函數(shù)、G函數(shù)、H函數(shù)、l函數(shù)。每一輪的輸入為當(dāng)前處理的消息分組yq和緩沖區(qū) 當(dāng)前值，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。每一輪處理還需要加上第二章相關(guān)的基礎(chǔ)知識(shí)9常數(shù)表中的常數(shù)。常數(shù)表中一共有64個(gè)元素，第i個(gè)常數(shù)值為23

28、2 xabs(sin(i) 的整數(shù)部分。第四輪的輸出再與第一輪的輸入值相加；相加的結(jié)果即為壓縮函數(shù) 的輸出值。5輸出。消息L個(gè)分組都被處理完后，最后一個(gè)壓縮函數(shù)輸出值即為整個(gè)MD5 運(yùn)算的最終Hash值，即消息摘要。212壓縮函數(shù)壓縮函數(shù)是MD5算法的核心部件，對(duì)壓縮函數(shù)的分析是對(duì)算法進(jìn)行成功攻擊 的重要前提。該壓縮函數(shù)中有4輪處理過(guò)程，每一輪有對(duì)緩沖區(qū)ABCD進(jìn)行16步 迭代運(yùn)算，每一步的運(yùn)算形式(如圖22所示)為：a=b+(g+func(b，c，d)+x【i】+T【i】)<<<k)式(2-5)其中a、b、c、d為緩沖區(qū)的4個(gè)字，func代表具體的布爾函數(shù)，為F、G、H、I

29、 之一；X【i】為該步使用的明文字；T【i】為該步使用的常數(shù)；K為該步循環(huán)左移的比 特?cái)?shù)。YCVq+1圖22迭代結(jié)構(gòu)10 Hash函數(shù)MD5攻擊技術(shù)研究在計(jì)算新的a的表達(dá)式中，“+”為模232的加法。明文字(消息字)在4輪處 理的過(guò)程中，每一輪以不同的次序使用16個(gè)明文字，第一輪按照原來(lái)順序進(jìn)行使 用。第二輪到第四輪分別對(duì)這16個(gè)字的次序進(jìn)行變換(如表21所示)，然后以新 的次序使用這16個(gè)字。表21明文字轉(zhuǎn)換次序輪數(shù) 明文字的次序1l2(1+5半i)mod 163(5+3半i)mod 164(7木i)mod 164輪處理過(guò)程分別使用不同的布爾函數(shù)F、G、H、I，每個(gè)布爾函數(shù)的輸入為3 個(gè)32

30、比特的字，輸出為一個(gè)32比特的字，其中的運(yùn)算為逐比特的邏輯運(yùn)算，即 輸出的第n個(gè)比特是3個(gè)輸入的第n個(gè)比特的函數(shù)。四個(gè)布爾函數(shù)，如表22所示：表22四個(gè)布爾函數(shù)輪數(shù) 布爾函數(shù) func(b，C，d)1V(b，C，d)(6 A c)V(，6 A d)2G(b，C，d)p A d)V(c A-,d)3H(b，C，d)bCod4I(b，C，d)c op Vd) 四個(gè)布爾函數(shù)的真值如表23：表23布爾函數(shù)真值表FGH00010 10111O0O01010110111第二章相關(guān)的基礎(chǔ)知識(shí)213移位和明文字順序表在對(duì)MD5算法進(jìn)行碰撞攻擊的過(guò)程中，必須考慮移位對(duì)整個(gè)差分路徑的影響。 在碰撞攻擊過(guò)程中，明文

31、字的編排順序是差分引入的重要考慮因素之一；在原像 攻擊過(guò)程中，明文字的編排順序很大程度上確定了初始結(jié)構(gòu)和過(guò)渡結(jié)構(gòu)的位置。表24移位比特表步驟 移位比特?cái)?shù)1，2，157 12 17 22 7 12 17 22 7 12 17 22 7 12 17 2216，17，315 9 14 205 9 14 205 9 14205 9 14 2032，33，474 11 16 23 4 11 16 23 4 11 16 23 4 11 16 2348，49，636 10 15 2l 6 10 15 21 6 10 15 21 6 10 15 21表25明文字順序步驟 明文字的順序1，2，15O 1 2 3

32、 4 5 6 7 8 9 10 11 12 13 14 1516，17，311 6 11 O 5 10 15 4 9 14 3 8 13 2 7 1232，33，475 8 11 14 1 4 7 10 13 O 3 6 9 12 15 248，49，63O 7 14 5 12 3 10 1 8 15 6 13 4 11 2 922MD5的差分分析221三種差分的概念引入差分分析是破譯Hash函數(shù)最有效的工具之一，其中涉及到異或差分、符號(hào)差 分和模差分等幾個(gè)重要的概念。異或差分：設(shè)X和X是兩個(gè)32位的數(shù)，其異或差分為兩個(gè)數(shù)的比特位的異 或運(yùn)算，表示為XoX。異或差分能反映兩個(gè)數(shù)的對(duì)應(yīng)位的相同與

33、否。符號(hào)差分：同樣，設(shè)X和X 7是兩個(gè)32位的數(shù)，為了更好的體現(xiàn)這兩個(gè)數(shù)的某一位的差別，在異或差分的基礎(chǔ)上進(jìn)一步引入符號(hào)差分“+"、“I"號(hào)。例如，XX=【5,6，7，8,"-,-27，這說(shuō)明X和X從第5到第27位都不同，而且從符號(hào)可以看 出X的第5到第26位是0，第27位是1；而X 7的第5到第26位是1，第27位 是0。符號(hào)差分可以很容易看出兩個(gè)數(shù)的各位的差別。模差分：同樣，設(shè)X和X是兩個(gè)32位的數(shù)，模差分是將兩個(gè)數(shù)的差別用整 數(shù)減法體現(xiàn)出來(lái)。例如，X 7X用符號(hào)差分表示為【5，6，7，8,-",-27，此時(shí)用模差分 表示為X 7X=-24。符號(hào)差分

34、的擴(kuò)展在MD5算法破譯過(guò)程中具有廣泛的應(yīng)用，利用符號(hào)差分的擴(kuò) 展，可以達(dá)到自己所需要的差分目標(biāo)。例如，對(duì)2k、2k可以進(jìn)行如下擴(kuò)展：2k=2k¨2k=2k+22k+1-2k='''=2n-l_2n-22n-32k，其中0sk<ns322k=2k+1+2k=2k+2+2k+1+2k= =2n+2n'2+2n-3·+2k，其中0<k<n"：3212 Hash函數(shù)MD5攻擊技術(shù)研究在MD5的運(yùn)算中，第32位的位置既特殊又重要，其“+"和“”在某種程度 上是可以看成一致的。鑒于這一位的特殊性，可以將上面兩個(gè)等式進(jìn)

35、行進(jìn)一步擴(kuò) 展：2k=2k+I2k：2k+2_2k+12k= =231230229一·2k=一(231+230+229+2k)式(26)2k=2k+1+2k=2k+2+2“1+2k= =231+230+229-+2k=(231+230+229一·+2k)式(27)為了便于分析，符號(hào)差分可以簡(jiǎn)化為如下的表示方式：【k】=【k+1，-k】=【k+2，一(k+1)，-k】= =In一1，-(n一2) -k】=【32，-31-',-k】=【一32，-31"-,-k】式(2-8)【-k】=【-(k+1)，k】=【-(k+2)，(k+1)，k】= =【-(n一1)，(

36、n-2) k】=【-32，31 ，k】=【32，31 ，k】式(29)另外，上面的差分?jǐn)U展還可以將兩個(gè)元素聯(lián)合起來(lái)考慮：【-+2)，k】=【-(k+2)，(k+1)，一k】=【-(k+1)，-k】=【·(k+3)，(k+2)，(k+1)，-k】=【-(k+3)，(k+2)，k】=式(2-10)符號(hào)差分?jǐn)U展在MD5差分路徑的控制上有著至關(guān)重要的作用，一般情況下，在模差分確定后，可以根據(jù)具體需要確定符號(hào)差分。222循環(huán)左移的結(jié)果分析MD5算法在運(yùn)算過(guò)程中有大量的左循環(huán)移位，所以在引入差分之后，符號(hào)差分的左循環(huán)移位會(huì)出現(xiàn)幾種不同的情況，需要分別進(jìn)行分析處理。 例如，文獻(xiàn)【24】，設(shè)2。=【

37、k+x，·(1【+x-1),-,-k，其中1 s x32-k，設(shè)循環(huán)左移的位數(shù)為s(用<<<s表示)，分三種情況討論移位后的結(jié)果： 當(dāng)k+x+s<32，移位的結(jié)果為(2。<<<s)=2“。； 當(dāng)k+x+s>32且k+x<32，移位的結(jié)果為(2。<<<s)=2m+1；當(dāng)k+x>32，移位的結(jié)果為(2。<<<s)=2。砝。證明過(guò)程如下：1當(dāng)k+x+ss32時(shí)，(2。<<<s)=【k+x，一(k+x一1)，-(k+x一2， )，-k，】<<<s=【k+x+s，

38、(k+x+s1)， ，-(k+s)】=2k+5 mod(232)式(211)2當(dāng)k+x+s>32且k+s<32時(shí)，(2。<<<s)=【k+x，-(k+x一1)，一(k+x·2， )，-k，】<<<s=【-32,"-,-(k+x)，k+x+s-32，一(k+x+s一32-1)， ，一1=【32,"-,-(k+x)，k+x+s一32，一(k+x+s-32-1)， ，一1第二章相關(guān)的基礎(chǔ)知識(shí)13=(2h+1)mod(232)式(212)3當(dāng)k+s>32時(shí)，(2。<<<s)=【k+x，-(k+x

39、83;1)，-(k+x-2， )，-k，】<<<s=fk+x+s一32，一(k+x+s一321)，一(k+s一32)=(2“。32)mod(232)式(213) 同理，設(shè)一2。-(k+x)，(k+x1)， ，k】，其中1 s X s 32一k，同樣分三種情況討論：當(dāng)k+x+s s 32，移位的結(jié)果為(2。<<<s)=2；當(dāng)k+x+s>32，k+s s 32，移位的結(jié)果為(2。<<<s)=(2k+5+1)； 當(dāng)k+s>32，移位的結(jié)果為(2。<<<s)=2k-“-32。第三章MD5的碰撞攻擊第三章MD5的碰撞攻擊

40、31碰撞攻擊的整體思想破譯MD5算法是個(gè)系統(tǒng)工程例。在破譯過(guò)程中，首先，要從整體上確立一個(gè) 框架，確定一個(gè)產(chǎn)生碰撞的總體思路；其次，根據(jù)整體思路應(yīng)用明文修改等相關(guān) 技術(shù)和非線(xiàn)性函數(shù)的特性等來(lái)實(shí)現(xiàn)差分路徑；最后，盡可能簡(jiǎn)化實(shí)現(xiàn)差分路徑的 充分條件，降低計(jì)算復(fù)雜度，提高計(jì)算機(jī)“搜索”到碰撞的概率。311引入明文差分破譯MD5算法的關(guān)鍵之一是在明文中引入差分。好的明文差分有以下幾個(gè)特 點(diǎn)：首先，要有盡可能多的“自由字"，這樣可以放寬產(chǎn)生碰撞的充分條件，提高 碰撞概率；其次，明文中第一次出現(xiàn)差分的位置應(yīng)該盡量遠(yuǎn)離第一個(gè)字，這對(duì)于 消息修改技術(shù)至關(guān)重要，可以使明文存在更大的修改空間，同時(shí)也有利

41、于計(jì)算機(jī) 的成功搜索；再次，實(shí)現(xiàn)碰撞所需要的充分條件越少越好，這樣可以有效的降低計(jì)算復(fù)雜度；最后，明文的“塊數(shù)”越少，說(shuō)明實(shí)現(xiàn)碰撞的技術(shù)水平越高。目前，發(fā)表的三種MD5算法的碰撞實(shí)例17，23，24，都是采用“兩個(gè)明文塊"，即1024位 的明文，其中文獻(xiàn)17，23】的兩個(gè)明文塊的差分的位置都是位置對(duì)稱(chēng)、符號(hào)相反， 這種差分的引入是針對(duì)Hash函數(shù)MD結(jié)構(gòu)的特點(diǎn)而設(shè)計(jì)的，它能使得第一明文塊和第二明文塊分別產(chǎn)生的差分值能夠位置對(duì)稱(chēng)，符號(hào)相反(第32位除外)，最終 的Hash值是將兩個(gè)值相加。這樣，兩個(gè)明文塊產(chǎn)生的差分最終將抵消(第32位 以溢出的形式抵消)，從而產(chǎn)生了碰撞。文獻(xiàn)f24】差

42、分的引入擺脫了對(duì)稱(chēng)的模式，但其差分的消除仍遵循上述原則。最后要說(shuō)明的是，以上三種MD5算法的碰撞實(shí)例，在尋找碰撞的過(guò)程中，都需要利用明文修改技術(shù)來(lái)確保得到碰撞所需的明文。312選擇差分路徑破譯MD5算法的關(guān)鍵之二是要選擇好差分路徑。差分路徑的控制很大程序上 是利用符號(hào)差分的擴(kuò)展來(lái)實(shí)現(xiàn)的，使得整個(gè)差分按照整體的需要進(jìn)行。選擇差分 路徑時(shí)，要盡量減少差分中的漢明重量。一般情況下，盡量把差分引到第32位， 由于該位置的特殊性，容易消除差分。在選擇差分路徑的過(guò)程中，必須關(guān)注每一步運(yùn)算中差分的繼承和非線(xiàn)性函數(shù)的 位運(yùn)算。以MD5第12步為例，b3=c3+(b2+F(c3，d3，a3)+m11+t11)&

43、lt;<<22)，令16 Hash函數(shù)MD5攻擊技術(shù)研究11=b2+F(c3，d3，a3)+m1，+ll，其中tn是常數(shù)。b3的差分有以下兩個(gè)來(lái)源：1直接繼承c。的差分。2間接繼承。，的差分：第一是b：的差分，第二是F(c，d，a。)的差分，第三是m，的差分(如果m，有差分的前提下)。在計(jì)算b，運(yùn)算中，只有F函數(shù)是位運(yùn)算，其他都是在模232下的加法運(yùn)算。在 這個(gè)過(guò)程中，首先充分關(guān)注F函數(shù)，利用F函數(shù)的性質(zhì)，產(chǎn)生下面步驟所需要的 差分，同時(shí)消除不需要的差分；其次，符號(hào)差分的擴(kuò)展很大程度上是依靠”來(lái)實(shí)現(xiàn)的。在模差分確定的前提下，符號(hào)差分有多種可能，必須根據(jù)需要來(lái)選擇；最后，結(jié)合第32位

44、的特殊性和符號(hào)差分的擴(kuò)展，跟蹤循環(huán)左移對(duì)這個(gè)差分繼承的影響。313確定充分條件破譯MD5算法的關(guān)鍵之三是控制差分路徑的充分條件。充分條件越少，對(duì)明 文的限制程度越小，越容易找到碰撞。在MD5中利用F函數(shù)、G函數(shù)、H函數(shù)和 I函數(shù)的性質(zhì)，循環(huán)左移的性質(zhì)和差分路徑的整體需要，來(lái)確定差分的充分條件。在確定充分條件的過(guò)程中，必須利用非線(xiàn)性函數(shù)的性質(zhì)。MD5算法中有F函 數(shù)、G函數(shù)、H函數(shù)和I函數(shù)這四個(gè)非線(xiàn)性函數(shù)，現(xiàn)在以F函數(shù)和H函數(shù)為例， 總結(jié)非線(xiàn)性函數(shù)的特性【31】。從F(X，Y z)-(x八V(-i XAY)的表達(dá)式，可以看出F函數(shù)是一個(gè)選擇函 數(shù)。選擇函數(shù)的意思是：F函數(shù)的值的選取是根據(jù)X的值來(lái)

45、決定選取Y或者Z的 值：即如果X=I，F(xiàn)函數(shù)的值等于Y的值；如果X=0，F(xiàn)函數(shù)的值等于Z的值。X 的值對(duì)F函數(shù)的值起到一個(gè)選取的作用。根據(jù)上述所說(shuō)的F函數(shù)的選取的性質(zhì)， 我們可以總結(jié)出F函數(shù)的三個(gè)性質(zhì)：1F(X，Y z)=F(1 X，Y z)，當(dāng)且僅當(dāng)Y=z；2F(X，Y z)=F(X，-I Y z)，當(dāng)且僅當(dāng)x=O；3F(X，Y z)=F(X，Y 1 z)，當(dāng)且僅當(dāng)x=1；從H(X，Y Z)=XoYOZ的表達(dá)式，可以看出H函數(shù)是個(gè)對(duì)稱(chēng)函數(shù)，該函數(shù)具有以下兩個(gè)性質(zhì)：1X，Y z這三個(gè)參數(shù)中相同的位有奇數(shù)個(gè)1， H函數(shù)的值對(duì)應(yīng)的位為1；2x，Y Z這三個(gè)參數(shù)中相同的位有偶數(shù)個(gè)1，H函數(shù)的值對(duì)應(yīng)的

46、位為O。 總之，在尋找MD5碰撞的過(guò)程中，上述三個(gè)方面都很關(guān)鍵，他們相輔相成，相互協(xié)調(diào)，必須統(tǒng)一起來(lái)整體考慮。第三章MD5的碰撞攻擊1732比特跟蹤技術(shù)在MD5碰撞攻擊的過(guò)程中，在差分引入之后，必須應(yīng)用比特跟蹤技術(shù)對(duì)差分進(jìn)行比特級(jí)別的跟蹤，以確保有效地控制差分路徑，最終實(shí)現(xiàn)碰撞。就MD5的第一輪而言，以四個(gè)連續(xù)步驟為例：a=b+(a+F(b，C，d)+mi+ti)<<<si)；式(31) d=a+(d+F(a，b，c)+m“1+t“1)<<<s“1)；式(32) c=d+(c+F(d，a，b)+mi+2+ti+2)<<<si+2)；式(3-

47、3) b=c+(b+F(c，d，a)+mi+3+t“3)<<<si+3)；式(34) 在這每一步中，只有F函數(shù)的運(yùn)算是位運(yùn)算，除此以外的運(yùn)算都是模232的加法運(yùn)算。因此，在F函數(shù)中，其三個(gè)參數(shù)某一比特的變化，最終只會(huì)影響F函數(shù) 的相應(yīng)的比特位；F函數(shù)以外的運(yùn)算，由于可能存在進(jìn)位的問(wèn)題，所以影響的可能 不只是變化的那一比特，而且可能是影響其周?chē)囊贿B串的比特位，影響的范圍可能很大，這就需要依靠比特跟蹤技術(shù)來(lái)監(jiān)控。在整個(gè)運(yùn)算過(guò)程中，第32比特位置特殊，其進(jìn)位將會(huì)產(chǎn)生溢出，這個(gè)性質(zhì)在比特跟蹤過(guò)程中至關(guān)重要。下面將以 文獻(xiàn)f171為例，介紹比特跟蹤技術(shù)在碰撞攻擊中的應(yīng)用。321符號(hào)說(shuō)

48、明1M=(mo，m。， ，m。5)和M=(mo，m。， ，m。，I)代表相對(duì)應(yīng)的兩個(gè)512比特的明文 塊，AM=(Am。，Aml，一，Am。，)代表兩個(gè)相對(duì)應(yīng)的明文塊的差分，其中每個(gè)m；為32比特的字。2ai,di，ci，bi分別代表第(4i3)步，第(4i2)步，第(4i1)步，第4i步的輸出，其中1i16；同樣的方法定義a；，b；，ci',d；。3ai,j,bi,j,ciJ,du分別代表ai，di，ci，bi的第j比特，其中，最高位為第32比特，最低位為第1比特。4西艫IIij,分別表示mi和E的第j比特，其中中；表示第i步的邏輯函數(shù)，V； 表示循環(huán)左移的整體的表達(dá)式。 例如，第8

49、步中，西7=F(c2，d2，a2)=(c2 A d2)V(-1c2a2)，1l，7=bl+F(c2，d2，a2)+m7+t7。5Xi,j=x硒tx硝=-1，這是表示第j比特的差分。如果值為1，說(shuō)明xi的第j Lt 特是1而X；的第j比特是0；如果值是0，說(shuō)明xi 7的第j比特是0而x；的第j比 特是1，其中X可以是a,b，c，d，西，V。6Ax；jl,j2， ，jl】=Xijl,j2， 'jl】-X；，表示x；的第jLj2， ,jl比特的變化。 x；【j1，j2， ，jl】表示具體第j1，j2""jl的比特的變化，其中“+"表示該比特從O 變成了1；“”表

50、示該比特從1變成了0。18 Hash函數(shù)MD5攻擊技術(shù)研究322比特跟蹤技術(shù)的應(yīng)用文獻(xiàn)1171是用兩個(gè)明文塊(M。，M，)，明文長(zhǎng)度共為1024比特，對(duì)應(yīng)的差分明文 塊為(M。，M1)，經(jīng)過(guò)兩次MD5運(yùn)算，(Mo，M1)和(Mo，M。)產(chǎn)生相同的Hash值，這就成功找到了碰撞。本文通過(guò)對(duì)第一次MD5迭代運(yùn)算的前8步進(jìn)行研究，所以只關(guān)注Mo和M o，其中：AMo=Mo'-Mo=(0，0，0，0，231,0，0，0，0，0，0，215,0，0，231,0)。從這 里可以看出，m。開(kāi)始引入差分，本文結(jié)合文獻(xiàn)【17】，以前8步為例，介紹比特跟 蹤技術(shù)對(duì)差分路徑的控制。第5步分析： 第5步的表達(dá)

51、式：a2=b。+(a1+F(b1，Ca，d1)+m4+t4)<<<7)，開(kāi)始引入了差分，&rn。=231，在前4步的過(guò)程中，明文沒(méi)有引入差分，所以ax,b，C1，d，都沒(méi)有出現(xiàn)差 分，即81=a1，dl=d1，ca=C1，bl=b1。Aa2=(lI，4【31】<<<7)=(一231)<<<7)=-26。 根據(jù)基礎(chǔ)知識(shí)，第32比特的“+”和“”是相同的，所以，此時(shí)明文引入的差分231， 看成231來(lái)處理，經(jīng)過(guò)循環(huán)左移，a，的模差分為26，為了下面步驟的需要，需要將這個(gè)模差分進(jìn)行擴(kuò)展，滿(mǎn)足a2【+7，+8，+9，+22，23】。此時(shí)要求

52、a2,7=a 2，8=a2，9= =a2刀=O， a2，23=1。第6步分析：第6步的表達(dá)式：d2-a2+(d1+F(a2，b1，c1)+m5+t5)<<<12)，這步明文Am5=O， Ad2=Aa2+(V 5<<<12)，Ad：的差分由兩部分組成：首先，d：繼承了Aa2=26這 部分的值；其次，(胛。<<<12)產(chǎn)生了后面所需要的差分223+231。根據(jù)前面的基礎(chǔ)知識(shí)，為了達(dá)到這個(gè)目標(biāo)，需要充分利用F函數(shù)的性質(zhì)：1利用F(X，Y z)=Fn x，Y Z)，當(dāng)且僅當(dāng)Y=Z。第6步中b。j=clj，這個(gè)條件確保a：的第 i比特的變化不會(huì)影響d

53、：， 其中i=7，8，9，10，11，13，14，15，16，17，18，19，21，22，23。2223+231是由胖，12】和Aqs，20】經(jīng)過(guò)循環(huán)左移12比特形成的。此時(shí)由于沒(méi) 有差分的擴(kuò)展，滿(mǎn)足Aqs，12】=中，【12】=1，胛；201=A，201=1。此時(shí)要求 bz121-121=1，bl201-q201=1，即bl【12】=1，121=0，bx201=1，ca20=O(見(jiàn)文獻(xiàn)【17】表4)。第7步分析：第7步表達(dá)式：c2=d2+(Cl+F(d2，a2，b1)+m6+t6)<<<17)，這步明文am6=O，Ac：=Ad，+OF。<<<12)，同第

54、6步的分析一樣，c，的差分由兩部分組成：1Ac2繼承了Ad2=-26+223這部分的值，而且都進(jìn)行了擴(kuò)展，c2【7，8，9，10，11，-12】 這些變化都是由26引起的：設(shè)C：。的第7到12比特為?，由于C2嘲=0， 其中i=7，8，9，10，11，C2【12】-1，差分計(jì)算?7100000=26，這樣就實(shí)現(xiàn)了 C2【7，8，9，10，11，一12】的變化。同理，223導(dǎo)致了c2【-24，-25，-26，27】的變化。第三章MD5的碰撞攻擊192研究r(d2，a2，b1)部分，根據(jù)F函數(shù)的性質(zhì)、d2、a2，可以得出：6=【-23，22，21，20，19，18，17，16，14，13，12，1

55、1】，在經(jīng)過(guò)V6=c1+m6+m6+t6，異或差分 進(jìn)行了變化，1l，6=216+214+213+212+211，即AW6=【16，14，13，12，11】。3經(jīng)過(guò)循環(huán)左移17比特，AtlJ6<<<17=【一1，31，30，29，28】。Ac2繼承了V6<<<17 的比特變化，其中，第1比特的差分進(jìn)行了擴(kuò)展了6個(gè)比特，使得c：【-6，5，4，3，2，1】， 其他比特沒(méi)有進(jìn)行擴(kuò)展。4Ac2還繼承了Ad2=231這部分的值，聯(lián)合AtlJ6<<<17=【31，30，29，28】，這些部分共同構(gòu)建了C232，31，30，29，28】。 詳細(xì)解析第8步中各比特的由來(lái)：第8步在文獻(xiàn)171中是個(gè)關(guān)鍵的步驟，控制好該步的差分對(duì)最終產(chǎn)生碰撞有著 重要的作用。該步的差分是由前7步差分共同作用產(chǎn)生的，即 (ac：，Ad：，Aa：，Ab。)一b：。為了控制好差分路徑，使得經(jīng)過(guò)第8步的運(yùn)算以后，達(dá) 到b2t-b2【1，16，-17，18，19，20，一21，一24】的差分特性，必須控制好前面的c2，d2， a2，b。的值。前7步的運(yùn)算為第8步提供了以下前提條件：