密碼學(xué)基密碼學(xué) 在線

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

保密性3

完整性3

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

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

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

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

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

h也被稱為消息或數(shù)據(jù)的“指紋”將h和消息M一起發(fā)送，可檢測(cè)到基本的傳輸錯(cuò)誤h和M分別獨(dú)立發(fā)布，可解決一般的完整性問(wèn)題(前提是確保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ù)完整性口令保護(hù)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ù)中引入一個(gè)密鑰，其結(jié)果被稱為消息驗(yàn)證碼(MAC)定義4.1一個(gè)Hash族是滿足下列條件的四元組

(X,Y,K,H)：3

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

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

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

對(duì)每個(gè)k∈K，存在一個(gè)Hash函數(shù)hk∈H，hk:X→YHash函數(shù)如果hk(x)=y，則稱(x,y)∈X×Y在密鑰k下是有效的或正確的不帶密鑰的Hash函數(shù)是函數(shù)h:X→Y，可以看做定義4.1的特例，即只有一個(gè)密鑰的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ù)完整性保護(hù)的要求？Hash函數(shù)的基本要求3

快速：給定M，很容易計(jì)算h3

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

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

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

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

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

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

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

碰撞穩(wěn)固性?

對(duì)于任意的x,x’∈X，很難找到滿足x≠x’且h(x)=h(x的二元組(x,x’)Hash函數(shù)的安全性理想的Hash函數(shù)應(yīng)滿足，對(duì)給定的x，只能通過(guò)函數(shù)h計(jì)算得到h(x)的值，而無(wú)法通過(guò)其他方式得到已知h(x1),h(x2),...無(wú)法間接推算出h(x)，其中x和x1,x2,...均不相等Hash函數(shù)的安全性反例：假定Hash函數(shù)h:Zn×Zn→Zn，是一個(gè)線性函數(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)過(guò)h函數(shù)的計(jì)算直接得出h(x,y)的值為h(x1,y1)+h(x2,y2)因此這個(gè)Hash函數(shù)是不安全的生日悖論和生日攻擊生日悖論3隨機(jī)選擇多少個(gè)人，存在有兩人生日相同的概率大于1/2？3

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

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

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

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

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

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

混亂

3

擴(kuò)散

3

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

將消息分為長(zhǎng)度為64位的N個(gè)分組，利用加密函數(shù)計(jì)算Ci

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

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

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

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

具體做法:把原始消息M分成一些固定長(zhǎng)度的塊Yi最后一塊padding并使其包含消息M長(zhǎng)度設(shè)定初始值CV0壓縮函數(shù)f,CVi=f(CVi-1,Yi-1)最后一個(gè)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個(gè)輸入數(shù)據(jù)塊)f =

compression

algorithm

(壓縮算法）n =

length

of

hash

code

(散列碼的長(zhǎng)度)

b =

length

of

input

block(輸入塊的長(zhǎng)度)討論幾種常用的HASH算法MD5SHA-1MD5簡(jiǎn)介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)行美國(guó)標(biāo)準(zhǔn)SHA-1以MD5的前身MD4為基礎(chǔ)Dobbertin在1996年找到了兩個(gè)不同的512-bit塊,它們?cè)贛D5計(jì)算下產(chǎn)生相同的散列值2004年8月17日國(guó)際密碼學(xué)會(huì)議，山東大學(xué)王小云教授宣告破解了包含MD5在內(nèi)的數(shù)個(gè)單向散列算法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每一輪包含對(duì)緩沖區(qū)ABCD的16步操作所組成的一個(gè)序列。A B

+

((

A

+

g(B,C,D)

+

X[k]

+T[i])<<<s)其中，A,B,C,D 緩沖區(qū)的四個(gè)字，以一個(gè)給定的次序排列；g 基本邏輯函數(shù)F,G,H,I之一；<<<s 對(duì)32位字循環(huán)左移s位X[k]M[q 16+k]=在第q個(gè)512位數(shù)據(jù)塊中的第k個(gè)32位字T[i]+表T中的第i個(gè)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位可計(jì)算 128位hash值太短Dobbertin在1996年找到了兩個(gè)不同的512-bit塊,它們?cè)贛D5計(jì)算下產(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簡(jiǎn)介1992年NIST制定了SHA(128位)1993年SHA成為標(biāo)準(zhǔn)（FIPS

PUB

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

180-1)SHA-1要求輸入消息長(zhǎng)度<264輸入按512位的分組進(jìn)行處理

SHA-1的摘要長(zhǎng)度為160位基礎(chǔ)是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其中，