消息認(rèn)證與雜湊算法

消息認(rèn)證與雜湊算法第一頁，共六十六頁，編輯于2023年，星期日抗擊被動攻擊：加密抗擊主動攻擊：消息認(rèn)證消息認(rèn)證是一個過程，用以驗證接收消息的真實性和完整性，同時還用于驗證消息的順序性和時間性。第二頁，共六十六頁，編輯于2023年，星期日消息認(rèn)證機制需要產(chǎn)生認(rèn)證符。認(rèn)證符：用于認(rèn)證消息的數(shù)值。認(rèn)證符的產(chǎn)生方法：消息認(rèn)證碼MAC（messageauthenticationcode）和雜湊函數(shù)（hashfunction）兩大類。第三頁，共六十六頁，編輯于2023年，星期日消息認(rèn)證碼:指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的、用作認(rèn)證符的、固定長度的數(shù)值,或稱為密碼校驗和。此時需要通信雙方A和B共享一密鑰K。5.1消息認(rèn)證碼

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

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

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

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

的簽字，將此簽字連同

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

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

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

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

CV0=IV; CVq+1=SUM32(CVq,ABCDEq); MD=CVLIV：緩沖區(qū)ABCDE的初值。ABCDEq：第q個消息分組經(jīng)最后一輪處理過程處理后的輸出L：是消息(包括填充位和長度字段)的分組數(shù)SUM32：是對應(yīng)字的模232加法MD：最終的摘要值。第五十六頁，共六十六頁，編輯于2023年，星期日SHA的壓縮函數(shù)由4輪處理過程組成，每輪處理過程20步迭代運算組成，每一步迭代運算的形式為A，B，C，D，E：緩沖區(qū)的5個字t：迭代的步數(shù)（0≤t≤79）ft(B,C,D)：第t步迭代使用的基本邏輯函數(shù)CLSs：左循環(huán)移s位Wt：由當(dāng)前512比特長的分組導(dǎo)出的一個32比特長的字Kt：加法常量+：模232加法。5.4.2SHA的壓縮函數(shù)第五十七頁，共六十六頁，編輯于2023年，星期日一步迭代示意圖第五十八頁，共六十六頁，編輯于2023年，星期日基本邏輯函數(shù)的輸入為3個32比特的字，輸出是