第5章消息認證087課件

第5章

消息認證7/23/20231主要內(nèi)容消息認證基本概念消息加密認證消息認證碼

hash函數(shù)7/23/20232概念認證(Authentication)：即鑒別、確認，它是證實某事是否名副其實，或是否有效的一個過程。認證與加密的區(qū)別：加密用以確保數(shù)據(jù)的保密性，阻止對手的被動攻擊，如截取、竊聽。認證用以確保報文發(fā)送者和接收者的真實性以及報文的完整性，阻止對手的主動攻擊，如冒充、篡改、重播等。認證往往是應(yīng)用系統(tǒng)中安全保護的第一道防線，極為重要。7/23/20233基本思想通過驗證稱謂者(人或事)的一個或多個參數(shù)的真實性和有效性，來達到驗證稱謂者是否名副其實的目的。常用的參數(shù)有：口令、標識符、密鑰、信物、智能卡、指紋、視網(wǎng)紋等。利用人的生理特征參數(shù)進行認證的安全性高，但技術(shù)要求也高，至今尚未普及。目前廣泛應(yīng)用的還是基于密碼的認證技術(shù)。7/23/20234沒有消息認證的通信系統(tǒng)是極為危險的7/23/20235消息認證(MessageAuthentication)消息認證用于抗擊主動攻擊驗證接收消息的真實性和完整性真實性的確是由所聲稱的實體發(fā)過來的完整性未被篡改、插入和刪除驗證消息的順序性和時間性（未重排、重放和延遲）7/23/20236需求泄密：將消息透露給沒有合法秘密鑰的任何人或程序。傳輸分析：分析通信雙方的通信模式，如連接頻率，時間等偽裝：攻擊者產(chǎn)生一條消息并聲稱來自某合法實體內(nèi)容修改：對消息進行插入、刪除、轉(zhuǎn)化、修改順序修改：對消息順序進行插入、刪除、重新排序計時修改：對消息的延時和重放發(fā)送方否認接受方否認對付1、2可用加密；對付3、4、5、6可用消息認證；對付7、8可用數(shù)字簽名7/23/20237消息認證的基本概念消息認證：驗證所收到的消息確定是來自真正的發(fā)送方且未被修改過。認證符：一個用來認證消息的值。由消息的發(fā)送方產(chǎn)生認證符，并傳遞給接收方。認證函數(shù)：產(chǎn)生認證符的函數(shù)，認證函數(shù)實際上代表了一種產(chǎn)生認證符的方法?？商峁┱J證功能的認證碼的函數(shù)可分為三類：1、消息加密2、消息認證碼3、Hash函數(shù)7/23/202381消息加密---在對稱加密體制下由于攻擊者不知道密鑰K，他也就不知道如何改變密文中的信息位才能在明文中產(chǎn)生預(yù)期的改變。接收方可以根據(jù)解密后的明文是否具有合理的語法結(jié)構(gòu)來進行消息認證。但有時發(fā)送的明文本身并沒有明顯的語法結(jié)構(gòu)或特征，例如二進制文件，因此很難確定解密后的消息就是明文本身。MEKEK(M)DKM7/23/20239根據(jù)明文M和公開的函數(shù)F產(chǎn)生FCS，即錯誤檢測碼，或幀校驗序列，校驗和。把M和FCS合在一起加密，并傳輸。接收端把密文解密，得到M。根據(jù)得到的M，按照F計算FCS，并與接收到的FCS比較是否相等。MFFMFCS比較EKDKMFCS內(nèi)部錯誤控制7/23/202310攻擊者可以構(gòu)造具有正確錯誤控制碼的消息，雖然攻擊者不知道解密后的明文，但可以造成混淆并破壞通信。MFFCSEKDKM外部錯誤控制F比較7/23/2023111消息加密---在公鑰加密體制下由于大家都知道B的公鑰，所以這種方式不提供認證，只提供加密。MEKUbEKUb(M)DKRbMI.普通加密AB7/23/2023121消息加密---在公鑰加密體制下由于只有A有用于產(chǎn)生EKRa(M)的密鑰，所以此方法提供認證。由于大家都有KUa

，所以此方法不提供加密。MEKRaEKRa(M)DKUaMII.認證和簽名AB7/23/2023131消息加密---在公鑰加密體制下提供認證和加密。一次通信中要執(zhí)行四次復(fù)雜的公鑰算法。MEKRaEKRa(M)DKUaMIII.加密認證和簽名ABEKUbEKUb(EKRa(M))DKRbEKRa(M)7/23/2023142消息認證碼(MAC)MessageAuthenticaionCode消息認證碼是消息和密鑰的公開函數(shù)，它產(chǎn)生定長的值，以該值作為認證符。利用密鑰和消息生成一個固定長度的短數(shù)據(jù)塊，并將其附加在消息之后。通信雙方共享密鑰K7/23/2023152

消息認證碼用于認證A和B共享密鑰KA計算MAC=Ck(M),M和MAC一起發(fā)送到BB對收到的M，計算MAC，比較兩個MAC是否相同。MCMACKC比較KMAC如果兩個MAC相等，則：接收方可以相信消息未被修改，因為如果攻擊者改變了消息，由于不知道k，無法生成正確的MAC。接收方可以相信消息的確來自確定的發(fā)送方。因為其他人不能生成和原始消息相應(yīng)的MAC。7/23/202316MAC函數(shù)與加密函數(shù)的區(qū)別MAC函數(shù)與加密函數(shù)類似，都需要明文、密鑰和算法的參與。但MAC算法不要求可逆性，而加密算法必須是可逆的。例如：使用100比特的消息和10比特的MAC，那么總共有2100個不同的消息，但僅有210個不同的MAC。也就是說，平均每290個消息使用的MAC是相同的。因此，認證函數(shù)比加密函數(shù)更不易被攻破，因為即便攻破也無法驗證其正確性。關(guān)鍵就在于加密函數(shù)是一對一的，而認證函數(shù)是多對一的。7/23/202317消息認證碼的基本用途只提供消息認證，不提供保密性。（見前）提供消息認證和保密性：M||CK1CMCK1(M)K1比較EK2DK2ABA和B共享K1和K2K1：用于生成MACK2：用于加密與明文有關(guān)的認證7/23/202318消息認證碼的基本用途提供消息認證和保密性：ABA和B共享K1和K2K1：用于生成MACK2：用于加密與密文有關(guān)的認證M||CK1CK1比較EK2DK27/23/202319對MAC的攻擊—攻擊密鑰已知消息M1和MAC算法C，以及MAC1=

Ck1(M1)

，現(xiàn)要破解k1。密鑰為k個bit，MAC為n個bit。當k>n：可能的密鑰個數(shù)為2k?？赡艿腗AC個數(shù)為2n個。所以許多不同的密鑰(約2k-n個)，計算出來的MAC都等于MAC1。這些密鑰中哪一個是正確的密鑰不得而知。這時需要新的M-MAC對來測試這2k-n個密鑰，于是有如下的重復(fù)攻擊：7/23/202320重復(fù)攻擊Step1:給定M1和MAC1=

Ck1(M1)

對所有2k個密鑰，判斷MACi

=

C

ki

(M1)

匹配數(shù)約為：2k-nStep2:給定M2和MAC2=

Ck2(M1)對所有2k-n個密鑰，判斷MACi

=

C

ki

(M2)匹配數(shù)約為：2k-2n平均來講，若k=x*n，則需x次循環(huán)才能找到正確的密鑰。所以，用窮舉法攻破MAC比攻破加密算法要困難得多。7/23/202321對MAC的攻擊—攻擊算法考慮下面的算法：

消息M=(X1‖X2‖…‖Xm)是由64比特長的分組Xi(i=1,…,m)鏈接而成

MAC算法是：加密算法是DES。因此，密鑰長為56比特。如果敵手得到M‖CK(M)，那么敵手使用窮搜索攻擊尋找K將需做256次加密。很困難!但攻擊者可以改變M的內(nèi)容，卻使MAC正確。方法如下：7/23/202322用Y1替換X1，Y2替換X2，…，Ym替換Xm

，其中Y1

，Y2

，…，Ym

是攻擊者編造的假消息。且

Ym=Y1Y2…Ym-1Δ(M)，

當接收者收到這個消息：M’=(Y1‖Y2‖…‖Ym)

則Δ(M’)=Y1Y2…Ym

=

Δ(M)所以：CK(M)=CK(M’)通過了驗證，攻擊得逞。7/23/202323MAC函數(shù)應(yīng)具有的性質(zhì)若攻擊者已知M和CK(M)，則他構(gòu)造滿足：

CK(M)=CK(M’)的消息M’在計算上不可行CK(M)應(yīng)是均勻分布的，即對于隨機消息M和M’，

CK(M)=CK(M’)的概率是2-n，n是MAC的位數(shù)7/23/202324基于DES的消息認證碼使用最廣泛的MAC算法之一：數(shù)據(jù)認證算法過程：把需要認證的數(shù)據(jù)分成連續(xù)的64位的分組。若最后一個分組不是64位，則填0利用DES加密算法E和密鑰K，計算認證碼。7/23/202325數(shù)據(jù)認證算法似乎可以滿足前面提出的要求。DACM-bits(16to64bits)7/23/202326為什么不直接使用加密而使用分離的消息認證碼？保密性與真實性是兩個不同的概念根本上,信息加密提供的是保密性而非真實性加密代價大(公鑰算法代價更大)鑒別函數(shù)與保密函數(shù)的分離能提供功能上的靈活性某些信息只需要真實性,不需要保密性廣播的信息難以使用加密(信息量大)網(wǎng)絡(luò)管理信息等只需要真實性政府/權(quán)威部門的公告7/23/2023273Hash函數(shù)(雜湊函數(shù)、散列函數(shù))Hash的特點：與消息認證碼一樣，hash函數(shù)的輸入是可變的消息M，輸出是固定大小的hash碼H(M)，或稱消息摘要(MessageDigest)

、hash值。與消息認證碼不同的是，hash碼的產(chǎn)生過程中并不使用密鑰。Hash碼是所有消息的函數(shù)，改變消息的任何一位或多位，都會導(dǎo)致hash碼的改變。Hash算法通常是公開的。又稱為：哈希函數(shù)、數(shù)字指紋（Digitalfingerprint)、壓縮（Compression)函數(shù)、緊縮（Contraction）函數(shù)、數(shù)據(jù)鑒別碼DAC（Dataauthenticationcode）、篡改檢驗碼MDC(Manipulationdetectioncode)7/23/202328h=H(M)

假定兩次輸入同樣的數(shù)據(jù)，那么散列函數(shù)應(yīng)該能夠生成相同的散列值。輸入數(shù)據(jù)中的一位發(fā)生了變化，會導(dǎo)致生成的散列值完全不一樣。散列函數(shù)有個非常重要的特性為單向性，也就是從M計算h容易，而從h計算M不可能。

7/23/202329散列函數(shù)H必須滿足以下幾個性質(zhì)

H對于任何大小的數(shù)據(jù)分組，都能產(chǎn)生定長的輸出。對于任何給定的M，H(M)要相對易于計算。單向性：對于任何給定的hash值h，計算出M在計算上不可行。弱無碰撞性：對任何給定的M1，尋找M2，使H(M1)=H(M2)在計算上不可行。強無碰撞性：尋找任何的（M1，M2），使H(M1)=H(M2)在計算上不可行。7/23/2023307/23/2023317/23/2023327/23/2023337/23/202334Hash與MAC的區(qū)別MAC需要對全部數(shù)據(jù)進行加密MAC速度慢Hash是一種直接產(chǎn)生鑒別碼的方法Hash可用于數(shù)字簽名7/23/202335常用Hash算法7/23/202336網(wǎng)絡(luò)工程08級迭代型hash函數(shù)的一般結(jié)構(gòu)目前使用的大多數(shù)雜湊函數(shù)如MD5、SHA，其結(jié)構(gòu)都是迭代型的，如下圖所示。其中函數(shù)的輸入M被分為L個分組Y0,Y1,…,YL-1，每一個分組的長度為b比特，最后一個分組的長度不夠的話，需對其做填充。最后一個分組中還包括整個函數(shù)輸入的長度值，這樣一來，將使得敵手的攻擊更為困難，即敵手若想成功地產(chǎn)生假冒的消息，就必須保證假冒消息的雜湊值與原消息的雜湊值相同，而且假冒消息的長度也要與原消息的長度相等。7/23/202337迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個分組Y0,Y1,…,YL-1b:明文分組長度n:輸出hash長度CV：各級輸出，最后一個輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計的關(guān)鍵7/23/202338算法中重復(fù)使用一壓縮函數(shù)f（注意，有些書將Hash函數(shù)也稱為壓縮函數(shù)，在此用壓縮函數(shù)表示Hash函數(shù)中的一個特定部分），f的輸入有兩項，一項是上一輪（第i-1輪）輸出的n比特值CVi-1，稱為鏈接變量，另一項是算法在本輪（第i輪）的b比特輸入分組Yi。f的輸出為n比特值CVi，CVi又作為下一輪的輸入。算法開始時還需對鏈接變量指定一個初值IV，最后一輪輸出的鏈接變量CVL即為最終產(chǎn)生的Hash值。通常有b>n，因此稱函數(shù)f為壓縮函數(shù)。算法可表達如下：

CV0=IV=n比特長的初值；

CVi=f(CVi-1,Yi-1)；1≤i≤L；

H(M)=CVL7/23/202339迭代型hash函數(shù)這種結(jié)構(gòu)的hash函數(shù)已被證明是合理的，如果采用其他結(jié)構(gòu)，不一定安全。設(shè)計新的hash函數(shù)只是改進這種結(jié)構(gòu)，或者增加hash碼長。算法的核心技術(shù)是設(shè)計無碰撞的壓縮函數(shù)f，而敵手對算法的攻擊重點是f的內(nèi)部結(jié)構(gòu)，由于f和分組密碼一樣是由若干輪處理過程組成，所以對f的攻擊需通過對各輪之間的位模式的分析來進行，分析過程常常需要先找出f的碰撞。由于f是壓縮函數(shù)，其碰撞是不可避免的，因此在設(shè)計f時就應(yīng)保證找出其碰撞在計算上是不可行的。7/23/202340MD5hash算法

MD5HashAlgorithm

MD4是MD5雜湊算法的前身，由RonRivest于1990年10月作為RFC提出，1992年4月公布的MD4的改進（RFC1320，1321）稱為MD5。7/23/202341網(wǎng)絡(luò)工程08級MD5的算法框圖輸入消息可任意長，壓縮后輸出為128bits。7/23/202342算法步驟(1)－分組填充

消息100…064bit消息長度填充圖樣L×512bitKbit如果消息長度大于264，則取其對264的模。執(zhí)行完后，消息的長度為512的倍數(shù)（設(shè)為L倍），則可將消息表示為分組長為512的一系列分組Y0，Y1，…，YL-1，而每一分組又可表示為16個32比特長的字，這樣消息中的總字數(shù)為N=L×16，因此消息又可按字表示為M[0,…,N-1]。7/23/202343算法步驟(2)－緩沖區(qū)初始化

hash函數(shù)的中間結(jié)果和最終結(jié)果保存于128位的緩沖區(qū)中，緩沖區(qū)用32位的寄存器表示?？捎?個32bits字表示：A,B,C,D。初始存數(shù)以十六進制表示為A=01234567B=89ABCDEFC=FEDCBA98D=765432107/23/202344算法步驟(3)-HMD5運算以分組為單位對消息進行處理,每一分組Yq(q=0,…,L-1)都經(jīng)一壓縮函數(shù)HMD5處理。HMD5是算法的核心，其中又有4輪處理過程。HMD5的4輪處理過程結(jié)構(gòu)一樣，但所用的邏輯函數(shù)不同，分別表示為F、G、H、I。每輪的輸入為當前處理的消息分組Yq和緩沖區(qū)的當前值A(chǔ)、B、C、D，輸出仍放在緩沖區(qū)中以產(chǎn)生新的A、B、C、D。每輪又要進行16步迭代運算，4輪共需64步完成。第四輪的輸出與第一輪的輸入相加得到最后的輸出。7/23/2023457/23/202346壓縮函數(shù)中的一步迭代7/23/202347基本邏輯函數(shù)定義

輪基本函數(shù)gg(b,c,d)fFF(b,c,d)(b^c)V(bˉ^d)fGG(b,c,d)(b^d)V(c^dˉ)fHH(b,c,d)b?c?dfII(b,c,d)c?(bV

dˉ)7/23/202348X[k]當前分組的第k個32位的字。第1輪x[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]x[8]x[9]x[10]x[11]x[12]x[13]x[14]x[15]第2輪x[1]x[6]x[11]x[0]x[5]x[10]x[15]x[4]x[9]x[14]x[3]x[8]x[13]x[2]x[7]x[12]第3輪x[5]x[8]x[11]x[14]x[1]x[4]x[7]x[10]x[13]x[0]x[3]x[6]x[9]x[12]x[15]x[2]第4輪x[0]x[7]x[14]x[5]x[12]x[3]x[10]x[1]x[8]x[15]x[6]x[13]x[4]x[11]x[2]x[9]7/23/202349T[i]T[1,…,64]為64個元素表，分四組參與不同輪的計算。T[i]為232×abs(Sin(i))的整數(shù)部分，i是弧度。T[i]可用32bit二元數(shù)表示，T是32bit隨機數(shù)源。7/23/202350T[1]=d76aa478T[17]=f61e2562T[33]=fffa3942T[49]=f4292244T[2]=e8c7b756T[18]=c040b340T[34]=8771f681T[50]=432aff97T[3]=242070dbT[19]=265e5a51T[35]=6d9d6122T[51]=ab9423a7T[4]=c1bdceeeT[20]=e9b6c7aaT[36]=fde5380cT[52]=fc93a039T[5]=f57c0fafT[21]=d62f105dT[37]=a4beea44T[53]=655b59c3T[6]=4787c62aT[22]=02441453T[38]=4bdecfa9T[54]=8f0ccc92T[7]=a8304613T[23]=d8a1e681T[39]=f6bb4b60T[55]=ffeff47dT[8]=fd469501T[24]=e7d3fbc8T[40]=bebfbc70T[56]=85845dd1T[9]=698098d8T[25]=21e1cde6T[41]=289b7ec6T[57]=6fa87e4fT[10]=8b44f7afT[26]=c33707d6T[42]=eaa127faT[58]=fe2ce6e0T[11]=ffff5bb1T[27]=f4d50d87T[43]=d4ef3085T[59]=a3014314T[12]=895cd7beT[28]=455a14edT[44]=04881d05T[60]=4e0811a1T[13]=6b901122T[29]=a9e3e905T[45]=d9d4d039T[61]=f7537e82T[14]=fd987193T[30]=fcefa3f8T[46]=e6db99e5T[62]=bd3af235T[15]=a679438eT[31]=676f02d9T[47]=1fa27cf8T[63]=2ad7d2bbT[16]=49b40821T[32]=8d2a4c8aT[48]=c4ac5665T[63]=eb86d3917/23/202351CLSs

：循環(huán)左移s位第一輪：7、12、17、22第二輪：5、9、14、20第三輪：4、11、16、23第四輪：6、10、15、217/23/202352MD-5的安全性MD-5的輸出為128-bit，若采用純強力攻擊尋找一個消息具有給定Hash值的計算困難性為2128，用每秒可試驗1000000

000個消息的計算機需時1.07×1022年。采用生日攻擊法，找出具有相同雜湊值的兩個消息需執(zhí)行264次運算。7/23/202353SHA算法SecureHashAlgorithm7/23/202354網(wǎng)絡(luò)工程08級算法簡介美國標準與技術(shù)研究所NIST設(shè)計1993年成為聯(lián)邦信息處理標準(FIPSPUB180)基于MD4算法，與之非常類似。輸入為小于264比特長的任意消息分組512bit長輸出160bit7/23/202355迭代型hash函數(shù)的一般結(jié)構(gòu)fffY0Y1YL-1bbbnnnnnIV=CV0CV1CVL-1CVL明文M被分為L個分組Y0,Y1,…,YL-1b:明文分組長度n:輸出hash長度CV：各級輸出，最后一個輸出值是hash值無碰撞壓縮函數(shù)f是設(shè)計的關(guān)鍵7/23/202356算法描述消息填充：與MD5完全相同附加消息長度：64bit長度緩沖區(qū)初始化A＝67452301B＝EFCDAB89C＝98BADCFBD＝10325476E＝C3D2E1F07/23/202357分組處理模232加7/23/202358SHA-1壓縮函數(shù)（單步）7/23/202359ft----基本邏輯函數(shù)7/23/202360CLS5：32位的變量循環(huán)左移5位。CLS30：32位的變量循環(huán)左移30位。7/23/202361Wt---從當前512位輸入分組導(dǎo)出的32位字前16個值（即W0,W1,…,W15）直接取為輸入分組的16個相應(yīng)的字，其余值（即W16,W17,…,W79）取為7/23/202362Kt---加法常量步驟十六進制0≤t≤19Kt=5A82799920≤t≤39Kt=6ED9EBA140≤t≤59Kt=8F1BBCDC60≤t≤79Kt=CA62C1D67/23/202363SHA與MD5的比較抗窮舉搜索能力尋找指定hash值，SHA：O(2160)，MD5：O(2128)生日攻擊：SHA：O(280)，MD5：O(264)抗密碼分析攻擊的強度SHA似乎高于MD5速度SHA較MD5慢簡捷與緊致性描述都比較簡單，都不需要大的程序和代換表7/23/202364其它hash算法MD4MD4使用三輪運算，每輪16步；MD5使用四輪運算，每輪16步。MD4的第一輪沒有使用加法常量，第二輪運算中每步迭代使用的加法常量相同，第三輪運算中每步迭代使用的加法常量相同，但不同于第二輪使用的加法常量；MD5的64部使用的加法常量T[i]均不同。MD4使用三個基本邏輯函數(shù)，MD5使用四個。MD5中每步迭代的結(jié)果都與前一步的結(jié)果相加，MD4則沒有。MD5比MD4更復(fù)雜，所以其執(zhí)行速度也更慢，Rivest認為增加復(fù)雜性可以增加安全性。7/23/202365RIPEMD-160歐共體RIPE項目組研制。輸入可以是任意長的報文，輸出160位摘要。對輸入按512位分組。以分組為單位處理。算法的核心是具有十輪運算的模塊，十輪運算分成兩組，每組五輪，每輪16步迭代。7/23/202366對Hash函數(shù)的攻擊對一個hash算法的攻擊可分三個級別：預(yù)映射攻擊（PreimageAttack）：給定Hash值h，找到其所對應(yīng)的明文M，使得Hash(M)=h，這種攻擊是最徹底的，如果一個hash算法被人找出預(yù)映射，那這種算法是不能使用的。次預(yù)映射攻擊（SecondPreimageAttack）：給定明文M1，找到另一明文M2（M1≠M2），使得hash(M1)=hash(M2)，這種攻擊其實就是要尋找一個