信息技術--趙澤茂--第四章.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

14、60 bit的消息摘要緩沖區(qū)(即設定IV值)，該緩沖區(qū)用于保存中間和最終摘要結果。每個緩沖區(qū)由5個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章 消息認證技術(3) 處理512 bit消息塊Yq，進入主循環(huán)。主循環(huán)的次數(shù)正好是消息中512 bit的塊的數(shù)目L。先從Y0開始，以上一循環(huán)的輸出作為下一循環(huán)的輸入，直到處理完YL-1為止。主循環(huán)有4輪，每輪20次操作(MD5算法有4輪，每輪16次操作)。每次操作對A、B、 C、 D和E中的3個做一次非

15、線性函數(shù)運算，然后進行與MD5算法中類似的移位運算和加運算。第4章 消息認證技術四個非線性函數(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章 消息認證技術用下面的算法將消息塊從16個32 bit子塊變成80個32 bit子塊(W0到W79):

16、 Wt=Mt (0t15) Wt=(Wt-3Wt-8Wt-14Wt-16)1 (16t79)第4章 消息認證技術 該算法主循環(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次處理完后，處理下一個512 bit的數(shù)據(jù)塊，直到處理完YL-1為止。最后輸出ABCDE級聯(lián)后的結果。SHA-1算法與MD5算法的比較如表4-4-1所示。 第4章 消息認證技術表表4-4-1 SHA-1算法與算法與MD5算法的比較

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

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

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

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