报文鉴别与散列函数

1、第6讲 报文鉴别与散列函数,wangzhiwei 博士 计算机学院 信息安全系 ,2020/7/18,南京邮电大学,2,本讲内容,报文鉴别码,1,散列函数,2,常见的散列算法,3,小结,4,概要,报文鉴别（消息认证）是用来验证消息完整性的一种机制。报文鉴别确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放），且发送方声称的身份真实有效。 对称密码在那些相互共享密钥的用户间提供认证。用消息发送方的私钥加密消息也可提供一种形式的认证。 用于消息认证的最常见的密码技术是报文鉴别码（消息认证码）和安全散列函数。 MAC是一种需要使用秘密钥的算法，以可变长度的消息和秘密钥作为输入，产生一个认

2、证码。拥有秘密钥的接受方产生一个认证码来验证消息的完整性。 散列函数将可变长度的消息映射为固定长度的散列值，或叫消息摘要。对于消息认证码，安全散列函数必须以某种方式和秘密钥捆绑起来。,2020/7/18,南京邮电大学,3,2020/7/18,南京邮电大学,4,报文鉴别的应用场合,在网络通信中，攻击方法 泄密：透露消息给没有密钥的实体 传输分析：分析通信模式，连接频率、时间，消息的数量和大小 伪装：欺诈消息，伪装发送或应答 内容修改：插入、删除、转换和修改消息 顺序修改：对通信双方消息顺序进行修改 计时修改：消息重放或者延迟 发送方否认 接收方否认,2020/7/18,南京邮电大学,5,报文鉴别

3、的作用,报文鉴别(消息认证) 对收到的消息进行验证，证明确实是来自声称的发送方，并且没有被修改过。 如果在消息中加入时间及顺序信息，则可以完成对时间和顺序的认证 数字签名是一种认证手段，其中的一些方法可以用来抗发送方的否认攻击。,2020/7/18,南京邮电大学,6,报文鉴别的三种方式,Message encryption：用整个消息的密文作为认证标识 接收方必须能够识别错误 MAC：一个公开函数，加上一个密钥产生一个固定长度的值作为认证标识 Hash function（哈希/散列函数）：一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识,2020/7/18,南京邮电大学,7

4、,Message Authentication Code,使用一个双方共享的秘密密钥生成一个固定大小的小数据块，并加入到消息中，称MAC，或密码校验和(cryptographic checksum) 用户A和用户B，共享密钥K，对于消息M， MAC=CK(M) 如果接收方计算的MAC与收到的MAC匹配，则 接收者可以确信消息M未被改变 接收者可以确信消息来自所声称的发送者 如果消息中含有序列号，则可以保证正确的消息顺序 MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少,2020/7/18,南京邮电大学,8,MAC应用方式（1）,M,C,|,C,K,K,Compa

5、re,M,Ck(M),缺点,报文鉴别,2020/7/18,南京邮电大学,9,MAC应用方式（2）,M,C,|,K1,C,K1,Compare,E,Ek2【M|Ck1(M)】,K2,D,K2,M,Ck1(M),消息认证和保密性：明文相关,2020/7/18,南京邮电大学,10,MAC应用方式（3）,M,C,|,K1,C,K1,Compare,E,Ck1(Ek2(M),K2,D,K2,M,Ck1(M),Ek2(M),消息认证和保密性：密文相关,2020/7/18,南京邮电大学,11,关于MAC算法,MAC不等于数字签名 因为通讯双方共享同一个密钥 MAC有固定的长度 MAC结构的重要性，例如，密钥

6、足够长+加密算法足够好安全 M=(X1,X2,Xt) 对M产生校验和M=X1X2Xt MAC = EK(M) 攻击者选择M=(Y1,Y2,Yt-1,Yt),使得Yt满足: Yt = Y1Y2Yt-1M 于是M=MCK(M)=CK(M) 所以，尽管攻击者不知道K，仍然可以伪造消息M,参见P119页上,2020/7/18,南京邮电大学,12,MAC based on DES,ANSI标准(X9.17) 即为CBC模式结构，初始向量为0 该方法适用于其他加密算法,算法： M=(D1,D2,DN) O1=EK(D1) Oj+1=EK(Dj+1Oj), 1jt MAC= Ot,2020/7/18,南京邮

7、电大学,13,本讲内容,报文鉴别码,1,散列函数,2,常见的散列算法,3,小结,4,2020/7/18,南京邮电大学,14,散列函数 Hash Function,MAC需要对全部数据进行加密 MAC速度慢 Hash是一种直接产生认证码的方法 没有密钥 消息中任何一位的改变会导致Hash码的改变 Hash函数: h=H(x), 要求: 散列算法是公开的 不同的报文不能产生相同的散列码 H(x)能够快速计算 对于任意报文无法预知它的散列码 无法根据散列码倒推报文 可作用于任何尺寸数据且均产生定长输出,2020/7/18,南京邮电大学,15,散列函数,Hash函数: h=H(x) 单向性: 给定h，

8、找到x使h=H(x)在计算上不可行 抗弱碰撞性： Weak Collision Resistence(WCR):给定x，找到yx使H(x)=H(y)在计算上不可行 抗强碰撞性： Strong Collision Resistence(SCR): 找到任意的yx使H(x)=H(y)在计算上不可行,2020/7/18,南京邮电大学,16,Hash函数的基本用途（a）,M,H,|,H,Compare,E,Ek M | H(M) ,K,D,K,M,H(M),2020/7/18,南京邮电大学,17,Hash函数的基本用途（b）,M,H,|,H,Compare,M,E,EkH(M),K,D,K,不要求保密

9、，处理代价小,2020/7/18,南京邮电大学,18,Hash函数的基本用途（c）,M,H,|,H,Compare,M,E,EkRaH(M),KRa私钥,D,KUa,数字签名,2020/7/18,南京邮电大学,19,Hash函数的基本用途（d）,M,H,|,H,Compare,E,Ek M | EkRaH(M),K,D,K,M,EkRa(H(M),E,KRa 私钥,D,KRa,常用，保密并且数字签名,2020/7/18,南京邮电大学,20,散列函数的问题,Hash值冲突会有什么问题？ Hash的用途 会这样的冲突吗？ 能定制这样的冲突吗？,2020/7/18,南京邮电大学,21,生日攻击理论基

10、础,理论基础 若k1.182m/22m/2, 则k个在1,2m的随机数中有两个数相等的概率不低于0.5 因此，当Hash算法选用N位的Hash值时，两组消息（选择k2N/2）中有一对消息产生相同Hash值的概率超过0.5,对策：Hash值足够长，64-128-160-256,2020/7/18,南京邮电大学,22,hash函数通用模型,由Merkle于1989年提出 几乎被所有hash算法采用 具体做法: 把原始消息M分成一些固定长度的块Yi 最后一块padding并使其包含消息M的长度 设定初始值CV0 压缩函数f, CVi=f(CVi-1,Yi-1) 最后一个CVi为hash值,2020/

11、7/18,南京邮电大学,23,hash函数模型图,b,Y0,n,IV= CV0,f,b,Y1,n,f,b,YL-1,n,CVL-1,f,CV1,n,n,IV = initial value 初始值 CV = chaining value 链接值 Yi = ith input block (第i 个输入数据块) f = compression algorithm (压缩算法） n = length of hash code (散列码的长度) b = length of input block(输入块的长度),CVL,2020/7/18,南京邮电大学,24,本讲内容,报文鉴别码,1,散列函数,2,

12、常见的散列算法,3,小结,4,2020/7/18,南京邮电大学,25,MD5 算法,作者：Ron Rivest 算法 输入：任意长度的消息 输出：128位消息摘要 处理：以512位输入数据块为单位 采纳位标准：RFC1321,2020/7/18,南京邮电大学,26,MD5: 示意图,2020/7/18,南京邮电大学,27,MD5步骤,第一步：padding 补长到512的倍数 最后64位为消息长度的低64位 一定要补长(64+1-64+512)，内容为1000 第二步 把结果分割为512位的块：Y0,Y1,YL-1 第三步 初始化MD buffer，128位常量(4个字)，进入循环迭代，共L次

13、 每次：一个输入128位，另一个输入512位，结果输出128位，用于下一轮输入 第四步 最后一步的输出即为散列结果128位,2020/7/18,南京邮电大学,28,MD5的每一步运算示意图,具体参见 P122-124,2020/7/18,南京邮电大学,29,关于MD5,MD5不是足够安全的, 128位hash值太短 Dobbertin在1996年找到了两个不同的512-bit块,它们在MD5计算下产生相同的hash 2004年8月17日在美国加州圣巴巴拉的国际密码学会议（Crypto2004），来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。,20

14、20/7/18,南京邮电大学,30,Secure Hash Algorithm简介,1992年NIST制定了SHA(128位) 1993年SHA成为标准 1994年修改产生SHA-1(160位) 1995年SHA-1成为新的标准 SHA-1要求输入消息长度264 SHA-1的摘要长度为160位 基础是MD4,2020/7/18,南京邮电大学,31,SHA-1算法,结构与MD5类似 第一步：pading 与MD5相同，补齐到512的倍数 第二步 分块 第三步 初始化MD buffer，160位常量(5个字) 进入循环，160输入+512输入-160输出 第四步 最后的输出为SHA-1的结果,20

15、20/7/18,南京邮电大学,32,压缩函数,2020/7/18,南京邮电大学,33,SHA-1算法结论,SHA-1使用big-endian 抵抗生日攻击: 160位hash值 没有发现两个不同的512-bit块,它们在SHA-1计算下产生相同的“hash” 速度慢于MD5 安全性优于MD5,2020/7/18,南京邮电大学,34,RIPEMD-160简介,欧洲RIPE项目的结果 RIPEMD为128位 更新后成为RIPEMD-160 基础是MD5 算法 输入：任意长度的消息 输出：长度为160位的消息摘要 处理：以512位数据块为单位,2020/7/18,南京邮电大学,35,RIPEMD-1

16、60的压缩函数,2020/7/18,南京邮电大学,36,HMAC简介,MAC可用块加密算法产生 MAC算法速度慢 加密算法出口受限制 hash函数可用来构造MAC HMAC为其中之一,2020/7/18,南京邮电大学,37,HMAC示意图,2020/7/18,南京邮电大学,38,HMAC的定义与特征,对密钥K左边补0以产生一个hash块K+ K+每个字节与ipad(00110110)作XOR以产生Si 对(Si|M)进行hash K+每个字节与opad(01011010)作XOR以产生S0 HMACK(M)=HIV,S0|H(IV,Si|M) HMAC特征: 可直接使用各种hash算法 可使用将来的更加安全和更加快速的hash算法 保持原始hash算法的性能 密钥的使用简单 与hash函数有同等的安全性,小结,报文鉴别（消息认证）是用来验证消息完整性的一种机制。报文鉴别确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放），且发送方声称的身份真实有效。 对称密码在那些相互共享密钥的用户间提供认证。用消息发送方的私钥加密消息也可提供一种形式的认证。 用于消息认证的最常见的密码技术是报文鉴别码（消息认证码）和安全散列函数。 MAC是一种需要使用秘密钥的算法，以可变长度的消息和秘密钥作为输入，产生一个认证码。拥有秘密钥的接受方产生一个认证码来验证