05-报文鉴别与散列函数

南京邮电大学第6讲报文鉴别与散列函数wangzhiwei博士计算机学院信息安全系[e-mail]2020/1/29南京邮电大学2本讲内容报文鉴别码1散列函数2常见的散列算法3小结4概要报文鉴别（消息认证）是用来验证消息完整性的一种机制。报文鉴别确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放），且发送方声称的身份真实有效。对称密码在那些相互共享密钥的用户间提供认证。用消息发送方的私钥加密消息也可提供一种形式的认证。用于消息认证的最常见的密码技术是报文鉴别码（消息认证码）和安全散列函数。MAC是一种需要使用秘密钥的算法，以可变长度的消息和秘密钥作为输入，产生一个认证码。拥有秘密钥的接受方产生一个认证码来验证消息的完整性。散列函数将可变长度的消息映射为固定长度的散列值，或叫消息摘要。对于消息认证码，安全散列函数必须以某种方式和秘密钥捆绑起来。2020/1/29南京邮电大学32020/1/29南京邮电大学4报文鉴别的应用场合在网络通信中，攻击方法泄密：透露消息给没有密钥的实体传输分析：分析通信模式，连接频率、时间，消息的数量和大小伪装：欺诈消息，伪装发送或应答内容修改：插入、删除、转换和修改消息顺序修改：对通信双方消息顺序进行修改计时修改：消息重放或者延迟发送方否认接收方否认2020/1/29南京邮电大学5报文鉴别的作用报文鉴别(消息认证)对收到的消息进行验证，证明确实是来自声称的发送方，并且没有被修改过。如果在消息中加入时间及顺序信息，则可以完成对时间和顺序的认证数字签名是一种认证手段，其中的一些方法可以用来抗发送方的否认攻击。2020/1/29南京邮电大学6报文鉴别的三种方式1.Messageencryption：用整个消息的密文作为认证标识接收方必须能够识别错误2.MAC：一个公开函数，加上一个密钥产生一个固定长度的值作为认证标识3.Hashfunction（哈希/散列函数）：一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识2020/1/29南京邮电大学7MessageAuthenticationCode使用一个双方共享的秘密密钥生成一个固定大小的小数据块，并加入到消息中，称MAC，或密码校验和(cryptographicchecksum)用户A和用户B，共享密钥K，对于消息M，MAC=CK(M)如果接收方计算的MAC与收到的MAC匹配，则接收者可以确信消息M未被改变接收者可以确信消息来自所声称的发送者如果消息中含有序列号，则可以保证正确的消息顺序MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少2020/1/29南京邮电大学8MAC应用方式（1）MC||CKKCompareMCk(M)缺点报文鉴别2020/1/29南京邮电大学9MAC应用方式（2）MC||K1CK1CompareEEk2【M||Ck1(M)】K2DK2MCk1(M)消息认证和保密性：明文相关2020/1/29南京邮电大学10MAC应用方式（3）MC||K1CK1CompareECk1(Ek2(M))K2DK2MCk1(M)Ek2(M)消息认证和保密性：密文相关2020/1/29南京邮电大学11关于MAC算法MAC不等于数字签名因为通讯双方共享同一个密钥MAC有固定的长度MAC结构的重要性，例如，密钥足够长+加密算法足够好安全M=(X1,X2,…,Xt)对M产生校验和M=X1X2…XtMAC=EK(M)攻击者选择M=(Y1,Y2,…,Yt-1,Yt),使得Yt满足:Yt=Y1Y2…Yt-1M于是M=MCK(M)=CK(M)所以，尽管攻击者不知道K，仍然可以伪造消息M参见P119页上2020/1/29南京邮电大学12MACbasedonDESANSI标准(X9.17)即为CBC模式结构，初始向量为0该方法适用于其他加密算法算法：M=(D1,D2,…,DN)O1=EK(D1)Oj+1=EK(Dj+1Oj),1jtMAC=Ot2020/1/29南京邮电大学13本讲内容报文鉴别码1散列函数2常见的散列算法3小结42020/1/29南京邮电大学14散列函数HashFunctionMAC需要对全部数据进行加密MAC速度慢Hash是一种直接产生认证码的方法没有密钥消息中任何一位的改变会导致Hash码的改变Hash函数:h=H(x),要求:散列算法是公开的不同的报文不能产生相同的散列码H(x)能够快速计算对于任意报文无法预知它的散列码无法根据散列码倒推报文可作用于任何尺寸数据且均产生定长输出2020/1/29南京邮电大学15散列函数Hash函数:h=H(x)单向性:给定h，找到x使h=H(x)在计算上不可行抗弱碰撞性：WeakCollisionResistence(WCR):给定x，找到yx使H(x)=H(y)在计算上不可行抗强碰撞性：StrongCollisionResistence(SCR):找到任意的yx使H(x)=H(y)在计算上不可行2020/1/29南京邮电大学16Hash函数的基本用途（a）MH||HCompareEEk[M||H(M)]KDKMH(M)2020/1/29南京邮电大学17Hash函数的基本用途（b）MH||HCompareMEEk[H(M)]KDK不要求保密，处理代价小2020/1/29南京邮电大学18Hash函数的基本用途（c）MH||HCompareMEEkRa[H(M)]KRa私钥DKUa数字签名2020/1/29南京邮电大学19Hash函数的基本用途（d）MH||HCompareEEk[M||EkRa[H(M)]]KDKMEkRa(H(M))EKRa私钥DKRa常用，保密并且数字签名2020/1/29南京邮电大学20散列函数的问题Hash值冲突会有什么问题？Hash的用途会这样的冲突吗？能定制这样的冲突吗？2020/1/29南京邮电大学21生日攻击理论基础理论基础若k1.182m/22m/2,则k个在[1,2m]的随机数中有两个数相等的概率不低于0.5因此，当Hash算法选用N位的Hash值时，两组消息（选择k＝2N/2）中有一对消息产生相同Hash值的概率超过0.5对策：Hash值足够长，64-〉128-〉160-〉2562020/1/29南京邮电大学22hash函数通用模型由Merkle于1989年提出几乎被所有hash算法采用具体做法:把原始消息M分成一些固定长度的块Yi最后一块padding并使其包含消息M的长度设定初始值CV0压缩函数f,CVi=f(CVi-1,Yi-1)最后一个CVi为hash值2020/1/29南京邮电大学23hash函数模型图bY0nIV=CV0fbY1nfbYL-1nCVL-1fCV1nnIV=initialvalue初始值CV=chainingvalue链接值Yi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度)CVL2020/1/29南京邮电大学24本讲内容报文鉴别码1散列函数2常见的散列算法3小结42020/1/29南京邮电大学25MD5算法作者：RonRivest算法输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位采纳位标准：RFC13212020/1/29南京邮电大学26MD5:示意图2020/1/29南京邮电大学27MD5步骤第一步：padding补长到512的倍数最后64位为消息长度的低64位一定要补长(64+1--64+512)，内容为100…0第二步把结果分割为512位的块：Y0,Y1,…YL-1第三步初始化MDbuffer，128位常量(4个字)，进入循环迭代，共L次每次：一个输入128位，另一个输入512位，结果输出128位，用于下一轮输入第四步最后一步的输出即为散列结果128位2020/1/29南京邮电大学28MD5的每一步运算示意图具体参见P122-1242020/1/29南京邮电大学29关于MD5MD5不是足够安全的,128位hash值太短Dobbertin在1996年找到了两个不同的512-bit块,它们在MD5计算下产生相同的hash2004年8月17日在美国加州圣巴巴拉的国际密码学会议（Crypto’2004），来自山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。2020/1/29南京邮电大学30SecureHashAlgorithm简介1992年NIST制定了SHA(128位)1993年SHA成为标准1994年修改产生SHA-1(160位)1995年SHA-1成为新的标准SHA-1要求输入消息长度264SHA-1的摘要长度为160位基础是MD42020/1/29南京邮电大学31SHA-1算法结构与MD5类似第一步：pading与MD5相同，补齐到512的倍数第二步分块第三步初始化MDbuffer，160位常量(5个字)进入循环，160输入+512输入-〉160输出第四步最后的输出为SHA-1的结果2020/1/29南京邮电大学32压缩函数2020/1/29南京邮电大学33SHA-1算法结论SHA-1使用big-endian抵抗生日攻击:160位hash值没有发现两个不同的512-bit块,它们在SHA-1计算下产生相同的“hash”速度慢于MD5安全性优于MD52020/1/29南京邮电大学34RIPEMD-160简介欧洲RIPE项目的结果RIPEMD为128位更新后成为RIPEMD-160基础是MD5算法输入：任意长度的消息输出：长度为160位的消息摘要处理：以512位数据块为单位2020/1/29南京邮电大学35RIPEMD-160的压缩函数2020/1/29南京邮电大学36HMAC简介MAC可用块加密算法产生MAC算法速度慢加密算法出口受限制hash函数可用来构造MACHMAC为其中之一2020/1/29南京邮电大学37HMAC示意图小结报文鉴别（消息认证）是用来验证消息完整性的一种机制。报文鉴别确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放），且发送方声称的身份真实有效。对称密码在那些相互共享密钥的用户间提供认证。用消息发送方的私钥加密消息也可提供一种形式的认证。用于消息认证的最常见的密码技术是报文鉴别码（消息认证码）和安全散列函数。MAC是一种需要使用秘密钥的算法，以可变长度的消息和秘密钥作为输入，产生一个认证码。拥有秘密钥的接受方产生一个认证码来验证消息的完整性。散列函数将可变长度的消息映射为固定长度的散列值，或叫消息摘要。对于消息认证码，安全散列函数必须以某种方式和秘密钥捆绑起来。2020/1/29南京邮电大学392020/1/29南京邮电大学40问题1.消息认证是为了对付那些攻击？2.消息认证或数字签名有哪两层功能？3.产生消息认证有哪些方法？4.MAC和Hash函数之间的区别是什么？5.为了攻击MAC算法，需要恢复密码吗？6.安全的Hash函数需要的特性是什么？7.抗弱碰撞和抗强碰撞之间的区别是什么？8.了解MD4MD5SHAHMAC？南京邮电大学[e-mail]