【正文】 1 散列函數(shù) 《 現(xiàn)代密碼學 》 第 7章 2 本章主要內(nèi)容 ? 消息認證碼 ? 散列函數(shù) ? MD5雜湊算法 ? 安全雜湊算法 ? HMAC算法 ? 習題 3 曾介紹過信息安全所面臨的基本攻擊類型，包括被動攻擊（獲取消息的內(nèi)容、業(yè)務(wù)流分析）和主動攻擊（假冒、重放、消息的篡改、業(yè)務(wù)拒絕）?？箵舯粍庸舻姆椒ㄊ乔懊嬉呀榻B過的加密，本章介紹的消息認證則是用來抗擊主動攻擊的。 消息認證是一個過程，用以驗證接收消息的真實性（的確是由它所聲稱的實體發(fā)來的）和完整性（未被篡改、插入、刪除），同時還用于驗證消息的順序性和時間性（未重排、重放、延遲）。 攻擊的類型 4 ? 除此之外，在考慮信息安全時還需考慮業(yè)務(wù)的不可否認性，即防止通信雙方中的某一方對所傳輸消息的否認。實現(xiàn)消息的不可否認性可通過數(shù)字簽字，數(shù)字簽字也是一種認證技術(shù)，它也可用于抗擊主動攻擊。 攻擊的類型 5 攻擊的類型 攻擊 主動攻擊 被動攻擊 獲取消息的內(nèi)容 業(yè)務(wù)流分析 假冒 重放 篡改 6 1 用來驗證消息的真實性。 2 用來驗證消息的完整性。 3 用來驗證消息的順序性和時間性。 4 用來驗證消息的不可否認性。 認證是一個過程，消息認證機制需要有產(chǎn)生認證符的基本功能。認證符用來判斷消息的真實性。認證符的產(chǎn)生有消息認證碼（ MAC)和散列函數(shù) (hash)兩大類。 認證的功能 7 消息認證包括 : ? 消息完整性 ? 身份識別 ? 不可否認性 消息認證的含義 8 消息認證碼是指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的、用作認證符的、固定長度的數(shù)值，也稱為密碼校驗和。此時需要通信雙方 A和 B共享一密鑰 K。設(shè) A欲發(fā)送給 B的消息是 M， A首先計算 MAC=CK(M)，其中CK()是密鑰控制的公開函數(shù)，然后向 B發(fā)送M‖MAC， B收到后做與 A相同的計算，求得一新 MAC，并與收到的 MAC做比較，如圖 1（ a）所示。 消息認證碼的定義及使用方式 9 如果僅收發(fā)雙方知道 K，且 B計算得到的 MAC與接收到的 MAC一致，則這一系統(tǒng)就實現(xiàn)了以下功能： ① 接收方相信發(fā)送方發(fā)來的消息未被篡改，這是因為攻擊者不知道密鑰，所以不能夠在篡改消息后相應(yīng)地篡改 MAC，而如果僅篡改消息，則接收方計算的新 MAC將與收到的 MAC不同。 ② 接收方相信發(fā)送方不是冒充的，這是因為除收發(fā)雙方外再無其他人知道密鑰，因此其他人不可能對自己發(fā)送的消息計算出正確的 MAC。 消息認證碼的定義及使用方式 10 MAC函數(shù)與加密算法類似，不同之處為 MAC函數(shù)不必是可逆的，因此與加密算法相比更不易被攻破。 上述過程中，由于消息本身在發(fā)送過程中是明文形式，所以這一過程只提供認證性而未提供保密性。為提供保密性可在 MAC函數(shù)以后 (如圖 1(b))或以前 (如圖 1(c))進行一次加密，而且加密密鑰也需被收發(fā)雙方共享。在圖 1(b)中， M與 MAC鏈接后再被整體加密，在圖 1(c)中， M先被加密再與 MAC鏈接后發(fā)送。通常希望直接對明文進行認證，因此圖1(b)所示的使用方式更為常用。 消息認證碼的定義及使用方式 11 ? message authentication code (MAC) ? 簽名的電子等價形式 ? 與消息同時發(fā)送 ? 通過一些算法 , 依賴于消息及雙方共享的秘密 ? 消息可以是不任意長 ? MAC 可以是任意長 ,但常選固定長度 ? 這需要 hash function ? “壓縮 ” 消息成固定長度 12 MAC的基本使用方式 13 消息認證過程 14 利用對稱密碼進行認證 ? 利用對稱密碼加密的消息可以作為認證內(nèi)容 ? 因為只有密鑰的擁有者才可以生成 ? (要求消息有一定的冗余度 ) ? 但不能解決消息的不可否認性 ? （無法證明誰生成的消息） 15 使用加密算法（單鑰算法或公鑰算法）加密消息時，其安全性一般取決于密鑰的長度。如果加密算法沒有弱點，則敵手只能使用窮搜索攻擊以測試所有可能的密鑰。如果密鑰長為 k比特，則窮搜索攻擊平均將進行2k1個測試。特別地，對惟密文攻擊來說，敵手如果知道密文 C，則將對所有可能的密鑰值 Ki執(zhí)行解密運算 Pi=DKi(C)，直到得到有意義的明文。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 16 對 MAC來說，由于產(chǎn)生 MAC的函數(shù)一般都為多到一映射，如果產(chǎn)生 n比特長的 MAC，則函數(shù)的取值范圍即為 2n個可能的 MAC，函數(shù)輸入的可能的消息個數(shù) N2n，而且如果函數(shù)所用的密鑰為 k比特，則可能的密鑰個數(shù)為 2k。 如果系統(tǒng)不考慮保密性，即敵手能獲取明文消息和相應(yīng)的 MAC，那么在這種情況下要考慮敵手使用窮搜索攻擊來獲取產(chǎn)生 MAC的函數(shù)所使用的密鑰。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 17 假定 kn，且敵手已得到 M1和 MAC1，其中 MAC1=CK1（ M1），敵手對所有可能的密鑰值 Ki求 MACi=CKi(M1)，直到找到某個 Ki使得MACi=MAC1。由于不同的密鑰個數(shù)為 2k，因此將產(chǎn)生 2k個 MAC，但其中僅有 2n個不同，由于 2k2n，所以有很多密鑰（平均有2k/2n=2kn個）都可產(chǎn)生出正確的 MAC1，而敵手無法知道進行通信的兩個用戶用的是哪一個密鑰，還必須按以下方式重復(fù)上述攻擊： 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 18 第 1輪 已知 M MAC1，其中 MAC1=CK(M1)。對所有 2k個可能的密鑰計算 MACi=CKi(M1)，得 2kn個可能的密鑰。 第 2輪 已知 M MAC2，其中 MAC2=CK(M2)。對上一輪得到的 2kn個可能的密鑰計算 MACi=CKi(M2)，得 2k2 n個可能的密鑰。 如此下去，如果 k=αn，則上述攻擊方式平均需要 α輪。例如，密鑰長為 80比特， MAC長為 32比特，則第 1輪將產(chǎn)生大約 248個可能密鑰，第 2輪將產(chǎn)生216個可能的密鑰，第 3輪即可找出正確的密鑰。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 19 如果密鑰長度小于 MAC的長度，則第 1輪就有可能找出正確的密鑰，也有可能找出多個可能的密鑰，如果是后者，則仍需執(zhí)行第2輪搜索。 所以對消息認證碼的窮搜索攻擊比對使用相同長度密鑰的加密算法的窮搜索攻擊的代價還要大。然而有些攻擊法卻不需要尋找產(chǎn)生 MAC所使用的密鑰。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 20 例如，設(shè) M=(X1‖X2‖… ‖Xm)是由 64比特長的分組 Xi(i=1,… ,m)鏈接得到的，其消息認證碼由以下方式得到： 式的 DES。 ? ?12()( ) ( )mKKM X X XC M E M? ? ? ? ???? 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 21 ? 因此，密鑰長為 56比特， MAC長為 64比特，如果敵手得到 M‖CK(M)，那么敵手使用窮搜索攻擊尋找 K將需做 256次加密。然而敵手還可用以下方式攻擊系統(tǒng)： 將 X1到 Xm1分別用自己選取的 Y1到 Ym1替換，求出 Ym=Y1Y2 … Ym1 Δ(M)，并用 Ym替換 Xm。因此敵手可成功偽造一新消息 M′=Y1 … Ym，且 M′的 MAC與原消息 M的 MAC相同。 ?????? 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 22 考慮到 MAC所存在的以上攻擊類型，可知它應(yīng)滿足以下要求，其中假定敵手知道函數(shù) C，但不知道密鑰 K： ① 如果敵手得到 M和 CK(M)，則構(gòu)造一滿足CK(M′)=CK(M)的新消息 M′在計算上是不可行的。 ② CK(M)在以下意義下是均勻分布的： 隨機選取兩個消息 M、 M′， Pr[CK(M)=CK(M′)]=2n，其中 n為MAC的長。 ③ 若 M′是 M的某個變換，即 M′=f(M)，例如 f為插入一個或多個比特，那么 Pr[CK(M)=CK(M′)] = 2n。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 23 第 1個要求是針對上例中的攻擊類型的，此要求是說敵手不需要找出密鑰 K而偽造一個與截獲的 MAC相匹配的新消息在計算上是不可行的。 第 2個要求是說敵手如果截獲一個 MAC，則偽造一個相匹配的消息的概率為最小。 最后一個要求是說函數(shù) C不應(yīng)在消息的某個部分或某些比特弱于其他部分或其他比特，否則敵手獲得 M和 MAC后就有可能修改 M中弱的部分，從而偽造出一個與原 MAC相匹配的新消息。 產(chǎn)生 MAC的函數(shù)應(yīng)滿足的要求 24 數(shù)據(jù)認證算法是最為廣泛使用的消息認證碼中的一個，已作為 FIPS Publication（ FIPS PUB 113）并被 ANSI作為 。 算法基于 CBC模式的 DES算法，其初始向量取為零向量。需被認證的數(shù)據(jù)（消息、記錄、文件或程序）被分為 64比特長的分組 D1，D2， … ， DN，其中最后一個分組不夠 64比特的話，可在其右邊填充一些 0，然后按以下過程計算數(shù)據(jù)認證碼（見圖 2）： 數(shù)據(jù)認證算法 25 數(shù)據(jù)認證算法 26 其中 E為 DES加密算法， K為密鑰。 數(shù)據(jù)認證碼或者取為 ON或者取為 ON的最左 M個比特，其中 16≤M≤64。 112 2 13 3 21()()()()KKKN K N NO E DO E D OO E D OO E D O????????27 散列函數(shù) H是一公開函數(shù)，用于將任意長的消息 M映射為較短的、固定長度的一個值 H(M)，作為認證符，稱函數(shù)值 H(M)為雜湊值、雜湊碼或消息摘要。雜湊碼是消息中所有比特的函數(shù)，因此提供了一種錯誤檢測能力，即改變消息中任何一個比特或幾個比特都會使雜湊碼發(fā)生改變。 散列函數(shù)的定義及使用方式 28 圖 3 表示散列函數(shù)用來提供消息認證的基