第7章-Hash函数分解

1/第七章杂凑函数2杂凑函数(Hash函数）•杂凑函数是密码学的一个基本工具，在数字签名、身份认证和消息的完整性检测等方面有着重要的应用•杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。•杂凑码是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑码发生改变。•特点：H打上了输入数字串的烙印，为数字指纹(DigitalFingerPrint)3散列函数的性质（1）一般杂凑函数h(m)算法公开，不需要密钥（2）具有数据压缩功能，可将任意长度的输入数据转换成一个固定长度的输出。（3）对任何给定的m，h(m)易于计算。4Hash函数的应用•在密码学和数据安全技术中，它是实现有效、安全可靠数字签字和认证的重要工具，是安全认证协议中的重要模块。ABMH(M)消息杂凑算法MH(M)TH(M)=H(M')(正常)或H(M)H(M')(错误发生)M'消息H(M')==杂凑算法5Hash函数的应用注：实际应用中，未必一定是如h(m‖k)的计算方式，明文与密钥k的组合方式因不同的实现可以不同。6单向杂凑函数要求•密码学中所用的杂凑函数必须满足一定安全性的要求，要能防伪造，抗击各种类型的攻击，如生日攻击、中途相遇攻击等等。•安全要求：•（1）具有单向性。给定消息的散列值h(m)，要得到消息m在计算上不可行；•（2）具有弱抗碰撞性（Weakcollisionresistance）。对任何给定的消息m，寻找与m不同的消息m’，使得它们的散列值相同，即h(m’)＝h(m)，在计算上不可行。•（3）具有强抗碰撞性（Strongcollisionresistance)。寻找任意两个不同的消息m和m’，使得h(m)＝h(m’)在计算上不可行。7H是多对一映射•杂凑函数是多对一映射，所以必然存在碰撞outputhHMM’H‘8Hash函数的无碰撞性•弱单向杂凑，是在给定M下，考察与特定M的无碰撞性；而强单向杂凑函数是考察输入集中任意两个元素的无碰撞性。•显然，对于给定的输入数字串的集合，后一种碰撞要容易实现。•因为从下面要介绍的生日悖论知，在N个元素的集中，给定M找与M相匹配的M＇的概率要比从N中任取一对元素M，M’相匹配的概率小得多。9单向杂凑函数安全性要求杂凑函数的安全性取决于其抗击各种攻击的能力，对手的目标是找到两个不同消息映射为同一杂凑值。一般假定对手知道杂凑算法，采用选择明文攻击法对杂凑函数的基本攻击方法：（1）穷举攻击（或暴力攻击）：不涉及杂凑算法的结构，能对任何类型的散列函数进行攻击。其中最典型方法是“生日攻击”：给定初值H0，寻找M’M，使h(H0,M’)=h(H0,M)。（2）密码分析法，这类攻击方法依赖于对散列函数的结构和代数性质分析，采用针对散列函数弱性质的方法进行攻击。这类攻击方法有中间相遇攻击、修正分组攻击和差分分析等等。10生日攻击•1生日悖论：在一个会场参加会议的人中，找一个与某人生日相同的概率超过0.5时，所需参会人员为183人。但要问使参会人员中至少有两个同日生的概率超过0.5的参会人数仅为23人。•这是因为，对于与某个已知生日的人同日生的概率为1/365，若房中有t人，则至少找到一人与此人同日生的概率为多少。易于解出，当t183时可使p0.5。•第一个人在特定日生的概率为1/365，而第二人不在该日生的概率为(1-1/365)，类似地第三人与前两位不同日生的概率为(1-2/365)，以此类推，t个人都不同时生日概率为Pt=(1-1/365)(1-2/365)…(1-(t-1)/365)，因此，至少有两人于同日生的概率为1-Pt.解之，当t23时，p0.5。11对散列函数的生日攻击与散列函数相关的类似问题可表述如下：给定一个散列函数h的输出长度为n位，共有2n个可能的散列值输出，找x和y满足H(x)=H(y)，则尝试多少个报文可以找到一对（假设散列值n比特）–显然，最多尝试2n＋1个报文，必有一对冲突•其实，远在到达2n＋1之前，很可能早就找到了(期望2n-1)–如果只要达到一定的概率(如1/2)，约需尝试多少个不同报文？答案：2n/212杂凑函数的构造(Merkle-Damgard)迭代型散列函数的一般结构：算法中重复使用某个函数f。函数f的输入有两项，一项是上一轮（第i-1轮）的输出CVi-1，称为链接变量，另一项是算法在本轮（第i轮）b位的输入分组mi。整个散列函数的逻辑关系可表示为：CV0=IV；CVi=f（CVi-1，mi）；1≤i≤t；h（M）=CVt13直接设计散列函数•MD5、SHA－1是当前国际通行的两大密码标准。MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA－1是由美国专门制定密码算法的标准机构——美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。•两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中，SHA－1早在1994年便为美国政府采纳，目前是美国政府广泛应用的计算机密码系统。141990MD419911992MD51993SHA019941995SHA119961997199819992000200120022003SHA-256,384,512200420052006MD4isbrokentheoreticalattackonSHA0MD5,SHA0broken,theoreticalattackonSHA1直接设计散列函数15MD系列•MIT一系列杂凑算法(RonalRivest设计)•~rivest/•MessageDigest(MD)–MD2(RFC1319)–MD4(RFC1320)–MD5(RFC1321)•应用–曾经是最广泛的摘要算法–但是摘要太短(128bits)–而SHA有160bits16MD5•特性：输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位•步骤1(填充消息):使得消息的长度（bit为单位）模512为448。如果数据长度正好是模512为448，增加512个填充bit，也就是说填充的个数为1-512。填充方法：第一个bit为1，其余全部为0。•步骤2(补足长度):将数据长度转换为64bit的数值，如果长度超过64bit所能表示的数据长度的范围，值保留最后64bit，增加到前面填充的数据后面，使得最后的数据为512bit的整数倍。•然后对每个512bit按每组32bit进行分组,可分为16组。512=32*1617报文KbitsL512bits=N32bits报文长度(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512512512512128-bit摘要MD5产生报文摘要的过程填充(1to512bits)18MD5算法实例•例7-1对字符串”abc”，运用MD5求散列值解:首先”abc”二进制表示为：011000010110001001100011，共24位长度MD5算法：第一步：按照MD5要求，填充数据:512－64－24＝424（填充1位“1”，423位“0”，及1000…000)512位的输入数据为(十六进制表示）：6162638000000000,……,00000018而W0=61626380,W1=W2=…=W14=00000000,W15=0000001819MD5算法步骤三：初始化变量用到4个变量，分别为A、B、C、D，均为32bit长。初始化为：A=01234567B=89abcdefC=fedcba98D=7654321020MD5算法第四步：数据处理，共进行四轮。设对512bit按每组32bit进行分组为M[0],M[1],……,M[15]。第一轮的辅助函数：F(X,Y,Z)=(X∧Y)∨(～X∧Z)X∧Y表示按位与，X∨Y表示按位或，～X表示按位取反。第一轮的操作：FF(a,b,c,d,M[j],s,t[i])表示为：a=b+((a+(F(b,c,d)+M[j]+t[i]))s)其中：M[j]表示第j个分组，s表示循环左移s位t[i]是给定的常数，t[i]=0x(int(232*sin(i)).21ABCDCLSsgABCDM[k]T[i]abcd本次缓存器交换(各次不同)下次缓存器a=b+((a+g(b,c,d)+M[k]+T[i])s)b=bc=cd=d然后交换：A=dB=aC=bD=cMD5压缩函数22MD5算法-计算t[1]计算t[1]x=sin(1)=0.8414709848078965066525023216303y=2^32=4294967296z=x*y=2^32*sin(1)=3614090360.2828283386251439079649int(z)=3614090360=oxD76AA47823MD5算法第一轮循环FF(a,b,c,d,M[0],7,0xd76aa478);/*1*/FF(d,a,b,c,M[1],12,0xe8c7b756);/*2*/FF(c,d,a,b,M[2],17,0x242070db);/*3*/FF(b,c,d,a,M[3],22,0xc1bdceee);/*4*/FF(a,b,c,d,M[4],7,0xf57c0faf);/*5*/FF(d,a,b,c,M[5],12,0x4787c62a);/*6*/FF(c,d,a,b,M[6],17,0xa8304613);/*7*/FF(b,c,d,a,M[7],22,0xfd469501);/*8*/FF(a,b,c,d,M[8],7,0x698098d8);/*9*/FF(d,a,b,c,M[9],12,0x8b44f7af);/*10*/FF(c,d,a,b,M[10],17,0xffff5bb1);/*11*/FF(b,c,d,a,M[11],22,0x895cd7be);/*12*/FF(a,b,c,d,M[12],7,0x6b901122);/*13*/FF(d,a,b,c,M[13],12,0xfd987193);/*14*/FF(c,d,a,b,M[14],17,0xa679438e);/*15*/FF(b,c,d,a,M[15],22,0x49b40821);/*16*/24MD5算法第二、三、四轮第二、三、四轮与第一轮非常相似。第二轮的辅助函数：G(X,Y,Z)=(X∧Z)∨(Y∧～Z)第三轮的辅助函数：H(X,Y,Z)=X⊕Y⊕Z第四轮的辅助函数：I(X,Y,Z)=Y⊕(X∨～Z)第二轮的操作：GG(a,b,c,d,M[j],s,t[i])表示：a=b+((a+(G(b,c,d)+M[j]+t[i]))s)第三轮的操作HH(a,b,c,d,M[j],s,t[i])表示：a=b+((a+(H(b,c,d)+M[j]+t[i]))s)第四轮的操作II(a,b,c,d,M[j],s,t[i])表示：a=b+((a+(I(b,c,d)+M[j]+t[i]))s)25GG(a,b,c,d,M[1],5,0xf61e2562);/*17*/GG(d,a,b,c,M[6],9,0xc040b340);/*18*/GG(c,d,a,b,M[11],14,0x265e5a51);/*19*/GG(b,c,d,a,M[0],20,0xe9b6c7aa);/*20*/GG(a,b,c,d,M[5],5,0xd62f105d);/*21*/GG(d,a,b,c,M[10],9,0x2441453);/*22*/GG(c,d,a,b,M[15],14,0xd8a1e681);/*23*/GG(b,c,d,a,M[4],20,0xe7d3fbc8);/*