第5章-消息認(rèn)證與雜湊算法

第5章消息認(rèn)證和雜湊算法5.1消息認(rèn)證碼5.2雜湊函數(shù)5.3MD5雜湊算法5.4安全雜湊算法5.5HMAC算法抗擊被動(dòng)攻擊：加密抗擊主動(dòng)攻擊：消息認(rèn)證消息認(rèn)證是一個(gè)過程，用以驗(yàn)證接收消息的真實(shí)性和完整性，同時(shí)還用于驗(yàn)證消息的順序性和時(shí)間性。消息認(rèn)證機(jī)制需要產(chǎn)生認(rèn)證符。認(rèn)證符：用于認(rèn)證消息的數(shù)值。認(rèn)證符的產(chǎn)生方法：消息認(rèn)證碼MAC（messageauthenticationcode）和雜湊函數(shù)（hashfunction）兩大類。消息認(rèn)證碼:指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的、用作認(rèn)證符的、固定長度的數(shù)值,或稱為密碼校驗(yàn)和。此時(shí)需要通信雙方A和B共享一密鑰K。5.1消息認(rèn)證碼

5.1.1消息認(rèn)證碼的定義及使用方式如果僅收發(fā)雙方知道K，且B計(jì)算得到的MAC與接收到的MAC一致，則這一就實(shí)現(xiàn)了以下功能：①接收方相信發(fā)送方發(fā)來的消息未被篡改。②接收方相信發(fā)送方不是冒充的。MAC函數(shù)與加密算法類似，不同之處為MAC函數(shù)不必是可逆的，因此與加密算法相比更不易被攻破。上述過程中，由于消息本身在發(fā)送過程中是明文形式，所以這一過程只提供認(rèn)證性而未提供保密性。圖5.1MAC的基本使用方式5.1.2產(chǎn)生MAC的函數(shù)應(yīng)滿足的要求(1)消息認(rèn)證碼的窮搜索攻擊的代價(jià)比使用相同長度密鑰的加密算法的窮搜索攻擊還要大。攻擊者可假冒發(fā)假消息給接收方。(2)有些攻擊法卻不需要尋找產(chǎn)生MAC所使用的密鑰。先說明兩點(diǎn)，然后給出MAC函數(shù)應(yīng)滿足的要求。第1輪已知M1、MAC1，其中MAC1=CK(M1)。對(duì)所有2k個(gè)可能的密鑰計(jì)算MACi=CKi(M1)，得2k-n個(gè)可能的密鑰。第2輪已知M2、MAC2，其中MAC2=CK(M2)。對(duì)上一輪得到的2k-n個(gè)可能的密鑰計(jì)算MACi=CKi(M2)，得2k-2×n個(gè)可能的密鑰。如此下去，如果k=αn，則上述攻擊方式平均需要α輪。例如，密鑰長為80比特，MAC長為32比特，則第1輪將產(chǎn)生大約248個(gè)可能密鑰，第2輪將產(chǎn)生216個(gè)可能的密鑰，第3輪即可找出正確的密鑰。攻擊MAC(找K):例如:設(shè)M=(X1‖X2‖…‖Xm)是由64比特長的分組Xi(i=1,…,m)鏈接得到的，其消息認(rèn)證碼由以下方式得到：其中表示異或運(yùn)算，加密算法是電碼本模式的DES。因此，密鑰長為56比特，MAC長為64比特，如果敵手得到M‖CK(M)，那么敵手使用窮搜索攻擊尋找K將需做256次加密。然而敵手還可用以下方式攻擊系統(tǒng)：且M′的MAC與原消息M的MAC相同?？紤]到MAC所存在的以上攻擊類型，可知它應(yīng)滿足以下要求，其中假定敵手知道函數(shù)C，但不知道密鑰K：①如果敵手得到M和CK(M)，則構(gòu)造一滿足CK(M′)=CK(M)的新消息M′在計(jì)算上是不可行的。②CK(M)在以下意義下是均勻分布的：隨機(jī)選取兩個(gè)消息M、M′，Pr[CK(M)=CK(M′)]=2-n，其中n為MAC的長。③若M′是M的某個(gè)變換，即M′=f(M)，例如f為插入一個(gè)或多個(gè)比特，那么Pr[CK(M)=CK(M′)]=2-n。數(shù)據(jù)認(rèn)證算法：最為廣泛使用的消息認(rèn)證碼中的一個(gè)。算法基于CBC模式的DES算法，其初始向量取為零向量。需被認(rèn)證的數(shù)據(jù)被分為64比特長的分組D1，D2，…，DN，其中最后一個(gè)分組不夠64比特的話，可在其右邊填充一些0，然后按以下過程計(jì)算數(shù)據(jù)認(rèn)證碼：5.1.3數(shù)據(jù)認(rèn)證算法圖5.2數(shù)據(jù)認(rèn)證算法其中E為DES加密算法，K為密鑰。數(shù)據(jù)認(rèn)證碼或者取為ON或者取為ON的最左M個(gè)比特，其中16≤M≤64。雜湊函數(shù)H是一公開函數(shù)：用于將任意長的消息M映射為較短的、固定長度的一個(gè)值H(M)。作為認(rèn)證符。稱函數(shù)值H(M)為雜湊值、雜湊碼、消息摘要，hash值、散列值。雜湊碼是消息中所有比特的函數(shù)，因此提供了一種錯(cuò)誤檢測能力，即改變消息中任何一個(gè)比特或幾個(gè)比特都會(huì)使雜湊碼發(fā)生改變。5.2雜湊函數(shù)

5.2.1雜湊函數(shù)的定義及使用方式認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法（a）M||H(M)HKHM比較EKMDMBobAlice提供認(rèn)證提供保密EK(M|H(M))認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法（b）M||KEK(H(M))HHM比較EDBobAlice提供認(rèn)證K認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法（c）M||K’bDK’b(H(M))HHM比較DEBobAlice提供認(rèn)證Kb認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法(d)M||KDK’b(H(M))HHM比較EDBobAlice提供認(rèn)證提供保密KMMDK’bEKbEk(M|DK’b(H(M))認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法（e）M||H(M||S)||HM比較BobAlice提供認(rèn)證SS||H認(rèn)證函數(shù)：Hash函數(shù)（續(xù)）哈希函數(shù)的基本用法（f）M||H(M||S)||KHM比較EKMDMBobAlice提供認(rèn)證提供保密EK(M||H(M||S)SS||H雜湊函數(shù)的目的是為需認(rèn)證的數(shù)據(jù)產(chǎn)生一個(gè)“指紋”。為了能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)的認(rèn)證，雜湊函數(shù)應(yīng)滿足以下條件：①函數(shù)的輸入可以是任意長。②函數(shù)的輸出是固定長。③已知x，求H(x)較為容易，可用硬件或軟件實(shí)現(xiàn)。④已知h，求使得H(x)=h的x在計(jì)算上是不可行的，這一性質(zhì)稱為函數(shù)的單向性，稱H(x)為單向雜湊函數(shù)。⑤已知x，找出y(y≠x)使得H(y)=H(x)在計(jì)算上是不可行的。如果單向雜湊函數(shù)滿足這一性質(zhì)，則稱其為弱單向雜湊函數(shù)。⑥找出任意兩個(gè)不同的輸入x、y，使得H(y)=H(x)在計(jì)算上是不可行的。強(qiáng)單向雜湊函數(shù)。5.2.2雜湊函數(shù)應(yīng)滿足的條件1.相關(guān)問題已知一雜湊函數(shù)H有n個(gè)可能的輸出，H(x)是一個(gè)特定的輸出，如果對(duì)H隨機(jī)取k個(gè)輸入，則至少有一個(gè)輸入y使得H(y)=H(x)的概率為0.5時(shí)，k有多大？以后為敘述方便，稱對(duì)雜湊函數(shù)H尋找上述y的攻擊為第Ⅰ類生日攻擊。5.2.3生日攻擊因?yàn)镠有n個(gè)可能的輸出，所以輸入y產(chǎn)生的輸出H(y)等于特定輸出H(x)的概率是1/n，反過來說H(y)≠H(x)的概率是1-1/n。y取k個(gè)隨機(jī)值而函數(shù)的k個(gè)輸出中沒有一個(gè)等于H(x)，其概率等于每個(gè)輸出都不等于H(x)的概率之積，為[1-1/n]k，所以y取k個(gè)隨機(jī)值得到函數(shù)的k個(gè)輸出中至少有一個(gè)等于H(x)的概率為1-[1-1/n]k。由(1+x)k≈1+kx，其中|x|<<1，可得1-[1-1/n]k≈1-[1-k/n]=k/n若使上述概率等于0.5，則k=n/2。特別地，如果H的輸出為m比特長，即可能的輸出個(gè)數(shù)n=2m，則k=2m-1。2.生日悖論生日悖論是考慮這樣一個(gè)問題：在k個(gè)人中至少有兩個(gè)人的生日相同的概率大于0.5時(shí)，k至少多大？設(shè)有k個(gè)整數(shù)項(xiàng)，每一項(xiàng)都在1到n之間等可能地取值。P(n,k)：k個(gè)整數(shù)項(xiàng)中至少有兩個(gè)取值相同的概率。生日悖論就是求使得P(365,k)≥0.5的最小k。Q(365,k)

：k個(gè)數(shù)據(jù)項(xiàng)中任意兩個(gè)取值都不同的概率。如果k>365，則不可能使得任意兩個(gè)數(shù)據(jù)都不相同，因此假定k≤365。k個(gè)數(shù)據(jù)項(xiàng)中任意兩個(gè)都不相同的所有取值方式數(shù)為如果去掉任意兩個(gè)都不相同這一限制條件，可得k個(gè)數(shù)據(jù)項(xiàng)中所有取值方式數(shù)為365k。所以可得當(dāng)k=23時(shí)，P(365,23)=0.5073，即上述問題只需23人，人數(shù)如此之少。若k取100，則P(365,100)=0.9999997，即獲得如此大的概率。之所以稱這一問題是悖論是因?yàn)楫?dāng)人數(shù)k給定時(shí)，得到的至少有兩個(gè)人的生日相同的概率比想象的要大得多。將生日悖論推廣為下述問題：已知一個(gè)在1到n之間均勻分布的整數(shù)型隨機(jī)變量，若該變量的k個(gè)取值中至少有兩個(gè)取值相同的概率大于0.5，則k至少多大？與上類似，，令P(n,k)>0.5，可得。若取n=365，則。3.生日攻擊生日攻擊基于結(jié)論：設(shè)雜湊函數(shù)H有2m個(gè)可能的輸出（即輸出長m比特），如果H的k個(gè)隨機(jī)輸入中至少有兩個(gè)產(chǎn)生相同輸出的概率大于0.5，則。第Ⅱ類生日攻擊：尋找函數(shù)H的具有相同輸出的兩個(gè)任意輸入的攻擊方式。AB敵手對(duì)M產(chǎn)生出2m/2個(gè)變形消息:敵手還準(zhǔn)備一個(gè)假冒的消息M′，產(chǎn)生出2m/2個(gè)變形的消息:將提交給A請求簽字ABAB第Ⅱ類生日攻擊方式：第Ⅱ類生日攻擊方式：①設(shè)用戶將用圖

(c)所示的方式發(fā)送消息，即A用自己的秘密鑰對(duì)消息的雜湊值加密，加密結(jié)果作為對(duì)消息的簽字，連同明文消息一起發(fā)往接收者。②敵手對(duì)A發(fā)送的消息M產(chǎn)生出2m/2個(gè)變形的消息，同時(shí)敵手還準(zhǔn)備一個(gè)假冒的消息M′，并對(duì)假冒的消息產(chǎn)生出2m/2個(gè)變形的消息。③敵手在產(chǎn)生的兩個(gè)消息集合中，找出雜湊值相同的一對(duì)消息,，由上述討論可知敵手成功的概率大于0.5。如果不成功，則重新產(chǎn)生一個(gè)假冒的消息，并產(chǎn)生2m/2個(gè)變形，直到找到雜湊值相同的一對(duì)消息為止。④敵手將提交給A請求簽字，由于與的雜湊值相同，所以可將A對(duì)的簽字當(dāng)作對(duì)

的簽字，將此簽字連同

一起發(fā)給意欲的接收者。將一個(gè)消息變形為具有相同含義的另一消息的方法有很多。例如：對(duì)文件，敵手可在文件的單詞之間插入很多“space-space-backspace”字符對(duì)，然后將其中的某些字符對(duì)替換為“space-backspace-space”就得到一個(gè)變形的消息。目前使用的大多數(shù)雜湊函數(shù)其結(jié)構(gòu)都是迭代型的，如下圖所示。5.2.4迭代型雜湊函數(shù)的一般結(jié)構(gòu)圖5.4迭代型雜湊函數(shù)的一般結(jié)構(gòu)CV0=IV=n比特長的初值；CVi=f(CVi-1,Yi-1)1≤i≤L；H(M)=CVLCVi-1，稱為鏈接變量通常b>n，稱函數(shù)f為壓縮函數(shù)分析時(shí)需要先找出f的碰撞MD4是MD5雜湊算法的前身，由RonRivest于1990年10月作為RFC提出，1992年4月公布的MD4的改進(jìn)（RFC1320，1321）稱為MD5。5.3MD5雜湊算法MD5算法采用圖5.4描述的迭代型雜湊函數(shù)的一般結(jié)構(gòu)，算法的框圖如圖5.5所示。輸入：任意長的消息（圖中為K比特）分組：512比特輸出：128比特的消息摘要。5.3.1算法描述圖5.5MD5的算法框圖①對(duì)消息填充：對(duì)消息填充，使得其比特長在模512下為448，即填充后消息的長度為512的某一倍數(shù)減64，留出的64比特備第2步使用。步驟①是必需的，即使消息長度已滿足要求，仍需填充。例如，消息長為448比特，則需填充512比特，使其長度變?yōu)?60，因此填充的比特?cái)?shù)大于等于1而小于等于512。填充方式是:第1位為1，其后各位皆為0。處理過程有以下幾步：②附加消息的長度：用留出的64比特以little-endian方式來表示消息被填充前的長度。如果消息長度大于264，則以264為模數(shù)取模。消息的長度為512的倍數(shù)（設(shè)為L倍）消息分Y0，Y1，…，YL-1每一分組為16個(gè)32比特長的字消息中的總字?jǐn)?shù)為N=L×16消息按字表示為M[0,…,N-1]。Little-endian將最低有效字節(jié)存于低地址字節(jié)。相反的存儲(chǔ)方式稱為big-endian方式。③對(duì)MD緩沖區(qū)初始化：算法使用128比特長的緩沖區(qū)存儲(chǔ)中間結(jié)果和最終雜湊值。緩沖區(qū)表示為4個(gè)32比特長的寄存器(A，B，C，D)，每個(gè)寄存器都以littleendian方式存儲(chǔ)數(shù)據(jù)。其初值取為（以存儲(chǔ)方式）A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210實(shí)際上為67452301，EFCDAB89，98BADCFE，10325476。④以分組為單位對(duì)消息進(jìn)行處理：每一分組Yq(q=0,…,L-1)都經(jīng)一壓縮函數(shù)HMD5處理。HMD5是算法的核心，其中又有4輪處理過程，如圖所示。⑤輸出：消息的L個(gè)分組都被處理完后，最后一個(gè)HMD5的輸出即為產(chǎn)生的消息摘要。MD5的分組處理框圖CV0=IV;CVq+1=CVq+RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]MD=CVL處理過程總結(jié)如下： CV0=IV;CVq+1=CVq+RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]] MD=CVLIV:

緩沖區(qū)ABCD的初值Yq:

消息的第q個(gè)512比特長的分組L:消息經(jīng)過處理后的分組數(shù)CVq:消息的第q個(gè)分組時(shí)輸入的鏈接變量RFx:使用基本邏輯函數(shù)x的輪函數(shù)+:對(duì)應(yīng)字的模232加法MD:最終的雜湊值。5.3.2MD5的壓縮函數(shù)壓縮函數(shù)HMD5中有4輪處理過程，每輪又對(duì)緩沖區(qū)ABCD進(jìn)行16步迭代運(yùn)算，每一步的運(yùn)算形式:壓縮函數(shù)中的一步迭代示意圖a←b+CLSs(a+g(b,c,d)+X[k]+T[i])a、b、c、d:緩沖區(qū)的4個(gè)字，運(yùn)算后再右循環(huán)一個(gè)字，即得這一步迭代的輸出g:基本邏輯函數(shù)F、G、H、I之一CLSs:左循環(huán)移s位，s的取值由表5.2給出。T[i]:表T中的第i個(gè)字，+為模232加法。X[k]=M[q×16+k]:消息第q個(gè)分組中的第k個(gè)字（k=1,…,16）。4輪處理過程中，每輪以不同的次序使用16個(gè)字第1輪以字的初始次序使用。第2輪到第4輪分別對(duì)字的次序i做置換后得到一個(gè)新次序，然后以新次序使用16個(gè)字。3個(gè)置換分別為:

ρ2(i)=(1+5i)mod16 ρ3(i)=(5+3i)mod16 ρ4(i)=7imod164輪處理過程分別使用不同的基本邏輯函數(shù)F、G、H、I，輸入為3個(gè)32比特的字輸出是一個(gè)32比特的字運(yùn)算為逐比特的邏輯運(yùn)算，分別是邏輯與、邏輯或、邏輯非和異或運(yùn)算。輪數(shù)基本邏輯函數(shù)g(b,c,d)1234F(b,c,d)G(b,c,d)H(b,c,d)I(b,c,d)MD5的安全性安全雜湊算法(SecureHashAlgorithm,SHA)由美國NIST設(shè)計(jì)，于1993年作為聯(lián)邦信息處理標(biāo)準(zhǔn)公布。SHA是基于MD4的算法，其結(jié)構(gòu)與MD4非常類似。5.4安全雜湊算法算法的輸入：小于264比特長的任意消息，分為512比特長的分組。算法的輸出：160比特長的消息摘要。算法的框圖與MD5一樣，但雜湊值的長度和鏈接變量的長度為160比特。5.4.1算法描述160bit摘要KK<264bit160SHASHASHASHA160160160算法的處理過程有以下幾步：①對(duì)消息填充:與MD5的步驟①完全相同。②附加消息的長度:與MD5的步驟類似，不同以big-endian方式表示填充前消息的長度。③對(duì)MD緩沖區(qū)初始化:使用160比特長的緩沖區(qū)存儲(chǔ)中間結(jié)果和最終雜湊值。緩沖區(qū)可表示為5個(gè)32比特長的寄存器(A,B,C,D,E)，每個(gè)寄存器都以big-endian方式存儲(chǔ)數(shù)據(jù)。初始值分別為A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0。④以分組為單位對(duì)消息進(jìn)行處理：每一分組Yq都經(jīng)一壓縮函數(shù)處理，壓縮函數(shù)由4輪處理過程（如圖5.8所示）構(gòu)成，每一輪又由20步迭代組成。5.8SHA的分組處理框圖第4輪的輸出（即第80步迭代的輸出）再與第1輪的輸入CVq相加，以產(chǎn)生CVq+1，其中加法是緩沖區(qū)5個(gè)字中的每一個(gè)字與CVq中相應(yīng)的字模232相加。⑤輸出消息的L個(gè)分組都被處理完后，最后一個(gè)分組的輸出即為160比特的消息摘要。步驟③到步驟⑤的處理過程可總結(jié)如下：

CV0=IV; CVq+1=SUM32(CVq,ABCDEq); MD=CVLIV：緩沖區(qū)ABCDE的初值。ABCDEq：第q個(gè)消息分組經(jīng)最后一輪處理過程處理后的輸出L：是消息(包括填充位和長度字段)的分組數(shù)SUM32：是對(duì)應(yīng)字的模232加法MD：最終的摘要值。SHA的壓縮函數(shù)由4輪處理過程組成，每輪處理過程20步迭代運(yùn)算組成，每一步迭代運(yùn)算的形式為A，B，C，D，E：緩沖區(qū)的5個(gè)字t：迭代的步數(shù)（0≤t≤79）ft(B,C,D)：第t步迭代使用的基本邏輯函數(shù)CLSs：左循環(huán)移s位Wt：由當(dāng)前512比特長的分組導(dǎo)出的一個(gè)32比特長的字Kt：加法常量+：模232加法。5.4.2SHA的壓縮函數(shù)一步迭代示意圖基本邏輯函數(shù)的輸入為3個(gè)32比特的字，輸出是一個(gè)32比特的字。表中∧,∨,－,分別是與、或、非、異或4個(gè)邏輯運(yùn)算。定義函數(shù)名迭代的步數(shù)下面說明如何由當(dāng)前的輸入分組（512比特長）導(dǎo)出W0,W1,…,W15，W16,W17,…,W79）圖5.10SHA分組處理所需的80個(gè)字的產(chǎn)生過程由于SHA與MD5都是由MD4演化而來，所以兩個(gè)算法極為相似。1.抗窮搜索攻擊的強(qiáng)度由于SHA和MD5的消息摘要長度分別為160和128，SHA抗擊窮搜索攻擊的