第4講消息認證技術new2

第4章消息認證技術Hash函數消息認證碼MD5算法SHA-1算法Hash函數的攻擊分析為什么要進行消息認證？信息在傳輸過程中有可能被改變！主動攻擊——篡改消息截獲Bob發(fā)出的消息，篡改后再轉發(fā)給Alice3BobAliceEve通信網絡如何確認消息來自發(fā)送方？IloveyouIdon’tloveyou完整性需要驗證：信息發(fā)送方是否真實？接收方是否真實？信息在傳輸過程中是否被改變？信息的到達時間是否在指定的期限內？消息認證是指對消息的真實性和完整性的驗證。對消息的真實性的驗證，也稱為消息源認證，即驗證消息發(fā)送者或消息的來源是真實的。對消息的完整性驗證，也稱為消息完整性認證，即驗證消息在傳送或存儲過程中未被篡改、重放、刪除或插入等。4.1Hash函數Hash函數，就是將一種任意長度的消息壓縮成某一固定長度的消息摘要的函數，又稱消息摘要函數，散列函數或雜湊函數，記為：h=H(M)。我們把Hash值稱為輸入數據M的“數字指紋”。Hash函數的這種單向性特征和輸出數據長度固定的特征使得它可以用于檢驗消息的完整性是否遭到破壞。如果消息或數據被篡改，那么數字指紋就不正確了。4.1Hash函數用作消息認證的Hash函數具有如下一些性質：(1)消息M可以是任意長度的數據。(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’，它們的摘要值不可能相同，這條性質被稱為抗強碰撞性。4.1Hash函數弱抗碰撞性保證對于一個消息M及其Hash值，無法找到一個替代消息M’

，使它的Hash值與給定的Hash值相同。這條性質可用于防止偽造。強抗碰撞性對于消息Hash函數的安全性要求更高，這條性質保證了對生日攻擊的防御能力。碰撞性是指對于兩個不同的消息M和M’，如果它們的摘要值相同，則發(fā)生了碰撞。雖然可能的消息是無限的，但可能的摘要值卻是有限的。因此，不同的消息可能會產生同一摘要，碰撞是可能存在的。但是，Hash函數要求用戶不能按既定需要找到一個碰撞，意外的碰撞更是不太可能的。顯然，從安全性的角度來看，Hash函數輸出的比特越長，抗碰撞的安全強度越大。4.1.1一個簡單的Hash函數4.1.1一個簡單的Hash函數

對于明文m，按每組n比特進行劃分，如果最后一組長度不夠，則補充0。不妨設劃分為r組，mi={mi1，mi2，…，min}，1≤i≤r，mij=0或1，然后將各分組逐比特進行模2加運算，則輸出為h={h1，h2，…，hn}，其中h1=m11+m21+…+mr1(mod2)，…，hn=m1n+m2n+…+mm(mod2)。從定義可見，hi表示所有分組的第i比特進行模2加，因此，若消息改變，摘要值也會隨之改變。一個例外的情況是，若消息出錯，而摘要值仍然不變的概率為2-n。當n充分大時，出錯的概率或者說消息被篡改的概率非常小，視為小概率事件，可忽略不計。4.1.2完整性檢驗一般方法消息完整性檢驗的一般機制如圖所示。無論是存儲文件還是傳輸文件，都需要同時存儲或發(fā)送該文件的數字指紋；驗證時，對于實際得到的文件重新產生其數字指紋，再與原數字指紋對比，如果一致，則說明文件是完整的。否則，是不完整的。4.2消息認證碼消息的完整性檢驗，只能檢驗消息是否是完整的，不能說明消息是否是偽造的。因為，一個偽造的消息與其對應的數字指紋也是匹配的。消息認證具有兩層含義：一是檢驗消息的來源是真實的，即對消息的發(fā)送者的身份進行認證；二是檢驗消息是完整的，即驗證消息在傳送或存儲過程中未被篡改、刪除或插入等。當需要進行消息認證時，僅有消息作為輸入是不夠的，需要加入密鑰k，這就是消息認證的原理。能否認證，關鍵在于信息發(fā)送者或信息提供者是否擁有密鑰k。消息認證碼(MessageAuthenticationCode，MAC)通常表示為MAC=CK(M)其中M是可變長的消息，K是收發(fā)雙方共享的密鑰，函數值CK(M)是定長的認證碼，也稱為密碼校驗和。MAC就是帶密鑰的消息摘要函數，其實就是一種帶密鑰的數字指紋，它與不帶密鑰的數字指紋是有本質區(qū)別的。4.2消息認證碼1.消息認證認證碼被附加到消息后以M||MAC方式一并發(fā)送，收方通過重新計算MAC以實現對M的認證。如圖所示。假定收、發(fā)雙方共享密鑰k，如果收到的MAC與計算得出的MAC一致，那么可以得出如下結論：①接收方確信消息M未被篡改。此為完整性驗證。②接收方確信消息來自所聲稱的發(fā)送者，因為沒有其他人知道這個共享密鑰，其他人也就不可能為消息M附加合適的MAC。此為消息源驗證。4.2消息認證碼2.消息認證與保密在(1)中，消息以明文方式傳送，這一過程只提供認證而不具備保密性。如圖4-2-2所示提供一種即加密又認證的方式，發(fā)送方發(fā)送Ek2[M||Ck1(M)]。該種處理方式除具備(1)的功能外，還具有保密性。4.2消息認證碼3.密文認證改變(2)中加密的位置，得到另外一種消息保密與認證方式，如圖所示。該種處理方式先對消息進行加密，然后再對密文計算MAC，傳送Ek2(M)||Ck1(Ek2(M))給接收方。接收方先對收到的密文進行認證，認證成功后，再解密。4.3MD5算法MD表示消息摘要(MessageDigest，簡記為MD)，MD5以512比特一塊的方式處理輸入的消息文本，每個塊又劃分為16個32比特的子塊。算法的輸出是由4個32比特的塊組成，將它們級聯(lián)成一個128比特的摘要值。MD5算法如圖所示，包括以下幾個步驟。4.3MD5算法(1)填充消息使其長度正好為512位的整數倍L首先在消息的末尾處附上64比特的消息長度的二進制表示，大小為，n表示消息長度。然后在消息后面填充一個“1”和多個“0”，填充后的消息恰好是512比特的整倍長L。Y0，Y1，…，YL-1表示不同的512比特長的消息塊，用M[0]，M[1]，…，M[N－1]表示各個Yq中按32比特分組的字，N一定是16的整數倍。(2)初始化緩沖區(qū)算法中使用了128位的緩沖區(qū)，每個緩沖區(qū)由4個32比特的寄存器A，B，C，D組成，先把這4個寄存器初始化為：A=01234567

B=89ABCDEF

C=FEDCBA98D=765432104.3MD5算法(3)處理512位消息塊Yq，進入主循環(huán)主循環(huán)的次數正好是消息中512位的塊的數目L。先從Y0開始，上一循環(huán)的輸出作為下一循環(huán)的輸入，直到處理完YL-1為止。消息塊Yq的處理，以當前的512位數據塊Yq和128位緩沖值A，B，C，D作為輸入，并修改緩沖值的內容。消息塊的處理包含4輪操作，每一輪由16次迭代操作組成，上一輪的輸出作為下一輪的輸入，如圖所示。4.3MD5算法4輪處理具有相似的結構，但每輪處理使用不同的非線性函數，如圖所示。4個非線性函數分別為：常數表T[i]()共有64個元素，每個元素32位長，T[i]＝232abs(sin(i)),其中i是弧度。處理每一個消息塊Yi時，每一輪使用常數表T[i]中的16個，正好用4輪。4.3MD5算法(4)輸出每一輪不斷地更新緩沖區(qū)A，B，C，D中的內容，4輪之后進入下一個主循環(huán)，直到處理完所有消息塊為止。最后輸出就是結束時緩沖區(qū)中的內容。4.4SHA-1算法SHA（SecureHashAlgorithm，SHA）是由美國NIST開發(fā)，作為聯(lián)邦信息處理標準于1993年發(fā)表，1995年修訂，成為SHA-1版本。SHA-1在設計方面基本上模仿MD5，如圖所示。4.4SHA-1算法(1)填充消息首先將消息填充為512的整數倍，填充方法與MD5相同。與MD5不同的是SHA-1的輸入為長度小于2的64次方比特的消息。(2)初始化緩沖區(qū)初始化160位的消息摘要緩沖區(qū)（即設定IV值），該緩沖區(qū)用于保存中間和最終摘要結果。每個緩沖區(qū)由5個32比特的寄存器A，B，C，D，E組成，初始化為：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C2D2E1F04.4SHA-1算法(3)處理512位消息塊Yq，進入主循環(huán)主循環(huán)的次數正好是消息中512位的塊的數目L。先從Y0開始，上一循環(huán)的輸出作為下一循環(huán)的輸入，直到處理完YL-1為止。主循環(huán)有四輪，每輪20次操作（有四輪，每輪16次操作）。每次操作對A、B、C、D和E中的三個做一次非線性函數運算，然后進行與MD5中類似的移位運算和加運算。四個非線性函數為用下面的算法將消息塊從16個32比特子塊變成80個32比特子塊（W0到W79）：4.4SHA-1算法該算法主循環(huán)4輪，每輪20次，0≤t≤79，每一次的變換的基本形式是相同的：其中(A<<5)表示寄存器A循環(huán)左移5比特，(B<<30)表示寄存器K循環(huán)左移30比特。80次處理完后，處理下一個512位的數據塊，直到處理完YL-1為止。最后輸出A║B║C║D║E級聯(lián)后的結果。4.4SHA-1算法SHA－1與MD5的比較如表所示。4.5Hash函數的攻擊分析問題：在一個教室中最少應有多少學生才使得至少有兩個學生的生日在同一天的概率不小于1/2？忽略閏年，假設所有的生日都是等可能的答案是234.5Hash函數的攻擊分析考慮23個人的情況，計算他們生日互不相同的概率。將他們列成一行。第一個人的生日用了一天，因此第二個人生日是另一天的概率是(1－1/365)。對第三人來說，已經有兩天用過了，第三個生日和前兩個不同的概率是(1－2/365)。因此，三個人生日互不相同的概率是(1－1/365)(1－2/365)。如此繼續(xù)，可以得到23個人生日互不相同的概率是0.493因此，至少有兩個人有相同生日的概率是1－0.493＝0.507。4.5Hash函數的攻擊分析所以，屋子里有23個人，其中兩人生日相同的概率略大于50%。如果是30人，概率大約是70%。這是個看起來有些讓人吃驚的結論，稱為生日悖論（birthdayparadox）生日攻擊這個術語來自于生日悖論。生日攻擊方法可用于攻擊任何類型的Hash方案。生日攻擊方法只依賴于消息摘要的長度，即Hash函數值的長度。生日攻擊給出消息摘要的長度的一個下界。4.5Hash函數的攻擊分析除生日攻擊法外，對一些類型的Hash函數還有一些特殊的攻擊方法，例如，中間相遇攻擊、修正分組攻擊和差分分析法等。山東大學王小云教授等于2004年8月在美國加州召開的國際密碼大會(Crypto’2004)上所做的Hash函數研究報告中指出，她們已成功破譯了MD4、MD5、HAVAL-128、RIPEMD-128等Hash算法。2006年，王小云宣布了攻破SHA-1的消息。她的研究成果表明了從理論上講電子簽名可以偽造，必須及時添加限制條件，或者重新選用更為安全的密碼標準，以保證電子商務的安全。小結1．用作消息認證的摘要函數具有單向性、抗碰撞性。單向函數的優(yōu)良性質，使其成為公鑰密碼、消息壓縮的數學基礎。2．消息認證碼特指使用收發(fā)雙方共享的密鑰K和可變長的消息M，輸出長度固定的函數值MAC，也稱為密碼校驗和。MAC就是帶密鑰的消息摘要函數，或稱為一種帶密鑰的數字指紋，它與普通摘要函數(Hash函數)是有本質區(qū)別的。小結3．消息完整性校驗的一般準則是將實際得到的消息的數字指紋，與原數字指紋進行匹配。如果一致，則說明消息是完整的