第十講密碼Hash函數1謝謝您的觀賞2019-8-29第十講密碼Hash函數1謝謝您的觀賞2019-8-29本講提要分類與架構基本構造修改發(fā)現碼(MDC)

消息認證碼(MAC)2謝謝您的觀賞2019-8-29本講提要分類與架構2謝謝您的觀賞2019-8-291分類與架構

定義1Hash函數(在不嚴格意義下)是至少滿足下列兩條性質的函數h。(1)壓縮：h將任意有限比特長度的輸入x映射為固定長度為n的輸出h(x)。(2)容易計算：給定h和輸入x，容易計算出h(x)。1.1基本性質與定義3謝謝您的觀賞2019-8-291分類與架構定義1Hash函數(在不嚴格意義下)1分類與架構(續(xù))

密碼中使用的Hash函數主要為兩類：

(1)修改發(fā)現碼(MDC)：不帶密鑰的Hash函數，主要用于提供消息完整性檢查。

(2)消息認證碼(MAC)：帶密鑰的Hash函數，主要用于認證消息源及保證其完整性。1.1基本性質與定義(續(xù))4謝謝您的觀賞2019-8-291分類與架構(續(xù))密碼中使用的Hash函數主要為兩類1分類與架構(續(xù))

定義2

修改發(fā)現碼(MDC)是Hash函數h，對于輸入x和x以及相應輸出y和y滿足如下性質：(1)原像不可逆：對于幾乎所有的Hash輸出不可能計算出其的Hash輸入。也就是，在不知道輸入的情況下給定任意一個輸出y，找到任意一個輸入x滿足h(x)=y是計算不可能的。(2)二次原像不可逆：對于任何一個給定的輸入x，找到另一個輸入xx，且滿足h(x)=h(x)，在計算上不可能。(3)抵抗碰撞：找到兩個不同的輸入x和x，滿足h(x)=h(x)，在計算上不可能(注意：這里兩個輸入可以自由選擇)。1.1基本性質與定義(續(xù))5謝謝您的觀賞2019-8-291分類與架構(續(xù))定義2修改發(fā)現碼(MDC)是H1分類與架構(續(xù))定義1和定義2的說明：(1)“容易”和“計算上不可能”都留下來沒有準確定義?！叭菀住币馕吨囗検綍r間和空間；“計算上不可能”意味著超越多項式的計算需求。(2)一般認為，抗原像單向；抗二次原像抗弱碰撞；抵抗碰撞抗強碰撞。1.1基本性質與定義(續(xù))6謝謝您的觀賞2019-8-291分類與架構(續(xù))定義1和定義2的說明：1.1基本性1分類與架構(續(xù))

定義3單向Hash函數(OWHF)是滿足定義1以及定義2中(1)和(2)的Hash函數。定義4抗碰撞Hash函數(CRHF)是滿足定義1以及定義2中(2)和(3)的Hash函數。

#雖然幾乎所有實際使用的CRHF都有抗原像攻擊的性質，但由于技術原因定義4并未給出。1.1基本性質與定義(續(xù))7謝謝您的觀賞2019-8-291分類與架構(續(xù))定義3單向Hash函數(OWH

1.1基本性質與定義(續(xù))

攻擊者攻擊MDC的主要目標如下：(1)給定Hash值y，發(fā)現原像x滿足y=h(x)；或者給定對(x，h(x))發(fā)現另一個像x滿足h(x)=h(x)。(2)發(fā)現兩個Hash輸入x和x滿足h(x)=h(x)。1分類與架構(續(xù))8謝謝您的觀賞2019-8-291.1基本性質與定義(續(xù))1分類與架構(續(xù))8謝謝您的1分類與架構(續(xù))

定義5

消息認證碼(MAC)算法是帶有密鑰k的函數族hk，其具有如下性質：(1)易于計算：對于任何已知函數hk，給定值k和輸入x，值hk(x)容易計算出來。這個值被稱做MAC值或MAC。1.1基本性質與定義(續(xù))9謝謝您的觀賞2019-8-291分類與架構(續(xù))定義5消息認證碼(MAC)算法是(2)壓縮：函數hk可以將任意有限比特長度的輸入x映射為固定n比特長度的位串。進一步，給出函數族h的算法描述，對于任何一個固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質：(3)計算抵抗：給定0個或多個消息-MAC值對(xi，hk(xi))，找到任意消息-MAC值對(x，hk(x))滿足xxi在計算上不可能(當然也包括某些i滿足hk(x)=hk(xi)的可能性)。1分類與架構(續(xù))1.1基本性質與定義(續(xù))10謝謝您的觀賞2019-8-29(2)壓縮：函數hk可以將任意有限比特長度的輸入x

評述.

(1)計算抵抗隱含了密鑰k是不可恢復的性質，但密鑰不可恢復并不意味著計算抵抗。

(2)定義5并沒有顯示攻擊者知道密鑰k的情況下是否要抗原像和抗碰撞，但對不知道密鑰k的情況下，應該滿足這些性質。1分類與架構(續(xù))1.1基本性質與定義(續(xù))11謝謝您的觀賞2019-8-29評述.1分類與架構(續(xù))1.1基本性質與定義(續(xù))攻擊者攻擊MAC的目標為：在不知道密鑰k的情況下，給定一個或多個消息-MAC值對(xi，hk(xi))，計算出一個或多個新消息-MAC值對(x，hk(x))，滿足xxi。

攻擊者潛在的能力有：(1)已知消息攻擊。(2)選擇消息攻擊：掌握一個或多個由攻擊者選擇的xi對應的消息-MAC值對(xi，hk(xi))。(3)適應性選擇消息攻擊：允許根據前面的詢問結果連續(xù)做出消息選擇。1分類與架構(續(xù))1.1基本性質與定義(續(xù))12謝謝您的觀賞2019-8-29攻擊者攻擊MAC的目標為：1分類與架構(續(xù))1.1在實際中造成的破壞程度取決于攻擊者控制消息x并偽造其MAC值的程度，依此可以做如下分類。(1)選擇性偽造攻擊：攻擊者可以根據選擇，控制消息的內容偽造出消息-MAC值對(或者至少為部分控制消息內容)。(2)存在性偽造攻擊：攻擊者雖然可以偽造出消息-MAC值對，但無法控制消息的內容。1分類與架構(續(xù))1.1基本性質與定義(續(xù))13謝謝您的觀賞2019-8-29在實際中造成的破壞程度取決于攻擊者控制消息x并偽與特定性質聯系在一起的是開銷，如CRHF一般比OWHF要難于構造，且其Hash值應是OWHF的比特長度的兩倍。因此，考慮具體應用十分重要。假如可由不可信方控制Hash函數的輸入的準確內容，則可能需要CRHF，如數字簽名。假如只是可信方的單方應用，使用OWHF就足夠了，如口令表的應用。1分類與架構(續(xù))1.2特定應用需要的性質14謝謝您的觀賞2019-8-29與特定性質聯系在一起的是開銷，如CRHF一般比OW

事實1

Hash函數的抗碰撞隱含抗二次原像。

事實2Hash函數抗碰撞不能保證抗原像。

事實3

Hash函數抗二次原像不能保證抗原像，抗原像也不能保證抗二次原像。事實4

hk是MAC，hk符合計算抵抗性質。若攻擊者不知道密鑰k，hk抗選擇消息攻擊，則應該抗二次原像、抗碰撞、抗原像。1分類與架構(續(xù))1.3性質之間的關系15謝謝您的觀賞2019-8-29事實1Hash函數的抗碰撞隱含抗二次原像。1MDC的其他應用

(1)知識確認。

(2)密鑰產生。

(3)偽隨機數發(fā)生。

#這些MDC可能需要滿足一些超過之前定義的附加性質。1分類與架構(續(xù))1.4其他應用16謝謝您的觀賞2019-8-29MDC的其他應用1分類與架構(續(xù))1.4其他應用12基本構造2.1迭代結構的一般模型高級視圖輸出可選輸出變換迭代壓縮函數任意長度輸入固定長度輸出17謝謝您的觀賞2019-8-292基本構造2.1迭代結構的一般模型高級視圖輸出可選輸出變2基本構造(續(xù))2.1迭代結構的一般模型(續(xù))詳細視圖fHash函數h初始輸入x預處理附加長度分組附加填充比特迭代處理壓縮函數fHiHi-1Htgxi輸出h(x)=g(Ht)格式化輸入x=x1x2…xt18謝謝您的觀賞2019-8-292基本構造(續(xù))2.1迭代結構的一般模型(續(xù))詳細視圖f2基本構造(續(xù))2.1迭代結構的一般模型(續(xù))Hi表示第i步的部分結果，輸入為x=x1x2…xt的迭代函數的一般模型為

H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=g(Ht)。

Hi-1表示第i-1步和第i步之間的n比特鏈變量，H0是預定義的開始值或初始值(IV)。最后一步用可選的輸出變換g將n比特鏈變量映射為m比特結果g(Ht)，通常g(Ht)=Ht。19謝謝您的觀賞2019-8-292基本構造(續(xù))2.1迭代結構的一般模型(續(xù))H2基本構造(續(xù))2.2實際安全需要的輸出比特大小

事實5

一個n比特輸出的不帶密鑰Hash函數是理想安全的，如果：(1)給定一個Hash輸出，產生一個原像和二次原像需要大約2n次操作規(guī)模；(2)產生一個碰撞需要大約2n/2次操作規(guī)模。

事實6

假定n比特輸出的Hash函數，280次操作在計算上不可能，則有：(1)OWHF要求n80；(2)CRHF要求n160；(3)MAC對大部分環(huán)境要求n64以及64-80比特的密鑰，如果有特別控制，可小到n=32或64。20謝謝您的觀賞2019-8-292基本構造(續(xù))2.2實際安全需要的輸出比特大小事在分組密碼基礎上建立Hash函數的主要動機是：如果系統(tǒng)已經擁有了非常有效的分組密碼，那么以分組密碼作為實現Hash函數的主要部件，將既可以提供Hash函數的功能，又能使額外開銷最小。3無密鑰密碼Hash函數：MDC3.1基于分組密碼的Hash函數：MDC-221謝謝您的觀賞2019-8-29在分組密碼基礎上建立Hash函數的主要動機是：如果系統(tǒng)3.1基于分組密碼的Hash函數：MDC-2(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))22謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數：MDC-2(續(xù))3無3.1基于分組密碼的Hash函數：MDC-2(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))23謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數：MDC-2(續(xù))3無Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i3無密鑰密碼Hash函數：MDC(續(xù))3.1基于分組密碼的Hash函數：MDC-2(續(xù))24謝謝您的觀賞2019-8-29Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iC3.2定制的Hash函數：SHA-1

安全Hash算法(SHA)是美國國家標準技術研究所(NIST)設計，并于1993年作為聯邦信息處理標準(FIPS180)發(fā)布的。后做修改，于1995年再次公布修訂后的SHA，通常稱為SHA-1。3無密鑰密碼Hash函數：MDC(續(xù))25謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1安全Hash算法3.2定制的Hash函數：SHA-1(續(xù))

SHA-1算法的輸入為小于264比特長的任意消息，輸出為160比特的消息摘要，算法處理過程如下圖。YL-13無密鑰密碼Hash函數：MDC(續(xù))HSHAIV(160比特)Y0(512比特)HSHAY1CV1(160比特)…HSHACVqYq…CV2HSHACVL-1消息摘要26謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))

SHA-1消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。這形成了長度為512比特的一系列分組Y0，Y1，…，YL-1。需要產生Hash值的消息100…0消息長度K填充長度1-512比特K比特L×512比特3無密鑰密碼Hash函數：MDC(續(xù))27謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))

(2)初始化。SHA-1使用160比特的緩沖區(qū)存儲中間和最終Hash值，可用5個32比特寄存器A，B，C，D，E表示，初始值為(十六進制)A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。3無密鑰密碼Hash函數：MDC(續(xù))28謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))(2)初3.2定制的Hash函數：SHA-1(續(xù))

(3)處理。每個分組Yq經過壓縮函數處理，壓縮函數由4輪處理過程構成。每一輪又由20步迭代組成。4輪處理結構一樣，但基本邏輯函數不同，分別為f1，f2，f3，f4。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D、E的當前值，輸出仍放在對應緩沖區(qū)。每一輪處理有一個加法常量Ki，其中t表示迭代步數，0≤t≤79。第4輪的輸出與第1輪的輸入CVq依5個緩沖區(qū)對應進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是160比特消息摘要。3無密鑰密碼Hash函數：MDC(續(xù))29謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))(3)3.2定制的Hash函數：SHA-1(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))CVq160位Yq512位f1,K1,W[0…19]20步BADCEf2,K2,W[20…39]20步BADCEf3,K3,W[40…59]20步BADCEf4,K4,W[60…79]20步BADCE++++CVq+1160位+30謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))3無密鑰密碼H3.2定制的Hash函數：SHA-1(續(xù))

SHA-1的壓縮函數各個20步迭代運算的每一步運算可以表示為

A，B，C，D，E←(E+fi(B，C，D)+CLS5(A)+Wt+Ki)，A，CLS30(B)，C，D

其中，t是迭代的步數(0≤t≤79)，+是模232相加，fi是i(1≤i≤4)輪的基本邏輯函數，CLSs表示循環(huán)左移s位，Wt是當前512比特分組導出的一個32比特字。3無密鑰密碼Hash函數：MDC(續(xù))31謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))SHA-1的壓縮函數(續(xù))基本邏輯函數f1，f2，f3，f4分別定義為：f1(X，Y，Z)=(XY)(XZ)f2(X，Y，Z)=f4(X，Y，Z)=XYZf3(X，Y，Z)=(XY)(XZ)(YZ)其中，是與，是或，是異或，是非。3無密鑰密碼Hash函數：MDC(續(xù))32謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-1的壓縮3.2定制的Hash函數：SHA-1(續(xù))

SHA-1的壓縮函數(續(xù))

加法常量(十六進制)

K1=5a827999，對應0≤t≤19

K2=6ed9eba1，對應20≤t≤39

K3=8f1bbcdc

，對應40≤t≤59

K4=

ca62c1d6，對應60≤t≤79

字擴展前16個字W0，W1，…，W15，直接由輸入得到。其余由公式Wt=CLS1(Wt-3Wt-8Wt-14Wt-16)依次得到。3無密鑰密碼Hash函數：MDC(續(xù))33謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-3.3定制的Hash函數：MD5

MD5是1992年由Rivest提出的無密鑰Hash函數。MD5是MD4(1990年提出)的增強版本。MD5對任意長度的消息產生128比特的Hash值。MD4在280次壓縮函數計算下已經找到了碰撞，因此，不在被推薦用做抗碰撞的Hash函數。近年來，MD5也發(fā)現了一些弱點。3無密鑰密碼Hash函數：MDC(續(xù))34謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5MD5是1992年由3.3定制的Hash函數：MD5(續(xù))MD5算法的輸入為任意比特長的消息，輸出為128比特的消息摘要，算法處理過程如下圖。3無密鑰密碼Hash函數：MDC(續(xù))HMD5IV(128比特)Y0(512比特)HMD5Y1CV1(128比特)…HMD5CVqYq…CV2HMD5CVL-1YL-1消息摘要35謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5算法的3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))MD5消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。如果消息長度大于264，則以264取模。這形成了長度為512比特的一系列分組Y0，Y1，…

，YL-1。需要產生Hash值的消息100…0消息長度Kmod264填充長度1-512比特K比特L×512比特=N×32比特36謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))

(2)初始化。MD5使用128比特的緩沖區(qū)存儲中間和最終Hash值，可用4個32比特寄存器A，B，C，D表示，初始值為(十六進制)A=01234567，B=89abcdef，C=fedcba98，D=76543210。3無密鑰密碼Hash函數：MDC(續(xù))37謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))(2)初始化3.3定制的Hash函數：MD5(續(xù))

(3)處理。每個分組Yq經過壓縮函數處理，壓縮函數由4輪處理過程構成。每一輪又由16步迭代組成。4輪處理結構一樣，但基本邏輯函數不同，分別為F，G，H，I

。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D的當前值，輸出仍放在對應緩沖區(qū)。每一輪處理有一個常量T[i]，其中i表示迭代步數，1≤i≤64。第4輪的輸出與第1輪的輸入CVq依4個緩沖區(qū)對應進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是128比特消息摘要。3無密鑰密碼Hash函數：MDC(續(xù))38謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))(3)處理。3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))CVq128位Yq512位F,T[1…16],X[i],16步BADCBADCBADCBADC++++CVq+1128位G,T[17…32],X[p2(i)],16步H,T[33…48],X[p3(i)],16步I,T[49…64],X[p4(i)],16步39謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))MD5的壓縮函數一步迭代壓縮函數如下圖。ACBD+++<<<s+RACBDX[k]T[i]

R表示函數F、G、H、I中的一個，它們依次在連續(xù)16步中使用<<<s表示循環(huán)左移s比特X[k]表示在第q個長度為512比特分組中的第k個32比特分組T[i]表示常數中的第i個字

+表示模232相加40謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))

MD5的壓縮函數(續(xù))邏輯函數F，G，H，I分別定義為：

F(X，Y，Z)=(XY)(XZ)G(X，Y，Z)=(XY)(YZ)H(X，Y，Z)=XYZI(X，Y，Z)=Y(XZ)

T[i]定義為：

T[i]=232|sin(i)|，i=1,2,…,64，這里，i是弧度。

3無密鑰密碼Hash函數：MDC(續(xù))41謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數：MD5(續(xù))

MD5的壓縮函數(續(xù))

MD5壓縮的每個512比特消息分組要經過4輪處理，第1輪以其32比特連續(xù)分組的初始順序使用，而第2至4輪處理按如下三個置換計算出的順序使用：

p2(i)=(1+5i)mod16p3(i)=(5+3i)mod16

p4(i)=7imod16，這里i=0,1,…,15。3無密鑰密碼Hash函數：MDC(續(xù))42謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數：MD5(續(xù))

MD5的壓縮函數(續(xù))

4輪中每一步的循環(huán)左移位數見下表。3無密鑰密碼Hash函數：MDC(續(xù))43謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5的壓縮函4.1基于分組密碼的Hash函數：CBC的MAC4帶密鑰密碼Hash函數：MAC44謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數：CBC的MAC4帶密鑰4.1基于分組密碼的Hash函數：CBC的MAC(續(xù))M10EkH1M2EkH2…Ht-1MtEkHtEkDk'Ht可選4帶密鑰密碼Hash函數：MAC(續(xù))45謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數：CBC的MAC(續(xù))M1

4.1基于分組密碼的Hash函數：CBC的MAC(續(xù))

評論.(1)

很明顯，在生成CBC-MAC值(由運行CBC模式的分組密碼構造的MAC)的計算中包括了不可求逆的數據壓縮(本質上，CBC-MAC是整個消息的“短摘要”)，因此CBC-MAC是一個單向變換。所有的分組密碼加密算法的混合變換性質為這個單向函數變換增加了一個雜湊特點(也就是說，將MAC分布到MAC空間與分組密碼加密算法將密文分布到密文空間同樣均勻)。4帶密鑰密碼Hash函數：MAC(續(xù))46謝謝您的觀賞2019-8-294.1基于分組密碼的Hash函數：CBC的MAC((2)如果考慮窮舉密鑰搜索攻擊，可以考慮最后僅輸出n比特中的m比特作為MAC數值。

(3)單分組消息x1，x2的兩個文本消息-MAC對(x1,H1)和(x2,H2)。對一個2分組的第三個消息x1||z請求MAC值M，產生文本消息-MAC對(x1||z,M)。由此，知新2分組的消息X=x2||(H1zH2)的MAC值也是M。(4)可選處理減少了窮舉密鑰搜索攻擊的威脅，阻止了選擇文本攻擊的存在性偽造，由于沒有在整個過程中使用三重加密，所以不會特別影響效率。4帶密鑰密碼Hash函數：MAC(續(xù))4.1基于分組密碼的Hash函數：CBC的MAC(續(xù))47謝謝您的觀賞2019-8-29(2)如果考慮窮舉密鑰搜索攻擊，可以考慮最后僅輸出

由MDC算法構造MAC算法的一個建議是簡單地把秘密密鑰k作為MDC的輸入的一部分。但因為MDC和MAC的定義并不完全一致，因此這種設計必須細致分析。

(1)消息為x=x1x2…xt和使用迭代函數f的迭代MDCh：定義H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=Ht。(1.1)如果建議的MAC對x的值是M=h(k||x)，則攻擊者可以計算M=h(k||x||y)=f(M||y)作為x||y的MAC值。(1.2)如果建議的MAC對x的值是M=h(x||k)輸出是n比特，則產生x和x滿足M=h(x||k)=h(x||k)的復雜度為O(2n/2)，n是h函數的輸出比特長度。4帶密鑰密碼Hash函數：MAC(續(xù))4.2由MDC構造的MAC48謝謝您的觀賞2019-8-29由MDC算法構造MAC算法的一個建議是簡單地把秘密密鑰

(2)對密鑰為k和MDC為h，可按如下方式計算消息x的MAC值hk(x)=h(k||p||x||k)。其中p將用于將k填充為一個分組長度，從而保證內部至少進行兩次分組計算。

(3)對密鑰為k和MDC為h，另一種計算消息x的MAC值的方式是hk(x)=h(k||p1||h(k||p2||x))。其中p1，p2用于將k填充為一個分組長度。4帶密鑰密碼Hash函數：MAC(續(xù))4.2由MDC構造的MAC(續(xù))49謝謝您的觀賞2019-8-29(2)對密鑰為k和MDC為h，可按如下方式計算消息4帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC：MD5-MAC50謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC4帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC：MD5-MAC(續(xù))51謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC4帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC：MD5-MAC(續(xù))52謝謝您的觀賞2019-8-294帶密鑰密碼Hash函數：MAC(續(xù))4.3定制的MAC謝謝!53謝謝您的觀賞2019-8-29謝謝!53謝謝您的觀賞2019-8-29第十講密碼Hash函數54謝謝您的觀賞2019-8-29第十講密碼Hash函數1謝謝您的觀賞2019-8-29本講提要分類與架構基本構造修改發(fā)現碼(MDC)

消息認證碼(MAC)55謝謝您的觀賞2019-8-29本講提要分類與架構2謝謝您的觀賞2019-8-291分類與架構

定義1Hash函數(在不嚴格意義下)是至少滿足下列兩條性質的函數h。(1)壓縮：h將任意有限比特長度的輸入x映射為固定長度為n的輸出h(x)。(2)容易計算：給定h和輸入x，容易計算出h(x)。1.1基本性質與定義56謝謝您的觀賞2019-8-291分類與架構定義1Hash函數(在不嚴格意義下)1分類與架構(續(xù))

密碼中使用的Hash函數主要為兩類：

(1)修改發(fā)現碼(MDC)：不帶密鑰的Hash函數，主要用于提供消息完整性檢查。

(2)消息認證碼(MAC)：帶密鑰的Hash函數，主要用于認證消息源及保證其完整性。1.1基本性質與定義(續(xù))57謝謝您的觀賞2019-8-291分類與架構(續(xù))密碼中使用的Hash函數主要為兩類1分類與架構(續(xù))

定義2

修改發(fā)現碼(MDC)是Hash函數h，對于輸入x和x以及相應輸出y和y滿足如下性質：(1)原像不可逆：對于幾乎所有的Hash輸出不可能計算出其的Hash輸入。也就是，在不知道輸入的情況下給定任意一個輸出y，找到任意一個輸入x滿足h(x)=y是計算不可能的。(2)二次原像不可逆：對于任何一個給定的輸入x，找到另一個輸入xx，且滿足h(x)=h(x)，在計算上不可能。(3)抵抗碰撞：找到兩個不同的輸入x和x，滿足h(x)=h(x)，在計算上不可能(注意：這里兩個輸入可以自由選擇)。1.1基本性質與定義(續(xù))58謝謝您的觀賞2019-8-291分類與架構(續(xù))定義2修改發(fā)現碼(MDC)是H1分類與架構(續(xù))定義1和定義2的說明：(1)“容易”和“計算上不可能”都留下來沒有準確定義?！叭菀住币馕吨囗検綍r間和空間；“計算上不可能”意味著超越多項式的計算需求。(2)一般認為，抗原像單向；抗二次原像抗弱碰撞；抵抗碰撞抗強碰撞。1.1基本性質與定義(續(xù))59謝謝您的觀賞2019-8-291分類與架構(續(xù))定義1和定義2的說明：1.1基本性1分類與架構(續(xù))

定義3單向Hash函數(OWHF)是滿足定義1以及定義2中(1)和(2)的Hash函數。定義4抗碰撞Hash函數(CRHF)是滿足定義1以及定義2中(2)和(3)的Hash函數。

#雖然幾乎所有實際使用的CRHF都有抗原像攻擊的性質，但由于技術原因定義4并未給出。1.1基本性質與定義(續(xù))60謝謝您的觀賞2019-8-291分類與架構(續(xù))定義3單向Hash函數(OWH

1.1基本性質與定義(續(xù))

攻擊者攻擊MDC的主要目標如下：(1)給定Hash值y，發(fā)現原像x滿足y=h(x)；或者給定對(x，h(x))發(fā)現另一個像x滿足h(x)=h(x)。(2)發(fā)現兩個Hash輸入x和x滿足h(x)=h(x)。1分類與架構(續(xù))61謝謝您的觀賞2019-8-291.1基本性質與定義(續(xù))1分類與架構(續(xù))8謝謝您的1分類與架構(續(xù))

定義5

消息認證碼(MAC)算法是帶有密鑰k的函數族hk，其具有如下性質：(1)易于計算：對于任何已知函數hk，給定值k和輸入x，值hk(x)容易計算出來。這個值被稱做MAC值或MAC。1.1基本性質與定義(續(xù))62謝謝您的觀賞2019-8-291分類與架構(續(xù))定義5消息認證碼(MAC)算法是(2)壓縮：函數hk可以將任意有限比特長度的輸入x映射為固定n比特長度的位串。進一步，給出函數族h的算法描述，對于任何一個固定符合要求的密鑰值k(攻擊者不知其值)，需要滿足如下性質：(3)計算抵抗：給定0個或多個消息-MAC值對(xi，hk(xi))，找到任意消息-MAC值對(x，hk(x))滿足xxi在計算上不可能(當然也包括某些i滿足hk(x)=hk(xi)的可能性)。1分類與架構(續(xù))1.1基本性質與定義(續(xù))63謝謝您的觀賞2019-8-29(2)壓縮：函數hk可以將任意有限比特長度的輸入x

評述.

(1)計算抵抗隱含了密鑰k是不可恢復的性質，但密鑰不可恢復并不意味著計算抵抗。

(2)定義5并沒有顯示攻擊者知道密鑰k的情況下是否要抗原像和抗碰撞，但對不知道密鑰k的情況下，應該滿足這些性質。1分類與架構(續(xù))1.1基本性質與定義(續(xù))64謝謝您的觀賞2019-8-29評述.1分類與架構(續(xù))1.1基本性質與定義(續(xù))攻擊者攻擊MAC的目標為：在不知道密鑰k的情況下，給定一個或多個消息-MAC值對(xi，hk(xi))，計算出一個或多個新消息-MAC值對(x，hk(x))，滿足xxi。

攻擊者潛在的能力有：(1)已知消息攻擊。(2)選擇消息攻擊：掌握一個或多個由攻擊者選擇的xi對應的消息-MAC值對(xi，hk(xi))。(3)適應性選擇消息攻擊：允許根據前面的詢問結果連續(xù)做出消息選擇。1分類與架構(續(xù))1.1基本性質與定義(續(xù))65謝謝您的觀賞2019-8-29攻擊者攻擊MAC的目標為：1分類與架構(續(xù))1.1在實際中造成的破壞程度取決于攻擊者控制消息x并偽造其MAC值的程度，依此可以做如下分類。(1)選擇性偽造攻擊：攻擊者可以根據選擇，控制消息的內容偽造出消息-MAC值對(或者至少為部分控制消息內容)。(2)存在性偽造攻擊：攻擊者雖然可以偽造出消息-MAC值對，但無法控制消息的內容。1分類與架構(續(xù))1.1基本性質與定義(續(xù))66謝謝您的觀賞2019-8-29在實際中造成的破壞程度取決于攻擊者控制消息x并偽與特定性質聯系在一起的是開銷，如CRHF一般比OWHF要難于構造，且其Hash值應是OWHF的比特長度的兩倍。因此，考慮具體應用十分重要。假如可由不可信方控制Hash函數的輸入的準確內容，則可能需要CRHF，如數字簽名。假如只是可信方的單方應用，使用OWHF就足夠了，如口令表的應用。1分類與架構(續(xù))1.2特定應用需要的性質67謝謝您的觀賞2019-8-29與特定性質聯系在一起的是開銷，如CRHF一般比OW

事實1

Hash函數的抗碰撞隱含抗二次原像。

事實2Hash函數抗碰撞不能保證抗原像。

事實3

Hash函數抗二次原像不能保證抗原像，抗原像也不能保證抗二次原像。事實4

hk是MAC，hk符合計算抵抗性質。若攻擊者不知道密鑰k，hk抗選擇消息攻擊，則應該抗二次原像、抗碰撞、抗原像。1分類與架構(續(xù))1.3性質之間的關系68謝謝您的觀賞2019-8-29事實1Hash函數的抗碰撞隱含抗二次原像。1MDC的其他應用

(1)知識確認。

(2)密鑰產生。

(3)偽隨機數發(fā)生。

#這些MDC可能需要滿足一些超過之前定義的附加性質。1分類與架構(續(xù))1.4其他應用69謝謝您的觀賞2019-8-29MDC的其他應用1分類與架構(續(xù))1.4其他應用12基本構造2.1迭代結構的一般模型高級視圖輸出可選輸出變換迭代壓縮函數任意長度輸入固定長度輸出70謝謝您的觀賞2019-8-292基本構造2.1迭代結構的一般模型高級視圖輸出可選輸出變2基本構造(續(xù))2.1迭代結構的一般模型(續(xù))詳細視圖fHash函數h初始輸入x預處理附加長度分組附加填充比特迭代處理壓縮函數fHiHi-1Htgxi輸出h(x)=g(Ht)格式化輸入x=x1x2…xt71謝謝您的觀賞2019-8-292基本構造(續(xù))2.1迭代結構的一般模型(續(xù))詳細視圖f2基本構造(續(xù))2.1迭代結構的一般模型(續(xù))Hi表示第i步的部分結果，輸入為x=x1x2…xt的迭代函數的一般模型為

H0=IV；Hi=f(Hi-1,xi)，1it；h(x)=g(Ht)。

Hi-1表示第i-1步和第i步之間的n比特鏈變量，H0是預定義的開始值或初始值(IV)。最后一步用可選的輸出變換g將n比特鏈變量映射為m比特結果g(Ht)，通常g(Ht)=Ht。72謝謝您的觀賞2019-8-292基本構造(續(xù))2.1迭代結構的一般模型(續(xù))H2基本構造(續(xù))2.2實際安全需要的輸出比特大小

事實5

一個n比特輸出的不帶密鑰Hash函數是理想安全的，如果：(1)給定一個Hash輸出，產生一個原像和二次原像需要大約2n次操作規(guī)模；(2)產生一個碰撞需要大約2n/2次操作規(guī)模。

事實6

假定n比特輸出的Hash函數，280次操作在計算上不可能，則有：(1)OWHF要求n80；(2)CRHF要求n160；(3)MAC對大部分環(huán)境要求n64以及64-80比特的密鑰，如果有特別控制，可小到n=32或64。73謝謝您的觀賞2019-8-292基本構造(續(xù))2.2實際安全需要的輸出比特大小事在分組密碼基礎上建立Hash函數的主要動機是：如果系統(tǒng)已經擁有了非常有效的分組密碼，那么以分組密碼作為實現Hash函數的主要部件，將既可以提供Hash函數的功能，又能使額外開銷最小。3無密鑰密碼Hash函數：MDC3.1基于分組密碼的Hash函數：MDC-274謝謝您的觀賞2019-8-29在分組密碼基礎上建立Hash函數的主要動機是：如果系統(tǒng)3.1基于分組密碼的Hash函數：MDC-2(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))75謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數：MDC-2(續(xù))3無3.1基于分組密碼的Hash函數：MDC-2(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))76謝謝您的觀賞2019-8-293.1基于分組密碼的Hash函數：MDC-2(續(xù))3無Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iCR'iCLiCR'iCL'iCRiHiH'i3無密鑰密碼Hash函數：MDC(續(xù))3.1基于分組密碼的Hash函數：MDC-2(續(xù))77謝謝您的觀賞2019-8-29Eg(Hi-1)Eg'(Hi-1)MiCLiCRiCL'iC3.2定制的Hash函數：SHA-1

安全Hash算法(SHA)是美國國家標準技術研究所(NIST)設計，并于1993年作為聯邦信息處理標準(FIPS180)發(fā)布的。后做修改，于1995年再次公布修訂后的SHA，通常稱為SHA-1。3無密鑰密碼Hash函數：MDC(續(xù))78謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1安全Hash算法3.2定制的Hash函數：SHA-1(續(xù))

SHA-1算法的輸入為小于264比特長的任意消息，輸出為160比特的消息摘要，算法處理過程如下圖。YL-13無密鑰密碼Hash函數：MDC(續(xù))HSHAIV(160比特)Y0(512比特)HSHAY1CV1(160比特)…HSHACVqYq…CV2HSHACVL-1消息摘要79謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))

SHA-1消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。這形成了長度為512比特的一系列分組Y0，Y1，…，YL-1。需要產生Hash值的消息100…0消息長度K填充長度1-512比特K比特L×512比特3無密鑰密碼Hash函數：MDC(續(xù))80謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))

(2)初始化。SHA-1使用160比特的緩沖區(qū)存儲中間和最終Hash值，可用5個32比特寄存器A，B，C，D，E表示，初始值為(十六進制)A=67452301，B=efcdab89，C=98badcfe，D=10325476，E=c3d2e1f0。3無密鑰密碼Hash函數：MDC(續(xù))81謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))(2)初3.2定制的Hash函數：SHA-1(續(xù))

(3)處理。每個分組Yq經過壓縮函數處理，壓縮函數由4輪處理過程構成。每一輪又由20步迭代組成。4輪處理結構一樣，但基本邏輯函數不同，分別為f1，f2，f3，f4。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D、E的當前值，輸出仍放在對應緩沖區(qū)。每一輪處理有一個加法常量Ki，其中t表示迭代步數，0≤t≤79。第4輪的輸出與第1輪的輸入CVq依5個緩沖區(qū)對應進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是160比特消息摘要。3無密鑰密碼Hash函數：MDC(續(xù))82謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))(3)3.2定制的Hash函數：SHA-1(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))CVq160位Yq512位f1,K1,W[0…19]20步BADCEf2,K2,W[20…39]20步BADCEf3,K3,W[40…59]20步BADCEf4,K4,W[60…79]20步BADCE++++CVq+1160位+83謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))3無密鑰密碼H3.2定制的Hash函數：SHA-1(續(xù))

SHA-1的壓縮函數各個20步迭代運算的每一步運算可以表示為

A，B，C，D，E←(E+fi(B，C，D)+CLS5(A)+Wt+Ki)，A，CLS30(B)，C，D

其中，t是迭代的步數(0≤t≤79)，+是模232相加，fi是i(1≤i≤4)輪的基本邏輯函數，CLSs表示循環(huán)左移s位，Wt是當前512比特分組導出的一個32比特字。3無密鑰密碼Hash函數：MDC(續(xù))84謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-13.2定制的Hash函數：SHA-1(續(xù))SHA-1的壓縮函數(續(xù))基本邏輯函數f1，f2，f3，f4分別定義為：f1(X，Y，Z)=(XY)(XZ)f2(X，Y，Z)=f4(X，Y，Z)=XYZf3(X，Y，Z)=(XY)(XZ)(YZ)其中，是與，是或，是異或，是非。3無密鑰密碼Hash函數：MDC(續(xù))85謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-1的壓縮3.2定制的Hash函數：SHA-1(續(xù))

SHA-1的壓縮函數(續(xù))

加法常量(十六進制)

K1=5a827999，對應0≤t≤19

K2=6ed9eba1，對應20≤t≤39

K3=8f1bbcdc

，對應40≤t≤59

K4=

ca62c1d6，對應60≤t≤79

字擴展前16個字W0，W1，…，W15，直接由輸入得到。其余由公式Wt=CLS1(Wt-3Wt-8Wt-14Wt-16)依次得到。3無密鑰密碼Hash函數：MDC(續(xù))86謝謝您的觀賞2019-8-293.2定制的Hash函數：SHA-1(續(xù))SHA-3.3定制的Hash函數：MD5

MD5是1992年由Rivest提出的無密鑰Hash函數。MD5是MD4(1990年提出)的增強版本。MD5對任意長度的消息產生128比特的Hash值。MD4在280次壓縮函數計算下已經找到了碰撞，因此，不在被推薦用做抗碰撞的Hash函數。近年來，MD5也發(fā)現了一些弱點。3無密鑰密碼Hash函數：MDC(續(xù))87謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5MD5是1992年由3.3定制的Hash函數：MD5(續(xù))MD5算法的輸入為任意比特長的消息，輸出為128比特的消息摘要，算法處理過程如下圖。3無密鑰密碼Hash函數：MDC(續(xù))HMD5IV(128比特)Y0(512比特)HMD5Y1CV1(128比特)…HMD5CVqYq…CV2HMD5CVL-1YL-1消息摘要88謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5算法的3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))MD5消息處理過程：

(1)消息填充。填充使得消息的比特長度為512比特的某個倍數減64，即使原始消息已滿足要求，仍要填充。這樣填充的比特數在1到512。填充方式是第一位為1其他位是0。最后64比特位用來填充消息被填充前的長度。如果消息長度大于264，則以264取模。這形成了長度為512比特的一系列分組Y0，Y1，…

，YL-1。需要產生Hash值的消息100…0消息長度Kmod264填充長度1-512比特K比特L×512比特=N×32比特89謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))

(2)初始化。MD5使用128比特的緩沖區(qū)存儲中間和最終Hash值，可用4個32比特寄存器A，B，C，D表示，初始值為(十六進制)A=01234567，B=89abcdef，C=fedcba98，D=76543210。3無密鑰密碼Hash函數：MDC(續(xù))90謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))(2)初始化3.3定制的Hash函數：MD5(續(xù))

(3)處理。每個分組Yq經過壓縮函數處理，壓縮函數由4輪處理過程構成。每一輪又由16步迭代組成。4輪處理結構一樣，但基本邏輯函數不同，分別為F，G，H，I

。每輪處理消息分組Yq和緩沖區(qū)A、B、C、D的當前值，輸出仍放在對應緩沖區(qū)。每一輪處理有一個常量T[i]，其中i表示迭代步數，1≤i≤64。第4輪的輸出與第1輪的輸入CVq依4個緩沖區(qū)對應進行模232相加得到CVq+1。消息的L個分組都按上述計算處理完成后，最后一個分組的輸出就是128比特消息摘要。3無密鑰密碼Hash函數：MDC(續(xù))91謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))(3)處理。3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))CVq128位Yq512位F,T[1…16],X[i],16步BADCBADCBADCBADC++++CVq+1128位G,T[17…32],X[p2(i)],16步H,T[33…48],X[p3(i)],16步I,T[49…64],X[p4(i)],16步92謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Hash函數：MDC(續(xù))MD5的壓縮函數一步迭代壓縮函數如下圖。ACBD+++<<<s+RACBDX[k]T[i]

R表示函數F、G、H、I中的一個，它們依次在連續(xù)16步中使用<<<s表示循環(huán)左移s比特X[k]表示在第q個長度為512比特分組中的第k個32比特分組T[i]表示常數中的第i個字

+表示模232相加93謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))3無密鑰密碼Has3.3定制的Hash函數：MD5(續(xù))

MD5的壓縮函數(續(xù))邏輯函數F，G，H，I分別定義為：

F(X，Y，Z)=(XY)(XZ)G(X，Y，Z)=(XY)(YZ)H(X，Y，Z)=XYZI(X，Y，Z)=Y(XZ)

T[i]定義為：

T[i]=232|sin(i)|，i=1,2,…,64，這里，i是弧度。

3無密鑰密碼Hash函數：MDC(續(xù))94謝謝您的觀賞2019-8-293.3定制的Hash函數：MD5(續(xù))MD5的壓縮函3.3定制的Hash函數：