HASH函数

HASH函数与消息认证•学习要点：–了解HASH函数的基本概念、一般结构–了解SHA散列算法的基本处理方法–了解消息认证的目的及其实现方法哈希（Hash)密码学中哈希的几个基本要求输入可为任意长度输出定长函数单向足够小的冲突可能性Hash“我们的五年计划是…”“B*U@9374392l;qHUHW”杂凑函数任意长的消息固定长的消息摘要碰撞消息杂凑函数消息摘要杂凑函数的用途•杂凑可以把任意长的消息转换成固定大小的消息摘要。•可以使公钥密码系统在签名与验证的时候，减少运算，节省时间，提升效率，达到消息确认的目的。•确保公钥签名的安全性。基本思想：把哈希函数值h(x)看成x的消息摘要（messagedigest），或看成x的压缩代表图像（compactrepresen-tativeimage），当x中任一bit化身变化时都将引起哈希函数值的变化。这样就可以用对h(x)的签名代替对x签名1.Hash函数的概念散列函数h是一公开函数，用于将任意长的消息m映射为较短的、固定长度的一个值h(m)，作为认证符，称函数值h(m)为杂凑值、杂凑码或消息摘要。杂凑码是消息中所有比特的函数，改变消息中任何一个比特或几个比特都会使杂凑码发生改变。一.Hash函数的概念1.基本要求①公开性──算法公开、无需密钥②定长性──输入长度任意、输出长度固定③易算性──由消息容易计算散列值2.安全性要求①单向性──由消息的散列值倒算出消息在计算上不可行②抗弱碰撞性──对于任何给定消息及其散列值，不可能找到另一个能映射出该散列值的消息（任何给定原像都找不到其等价原像）③抗强碰撞性──对于任何两个不同的消息，它们的散列值必定不同（没有任何一对等价原像）密码学Hash函数h(x)必须满足下列特性1）压缩：对于任意大小的输入x，输出长度y=h(x)很小。实际应用中H产生定长输出h(x);2）效率：对任意给定的x,h(x)要相对易于计算,使得软硬件实现都实际可行;3）单向：对任意给定的值y,寻求x使得h(x)=y在计算上是不可行的，即求Hash的逆很困难;4）弱抗碰撞性：任意给定分组x,寻求不等于x的y,使得h(y)=h(x)在计算上不可行;5）强抗碰撞性：寻求对任何的(x,y)对使得h(x)=h(y)在计算上不可行。好的杂凑函数特性•高灵敏度－只要消息有些許的不同，经过杂凑函数转换出的消息摘要就会有极大的不同•低碰撞性－当消息转换成消息摘要時，不同消息转换成相同消息摘要的机会很低•无序性－无论消息的结构如何，所转换出的消息摘要都是沒有規律性的定义：理想的Hash函数是从所有可能的输入值到有限可能的输出值集合的一个随机映射如果散列函数对不同的输入可产生相同的输出，则称该函数具有碰撞性。攻击杂凑函数•攻击杂凑函数的原理是－伪造消息，使其与原來消息的杂凑码相同•常見的攻击方法:－生日攻击法(BirthdayAttack)－中点交会攻击法(Meet-In-The-Middle)1）相关问题已知一散列函数h有n个可能的输出，h(x)是一个特定的输出，如果对h随机取k个输入，则至少有一个输入y使得h(y)=h(x)的概率为0.5时，k有多大？以后为叙述方便，称对散列函数h寻找上述y的攻击为第Ⅰ类生日攻击。2.生日攻击因为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。1-[1-1/n]k≈1-[1-k/n]=k/n给定h(x)，如果对h随机取k个输入，至少有一个输入y使得h(y)=h(x)的概率为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。•生日攻击(基于生日悖论)在k个人中,找一个与某人生日相同的人的概率超过0.5时,只需k183;而在此人群中,至少有两个人生日相同的概率超过0.5,只需k23.将生日悖论推广为下述问题：已知一个在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二.Hash函数的应用1.由Hash函数产生消息的散列值2.以消息的散列值来判别消息的完整性3.用加密消息的散列值来产生数字签名4.用口令的散列值来安全存储口令（认证系中的口令列表中仅存储口令的Hash函数值，以避免口令被窃取。认证时用输入口令的Hash函数值与其比较）三.构造hash函数的原则现实的hash函数其结构几乎都是迭代型的，如MD5、SHA。压缩函数算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f的内部结构，由于f和分组密码一样是由若干轮处理过程组成，所以对f的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f的碰撞。由于f是压缩函数，其碰撞是不可避免的，因此在设计f时就应保证找出其碰撞在计算上是不可行的。下面介绍几个重要的迭代型散列函数。迭代型散列函数的一般结构3、Hash函数的构造方法1）UseablockcipherE(K,P).StartwithsomeinitialvalueX0andupdateasXi+1=E(Mi,Xi)Xi.FinalvalueXnisthehash.•E(Mi,Xi)Xiiscalled“compressionfunction”2.设计方法和典型算法1)基于模数运算用公开密钥加密实现通常使用CBC（分组链接模式）并以最后一个密文分组作为散列值因速度较慢而不太实用2)基于分组加密用分组密码体制加密实现同样使用CBC（分组链接模式）速度相对较快CBC•EncryptmessagewithblockcipherinCBCmode•IV=0,lastencryptedblockcanserveastag•Insecureforvariable-lengthmessagesAESM1kAESM2kAESMnktag…+++03)专门的构造与密码体制无关通常直接构造复杂的非线性关系达到单向要求目前被广泛应用常用HashFunctions•MD5:“MessageDigest5”inventedbyRivest–Input:multipleof512-bits(padded)–Output:128-bits•SHA1:developedbyNIST&NSA–Input:sameasMD5,512bits–Output:160-bitsMD5算法采用迭代型散列函数的一般结构，算法的输入为任意长的消息，512比特长的分组，输出为128比特的消息摘要。2）MD系列hash函数报文KbitsL512bits=N32bits消息长度(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512填充(1to512bits)512512512128-bit摘要MD5产生消息摘要的过程F,T[1…16],X[i]16stepsG,T[17…32],X[2i]16stepsH,T[33…48],X[3i]16stepsI,T[49…64],X[4i]16steps++++ABCDABCDABCDABCDCVq12832Yq512CVq+1128+ismod232单个512-bit分组的MD5处理过程HMD5的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Yq和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。。MD5算法描述2i=(1+5i)mod163i=(5+3i)mod162i=7imod16基本MD5操作(单步)ABCDABCD+++CLSs+gX[k]T[i]Functiongg(b,c,d)1F(b,c,d)(bc)(bd)2G(b,c,d)(bd)(cd)3H(b,c,d)bcd4I(b,c,d)c(bd)MD4(1990年10月作为RFC1320发表)byRonRivestatMIT•MD4的设计目标•安全性：•速度：32位体系结构下计算速度快.•简明与紧凑：易于编程.•有利的小数在前的结构(Intel80xxx,Pentium)•MD4与MD5的区别•MD4用3轮,每轮16步,MD5用4轮,每轮16步.•MD4中第一轮没有常量加；MD5中64步每一步用了一个不同的常量T[i]；•MD5用了四个基本逻辑函数，每轮一个；MD4用了三个.•MD5每轮加上前一步的结果；MD4没有.Rivest猜想作为128比特长的杂凑值来说，MD5的强度达到了最大，比如说找出具有相同杂凑值的两个消息需执行O(264)次运算，而寻找具有给定杂凑值的一个消息需要执行O(2128)次运算。MD5的安全性目前对MD5的攻击已取得以下结果：•2004年山东大学王小云等成功找出MD5的碰撞SHA-1算法逻辑•输入：最大长度为264位的消息；•输出：160位消息摘要；•处理：输入以512位数据块为单位处理；SHA由美国国家标准技术研究所NIST开发，作为联邦信息处理标准于1993年发表（FIPSPUB180），1995年修订，作为SHA-1(FIPSPUB180-1)，SHA-1基于MD4设计。SHA-1算法逻辑步骤2：添加长度。一个64位块，表示原始消息长度步骤3：初始化MD缓冲区。160位，表示为5个32位的寄存器(A,B,C,D,E)。初始化为：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0big-endianformat步骤1：添加填充位。使