信息技術(shù)趙澤茂第四章ppt

1、第4章 消息認(rèn)證技術(shù)4.1 Hash函數(shù)4.2 消息認(rèn)證碼4.3 MD5算法4.4 SHA-1算法4.5 Hash函數(shù)的攻擊分析小結(jié)習(xí)題第4章 消息認(rèn)證技術(shù)消息摘要函數(shù)、散列函數(shù)或雜湊函數(shù)，記為h=H(M)。我們把Hash函數(shù)值h稱為輸入數(shù)據(jù)M的“數(shù)字指紋”。Hash函數(shù)的這種單向性特征和輸出數(shù)據(jù)長(zhǎng)度固定的特征使得它可以用于檢驗(yàn)消息的完整性是否遭到破壞。如果消息或數(shù)據(jù)被篡改，那么數(shù)字指紋就不正確了。 4.1 Hash函數(shù)函數(shù) 第4章 消息認(rèn)證技術(shù)用做消息認(rèn)證的Hash函數(shù)具有如下一些性質(zhì): (1) 消息M可以是任意長(zhǎng)度的數(shù)據(jù)。(2) 給定消息M，計(jì)算它的Hash函數(shù)值h=H(M)是很容易的。

2、(3) 任意給定 ，則很難找到M使得h=H(M)，即給出Hash函數(shù)值，要求輸入M在計(jì)算上是不可行的。 這說(shuō)明Hash函數(shù)的運(yùn)算過(guò)程是不可逆的，這種性質(zhì)被稱為函數(shù)的單向性。(4) 給定消息M和其Hash函數(shù)值H(M)，要找到另一個(gè)M，且MM，使得H(M)=H(M) 在計(jì)算上是不可行的，這條性質(zhì)被稱為抗弱碰撞性。第4章 消息認(rèn)證技術(shù) 抗弱碰撞性保證對(duì)于一個(gè)消息M及其Hash函數(shù)值，無(wú)法找到一個(gè)替代消息M，使它的Hash函數(shù)值與給定的Hash函數(shù)值相同。這條性質(zhì)可用于防止偽造?？箯?qiáng)碰撞性對(duì)于消息Hash函數(shù)的安全性要求更高。 這條性質(zhì)保證了對(duì)生日攻擊方法的防御能力。第4章 消息認(rèn)證技術(shù)碰撞性是指對(duì)

3、于兩個(gè)不同的消息M和M，如果它們的摘要值相同，則發(fā)生了碰撞。雖然可能的消息是無(wú)限的，但可能的摘要值卻是有限的。如Hash函數(shù)MD5，其Hash函數(shù)值長(zhǎng)度為128位，不同的Hash函數(shù)值個(gè)數(shù)為2128。因此，不同的消息可能會(huì)產(chǎn)生同一摘要，碰撞是可能存在的。但是，Hash函數(shù)要求用戶不能按既定需要找到一個(gè)碰撞，意外的碰撞更是不太可能的。顯然，從安全性的角度來(lái)看，Hash函數(shù)輸出的比特越長(zhǎng)，抗碰撞的安全強(qiáng)度越大。第4章 消息認(rèn)證技術(shù)4.1.1 一個(gè)簡(jiǎn)單的一個(gè)簡(jiǎn)單的Hash函數(shù)函數(shù)基于安全強(qiáng)度的需要，現(xiàn)有的Hash函數(shù)一般都十分復(fù)雜。本節(jié)我們介紹一個(gè)簡(jiǎn)單的Hash函數(shù)，便于建立對(duì)Hash函數(shù)的感性認(rèn)識(shí)

4、。對(duì)于明文m，按每組n比特進(jìn)行劃分，如果最后一組長(zhǎng)度不夠，則補(bǔ)充0。不妨設(shè)劃分為r組，mi=mi1，mi2， ，min，1ir，mij=0或1，然后將各分組逐比特進(jìn)行模2加運(yùn)算，則輸出為h=h1，h2，hn，其中h1=m11+m21+mr1 (mod 2)，hn=m1n+m2n+mm(mod 2)。 從定義可見(jiàn)， hi表示所有分組的第i比特進(jìn)行模2加，因此，若消息改變，摘要值也會(huì)隨之改變。第4章 消息認(rèn)證技術(shù)一個(gè)例外的情況是，若消息出錯(cuò)，而摘要值仍然不變的概率為2-n。當(dāng)n充分大時(shí)，出錯(cuò)的概率或者說(shuō)消息被篡改的概率非常小，視為小概率事件，可忽略不計(jì)。第4章 消息認(rèn)證技術(shù)4.1.2 完整性檢驗(yàn)的

5、一般方法完整性檢驗(yàn)的一般方法消息完整性檢驗(yàn)的一般機(jī)制如圖4-1-1所示。無(wú)論是存儲(chǔ)文件還是傳輸文件，都需要同時(shí)存儲(chǔ)或發(fā)送該文件的數(shù)字指紋; 驗(yàn)證時(shí)，對(duì)于實(shí)際得到的文件重新產(chǎn)生其數(shù)字指紋，再與原數(shù)字指紋進(jìn)行對(duì)比，如果一致，則說(shuō)明文件是完整的，否則，是不完整的。 第4章 消息認(rèn)證技術(shù)圖 4-1-1 消息完整性檢驗(yàn)的一般機(jī)制 第4章 消息認(rèn)證技術(shù)在4.1節(jié)中我們簡(jiǎn)單介紹了消息的完整性檢驗(yàn)，這只能檢驗(yàn)消息是否是完整的，不能說(shuō)明消息是否是偽造的。因?yàn)?，一個(gè)偽造的消息與其對(duì)應(yīng)的數(shù)字指紋也是匹配的。消息認(rèn)證具有兩層含義: 一是檢驗(yàn)消息的來(lái)源是真實(shí)的，即對(duì)消息的發(fā)送者的身份進(jìn)行認(rèn)證; 二是檢驗(yàn)消息是完整的，即

6、驗(yàn)證消息在傳送或存儲(chǔ)過(guò)程中未被篡改、刪除或插入等。 4.2 消消 息息 認(rèn)認(rèn) 證證 碼碼 第4章 消息認(rèn)證技術(shù)產(chǎn)生消息的數(shù)字指紋的方法很多。當(dāng)需要進(jìn)行消息認(rèn)證時(shí)，僅有消息作為輸入是不夠的，需要加入密鑰K，這就是消息認(rèn)證的原理。能否認(rèn)證，關(guān)鍵在于信息發(fā)送者或信息提供者是否擁有密鑰K。消息認(rèn)證碼(Message Authentication Code，MAC)通常表示為MAC=CK(M)其中: M是長(zhǎng)度可變的消息; K是收、發(fā)雙方共享的密鑰; 函數(shù)值CK(M)是定長(zhǎng)的認(rèn)證碼，也稱為密碼校驗(yàn)和。MAC是帶密鑰的消息摘要函數(shù)，即一種帶密鑰的數(shù)字指紋，它與不帶密鑰的數(shù)字指紋是有本質(zhì)區(qū)別的。第4章 消息認(rèn)

7、證技術(shù)1. 消息認(rèn)證認(rèn)證碼被附加到消息后以MMAC方式一并發(fā)送，接收方通過(guò)重新計(jì)算MAC以實(shí)現(xiàn)對(duì)M的認(rèn)證，如圖4-2-1所示。 第4章 消息認(rèn)證技術(shù)圖 4-2-1 消息認(rèn)證第4章 消息認(rèn)證技術(shù)假定收、發(fā)雙方共享密鑰K，如果接收方收到的MAC與計(jì)算得出的MAC一致，那么可以得出如下結(jié)論: (1) 接收方確信消息M未被篡改。此為完整性驗(yàn)證。(2) 接收方確信消息來(lái)自所聲稱的發(fā)送者，因?yàn)闆](méi)有其他人知道這個(gè)共享密鑰，所以其他人也就不可能為消息M附加合適的MAC。此為消息源驗(yàn)證。第4章 消息認(rèn)證技術(shù)2. 消息認(rèn)證與保密在消息認(rèn)證中，消息以明文方式傳送，這一過(guò)程只提供認(rèn)證而不具備保密性。如圖4-2-2所示

8、提供了一種既加密又認(rèn)證的方式，發(fā)送方發(fā)送EK2(M)CK1(M)。該種處理方式除具備息認(rèn)證的功能外，還具有保密性。第4章 消息認(rèn)證技術(shù)圖 4-2-2 消息認(rèn)證與保密第4章 消息認(rèn)證技術(shù)3. 密文認(rèn)證密文認(rèn)證改變消息認(rèn)證與保密中加密的位置，得到另外一種消息保密與認(rèn)證方式，即密文認(rèn)證，如圖4-2-3所示。該種處理方式先對(duì)消息進(jìn)行加密，然后再對(duì)密文計(jì)算MAC，傳送EK2(M)CK1 (EK2(M)給接收方。接收方先對(duì)收到的密文進(jìn)行認(rèn)證，認(rèn)證成功后，再解密。 第4章 消息認(rèn)證技術(shù)圖 4-2-3 密文認(rèn)證第4章 消息認(rèn)證技術(shù)MD表示消息摘要(Message Digest，MD)。 MD4算法是1990年

9、由Ron Rivest設(shè)計(jì)的一個(gè)消息摘要算法，該算法的設(shè)計(jì)不依賴于任何密碼體制，采用分組方式進(jìn)行各種邏輯運(yùn)算而得到。1991年MD4算法又得到了進(jìn)一步的改進(jìn)，改進(jìn)后的算法就是MD5算法。MD5算法以512 bit為一塊的方式處理輸入的消息文本，每個(gè)塊又劃分為16個(gè)32 bit的子塊。算法的輸出是由4個(gè)32 bit的塊組成的，將它們級(jí)聯(lián)成一個(gè)128 bit的摘要值。MD5算法如圖4-3-1所示，包括以下幾個(gè)步驟。 4.3 MD5算法算法 第4章 消息認(rèn)證技術(shù)圖 4-3-1 MD5算法第4章 消息認(rèn)證技術(shù)(1) 填充消息使其長(zhǎng)度正好為512 bit的整數(shù)倍L。首先在消息的末尾處附上64 bit的消

10、息長(zhǎng)度的二進(jìn)制表示，大小為n(mod 264)，n表示消息長(zhǎng)度。然后在消息后面填充一個(gè)“1”和多個(gè)“0”，填充后的消息恰好是512 bit的整數(shù)倍長(zhǎng)L。Y0，Y1，YL-1表示不同的512 bit長(zhǎng)的消息塊，用M0，M1，MN1表示各個(gè)Yq中按32 bit分組的字，N一定是16的整數(shù)倍。 第4章 消息認(rèn)證技術(shù)(2) 初始化緩沖區(qū)。算法中使用了128 bit的緩沖區(qū)，每個(gè)緩沖區(qū)由4個(gè)32 bit的寄存器A、B、C、D組成，先把這4個(gè)寄存器初始化為A=01 23 45 67 B=89 AB CD EFC=FE DC BA 98D=76 54 32 10第4章 消息認(rèn)證技術(shù)(3) 處理512 bit

11、消息塊Yq，進(jìn)入主循環(huán)。主循環(huán)的次數(shù)正好是消息中512 bit的塊的數(shù)目L。先從Y0開(kāi)始，上一循環(huán)的輸出作為下一循環(huán)的輸入，直到處理完YL-1為止。消息塊Yq的處理，以當(dāng)前的512 bit數(shù)據(jù)塊Yq和128 bit緩沖值A(chǔ)、B、C、D作為輸入，并修改緩沖值的內(nèi)容。消息塊的處理包含4輪操作，每一輪由16次迭代操作組成，上一輪的輸出作為下一輪的輸入，如圖4-3-2所示。4輪處理具有相似的結(jié)構(gòu)，但每輪處理使用不同的非線性函數(shù)，如圖4-3-3所示。第4章 消息認(rèn)證技術(shù)圖 4-3-2 消息塊處理的主循環(huán)第4章 消息認(rèn)證技術(shù)圖 4-3-3 某一輪的執(zhí)行過(guò)程第4章 消息認(rèn)證技術(shù)4個(gè)非線性函數(shù)分別為F(X，Y

12、，Z)=(XY)(Z) G(X，Y，Z)=(XZ)(Y)H(X，Y，Z)=XYZI(X，Y，Z)=Y(X)各種運(yùn)算符號(hào)的含義: XY表示X與Y按位邏輯“與”; XY表示X與Y按位邏輯“或”; XY表示X與Y按位邏輯“異或”; 表示X按位邏輯“補(bǔ)”; X+Y表示整數(shù)模232加法運(yùn)算; Xs表示將X循環(huán)左移s個(gè)位置。XZZ第4章 消息認(rèn)證技術(shù)常數(shù)表Ti(1i64)共有64個(gè)元素，每個(gè)元素長(zhǎng)為32 bit，Ti232ABS(sin(i)，其中i是弧度。 處理每一個(gè)消息塊Yi時(shí)，每一輪使用常數(shù)表Ti中的16個(gè)，正好用4輪。(4) 輸出。每一輪不斷地更新緩沖區(qū)A、B、C、D中的內(nèi)容，4輪之后進(jìn)入下一個(gè)主

13、循環(huán)，直到處理完所有消息塊為止。最后輸出的就是運(yùn)算結(jié)束時(shí)緩沖區(qū)中的內(nèi)容。第4章 消息認(rèn)證技術(shù)SHA(Secure Hash Algorithm，SHA)由美國(guó)NIST開(kāi)發(fā)，作為聯(lián)邦信息處理標(biāo)準(zhǔn)于1993年發(fā)表，1995年修訂后，成為SHA1版本。SHA1算法在設(shè)計(jì)方面基本上是模仿MD5算法，如圖4-4-1所示，包含以下幾個(gè)過(guò)程。4.4 SHA-1算法算法第4章 消息認(rèn)證技術(shù)圖 4-4-1 SHA1算法第4章 消息認(rèn)證技術(shù)(1) 填充消息。首先將消息填充為512的整數(shù)倍，填充方法與MD5算法相同。與MD5算法不同的是SHA-1的輸入為長(zhǎng)度小于264 bit的消息。 (2) 初始化緩沖區(qū)。初始化1

14、60 bit的消息摘要緩沖區(qū)(即設(shè)定IV值)，該緩沖區(qū)用于保存中間和最終摘要結(jié)果。每個(gè)緩沖區(qū)由5個(gè)32 bit的寄存器A、B、C、D、E組成，初始化為 A=67 45 23 01 B=EF CD AB 89 C=98 BA DC FE D=10 32 54 76 E=C2 D2 E1 F0第4章 消息認(rèn)證技術(shù)(3) 處理512 bit消息塊Yq，進(jìn)入主循環(huán)。主循環(huán)的次數(shù)正好是消息中512 bit的塊的數(shù)目L。先從Y0開(kāi)始，以上一循環(huán)的輸出作為下一循環(huán)的輸入，直到處理完YL-1為止。主循環(huán)有4輪，每輪20次操作(MD5算法有4輪，每輪16次操作)。每次操作對(duì)A、B、 C、 D和E中的3個(gè)做一次非

15、線性函數(shù)運(yùn)算，然后進(jìn)行與MD5算法中類似的移位運(yùn)算和加運(yùn)算。第4章 消息認(rèn)證技術(shù)四個(gè)非線性函數(shù)為ft(X，Y，Z)=(XY)(Z) (0t19) ft(X，Y，Z)=XYZ (20t39)ft(X，Y，Z)=(XY)(XZ)(YZ) (40t59) ft(X，Y，Z)=XYZ (60t79)該算法使用了常數(shù)序列Kt(0t79)，分別為Kt=5a827999 (0t19) Kt=6ed9eba1 (20t39)Kt=8f1bbcdc (40t59)Kt=ca62c1d6 (60t79)X 第4章 消息認(rèn)證技術(shù)用下面的算法將消息塊從16個(gè)32 bit子塊變成80個(gè)32 bit子塊(W0到W79):

16、 Wt=Mt (0t15) Wt=(Wt-3Wt-8Wt-14Wt-16)1 (16t79)第4章 消息認(rèn)證技術(shù) 該算法主循環(huán)4輪，每輪20次， 0t79，每一次的變換的基本形式是相同的: A(E+ft(B，C，D)+(A5)+Wt+KtB=AC=(B30)D=CE=D其中: (A5)表示寄存器A循環(huán)左移5 bit， (B30)表示寄存器K循環(huán)左移30 bit。 80次處理完后，處理下一個(gè)512 bit的數(shù)據(jù)塊，直到處理完YL-1為止。最后輸出ABCDE級(jí)聯(lián)后的結(jié)果。SHA-1算法與MD5算法的比較如表4-4-1所示。 第4章 消息認(rèn)證技術(shù)表表4-4-1 SHA-1算法與算法與MD5算法的比較

17、算法的比較 第4章 消息認(rèn)證技術(shù)Hash函數(shù)須滿足4.1節(jié)的5條性質(zhì)，然而，抗強(qiáng)碰撞性對(duì)于消息Hash函數(shù)的安全性要求是非常高的。例如，MD5算法輸出的Hash函數(shù)值總數(shù)為2128，SHA-1算法輸出的Hash函數(shù)值總數(shù)為2160，這說(shuō)明可能Hash函數(shù)值是有限的，而輸入的消息是無(wú)限的，因此，函數(shù)的碰撞性是可能存在的。評(píng)價(jià)Hash函數(shù)的一個(gè)最好的方法是看攻擊者找到一對(duì)碰撞消息所花的代價(jià)有多大。一般地，假設(shè)攻擊者知道Hash函數(shù)，攻擊者的主要目標(biāo)是找到一對(duì)或更多對(duì)碰撞消息。目前已有一些攻擊Hash函數(shù)的方案和計(jì)算碰撞消息的方法，這些方法中的生日攻擊方法可用于攻擊任何類型的Hash函數(shù)方案。4.5

18、 Hash函數(shù)的攻擊分析函數(shù)的攻擊分析 第4章 消息認(rèn)證技術(shù)生日攻擊方法只依賴于消息摘要的長(zhǎng)度，即Hash函數(shù)值的長(zhǎng)度。生日攻擊給出消息摘要長(zhǎng)度的一個(gè)下界。一個(gè)40 bit長(zhǎng)的消息摘要是很不安全的，因?yàn)閮H僅用220 (大約一百萬(wàn))次Hash函數(shù)值的隨機(jī)計(jì)算就可至少以1/2的概率找到一對(duì)碰撞。為了抵抗生日攻擊，通常建議消息摘要的長(zhǎng)度至少應(yīng)為128 bit，此時(shí)生日攻擊需要約264次Hash函數(shù)值的計(jì)算。 第4章 消息認(rèn)證技術(shù)除生日攻擊法外，對(duì)一些類型的Hash函數(shù)還有一些特殊的攻擊方法，例如，中間相遇攻擊法、修正分組攻擊法和差分分析法等。值得一提的是，山東大學(xué)王小云教授等人于2004年8月在美國(guó)

19、加州召開(kāi)的國(guó)際密碼大會(huì)(Crypto2004)上所做的Hash函數(shù)研究報(bào)告中指出，他們已成功破譯了MD4、MD5、HAVAL128、RIPEMD128等Hash算法。最近國(guó)際密碼學(xué)家Lenstra利用王小云等人提供的MD5碰撞，偽造了符合X.509標(biāo)準(zhǔn)的數(shù)字證書(shū)，這就說(shuō)明了MD5算法的破譯已經(jīng)不僅僅是理論破譯結(jié)果，而是可以導(dǎo)致實(shí)際的攻擊，MD5算法的撤出迫在眉睫。他們的研究成果得到了國(guó)際密碼學(xué)界專家的高度評(píng)價(jià)，他們找到的碰撞基本上宣布了MD5算法的終結(jié)，這一成就或許是近年來(lái)密碼學(xué)界最具實(shí)質(zhì)性的研究進(jìn)展。 第4章 消息認(rèn)證技術(shù)在MD5算法被以王小云為代表的中國(guó)專家攻破之后，世界密碼學(xué)界仍然認(rèn)為S

20、HA-1算法是安全的。2006年2月，美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院發(fā)表申明，SHA-1算法沒(méi)有被攻破，并且沒(méi)有足夠的理由懷疑它會(huì)很快被攻破，開(kāi)發(fā)人員在2010年前應(yīng)該轉(zhuǎn)向更為安全的SHA-256和SHA-512算法。然而，一周之后，王小云就宣布了攻破SHA-1算法的消息。因?yàn)镾HA-1算法在美國(guó)等國(guó)家有更加廣泛的應(yīng)用，密碼被破的消息一出，在國(guó)際上的反響可謂石破天驚。換句話說(shuō)，王小云的研究成果表明了電子簽名從理論上講是可以偽造的，必須及時(shí)添加限制條件，或者重新選用更為安全的密碼標(biāo)準(zhǔn)，以保證電子商務(wù)的安全。第4章 消息認(rèn)證技術(shù)(1) 用做消息認(rèn)證的摘要函數(shù)具有單向性、抗碰撞性。單向函數(shù)的優(yōu)良性質(zhì)，使其成為公鑰密碼、消息壓縮的數(shù)學(xué)基礎(chǔ)。(2) 消息認(rèn)證碼特指使用收、發(fā)雙方共享的密鑰K和長(zhǎng)度可變的消