1、本資料來源HashHash函數函數消息認證碼消息認證碼MD5MD5算法算法SHA-1SHA-1算法算法Hash函數的攻擊分析函數的攻擊分析4.1.1 一個簡單的一個簡單的Hash函數函數4.1.2 完整性檢驗一般方法完整性檢驗一般方法Hash函數，就是將一種任意長度的消息壓縮成某一固定長度的消息摘要的函數，又稱消息摘要函數，散列函數或雜湊函數，記為：h=H(M) 。我們把Hash值 稱為輸入數據M的“數字指紋”。Hash函數的這種單向性特征和輸出數據長度固定的特征使得它可以用于檢驗消息的完整性是否遭到破壞。用作消息認證的Hash函數具有如下一些性質：(1) 消息M可以是任意長度的數據。(2)

2、給定消息M，計算它的Hash值 h=H(M) 是很容易的。(3) 任意給定 h，則很難找到M使得h=H(M) ，即給出Hash值，要求輸入M在計算上是不可行的，即運算過程是不可逆的，這種性質稱為函數的單向性。(4) 給定消息M和其Hash值H(M) ，要找到另一個 M，且M M，使得H(M) =H(M)在計算上是不可行的，這條性質被稱為抗弱碰撞性。(5) 對于任意兩個不同的消息 M M ，它們的摘要值不可能相同，這條性質被稱為抗強碰撞性。弱抗碰撞性保證對于一個消息M及其Hash值，無法找到一個替代消息M ，使它的Hash值與給定的Hash值相同。這條性質可用于防止偽造。強抗碰撞性對于消息Has

3、h函數的安全性要求更高，這條性質保證了對生日攻擊的防御能力。碰撞性是指對于兩個不同的消息M和M ，如果它們的摘要值相同，則發生了碰撞。雖然可能的消息是無限的，但可能的摘要值卻是有限的。因此，不同的消息可能會產生同一摘要，碰撞是可能存在的。但是， Hash函數要求用戶不能按既定需要找到一個碰撞，意外的碰撞更是不太可能的。顯然，從安全性的角度來看，Hash函數輸出的比特越長，抗碰撞的安全強度越大。一個例外的情況是，若消息出錯，而摘要值仍然不變的概率為 。當n充分大時，出錯的概率或者說消息被篡改的概率非常小，視為小概率事件，忽略不計。n2n2消息完整性檢驗的一般機制如圖所示。無論是存儲文件還是傳輸文

4、件，都需要同時存儲或發送該文件的數字指紋；驗證時，對于實際得到的文件重新產生其數字指紋，再與原數字指紋對比，如果一致，則說明文件是完整的。否則，是不完整的。消息認證具有兩層含義：一是檢驗消息的來源是真實的，即對消息的發送者的身份進行認證；二是檢驗消息是完整的，即驗證消息在傳送或存儲過程中未被篡改、刪除或插入等。當需要進行消息認證時，僅有消息作為輸入是不夠的，需要加入密鑰k，這就是消息認證的原理。能否認證，關鍵在于信息發送者或信息提供者是否擁有密鑰k。消息認證碼(Message Authentication Code，MAC)通常表示為MAC=CK(M)其中M是可變長的消息，K是收發雙方共享的密

5、鑰，函數值CK(M)是定長的認證碼，也稱為密碼校驗和。MAC就是帶密鑰的消息摘要函數，其實就是一種帶密鑰的數字指紋，它與不帶密鑰的數字指紋是有本質區別的。1. 消息認證消息認證認證碼被附加到消息后以M|MAC方式一并發送，收方通過重新計算MAC以實現對M的認證。如圖所示。假定收、發雙方共享密鑰k，如果收到的MAC與計算得出的MAC一致，那么可以得出如下結論： 接收方確信消息M未被篡改。此為完整性驗證。 接收方確信消息來自所聲稱的發送者，因為沒有其他人知道這個共享密鑰，其他人也就不可能為消息M附加合適的MAC。此為消息源驗證。2. 消息認證與保密消息認證與保密在(1)中，消息以明文方式傳送，這一

6、過程只提供認證而不具備保密性。如圖4-2-2所示提供一種即加密又認證的方式，發送方發送Ek2M|Ck1(M)。該種處理方式除具備(1)的功能外，還具有保密性。3. 密文認證密文認證改變(2)中加密的位置，得到另外一種消息保密與認證方式，如圖所示。該種處理方式先對消息進行加密，然后再對密文計算MAC，傳送Ek2(M)|Ck1(Ek2(M)給接收方。接收方先對收到的密文進行認證，認證成功后，再解密。MD表示消息摘要(Message Digest，簡記為MD)，MD5以512比特一塊的方式處理輸入的消息文本，每個塊又劃分為16個32比特的子塊。算法的輸出是由4個32比特的塊組成，將它們級聯成一個12

7、8比特的摘要值。MD5算法如圖所示，包括以下幾個步驟。(1) 填充消息使其長度正好為填充消息使其長度正好為512位的整數倍位的整數倍L首先在消息的末尾處附上64比特的消息長度的二進制表示，大小為 ，n表示消息長度。然后在消息后面填充一個“1”和多個“0”，填充后的消息恰好是512比特的整倍長L。Y0，Y1，YL-1表示不同的512比特長的消息塊，用M0，M1，MN1表示各個Yq中按32比特分組的字，N一定是16的整數倍。(2) 初始化緩沖區初始化緩沖區算法中使用了128位的緩沖區，每個緩沖區由4個32比特的寄存器A，B，C，D組成，先把這4個寄存器初始化為： A=01 23 45 67 B=8

8、9 AB CD EF C=FE DC BA 98 D=76 54 32 10(3) 處理處理512位消息塊位消息塊Yq，進入主循環，進入主循環主循環的次數正好是消息中512位的塊的數目L。先從Y0開始，上一循環的輸出作為下一循環的輸入，直到處理完YL-1為止。消息塊Yq的處理，以當前的512位數據塊Yq和128位緩沖值A，B，C，D作為輸入，并修改緩沖值的內容。消息塊的處理包含4輪操作，每一輪由16次迭代操作組成，上一輪的輸出作為下一輪的輸入，如圖所示。4輪處理具有相似的結構，但每輪處理使用不同的非線性函數，如圖所示。4個非線性函數分別為：常數表Ti( )共有64個元素，每個元素32位長，Ti

9、232abs(sin(i),其中i是弧度。處理每一個消息塊Yi時，每一輪使用常數表Ti中的16個，正好用4輪。(4) 輸出輸出每一輪不斷地更新緩沖區A，B，C，D中的內容，4輪之后進入下一個主循環，直到處理完所有消息塊為止。最后輸出就是結束時緩沖區中的內容。SHA（Secure Hash Algorithm，SHA）是由美國NIST開發，作為聯邦信息處理標準于1993年發表，1995年修訂，成為SHA-1版本。SHA-1在設計方面基本上模仿MD5，如圖所示。(1) 填充消息填充消息首先將消息填充為512的整數倍，填充方法與MD5相同。與MD5不同的是SHA-1的輸入為長度小于 比特的消息。 (

10、2) 初始化緩沖區初始化緩沖區初始化160位的消息摘要緩沖區（即設定IV值），該緩沖區用于保存中間和最終摘要結果。每個緩沖區由5個32比特的寄存器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(3) 處理處理512位消息塊位消息塊Yq，進入主循環，進入主循環主循環的次數正好是消息中512位的塊的數目L。先從Y0開始，上一循環的輸出作為下一循環的輸入，直到處理完YL-1為止。主循環有四輪，每輪20次操作（ 有四輪，每輪16次操作）。每次操作對A 、B 、C 、D 和E中

11、的三個做一次非線性函數運算，然后進行與MD5中類似的移位運算和加運算。四個非線性函數為用下面的算法將消息塊從16個32比特子塊變成80個32比特子塊（ W0 到W79 ）：該算法主循環4輪，每輪20次，0t79 ，每一次的變換的基本形式是相同的：其中(A5) 表示寄存器A循環左移5比特， (B30) 表示寄存器K循環左移30比特。80次處理完后，處理下一個512位的數據塊，直到處理完YL-1為止。最后輸出ABCDE 級聯后的結果。SHA1與MD5的比較如表所示。SHA1MD5Hash值長度160位128位分組處理長度512位512位步數80(420)64(416)最大消息長度264位不限非線性

12、函數3（第2、4輪相同）4生日攻擊方法可用于攻擊任何類型的Hash方案。生日攻擊方法只依賴于消息摘要的長度，即Hash函數值的長度。生日攻擊給出消息摘要的長度的一個下界。除生日攻擊法外，對一些類型的Hash函數還有一些特殊的攻擊方法，例如，中間相遇攻擊、修正分組攻擊和差分分析法等。山東大學王小云教授等于2004年8月在美國加州召開的國際密碼大會(Crypto2004)上所做的Hash函數研究報告中指出，她們已成功破譯了MD4、MD5、HAVAL-128、RIPEMD-128等Hash算法。2006年，王小云宣布了攻破SHA-1的消息。她的研究成果表明了從理論上講電子簽名可以偽造，必須及時添加限