第5章 散列函数与消息鉴别

四川大学电子信息学院1/40第1章密码学概述 第2章古典密码技术 第3章分组密码第4章公钥密码体制第5章散列函数与消息鉴别第6章数字签名技术第7章密钥管理技术第8章身份鉴别技术第9章序列密码基础第10章密码技术应用课程主要内容上周讲到……2/40一、散列函数的概念散列函数H(·)是一种单向密码体制，它是一个从明文到密文的不可逆函数，也就是说，是无法解密的。

Hash函数是一种将任意长度的消息M映射为较短的、固定长度的一个值H(M)的函数，称函数值H(M)为消息摘要MD(MessageDigest)或散列码。

散列函数的目的是为文件、报文或其他的分组数据产生“数字指纹”,主要用于报文鉴别和数字签名。第5章散列函数与消息鉴别鉴别服务是用来提供对通信中实体和数据原发(数据源)的鉴别。鉴别协议是能使通信各方证实对方身份或消息来源的通信协议。（ISO/IEC7498-2）

鉴别就是可信地确认实体是它所声明的。四川大学电子信息学院3/401.散列函数的基本性质

散列函数H必须具有如下性质：

(1)H能用于任何大小的数据分组；

(2)H产生定长输出；

(3)对任何给定的x，H(x)要相对易于计算，使得硬件和软件实现成为实际可行。

(4)对任何给定的码m，寻找x使得H(x)＝m在计算上是不可行的。(单向性质)

。碰撞概念：如果两个报文M与M’，M≠M’，但它们的散列值相等，即H(M)＝H(M’)，那么，我们就把这种现象称为发生了碰撞。散列函数具有碰撞不可避免性。但对散列函数的要求有：

(5)对任何给定的分组x，寻找不等于x的y，使得H(x)=H(y)在计算上是不可行的。

(弱抗冲突weakcollisionresistance)；

(6)寻找任何(x,y)对(x≠y)，使得H(x)＝H(y)在计算上是不可行的。(强抗冲突

strongcollisionresistance)。四川大学电子信息学院4/402.散列函数的主要应用（1）保证数据的完整性；例如，为保证数据的完整性，可以使用单向散列函数对数据生成并保存散列值，然后，每当使用数据时，用户将重新使用单向散列函数计算数据的散列值，并与保存的数值进行比较，如果相等，说明数据是完整的，没有经过改动；否则，数据已经被改动了。（2）单向数据加密：如口令表加密；

应用于诸如口令表加密等场合，使用单向函数保存口令表可避免以明文的形式保存口令，至今仍然在许多系统中得到广泛的使用。（3）数字签名。四川大学电子信息学院5/402.1简单的散列函数：

数字通信中的一些校验码能否作散列函数，如累加和校验、纵向奇偶校验、CRC循环冗余校验等等？如纵向奇偶校验：设输入分组序列为：M＝X1||X2||……||XN

(Xi为nbit分组)则输出散列码为：H(M)＝X1⊕X2⊕……⊕XN(按位异或)特点:(1)简单、对输入为随机数据的完整性检查有效；存在的问题：容易产生碰撞二.散列函数的构造与设计四川大学电子信息学院6/40原报文：M=X1||X2||……||XN，传送报文M||Ek[H(M)]被攻击者截获.(

将Ek[H(M)]作为报文鉴别码)

伪报文：M’=Y1||Y2||……||YN-1||YN；(显然M’不等于M)

其中，Y1、Y2、……YN-1可为任意报文分组。而YN则按以下方式构造,

计算：H(M)=X1⊕X2⊕……⊕XN

使YN=Y1⊕Y2⊕……⊕YN-1⊕H(M)

攻击者传送报文：

M’||Ek[H(M)]

;报文鉴别码不变接收方解密Ek[H(M)]得报文摘要：H(M)接收方验证：H(M’)

=Y1⊕

Y2⊕……⊕

YN-1⊕

YN=Y1⊕Y2⊕……⊕

YN-1⊕Y1⊕Y2⊕……⊕YN-1⊕H(M)

=H(M)

∴接收者不能发现报文已被篡改。若H(M)=X1⊕X2⊕……⊕XN，有报文篡改方案：问题原因：(1)M为明文；(2)算法太简单。

对手容易寻找一个M’≠M，但使H(M’)=H(M)返回报文鉴别码性质四川大学电子信息学院7/402.2迭代型散列函数的一般结构任意长度输入M迭代压缩函数可选输出变换CViCVi－1Mi固定长度输出散列函数输出四川大学电子信息学院8/402.2迭代型散列函数的一般结构（续）设报文M=M0||M1||…||ML－1bbbfffCVL=MDIV=CV0CV1CVL－1…M0M1ML－1nnnn散列函数输出IV=initialvalue初始值CV=chainingvalue链接值Mi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度)四川大学电子信息学院9/402.3散列函数的设计方法基于对称分组密码的CBC工作模式的Hash函数（还有其它方式）（基于公钥密码的构造方法：计算效率低，基本无实用价值）⊕Em1c0=IVkc1⊕Em2kc2⊕EmNkcNcN－1……H(M)=cN设：M=m1||m2||…||mN如果密钥k保密，则得到的是带密钥的Hash函数(又称为报文鉴别码，MessageAuthenticationCode)。

10/40如果密钥k公开，是否可以作为通常的不带密钥的Hash函数？在密钥公开条件下，由明文

M=m1||m2||…||mN，

攻击者可计算出：

x1,c1,x2,c2,……,cN－1

,xN,cN,设攻击者将m1→m1’,…,mN-1→mN－1’(做任意替换),可由

m1’→c1’→c2’

…

…→cN－1’,再构造最后一个明文分组：

mN’

＝cN－1’⊕xN

篡改后，M’=m1’||m2’

||m3’

||…||mN-1’

||mN’

M

这时在最后一个加密分组有：

mN’⊕cN-1’＝cN-1’⊕xN

⊕cN-1’＝xN

显然cN也未变，仍有：H(M’)=H(M)结论：在密钥k公开的情况下，基于分组密码的CBC工作模式的Hash函数是不安全的。⊕Em1IVkc1⊕Em2kc2⊕EmNkcNcN－1……H(M)=cN

xNx1x2⊕EmN－1kcN－1cN－2xN－1四川大学电子信息学院11/40无密钥的基于分组密码的散列函数一种用对称加密算法构造hash函数:M=(M1,M2,…,Mt),H0=InitialvalueHi=f(Mi,Hi-1),例如Hi=EMi(Hi-1)Hash:Ht下面四种被认为可能是安全的:特点：计算效率低，且许多这样的hash函数被证明不安全(与E的安全性无关)，现在很少使用。四川大学电子信息学院12/40这类单向散列函数并不基于任何假设和密码体制，它通过直接构造复杂的非线性关系达到单向性要求。这类算法典型的有：MD2、MD4、MD5、SHA－1、PIPE－MD、HAVAL等算法。目前，直接设计单向散列函数的方法受到了人们的广泛关注和青睐，是目前比较流行的一种设计方法。散列函数有与分组密码相似的进展：–强力攻击能力的提高，导致算法的改进；–分组密码从DEStoAES；–Hash算法从MD4&MD5到SHA-1&RIPEMD-160–与分组密码类似都使用了通用的迭代结构。2.4直接设计单向散列函数四川大学电子信息学院13/40三.单向散列函数SHA

基础是MD4，1992年NIST制定了SHA(128位)1994年，修改产生SHA-1(160位)1995年，SHA-1成为新的标准，作为SHA-1(FIPSPUB180-1)美国DSA签名方案使用的标准算法，InternetRFC3174

2002年，NIST发布修订版FIPSPUB180-2，增加了

SHA-256、SHA-384和SHA-512。

SHA-1是设计用来与DSS(数字签名标准)一起使用的。NIST在标准中指出：“本标准规定一种保证数字签名算法(DSA)安全所必需的安全散列算法(SHA)。当输入是长度小于264bit的消息时，SHA产生一个称为消息摘要的160bit输出，然后将该摘要输入到用于计算该消息签名的DSA中。”四川大学电子信息学院14/40单向散列函数SHA-1（续）

SHA-1每次循环中操作数80次，并且它处理的缓存为160比特，无需冗长的程序或很大的替换表，易于实现。对每个分组使用四次循环，每次循环20步，共80步。设报文M=M0||M1||…||ML－1图中：b=512n=160bbbfffCVL=MD(160bit)IV=CV0CV1CVL－1…M0M1ML－1nnnn散列函数输出输入：最大长度为264-1位的消息；输出：160位消息摘要；处理：输入以512位数据块为单位处理(SHA-384和SHA-512为1024位)

四川大学电子信息学院15/401.基本算法在结构和处理流程上，SHA与MD5非常相似。

SHA采用了Big－Endian结构作为基础:

即高位字节存储在低地址字节上。这一点与MD5相反。

SHA算法产生的输出是一个160比特的报文摘要(MD5是128比特)，它所接受的输入报文的最大长度不超过264比特。

(1)

报文分组与填充；分组长度为512bit，最后一个分组为448bit。(留64bit作报文长度域)

填充方法：填充串首1，其余各位为0。(2)附加消息长度；64bit

最大报文长度=264－1(bit)

≈261(Byte)

≈241(MB)四川大学电子信息学院16/40SHA-1的散列码为160位(32bit×5)，故使用了五个32bit的字单元作计算MD的缓存：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0ABCD与MD5一样，但存储方式不同：缓存的高位字节内容存放在低地址字节。(4)以512bit(16个字)分组处理消息；算法的核心：为四个循环的处理模块，但每个循环由20个运算步骤组成，且使用的逻辑函数和有关参数也不相同。(3)初始化MD缓存；17/40512bit(16个字)分组处理过程f3K3W40,…,W5920个步骤+++++ABCDECVqYq51251216032ABCDEABCDEABCDEf2K2W20,…,W1920个步骤f1K1W0,…,W1920个步骤f4K4W60,…,W7920个步骤注:：+是mod232CVq+1160Yq-----正在处理的分组；CVq-----上个分组的迭代输出；图中，fi------原始逻辑函数(i=1,2,3,4)，共4个；

Ki-----常数值,作附加限制(i=1,2,3,4)，共4个；

Wt-----由Yq导出的子分组(t=1～80)，共80个；18/40②每一步的附加限制与MD5不同：在SHA-1，在4次循环80步中，每次循环20步使用一个常数值Ki(i=1,2,3,4)①4个原始逻辑函数：f1，f2，f3，f4f1(b,c,d)=(b∧c)∨(b∧d)；用于第1轮循环，即第0～19步

f2(b,c,d)=b⊕c⊕d；用于第2轮循环，即第20～39步;f3(b,c,d)=(b∧c)∨(b∧d)∨(c∧d)；用于第3轮循环，即第40～59步;f4=(b,c,d)=f2(b,c,d)=b⊕c⊕d；用于第4轮循环，即第60～79步;19/40每步操作的形式为:(第i次循环,第t步,i=1,2,3,4，t=1~80)E←E+fi(b,c,d)+ROL(A,5)+Wt+Ki;

ROL为循环左移函数B

←ROL(B,30)

然后，5个字缓存单元按字循环右移，如下图：③每次循环的20步操作：ABCDEfi++++ABCDEEABCDROL5ROL30按字循环右移Wt

Ki20/40④子分组Wt的导出：

SHA的4次循环共80步，每步操作都是从Yq中导出一个子分组W[t]，而不是象MD5那样，16个子分组循环重复使用(尽管次序不一样)。

W0

～W15：直接取自当前分组Yq的16个子分组；

W16～W79：按下面公式导出(共64个)：

Wt=ROL(Wt－16

⊕Wt－14

⊕Wt－8

⊕Wt－3,1)（16≤t≤79）即Wt由前面4个W值异或后，再循环左移1位而得出，如下图：Yq(512bit)W0W1W2……W14W1532bit⊕ROL1W0W2W8W13W1632bit⊕ROL1Wt-16Wt-14Wt-8Wt-3Wt32bit⊕ROL1W63W65W71W76W7932bit…………共80个子分组四川大学电子信息学院21/40SHA系列算法的比较SHA-1，SHA-256，SHA-384，SHA-512这些散列函数的主要差别在于填充方法、字长、初始常数、基本函数等部分，它们的基本运算结构大体是相同的。

算法消息长度分组长度字长散列值长使用常数基本函数处理步骤SHA-1<264512321604×32480SHA-256<2645123225664×32664SHA-384<212810246438480×32680SHA-512<212810246451280×32680四川大学电子信息学院22/40四.对单向散列函数的攻击

对单向散列函数的攻击是指攻击者寻找一对产生碰撞消息的过程。评价单向散列函数的最好的方法就是看一个攻击者找到一对碰撞消息所花的代价有多高。通常在讨论单向散列函数的安全性时，我们都假设敌手已经知道单向散列函数算法（遵循Kerckhoffs假设）。目前对单向散列函数的攻击方法可以分为两类：强力攻击(或穷举攻击)：典型方法如生日攻击。利用单向散列函数的弱性质（结构和代数性质）：如中间相遇攻击、修正分组攻击和差分分析等，另外，若使用其他密码算法来构造单向散列函数，还可能因为所用的密码算法的弱点而引起攻击（例如，DES的一些众所周知的弱点，如互补性、弱密钥与半弱密钥等，都可用来攻击基于DES构造的单向散列函数）。四川大学电子信息学院23/404.1生日悖论在k个人中，要至少有两个人生日相同的概率大于0.5，问k的最小值？定义：P(n,k)-----k个个体中至少有一个值重复的概率，其中每个个体在1和n之间均匀分布。上述问题即为：求满足P(365,k)≥0.5时，k的最小值，这时n=365。四川大学电子信息学院24/40生日悖论（续）解：设Q(n,k)为k个个体不重复的概率(k个人没有相同生日的概率)

第1个人Z1的生日是随机的；第2个人Z2，与Z1相同的概率为1/n，不相同为1－1/n；第3个人Z3，与Z1,Z2其中某个人相同的概率为2/n，不相同为1－2/n；第4个人Z4，与Z1,Z2,Z3其中某个人相同的概率为3/n，不相同为1－3/n；

……第k个人Zk，与前面k－1个人其中1人相同的概率为(k－1)/n，不相同为1－(k－1)/n；∴k个人没有相同生日的概率为：k个人有相同生日的概率为：四川大学电子信息学院25/40一个有用的不等式：(1－x)≤e－xe－x(1－x)当x较小时，有：(1－x)≈e－x四川大学电子信息学院26/40对于较大的k，可用k2近似代替k(k－1)，有：∴随机23个人中，至少有两人生日相同的概率为0.5。将n=365，P=0.5代入,有：k=22.3≈23∵(1－x)≈e－x四川大学电子信息学院27/404.2生日攻击问题与散列函数相关的一个基本问题可描述为：

给定一个散列函数H(x)，有n个可能的输出。若H有k个随机输入，问：

k必须取为多大，才能使至少存在一个碰撞（即x≠y，但H(x)=H(y)?）的概率大于0.5?

四川大学电子信息学院28/404.2生日攻击问题(续)HMH(M)设散列码mbit,共有2m个可能的输出生日攻击的另外相关问题可描述为：

设散列函数H有2m个可能的输出。若让H接收k个随机输入产生集合X，再使用另外k个随机输入产生集合Y。问k必须取为多大，才能使两个集合间至少存在一个匹配的概率大于0.5?

这里，n=2m，按近似公式有：四川大学电子信息学院29/40

散列函数的生日攻击示例企业负责人要Alice为Bob写一份工作情况评价报告，Alice写好后需交公司负责人审阅并签名后（数字签名），送有关部门参加评比或升迁考核等等。事实：

Bob工作非常努力、具有很强的工作能力……。Alice的目标：把Bob评价得很低，但又能通过公司负责人的审阅，并使他完成签名。（假设散列函数是64位的。）攻击方法：(1)Alice写两份对Bob的评价报告M(积极评价)和M‘(消极评价)；(2)

对M和M′各做32处微小变化(保持原意)，分别产生232个64位Hash值。

根据前面的结论，超过0.5的概率能找到一个m和一个m′,它们的Hash值相同。(3)

Alice将m交公司负责人审阅，对m的Hash值完成数字签名；(4)

Alice将签名报告拦截，并用m’替换掉m，完成攻击。四川大学电子信息学院30/40五.报文鉴别

报文鉴别是指在两个通信者之间建立通信联系后，每个通信者对收到信息进行验证，以保证所收到信息的真实性的过程。确保：报文是由确认的发送方产生的；报文内容没有被篡改过；报文是按与发送时的相同顺序收到的。四川大学电子信息学院31/40鉴别符：附加在报文上的额外信息。当报文必须经过签别才能被接受时，鉴别符可使接收端验证该报文。鉴别符可以在功能上与报文本身的内容无关(例如，仅用一次的标识符或信源标识符），也可以是报文内容的一个函数。产生鉴别符的方法有三类：报文加密、散列函数或报文鉴别码。报文加密：报文用对称密钥算法加密后的密文作为鉴别符。散列函数：是一个将任意长度的报文映射为定长的散列值的公共函数，以散列值作为鉴别符。报文鉴别码(MAC,MessageAuthentication)：使用一个通信双方共享的秘密信息(如密钥)产生一个定长数据分组，并将它附加在报文中作为鉴别符。即所谓的密码检验(MAC)，如何实现报文鉴别？四川大学电子信息学院32/40将报文用对称密钥算法加密后的密文作为鉴别符。如何构造这样的结构？特点：要求接收端有判别明文合法性的手段和措施。措施：让明文带有某种容易识别而又不易被篡改的结构。5.1报文加密四川大学电子信息学院33/40一种解决办法：引入差错控制!MF||EKEk[M||F(M)]源点MF(M)F比较DKM终点F(M)F比较DMK内部差错控制!MF||EKEk[M]F(Ek[M])Ek[M]外部差错控制!34/405.2

基于报文鉴别码（MAC）的消息鉴别1.报文鉴别码的概念:

受密钥保护的报文摘要称为报文鉴别码（MAC），也称消息鉴别码。即：

MAC=Ck(M)

其中M为明文，Ck(·)是带密钥的函数。C任意长报文MMACK(密钥)2.对MAC函数C的一般需求:注前提：攻击者能获取M||Ck(M)；

攻击者已知MAC函数C，但不知道K。35/40基于报文鉴别码（MAC）的消息鉴别（续）(1)攻击者根据M||Ck(M)，生成一个报文M’≠M，使得Ck(M’)=Ck(M)在计算上不可行。若用“简单异或”+“加密”的办法构成MAC未能满足此要求。(2)Ck(M)应均匀分布。(注意报文空间远大于MAC空间)

M与Ck(M)是多对一的关系，即客观上存在M’≠M，而Ck(M’)=Ck(M)

这里要求，MAC函数C对于随机选择的两个消息M和M’

，满足：出现Ck(M’)=Ck(M)的概率为2－n；n为MAC的bit数(3)若M’为M的某个变换，即M’=f(M)，如f为插入或修改某些bit位，那么仍有，出现Ck(M’)=Ck(M)的概率为2－n

这一性质要求算法对报文特定bit位不应该比其他位更脆弱，使得攻击者尝试更改M中的某些位后，MAC却未发生改变的概率很小。四川大学电子信息学院36/403.报文鉴别码的基本应用方式MC||MCk(M)KCK比较源点终点MC||EK2K1Ek2[M||Ck1(M)]C比较DK2MK1Ck1(M)对明文鉴别四川大学电子信息学院37/40报文鉴别码的基本应用方式（续）MAC基本应用方式示意图MC||EK2K1Ck1[Ek2(M)]Ek2(M)D比较DK1对密文鉴别K2M四川大学电子信息学院38/404.基于分组密码（如DES）的报文鉴别码：

⊕Em1IVKc1⊕Em2Kc2⊕EmNKcNcN－1……MAC=cNx2x1加密算法若采用DES算法，则是美国联邦信息处理标准(FIPSPUB11.3)和ANSI标准(X9.17)

四川大学电子信息学院39/405.3基于散列函数的消息鉴别 散列函数并不是为MAC而设计的，由于散列函数不使用密钥，故不能直接用于消息鉴别。

仅采用散列函数不能保护信息的完整性。

解决办法：同时使用加密或采用带密钥散列函数。应用时散列值必须受到保护!!四川大学电子信息学院40/40(1)(2)1.基于散列函数的6种消息鉴别方法四川大学电子信息学院41/40基于散列函数的消息鉴别方法（续）(3)四川大学电子信息学院42/40基于散列函数的消息鉴别方法（续）(4)四川大学电子信息学院43/40(5)(6)基于散列函数的消息鉴别方法（续）四川大学电子信息学院44/40

2.HMAC算法

HMAC是带密钥的单向散列函数，已作为RFC2104被公布，并在IPSec和其他网络安全协议(如SSL)中得以应用。

HMAC设计目标：

(1)无需修改地使用现有的散列函数;(2)能以模块化方式使用(嵌入)散列函数；

(3)保持散列函数的原有性能，不会因用于MAC而导致其性能的降低；

(4)以简单的方式使用和处理密钥(或秘密信息)；

(5)在对嵌入散列函数合理假设的基础上，易于分析HMAC用于鉴别机制的强度。基本思路：H(K+||M)→HMAC四川大学电子信息学院45/40HMAC的计算公式可表示为：

HMACK(M)=H[(K+⊕opad)||H[(K+⊕ipad)||M]]其中，opad和ipad为两个扩展的bit翻转字。HMAC算法描述：n为Hush函数散列码长度；b为处理报文分组的大小，如MD5，n=128，b=512ipad=36H重复b/8，从而使ipad的长度也为bopad=5AH重复b/8，从而使opad的长度也为b包括了H函数所需的填充比特nSiY0Y1……YL－1Hash⊕报文M=Y0||Y1||…YL－2||YL－1bK+ipadIVnSo将H(Si||M)填充到b比特

H(Si||M)nHashHMACK(M)⊕bK+opadIVnbb四川大学电子信息学院46/40HMAC的密钥填充K+：HMAC的密钥K可为任意长度，MHAC作如下处理：b为Hash函数处理分组长度如MD5、SHA为512填充密钥K＋长度也为b利用H函数将K压缩为n个bit如MD5为128、SHA为160K的长度≥b填充K，使长度＝bK←H(K)KK+NY