密碼學基密碼學 在線

第四章Hash函數(shù)Hash函數(shù)的定義Hash函數(shù)的安全性迭代Hash函數(shù)數(shù)據(jù)完整性回顧信息安全的三個要點3

保密性3

完整性3

可用性加密算法解決了保密性問題，能否解決完整性問題？3

考慮通信數(shù)據(jù)傳送錯誤或被人為篡改的情況如何解決完整性問題？3

Hash函數(shù)(散列函數(shù))Hash函數(shù)一般定義3

Hash函數(shù)H(M)作用于一任意長度的消息M，它返回一固定長度(通常超過128位)的散列值h：h＝H(M)3

有時也稱“摘要函數(shù)”、“散列函數(shù)”或“雜湊函數(shù)”3

h也被稱為消息或數(shù)據(jù)的“指紋”將h和消息M一起發(fā)送，可檢測到基本的傳輸錯誤h和M分別獨立發(fā)布，可解決一般的完整性問題(前提是確保h不被篡改)Hello

Jerry,

this

is

Tom

speakingHello

Tom0a35

bc9d

87e2

1a9f

54a4

8856

ef2177da

ba15

e5c9

42f7

91ae

bc28

4c39消息M散列值h數(shù)據(jù)完整性數(shù)據(jù)完整性口令保護useridpassword

usernamelastlogintimeszhang9a32d6eb092d zhang

san2012-10-2

12:30:42sli5321b2a761e0 li

si2012-10-3

14:12:30wwangd50c2234e9f7 wang

wu2012-10-2

15:22:34使用des構(gòu)造macHash函數(shù)如果要在不安全的信道中保證消息的完整性，可以在Hash函數(shù)中引入一個密鑰，其結(jié)果被稱為消息驗證碼(MAC)定義4.1一個Hash族是滿足下列條件的四元組

(X,Y,K,H)：3

X是所有可能的消息的集合3

Y是所有可能的消息摘要構(gòu)成的有限集3

K是所有可能的密鑰集合，即密鑰空間3

對每個k∈K，存在一個Hash函數(shù)hk∈H，hk:X→YHash函數(shù)如果hk(x)=y，則稱(x,y)∈X×Y在密鑰k下是有效的或正確的不帶密鑰的Hash函數(shù)是函數(shù)h:X→Y，可以看做定義4.1的特例，即只有一個密鑰的Hash族，|K|=1定義4.1只給出了Hash函數(shù)的一般定義，即

X到Y(jié)的函數(shù)。X到Y(jié)的所有函數(shù)可記為FX,Y，因此h∈FX,Y。假定|X|=N，|Y|=M，有|FX,Y|=MNHash函數(shù)怎樣的Hash函數(shù)能滿足數(shù)據(jù)完整性保護的要求？Hash函數(shù)的基本要求3

快速：給定M，很容易計算h3

單向：給定h，根據(jù)H(M)=h無法計算出M3

防碰撞：給定M，要找到另一條消息M’并滿足

H(M)=H(M’)很難Hash函數(shù)的安全性安全的Hash函數(shù)滿足三個條件3

單向性(原像穩(wěn)固性)?

給定一個消息摘要y，很難找到符合h(x)=y的消息x3

第二原像穩(wěn)固性?

給定x∈X，很難找到一個x’∈X且x’≠x，滿足h(x)=h(x’)3

碰撞穩(wěn)固性?

對于任意的x,x’∈X，很難找到滿足x≠x’且h(x)=h(x的二元組(x,x’)Hash函數(shù)的安全性理想的Hash函數(shù)應滿足，對給定的x，只能通過函數(shù)h計算得到h(x)的值，而無法通過其他方式得到已知h(x1),h(x2),...無法間接推算出h(x)，其中x和x1,x2,...均不相等Hash函數(shù)的安全性反例：假定Hash函數(shù)h:Zn×Zn→Zn，是一個線性函數(shù)，有h(x,y)=(ax+by)

mod

n假定已知h(x1,y1)=z1；h(x2,y2)=z2令x=x1+x2,y=y1+y2則h(x,y)=h(x1+x2,y1+y2)=a(x1+x2)+b(y1+y2)=ax1+by1+ax2+by2=z1+z2已知h(x1,y1)和h(x2,y2)，可以不經(jīng)過h函數(shù)的計算直接得出h(x,y)的值為h(x1,y1)+h(x2,y2)因此這個Hash函數(shù)是不安全的生日悖論和生日攻擊生日悖論3隨機選擇多少個人，存在有兩人生日相同的概率大于1/2？3

說明發(fā)生碰撞的概率比一般想象中要大得多3隨機選擇多少個人，使得和某人生日相同的概率大于1/2？生日攻擊3

合同簽名欺詐生日悖論和生日攻擊給定一個散列函數(shù),有n個可能的輸出,輸出值為H(x),如果H有k個隨機輸入,k必須為多大才能使至少存在一個輸入y,使得

H(y)=H(x)的概率大于0.5.對單個y,

H(y)=H(x)的概率為1/n,反過來H(y) H(x)的概率為1-(1/n).如果產(chǎn)生k個隨機值y,他們之間兩兩不等的概率等于每個個體不匹配概率的乘積,即[1-(1/n)]k,這樣,至少有一個匹配的概率為1-[1-(1/n)]k

1-[1-(k/n)]=k/n.要概率等于0.5,只需k=n/2.對長度為m位的散列碼，共有2m個可能的散列碼，若要使任意的x,y有H(x)=H(y)的概率大于0.5,只需k=2m/2而對于給定的x，尋找y使得H(x)=H(y)的概率大于0.5，則需

k=2m-1生日悖論和生日攻擊A準備兩份合同M和M ，一份B會同意，一份會取走他的財產(chǎn)而被拒絕A對M和M 各做32處微小變化(保持原意),分別產(chǎn)生232個64位hash值根據(jù)前面的結(jié)論,超過0.5的概率能找到一個M和一個M ,它們的hash值相同A提交M,經(jīng)B審閱后產(chǎn)生64位hash值并對該值簽名,返回給AA用M 替換MHash必須足夠長散列函數(shù)的安全性強行攻擊：生日攻擊單向2n弱無碰撞2n-1強無碰撞2n/2Hash函數(shù)使用隨機諭示模型中的理想Hash函數(shù)是困難的，可參考一些分組密碼理論構(gòu)造近可能接近理想特性的Hash函數(shù)3

混亂

3

擴散

3

隨機Hash函數(shù)思考3能否將分組密碼在CBC模式下所產(chǎn)生的最后一組密文分組作為散列值，作為Hash函數(shù)？

將消息分為長度為64位的N個分組，利用加密函數(shù)計算Ci

=EK(Ci－1⊕Pi)令h＝CN3

MAC（消息認證碼）?在密鑰的控制下將任意長的消息映射為一個定長的數(shù)據(jù)3

缺點：運算代價過高Hash函數(shù)的構(gòu)造基于數(shù)學難題的構(gòu)造方法：計算速度慢，不實用利用對稱密碼體制來設計Hash直接設計hash函數(shù)通用結(jié)構(gòu)由Merkle于1989年提出Ron

Rivest于1990年提出MD4幾乎被所有hash函數(shù)使用

具體做法:把原始消息M分成一些固定長度的塊Yi最后一塊padding并使其包含消息M長度設定初始值CV0壓縮函數(shù)f,CVi=f(CVi-1,Yi-1)最后一個CVi為hash值IV=CV0Y0

Y1

Yl-1b

b

bn

f

n

fCV1n

nn

fCVL-1General

Structure

of

Secure

Hash

CodeCVLCV0=IV=

initial

n-bit

valueCVi=f(CVi-1,

Yi-1)

(1

i

L)H(M)

=

CVLIV=initial

value初始值CV=chaining

value鏈接值Yi=ith

input

block(第i個輸入數(shù)據(jù)塊)f =

compression

algorithm

(壓縮算法）n =

length

of

hash

code

(散列碼的長度)

b =

length

of

input

block(輸入塊的長度)討論幾種常用的HASH算法MD5SHA-1MD5簡介Ron

Rivest于1990年提出MD41992年,MD5

(RFC

1321)

developed

by

Ron

Rivest

atMITMD5把數(shù)據(jù)分成512-bit/塊，MD5的hash值是

128-bit在最近數(shù)年之前，MD5是最主要的hash算法現(xiàn)行美國標準SHA-1以MD5的前身MD4為基礎Dobbertin在1996年找到了兩個不同的512-bit塊,它們在MD5計算下產(chǎn)生相同的散列值2004年8月17日國際密碼學會議，山東大學王小云教授宣告破解了包含MD5在內(nèi)的數(shù)個單向散列算法MD5:示意圖MD5:

paddingStep

1:

Padding

M

M1|M1| 448

mod

512|M1|

>

|M|如果|M| 448

mod

512,則|M1|

=

|M|+512Padding內(nèi)容:

100…0Step

2:

Append

64-bit

length

M1

M2若|M|>264,則僅取低64位低字節(jié)在前(little-endian)|M2|為512的倍數(shù):Y0,Y1,…,YL-1MD5:

compressionMD5:

compressionStep

3:

Initialize

MD

buffer

(little-endian)A

=

01

23

45

67

(0x67452301)B

=

89

AB

CD

EF

(0xEFCDAB89)C

=

FE

DC

BA

98

(0x98BADCFE)D

=

76

54

32

10

(0x10325476)Step

4:

CompressionCV0=IVCVi=HMD5(CVi-1,Yi)Step

5:

OutputMD

=

CVLMD5

Compression

Function每一輪包含對緩沖區(qū)ABCD的16步操作所組成的一個序列。A B

+

((

A

+

g(B,C,D)

+

X[k]

+T[i])<<<s)其中，A,B,C,D 緩沖區(qū)的四個字，以一個給定的次序排列；g 基本邏輯函數(shù)F,G,H,I之一；<<<s 對32位字循環(huán)左移s位X[k]M[q 16+k]=在第q個512位數(shù)據(jù)塊中的第k個32位字T[i]+表T中的第i個32位字；T[j]=

[sin(j)*232]的整數(shù)部分,

1

j

64模

232的加；ABCDABCD+++CLSs+gX[k]T[i]Function

gg(B,C,D)2i

=

(1+5i)

mod

16

3i

=

(5+3i)

mod

16

4i

=

7i

mod

16s1[0…3]

=

[7,12,17,22]s2[0…3]

=

[5,9,14,20]s3[0…3]

=

[4,11,16,23]s4[0…3]

=

[6,10,15,21]MD5:總結(jié)MD5使用小數(shù)在前生日攻擊+64位可計算 128位hash值太短Dobbertin在1996年找到了兩個不同的512-bit塊,它們在MD5計算下產(chǎn)生相同的hashHow

to

Break

MD5

and

Other

Hash

Functions，Xiaoyun

Wang

and

Hongbo

Yu,

R.

Cramer

(Ed.):EUROCRYPT

2005,

LNCS

3494,

pp.

19–35,

2005.Collisions

for

Hash

FunctionsMD4,

MD5,HAVAL-128

and

RIPEMD，Xiaoyun

Wang,Dengguo

Feng,

Xuejia

Lai,

Hongbo

YuSecure

Hash

Algorithm簡介1992年NIST制定了SHA(128位)1993年SHA成為標準（FIPS

PUB

180）1994年修改產(chǎn)生SHA-1(160位)1995年SHA-1成為新的標準,作為SHA-1(FIPSPUB

180-1)SHA-1要求輸入消息長度<264輸入按512位的分組進行處理

SHA-1的摘要長度為160位基礎是MD4SHA-1:

padding與MD5相同Step

1:

Padding

M

M1|M1| 448

mod

512|M1|

>

|M|如果|M| 448

mod

512,則|M1|

=

|M|+512Padding內(nèi)容:

100…0Step

2:

Append

64-bit

length

M1

M2若|M|>264,則僅取低64位高字節(jié)在前(big-endian)|M2|為512的倍數(shù):Y0,Y1,…,YL-1SHA-1

step

4:示意圖SHA-1:

compressStep

3:

Initialize

MD

buffer

(big-endian)A

=

67

45

23

01

(0x67452301)B

=

EF

CD

AB

89

(0xEFCDAB89)C

=

98

BA

DC

FE

(0x98BADCFE)D

=

10

32

54

76

(0x10325476)E

=

C3

D2

E1

F0

(0xC3D2E1F0)Step

4:

CompressionCV0=IVCVi=HSHA-1(CVi-1,Yi)Step

5:

OutputMD

=

CVLSHA-1壓縮函數(shù)A,B,C,D,E(E

+

f(t,B,C,D)+S5(A)

+Wt

+

Kt),A,S30(B),C,D其中，