密码学哈希函数528

散列函数《现代密码学》第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函数在物联网的应用举例•物联网（TheInternetofthings）的定义是：通过射频识别（RFID）、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，把任何物品与互联网连接起来，进行信息交换和通讯，以实现智能化识别、定位、跟踪、监控和管理的一种网络。•描绘“物联网”时代的图景：当司机出现操作失误时汽车会自动报警；公文包会提醒主人忘带了什么东西；衣服会“告诉”洗衣机对颜色和水温的要求，等等。Hash函数在物联网的应用举例个人隐私问题暴露2、散列函数的使用方式基本使用方式，共有以下6种（图6.3）①消息与杂凑码链接后用单钥加密算法加密。由于所用密钥仅为收发双方A、B共享，因此可保证消息的确来自A并且未被篡改。同时还由于消息和杂凑码都被加密，这种方式还提供了保密性，见图6.3(a)。MH||EEK[M||H(M)]KDMH比较图1（a）杂凑函数使用方式之一K②用单钥加密算法仅对杂凑码加密。这种方式用于不要求保密性的情况下，可减少处理负担。将EK[H(M)]看作一个函数，函数的输入为消息M和密钥K，输出为固定长度。MHEEK[H(M)]KDM比较||KH图1（b）杂凑函数使用方式之二MHEESKA[H(M)]SKADM比较||PKAH图1（c）杂凑函数使用方式之三③用公钥加密算法和发送方的秘密钥仅加密杂凑码。和②一样，这种方式提供认证性，又由于只有发送方能产生加密的杂凑码，因此这种方式还对发送方发送的消息提供了数字签字，事实上这种方式就是数字签字。④消息的杂凑值用公钥加密算法和发送方的秘密钥加密后与消息链接，再对链接后的结果用单钥加密算法加密，这种方式提供了保密性和数字签字。MHEESKA[H(M)]SKADM比较||PKAH图1（d）杂凑函数使用方式之四EKDK⑤使用这种方式时要求通信双方共享一个秘密值S，A计算消息M和秘密值S链接在一起的杂凑值，并将此杂凑值附加到M后发往B。因B也有S，所以可重新计算杂凑值以对消息进行认证。由于秘密值S本身未被发送，敌手无法对截获的消息加以篡改，也无法产生假消息。这种方式仅提供认证。MHH(M||S)]M比较||H||S||S图1（e）杂凑函数使用方式之五⑥这种方式是在⑤中消息与杂凑值链接以后再增加单钥加密运算，从而又可提供保密性。MHH(M||S)]M比较||H||S||SEKDK图1（f）杂凑函数使用方式之六由于加密运算的速度较慢，代价较高，而且很多加密算法还受到专利保护，因此在不要求保密性的情况下，方式②和⑤将比其他方式更具优势。Hash散列函数一般模型mHASH散列函数h(m)任意长度固定长度消息1.3需求和安全性散列函数的目的是为需认证的数据产生一个“指纹”。为了能够实现对数据的认证，散列函数应满足以下条件：①函数的输入可以是任意长。②函数的输出是固定长。③已知x，求H(x)较为容易，可用硬件或软件实现。④已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数。⑤已知x，找出y(y≠x)使得H(y)=H(x)在计算上是不可行的。如果单向散列函数满足这一性质，则称其为弱单向散列函数。⑥找出任意两个不同的输入x、y，使得H(y)=H(x)在计算上是不可行的。outputhH（M）h是多对一映射MMoutputh由m计算h(m)容易outputhM由h(m)计算上m不容易散列算法的概念及结构outputhH抗弱碰撞性M给定H(M)mm‘散列算法的概念及结构outputH(m)=H(m’)H抗强碰撞性Mmm‘以上6个条件中，前3个是散列函数能用于消息认证的基本要求。第4个条件（即单向性）则对使用秘密值的认证技术(见图1(e))极为重要。假如散列函数不具有单向性，则攻击者截获M和C=H(S‖M)后，求C的逆S‖M，就可求出秘密值S。第5个条件使得敌手无法在已知某个消息时，找到与该消息具有相同杂凑值的另一消息。这一性质用于杂凑值被加密情况时(见图3(b)和图3(c))防止敌手的伪造，由于在这种情况下，敌手可读取传送的明文消息M，因此能产生该消息的杂凑值H(M)。但由于敌手不知道用于加密杂凑值的密钥，他就不可能既伪造一个消息M，又伪造这个消息的杂凑值加密后的密文EK[H(M)]。然而，如果第5个条件不成立，敌手在截获明文消息及其加密的杂凑值后，就可按以下方式伪造消息：首先求出截获的消息的杂凑值，然后产生一个具有相同杂凑值的伪造消息，最后再将伪造的消息和截获的加密的杂凑值发往通信的接收方。第6个条件用于抵抗生日攻击。MHH(M||S)]M比较||H||S||S图1（e）杂凑函数使用方式之五•原像：对于Hash函数h=H(x)，称x为H原像。•碰撞：因为H是多对一映射，所以对于任意给定的Hash值h，对应有多个原像。如果满足x≠y且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/n]k，所以y取k个随机值得到函数的k个输出中至少有一个等于H(x)的概率为1-[1-1/n]k。•由(1+x)k≈1+kx，其中|x|1，可得1-[1-1/n]k≈1-[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，则不可能使得任意两个数据都不相同，因此假定k≤365。k个数据项中任意两个都不相同的所有取值方式数为365!365364(3651)(365)!kk即第1个数据项可从365个中任取一个，第2个数据项可在剩余的364个中任取一个，依次类推，最后一个数据项可从365-k+1个值中任取一个。如果去掉任意两个都不相同这一限制条件，可得k个数据项中所有取值方式数为365k。所以可得365!(365,)(365)!365365!(365,)1(365,)1(365)!365kkQkkPkQkk当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，则。!(,)1()!knPnknkn1.18knn1.1836522.54k3.生日攻击生日攻击是基于下述结论：设散列函数H有2m个可能的输出（即输出长m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则。称寻找函数H的具有相同输出的两个任意输入的攻击方式为第Ⅱ类生日攻击。222mmk第Ⅱ类生日攻击可按以下方式进行：①设用户将用图3(c)所示的方式发送消息，即A用自己的秘密钥对消息的杂凑值加密，加密结果作为对消息的签字，连同明文消息一起发往接收者。②敌手对A发送的消息M产生出2m/2个变形的消息，每个变形的消息本质上的含义与原消息相同，同时敌手还准备一个假冒的消息M′，并对假冒的消息产生出2m/2个变形的消息。生日攻击③敌手在产生的两个消息集合中，找出杂凑值相同的一对消息,，由上述讨论可知敌手成功的概率大于0.5。如果不成功，则重新产生一个假冒的消息，并产生2m/2个变形，直到找到杂凑值相同的一对消息为止。④敌手将提交给A请求签字，由于与的杂凑值相同，所以可将A对的签字当作对的签字，将此签字连同一起发给意欲的接收者。,MMMMMMMM上述攻击中如果杂凑值的长为64比特，则敌手攻击成功所需的时间复杂度为O(232)。将一个消息变形为具有相同含义的另一消息的方法有很多，例如对文件，敌手可在文