,散列函数,现代密码学第7章,本章主要内容,1、散列函数 2、MD5杂凑算法 3、安全杂凑算法,1.散列函数,1.散列函数的描述,散列算法也叫散列函数、Hash函数、哈希函数、杂凑函数，在现代密码学中扮演着重要角色。 散列函数是一公开函数，通常记为H，用于将任意长的消息M映射为较短的、固定长度的一个值作为认证符，记为H(M)，经常称函数值H(M)为散列值、哈希值、杂凑值、杂凑码或消息摘要、数组指纹等等。 杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。,散列函数的描述,从密码角度看，散列函数也可以看作是一种单向密码体制，即它从一个明文到密文是不可逆映射，只有加密过程，不能解密。散列值是消息中所有比特的函数值，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使散列值发生改变。 在密码学和数据安全技术中，散列函数是实现有效、安全可靠数字签名和认证的重要工具，是安全认证协议中的重要模块 。,密码学Hash函数的应用,消息认证 消息认证是用来验证消息完整性的一种机制或服务。消息认证确保收到的数据确实和发送时的一样（即没有修改、插入、删除或重放），且发送方声称的身份是真实有效的。 当哈希函数用于提供消息认证功能时，Hash函数值通常称为消息摘要。,数字签名 在进行数字签名过程中使用用户的私钥加密消息的Hash值，其它任何知道该用户公钥的人都能够通过数字签名来验证消息的完整性。在这种情况下，攻击者要想篡改消息，则需要知道用户的私钥。,产生单向口令文件: 如操作系统存储口令的Hash值而不是口令本身。 入侵检测和病毒检测： 将每个文件的Hash值H(F)存储在安全系统中，随后就能够通过重新计算H(F)来判断文件是否被修改过。 构建随机函数（PRF）或用做伪随机发生器。,其他应用,具体应用,消息完整性检测 “网站卫士”是一个网络安全软件产品。它的主要功能是通过网络扫描网站的网页，监测网页是否被修改，当发现网页被修改后，系统能够自动报警和恢复。 初始化过程 （1）对监视网站的文件备份到监控主机上。 （2）对每个备份的文件生成一个结构：文件位置、文件的哈希值。 监控过程 监控主机对监控网站进行轮回扫描，对扫描的文件进行如下操作： （1）计算文件的哈希值，并与备份的文件哈希值进行比较，如果相同，转（4）步。 （2）如果不同，上载备份文件替换网站现有文件，转（4）步。 （3）如果备份文件不存在，则删除网站上这个文件，转（4）步。 （4）监控程序扫描下一文件。,Hash函数的用途,消息完整性检测,Hash函数的用途,口令认证 常见的Unix系统口令以及多数论坛/社区系统口令都是经MD5处理后保存其摘要信息串；,Hash函数在银行应用举例,采用Hash函数，银行操作人员不能获取到用户的密码,Hash函数在物联网的应用举例,物联网（The Internet of things）的定义是：通过射频识别（RFID）、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，把任何物品与互联网连接起来，进行信息交换和通讯，以实现智能化识别、定位、跟踪、监控和管理的一种网络。 描绘“物联网”时代的图景：当司机出现操作失误时汽车会自动报警；公文包会提醒主人忘带了什么东西；衣服会“告诉”洗衣机对颜色和水温的要求，等等。,Hash函数在物联网的应用举例,个人隐私问题暴露,2、散列函数的使用方式,基本使用方式，共有以下6种（图6.3）, 消息与杂凑码链接后用单钥加密算法加密。由于所用密钥 仅为收发双方A、B共享，因此可保证消息的确来自A并且未 被篡改。同时还由于消息和杂凑码都被加密，这种方式还提 供了保密性，见图6.3(a)。,M,H,|,E,EKM|H(M),K,D,M,H,比较,图1（a）杂凑函数使用方式之一,K, 用单钥加密算法仅对杂凑码加密。这种方式用于 不要求保密性的情况下，可减少处理负担。将 EKH(M)看作一个函数，函数的输入为消息M和密 钥K，输出为固定长度。,M,H,E,EKH(M),K,D,M,比较,|,K,H,图1（b）杂凑函数使用方式之二,M,H,E,ESKAH(M),SKA,D,M,比较,|,PKA,H,图1（c）杂凑函数使用方式之三, 用公钥加密算法和发送方的秘密钥仅加密杂凑码。 和一样，这种方式提供认证性，又由于只有发送 方能产生加密的杂凑码，因此这种方式还对发送方 发送的消息提供了数字签字，事实上这种方式就是 数字签字。, 消息的杂凑值用公钥加密算法和发送方的秘密钥加 密后与消息链接，再对链接后的结果用单钥加密算法 加密，这种方式提供了保密性和数字签字。,M,H,E,ESKAH(M),SKA,D,M,比较,|,PKA,H,图1（d）杂凑函数使用方式之四,E,K,D,K, 使用这种方式时要求通信双方共享一个秘密值S， A计算消息M和秘密值S链接在一起的杂凑值，并将此 杂凑值附加到M后发往B。因B也有S，所以可重新计 算杂凑值以对消息进行认证。由于秘密值S本身未被发 送，敌手无法对截获的消息加以篡改，也无法产生假 消息。这种方式仅提供认证。,M,H,H(M|S),M,比较,|,H,|,S,|,S,图1（e）杂凑函数使用方式之五, 这种方式是在中消息与杂凑值链接以后再增加单 钥加密运算，从而又可提供保密性。,M,H,H(M|S),M,比较,|,H,|,S,|,S,E,K,D,K,图1（f）杂凑函数使用方式之六,由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，方式和将比其他方式更具优势。,Hash散列函数一般模型,1.3 需求和安全性,散列函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，散列函数应满足以下条件： 函数的输入可以是任意长。 函数的输出是固定长。 已知x，求H(x)较为容易，可用硬件或软件实现。 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数。 已知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的。如果单向散列函数满足这一性质，则称其为弱单向散列函数。 找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。,output,h,H（M）,h是多对一映射,M,散列算法的概念及结构,output,h,H,抗弱碰撞性,M,给定H(M),m,m,散列算法的概念及结构,output,H(m)=H(m),H,抗强碰撞性,M,m,m,以上6个条件中，前3个是散列函数能用于消息认证的基本要求。第4个条件（即单向性）则对使用秘密值的认证技术(见图1(e)极为重要。 假如散列函数不具有单向性，则攻击者截获M和C=H(SM)后，求C的逆SM，就可求出秘密值S。第5个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。 这一性质用于杂凑值被加密情况时(见图3(b)和图3(c)防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息M，因此能产生该消息的杂凑值H(M)。,但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息M，又伪造这个消息的杂凑值加密后的密文EKH(M)。 然而，如果第5个条件不成立，敌手在截获明文消息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的加密的杂凑值发往通信的接收方。 第6个条件用于抵抗生日攻击。,M,H,H(M|S),M,比较,|,H,|,S,|,S,图1（e）杂凑函数使用方式之五,原像：对于Hash函数h=H(x)，称x为H原像。 碰撞：因为H是多对一映射，所以对于任意给定的Hash值h，对应有多个原像。如果满足xy且H(x)=H(y)，则称出现碰撞。 假设函数H的输入消息或数据块长度是b位，输出的长度为n位，且bn，则平均每个Hash值对应2b/n个原像。,抗强碰撞攻击,抗弱碰撞攻击,抗原像攻击,Hash函数安全特性之间的联系,1. 相关问题 已知一散列函数H有n个可能的输出，H(x)是一个特定的输出，如果对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？ 以后为叙述方便，称对散列函数H寻找上述y的攻击为第类生日攻击。,1.4 生日攻击,因为H有n个可能的输出，所以输入y产生的输出H(y)等于特定输出H(x)的概率是1/n，反过来说H(y)H(x)的概率是1-1/n。y取k个随机值而函数的k个输出中没有一个等于H(x)，其概率等于每个输出都不等于H(x)的概率之积，为1-1/nk，所以y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-1-1/nk。,由(1+x)k1+kx，其中|x|1，可得 1-1-1/nk1-1-k/n=k/n 若使上述概率等于0.5，则k=n/2。特别地，如果H的输出为m比特长，即可能的输出个数n=2m，则k=2m-1。,2. 生日悖论 生日悖论是考虑这样一个问题：在k个人中至少有两个人的生日相同的概率大于0.5时，k至少多大？,为了回答这一问题，首先定义下述概率：设有k个整数项，每一项都在1到n之间等可能地取值，则k个整数项中至少有两个取值相同的概率为P(n, k)。 因而生日悖论就是求使得P(365,k)0.5的最小k，为此首先考虑k个数据项中任意两个取值都不同的概率，记为Q(365, k)。如果k365，则不可能使得任意两个数据都不相同，因此假定k365。k个数据项中任意两个都不相同的所有取值方式数为,即第1个数据项可从365个中任取一个，第2个数据项可在剩余的364个中任取一个，依次类推，最后一个数据项可从365-k+1个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得k个数据项中所有取值方式数为365k。所以可得,当k=23时，P(365,23)=0.5073，即上述问题只需23人，人数如此之少。若k取100，则P(365,100)=0.9999997，即获得如此大的概率。之所以称这一问题是悖论是因为当人数k给定时，得到的至少有两个人的生日相同的概率比想象的要大得多。 这是因为在k个人中考虑的是任意两个人的生日是否相同，在23个人中可能的情况数为C223=253。,将生日悖论推广为下述问题：已知一个在1到n之间均匀分布的整数型随机变量，若该变量的k个取值中至少有两个取值相同的概率大于0.5，则k至少多大？ 与上类似， ， 令P(n, k)0.5，可得 。 若取n=365，则 。,3. 生日攻击 生日攻击是基于下述结论：设散列函数H有2m个可能的输出（即输出长m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则 。 称寻找函数H的具有相同输出的两个任意输入的攻击方式为第类生日攻击。,第类生日攻击可按以下方式进行： 设用户将用图3(c)所示的方式发送消息，即A用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。 敌手对A发送的消息M产生出2m/2个变形的消息，每个变形的消息本质上的含义与原消息相同，同时敌手还准备一个假冒的消息M，并对假冒的消息产生出2m/2个变形的消息。,