網(wǎng)絡(luò)安全-10-密碼學(xué)Hash函數(shù)

單純的加解密算法無(wú)法保證抵抗下述攻擊偽裝內(nèi)容修改順序修改計(jì)時(shí)修改發(fā)送方否認(rèn)接收方否認(rèn)消息認(rèn)證碼數(shù)字簽名不屬于機(jī)密性范疇,屬于數(shù)據(jù)完整性范疇

Chapter11

密碼學(xué)Hash函數(shù)《計(jì)算機(jī)與網(wǎng)絡(luò)安全》

哈希函數(shù)（雜湊函數(shù)）（1）Hash編碼；（2）Hash函數(shù)；（3）散列編碼：（4）散列函數(shù)；（5）單向壓縮函數(shù)。哈希函數(shù)在公鑰密碼的內(nèi)容中，已經(jīng)介紹了“單向函數(shù)”的概念。而哈希函數(shù)是一類特殊的單向函數(shù)。設(shè)數(shù)據(jù)文件是任意長(zhǎng)度的比特串x

。在密碼應(yīng)用中，希望有這樣的函數(shù)y=H(x)，滿足：（1）將x壓縮成為固定長(zhǎng)度的比特串y。（2）不同的x一定要生成不同的y。（一般情況）（3）由y的值無(wú)法倒算x的值。2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院5Hash函數(shù)濃縮任意長(zhǎng)的消息M到一個(gè)固定長(zhǎng)度的取值h=H(M)

通常假設(shè)hash函數(shù)是公開的且不使用密鑰（MAC使用密鑰）Hash函數(shù)用戶檢測(cè)對(duì)消息的改變密碼學(xué)Hash函數(shù)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院7哈希函數(shù)的應(yīng)用消息認(rèn)證數(shù)字簽名Hash函數(shù)用于消息認(rèn)證2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院8Hash函數(shù)用于消息認(rèn)證2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院9Hash函數(shù)用于數(shù)字簽名2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院10Hash函數(shù)的其他用途給明文增加結(jié)構(gòu)特征以保護(hù)密文從口令衍生密鑰挑戰(zhàn)-應(yīng)答認(rèn)證協(xié)議中用來產(chǎn)生隨機(jī)數(shù)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院11密碼學(xué)Hash函數(shù)的基本性質(zhì)單向性：對(duì)于預(yù)先給定的Hash值找不到對(duì)應(yīng)的數(shù)據(jù)塊抗碰撞性：找不到不同的數(shù)據(jù)塊對(duì)應(yīng)相同的Hash值2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院12Hash函數(shù)h=H(x)的安全性要求函數(shù)參數(shù)輸入：可以任意長(zhǎng)度輸出：必須固定長(zhǎng)度n比特，一般n=128、160bits函數(shù)特性效率：給定x，計(jì)算H(x)＝h是容易的單向性：給定h，要找x使H(x)＝h是困難的弱抗碰撞特性： 對(duì)于給定的y，找x，使H(x)＝H(y)是困難的強(qiáng)抗碰撞特性（生日攻擊）：找(x1,x2)，x1≠x2，H(x1)=H(x2)是困難的偽隨機(jī)性：輸出滿足偽隨機(jī)測(cè)試標(biāo)準(zhǔn)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院13找碰撞：生日攻擊最多嘗試2n＋1個(gè)報(bào)文，必有至少一對(duì)碰撞問：平均嘗試多少個(gè)報(bào)文，可以以1/2的概率找到一對(duì)碰撞？

~2n/2類比問題（生日問題）最多找365+1個(gè)人，則必有至少兩個(gè)人生日相同問：平均找多少個(gè)人，能以1/2的概率找到兩人生日相同？

23如果采用64-bit的Hash碼，以一半概率找到碰撞的代價(jià)的數(shù)量級(jí)是2322023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院14生日悖論2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院15Hash安全特性之間的關(guān)系抗原像攻擊抗弱碰撞攻擊抗強(qiáng)碰撞攻擊2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院16Hash函數(shù)設(shè)計(jì)考慮奇偶校驗(yàn)異或XOR（或者累加）只能檢出奇數(shù)個(gè)比特錯(cuò)誤CRC常用在幀校驗(yàn)仍有很高的比率不能檢出傳輸比特錯(cuò)誤*不能滿足單向性和抗碰撞性復(fù)雜的密碼學(xué)用散列函數(shù)MD2/MD5SHA/SHA12023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院17基于分組密碼的散列函數(shù)的缺點(diǎn)不利于隨機(jī)化因?yàn)榧用苁强赡娴?，分組密碼存在規(guī)則性分組密碼通常很慢分組密碼分組長(zhǎng)度小于散列值長(zhǎng)度通常64位或128位vs.128/160/256/384/5122023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院19Hash算法Hash函數(shù)和分組密碼的發(fā)展變化具有相似性窮舉攻擊能力的增強(qiáng)算法的不斷改進(jìn)分組密碼：從DES到AESHash算法:從MD4、MD5到SHA-1、RIPEMD-160、SHA-512、Whirlpool2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院20§12.1MD5消息摘要算法由RonaldRivest設(shè)計(jì)MD2(1989),MD4(1990),MD5(1991)

產(chǎn)生128-bit的hash值直到現(xiàn)在仍是被廣泛使用的hash算法最近已受到窮舉攻擊和密碼分析攻擊作為互聯(lián)網(wǎng)的RFC1321標(biāo)準(zhǔn)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院21MD5概覽增加填充位。使得填充后的消息長(zhǎng)度比512的某整數(shù)倍少64位（即長(zhǎng)度＝448mod512，64位用于存放消息的長(zhǎng)度mod264的結(jié)果）填充長(zhǎng)度（填充前消息的長(zhǎng)度為K位，將mod264的結(jié)果填充到第一步的最后，最低有效位在前。）初始化MD緩沖區(qū)(A,B,C,D):4個(gè)字共128-bit，每字32bit.A=67452301B=EFCDAB89C=98BADCFED=10325476以16個(gè)字（512bits）為分組處理消息用4輪（64次迭代）以16位操作對(duì)消息分組和緩沖區(qū)進(jìn)行處理把輸出與緩沖輸入相加作為新的緩沖值

把最后的緩沖值作為hash輸出值（128比特）2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院22MD5處理過程CV0=IVCVq+1=SUM32[CVq,RFI(Yq,RFH(Yq,RFG(Yq,RFF(Yq,CVq))))]MD=CVL-1其中：IV=第三步定義的緩沖區(qū)ABCD的初值Yq=消息的第q個(gè)512位分組L=消息分組的個(gè)數(shù)（包括填充位和長(zhǎng)度域）CVq=處理消息的第q個(gè)分組時(shí)所使用的鏈接變量RFx=使用基本邏輯函數(shù)x的輪函數(shù)MD=消息摘要SUM32=對(duì)輸入字分別執(zhí)行模232加法2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院23MD5Overview2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院232023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院242023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院25MD5的強(qiáng)度MD5的hash值依賴于消息的所有比特位Rivest聲稱它對(duì)于已知攻擊安全性足夠好:Berson92采用差分的方法對(duì)單輪的攻擊Boer&Bosselaers93說明了如何找到碰撞Dobbertin96提出的攻擊對(duì)MD5最具威脅，可使MD5壓縮函數(shù)產(chǎn)生碰撞。結(jié)論是MD5似乎不久就會(huì)有風(fēng)險(xiǎn)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院26§12.2安全Hash算法(SHA-1)SHA由NIST和NSA在1993年提出,修訂版于1995年發(fā)布，稱作SHA-1作為美國(guó)DSA數(shù)字簽名方案的標(biāo)準(zhǔn)FIPS180-11995,InternetRFC3174注意：算法是SHA,標(biāo)準(zhǔn)稱為SHS產(chǎn)生160-bithash值

現(xiàn)在作為建議的hash算法

基于MD4的設(shè)計(jì)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院27SHA概覽增加填充位

填充長(zhǎng)度初始化5個(gè)字(160-bit)緩沖區(qū)(A,B,C,D,E)為(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)以16個(gè)字（512-bit）為分組處理消息:將分組的16個(gè)字?jǐn)U充為80個(gè)字用于壓縮過程中4輪，每輪20步迭代把輸出和輸入相加以形成新的緩沖區(qū)取值將最后緩沖區(qū)的值作為hash值輸出2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院282023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院29SHA-1壓縮函數(shù)2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院30SHA-1versesMD5窮舉攻擊更加困難（SHA-1:160,MD5:128）

對(duì)已知攻擊不存在風(fēng)險(xiǎn)(與MD4/5相比)（SHA-1的設(shè)計(jì)原則尚未公開）速度比MD5慢(80步，64步)兩者設(shè)計(jì)都很簡(jiǎn)單緊湊2023/2/2西安電子科技大學(xué)計(jì)算機(jī)學(xué)院31SHA的修改NIST1981年已經(jīng)發(fā)布了FIPS180-2除SHA-1外，新增加了3個(gè)hash算法：

SHA-256,SHA-384,SHA-512，消息摘要的長(zhǎng)度分別為：256