散列函数与消息认证.ppt

1、2020/8/26,Page: 1,散列函数与认证,杨秋伟 湖南大学 计算机与通信学院,2020/8/26,Page: 2,散列函数与认证组成,认证 HASH函数的基本概念 MD5 SHA-1,2020/8/26,Page: 3,散列函数与认证：认证概述,保密服务与认证服务的区别 保密的目的是防止对手破译系统中的机密信息； 认证(Authentication)是防止主动攻击的重要技术，如伪装、窜扰等，包括对消息的内容、顺序、和时间的窜改以及重发等。 认证的分类 实体认证：验证信息的发送者是真的，而不是冒充的，包括信源、信宿等的认证和识别； 消息认证：验证信息的完整性，验证数据在传送或存储过程中

2、未被窜改、重放或延迟等。,2020/8/26,Page: 4,认证：认证系统模型,认证系统模型 发送者通过一个公开信道将消息送给接收者； 接收者不仅想收到消息本身，而且还要验证消息是否来自合法的发送者以及消息是否经过窜改。,2020/8/26,Page: 5,认证：认证系统的组成和基本设计标准,认证系统的组成 认证编码器 认证译码器 认证系统的基本设计标准 特定的接收者能够检验和证实消息的合法性、真实性和完整性； 消息的发送者和接收者不能抵赖； 除了合法的消息发送者，其它人不能伪造合法的消息。,认证函数,2020/8/26,Page: 6,认证：认证函数,认证系统的工作原理 发送方利用底层的认

3、证函数产生一个用来认证的认证标识； 消息接收方利用上层的认证协议基于认证标识验证真实性。 认证函数的分类 加密函数：用整个消息的密文作为消息认证的认证标识； 消息认证码(MAC)：指消息被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和； 散列函数：一个不需要密钥的公开函数，将任意长度的输入消息映射成一个固定长度的输出值，并以此值作为认证标识别。,2020/8/26,Page: 7,认证：基于消息加密的认证,采用对称加密体制实现加密和认证 基于密钥的保密性，在提供数据加密的同时可以实现认证； 对称加密体制实现认证的不足 额外的差错检验：确保消息的完整性帧校验序列

4、。 不提供数字签名：接收方可以伪造，发送方可以否认。,2020/8/26,Page: 8,认证：基于消息加密的认证,采用非对称加密体制实现认证 基于私钥的保密性，提供数字签名的同时，可以实现认证； 对称加密体制实现认证的不足 额外的差错检验：确保消息的完整性帧校验序列,2020/8/26,Page: 9,认证：基于消息加密的认证,采用非对称加密体制实现加密、认证和签名 在发送者用自己的私钥签名以后，用接收者的公钥进行加密。 非对称加密体制实现加密、认证和签名的不足 一次完整的通信需要执行公钥算法的加密、解密操作各两次。,2020/8/26,Page: 10,认证：消息认证码,消息认证码 指消息

5、被一密钥控制的公开函数作用后产生的、用作认证符的、固定长度的数值，也称为密码校验和。 设A欲发送给B的消息是m，操作过程如下 A首先计算MAC = Ck(m)，其中Ck(.)是密钥控制的公开函数，然后向B发送m | MAC； B收到后做与A相同的计算，求得一新MAC，并与收到的MAC做比较。,2020/8/26,Page: 11,认证：基于消息认证码的认证,消息认证码(Message Authentication Code，简称MAC)工作原理 通信双方共享一个密钥k； 发送者使用密钥k和明文m一起产生一个短小的定长数据分组 MAC = Ck(m) 接收者执行步骤二，将结果与收到的MAC进行比

6、对。如果二者相等，则可判断 接收者确信报文未被更改过； 接收者确信报文来自声称的发送者。 反之，则认证不通过(身份无效或者消息无效)。,2020/8/26,Page: 12,认证：基于消息认证码的认证,MAC实现认证的不足 不提供数字签名(认证编码密钥和认证译码密钥相同) 不提供消息机密性(MAC函数无需可逆) 改进版本 在产生MAC之前或者之后实现加密机制，以提供消息机密性 与明文相关 Ek2(m | Ck1(m) 与密文相关 Ek2(m) | Ck1(Ek2(m),2020/8/26,Page: 13,认证：基于散列函数的认证,散列函数H：是一种公开的单向密码体制函数，将任意长的消息映射为

7、较短的、固定长度的值H(m) ，又被称为HASH函数、哈希函数) 单向性：将明文映射到密文，并且映射是不可逆的； 固定长度性：可以将任意长度的输入映射为固定长度的输出。 散列值 将任意长度的消息或者数据块单向地映射成固定长度的输出结果，此输出结果被称为散列值(又被称为杂凑码、数字指纹、消息摘要) 散列函数在数据完整性验认证、数字签名等领域有广泛应用。,2020/8/26,Page: 14,HASH函数：设计目标,函数的输入可以是任意长； 函数的输出是固定长； 已知x，求H(x)较为容易，可以用硬件或软件实现； 已知h，求使得H(x) = h的x在计算上是不可行的； 已知x，找出y(yx)使得H

8、(x) = H(y)在计算上是不可行的； 找出任意两个不同的输入x,y，使得H(x) = H(y)在计算上是不可行的；,单向HASH函数,弱单向HASH函数,强单向HASH函数,2020/8/26,Page: 15,HASH函数：设计目标的内涵,前三条是HASH函数用于消息认证的基本要求 第四条单向性用于带秘密值的认证技术 假设待发送消息为m，c = H(s|m)，如果能求c的逆s|m，则秘密值s泄露。 弱单向性用于防止HASH值被加密时伪造 假设已知x能找到y，使得H(x) = H(y)成立，即使HASH值被加密，也可以用y伪造x； 强单向性用于抵抗生日攻击,2020/8/26,Page:

9、16,HASH函数：生日攻击,第类生日攻击(杂凑函数H有n个可能的输出，输出为m比特长) H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y) = H(x)的概率为0.5时，k有多大？ 问题分析 输入y产生的输出使得H(y) = H(x)的概率为1/n，反之等式不成立的概率为(1- 1/n)，所有都不相等的概率为(1-1/n)k，则至少一个相等的概率为(1-(1-1/n)k)； (1 + x)k = 1 + kx, |x|1, (1-(1-1/n)k) 1-(1-kx) = k/n = 0.5k = n/2 输出个数为n = 2m，则k = 2m-1,2020/8/

10、26,Page: 17,HASH函数：生日攻击,第类生日攻击(杂凑函数H有n个可能的输出，输出为m比特长) 如果对H随机取k个输入，则至少有两个输入产生相同输出的概率大于0.5，k应该有多大？ 寻找函数H的具有相同输出的两个任意输入的攻击方式称为第类生日攻击。 相关结论 k 2m/2 一台平均速度的计算机针对MD5的生日攻击，至少需要运行数百年才能找到符合要求的字符串,2020/8/26,Page: 18,HASH函数：生日攻击,攻击过程(Alice发送消息给Bob) Alice用自己的私钥对消息的HASH值加密，加密结果作为对消息的签名连同明文消息一起发送给接收者； 敌手对Alice发送的消

11、息m以及一个假冒的消息m产生出2|m|/2个变形的消息，每个变形的消息本质上的含义与原消息相同； 敌手在产生的两个消息集中找出HASH值相同的一对消息m，m，直到成功为止(由上述讨论可知敌手成功的概率大于0.5)； 敌手将m提交给Alice签名，由于m和m的HASH值相同，所以可将Alice对m的签名当成m的签名，将签名m与一起发给接收者。,2020/8/26,Page: 19,HASH函数：王小云与生日攻击,2004年8月17日在美国加州圣巴巴拉召开的 Crypto 2004传出的消息，在本次会议上，来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告

12、。 王小云教授等人的报告指出MD5算法不再具有唯一性的特征 王小云教授等人的破译方法大致可以说是一种针对MD5进行生日攻击的改进算法，使用这种算法，有可能在几个小时的时间里找到两个不同的字符串，使得它们产生的MD5值相同。 论文作者：王小云、冯登国、来学嘉、于红波,2020/8/26,Page: 20,HASH函数：迭代型HASH函数,迭代型HASH函数的设计思想 将输入M分为L个分组：Y0, Y1, , YL-1。每一个分组的长度为b比特，最后一个分组不足则填充，且最后一个分组还包括整个输入的长度值； 重复使用一个压缩函数f (两个输入一个输出，算法指定初值IV) 一项输入是上一轮输出的n比

13、特值CVi-1，称为链接变量； 另一项是算法本轮的b比特输入分组Yi； 输出为n 比特值CVi (通常b n)。 最后一轮输出的链接变量CVL即为最终产生的HASH值。,2020/8/26,Page: 21,HASH函数：迭代型HASH函数,压缩函数f的算法表达 CV0 = IV = n比特长的初值 CVi = f(CVi-1, Yi-1), 1i L H(M) = CVL,2020/8/26,Page: 22,MD5：概述,在上个世纪90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc.的Ronald L. Rives

14、t开发出来MD5(Message-digest Algorithm 5)，它是经MD2、MD3和MD4发展而来。 MD2、MD4和MD5都是通过一个随机长度的信息产生一个128位的信息摘要。这些算法的结构非常相似，但MD2为8位机器做过设计优化的，而MD4和MD5是面向32位的机器。 MD5以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个128位散列值。,2020/8/26,Page: 23,MD5：算法框图,2020/8/26,Page: 24,MD5：算法组成,算法分为四个部分 填充 附加消息的长度 对MD缓冲区初始化 以

15、分组为单位对消息进行处理,2020/8/26,Page: 25,MD5：填充,填充的目的 使消息长度恰好是512位的整数倍，同时确保不同的消息在填充后不相同。 填充的步骤 使得消息比特长在模512下为448，即填充后消息的长度为512的某一倍数减64。 首先在消息末端附一个“1” 然后再后接所需要的多个“0” 即使长度已满足要求，仍需填充，例如：消息长为448比特，需填充512比特，使得其长度为960。(填充的长度大于1小于等于512),2020/8/26,Page: 26,MD5：附加消息长度,附加消息长度 用步骤留出的64比特以little-endian方式来表示消息被填充前的长度。 如果

16、消息长大于264，则以264为模数取模 little-endian方式(相反的方式称为big-endian方式) 按数据的最低有效字节(或最低有效位)优先的顺序存储数据，即将最低有效字节存于低地址字节。 例如“0 x12345678” 低地址 高地址 | 12 | 34 | 56 | 78 |,两大CPU派系：Motorola的PowerPC系列采用big-endian方式，Intel的x86系列CPU采用little-endian方式。,2020/8/26,Page: 27,MD5：对MD缓冲区初始化,MD缓冲区 算法使用128比特长的缓冲区以存储中间结果和最终HASH值； 缓冲区可以表示为

17、4个32位的寄存器(A, B, C, D)，每个寄存器都以little-endian方式存储数据。 四个32位变量初始化(链接变量) A = 0 x01234567 B = 0 x89abcdef C = 0 xfedcba98 D = 0 x76543210 四个寄存器实际存储是怎样的？,2020/8/26,Page: 28,MD5：压缩函数HMD5,以分组为单位对消息进行处理 每一分组都经一压缩函数HMD5处理； HMD5是算法的核心，其中又有四轮处理过程，每轮处理过程结构一样，但所用的逻辑函数不一样，分别为F, G, H, I。 四轮处理(F, G, H, I) 每轮的输入为当前消息分组

18、Yq和缓冲区A,B,C,D，输出仍放入缓冲区； 每轮处理过程需加上常数表T中的四分之一个元素。,2020/8/26,Page: 29,MD5：压缩函数HMD5,常数表T 常数表有64个元素，第i个元素Ti为232abs(sin(i)的整数部分 sin为正弦函数； i以弧度为单位； abs为取绝对值。 将T划分为T1,16, T17,32, T33,48, T49,64。 第四轮 第四轮的输出再与第一轮的输入CVq按模232相加，得到压缩函数HMD5的输出。,2020/8/26,Page: 30,MD5：压缩函数HMD5,压缩函数的迭代 压缩函数有四轮处理过程，每轮又对缓冲区ABCD进行16次迭

19、代运算。,2020/8/26,Page: 31,MD5：压缩函数HMD5,一步迭代的形式化描述 a + b + CLSs(a + g(b,c,d) + Xk + Ti) a,b,c,d为缓冲区的四个字，运算完成后再右循环一个字，得到这一步的输出； g是基本逻辑函数F,G,H,I之一； CLSs是左循环移s位； Ti为表T中的第i个字； Xk = Mq16 + k，即消息第q个分组中的第k个字(k = 1,16)； “+”为模232加法。,2020/8/26,Page: 32,MD5：压缩函数HMD5,轮处理：四轮处理过程中，每轮以不同的次序使用16个字 第一轮以字的初始次序使用； 第二轮到第四

20、轮，分别对字的次序i做置换后得到一个新的次序，然后使用新次序使用16个字； 第二到第四轮三个置换分别为 v2(i) = (1 + 5i) mod 16 v3(i) = (1 + 5i) mod 16 v4(i) = (1 + 5i) mod 16,2020/8/26,Page: 33,MD5：压缩函数HMD5,逻辑函数：四轮处理过程中，每轮分别使用不同的逻辑函数F,G,H,I 每个逻辑函数输入为3个32比特的字，输出是一个32比特的字； 运算为逐比特的逻辑运算，及输出的第n比特是3个输入的第n比特的函数；,2020/8/26,Page: 34,MD5：算法的形式化描述,形式化描述：消息的L个分

21、组都被处理完毕后，最后一个HMD5的输出即为消息摘要。形式化描述如下 CV0 = IV CVq+1 = CVq + RFIYq, RFHYq, RFGYq, RFFYq, CVq MD = CVL 其中：IV是缓冲区ABCD的初值；L是消息初始处理后的分组数；Yq是消息的第q个512比特长的分组；CVq是处理消息的第q个分组时输入的链接变量；RFx为使用逻辑函数x的轮函数；“+”为对应模232加法；MD为最终的HASH值。,2020/8/26,Page: 35,MD5：安全性,Rivest猜想作为128比特长的HASH值来说，MD5的强度达到最大 例如，找出具有相同HASH值的两个消息执行O(

22、264)次运算，而寻找具有给定HASH值的一个消息需要O(2128)次运算。 2004年山东大学王小云等成功找出了MD5的碰撞 发生碰撞的消息由两个1024比特长的串M、Ni构成； 设消息M|Ni的碰撞是M|Ni，在IBM P960上找M和M花费时间大约为一小时； 找出M和M，则只需15至5分钟就能找出Ni和Ni。,2020/8/26,Page: 36,SHA-1：概述,SHA-1的发展历史 SHA是美国NIST和NSA共同设计的安全散列算法(Secure Hash Algorithm)，用于数字签名标准DSS(Digital Signature Standard)。 修改版SHA1于1995

23、年作为美国联邦信息处理标准公告发布。 SHA-1的值域空间 输入：长度小于264位的消息 输出：160位的消息摘要。,2020/8/26,Page: 37,SHA-1：算法框图,2020/8/26,Page: 38,SHA-1：算法组成,算法分为四个部分 填充 将消息填充为512位的整数倍，填充方法和MD5完全相同 附加消息的长度 与MD5完全相同 对MD缓冲区初始化 以512比特分组为单位对消息进行处理,2020/8/26,Page: 39,SHA-1：对MD缓冲区初始化,SHA-1的缓冲区(五个32位的寄存器) 缓冲区：A、B、C、D、E 初始化A、B、C、D、E A = 0 x67452301 B = 0 xEFCDAB89 C = 0 x98BADCFE D = 0 x10325476 E = 0 xC3D2E1F0,2020/8/26,Page: 40,SHA-1：以512比特为分组对消息进行处理,SHA运算主循环包括四轮，每轮20次操作 每一步迭代运算的运算