应用密码学_第09章_消息认证与Hash函数

散列函数（HashFunction）：也称哈希函数，对任意长度的明文进行变换，得到相对应的函数值，称为散列值，或称消息摘要（MessageDigest）、指纹（Fingerprint），变换的过程称为散列变换。散列值的长度一般是固定的。用途：消息鉴别码、数字签名之前的预处理要求：(1)对任意长度输入进行变换，得到固定长度输出(2)求逆不可行(3)对给定x，很难找到x’≠x，使得h(x’)=h(x)(4)很难找到一对不同的x,x’，使得h(x’)=h(x)满足条件(1)~(2)的称之为单向散列函数(One-WayHashFunction)满足条件(1)~(3)的称之为弱散列函数(WeakHashFunction)或弱无碰撞的散列函数满足条件(1)~(4)的称之为强散列函数(StrongHashFunction)或强无碰撞的散列函数。经度冗余校验：对明文进行等长分组，再将每个分组逐位异或。分组1b11b12……b1n分组2b21b22……b2n……分组mbm1bm2……bmnHash值C1C2……Cn利用DES的密码分组链接模式（CBC）设计将明文M按M=m1m2…mn进行分组，mi为64位，按DES的CBC模式依次对每个分组进行加密，令h0=初始向量，hi=Emi[hi-1]，加密过程不使用任何密钥，G=hn为最终得到的散列值。散列函数用于签名时，假设签名消息为(x,y)，y=sigk(h(x))，则攻击者可用如下方式伪造攻击者计算Z=h(x)，找到x’≠x，但h(x’)=h(x)，则（x’,y）构成有效的签名；攻击者找到任意两个不同消息x’，x，满足h(x’)=h(x)，令签名者对h(x)签名，则（x’,h(x)）也是有效签名；攻击者伪造一个签名Z，若能计算h-1(Z)=x，则(x,h(x))为有效签名。对hash函数的攻击可以看作是寻找碰撞的过程，攻击者的主要目标不是恢复原始的明文，而是用非法消息替代合法消息进行伪造和欺骗。攻击方法：生日攻击、中间相遇攻击、穷举攻击生日悖论（BirthdayParadox）一个房间内有k个人，当k多大时，其中存在两个人具有相同生日的概率大于1/2？答案：23k个人的生日排列总数：365k，k个人有不同生日的排列总数：N=P365kk个人有不同生日的概率：Q(k)=P365k/365kk个人中至少能找到两个人生日相同的概率：P(k)=1-Q(k)=1-P365k/365k。当k=23时，P(k)=0.5073，而当k=100时，P(k)=0.9999997。当人数超过100时，存在两个人生日相同几乎是一个必然事件。Yuval提出的方法第一步：攻击者产生一份合法的明文，再产生232个不同的明文变形，构成一个合法明文组；第二步：生成一份非法明文，构造232个不同的非法明文变形，产生一个非法明文组；Yuval提出的方法第三步：分别对以上两个组产生散列值，在两组明文中找出具有相同散列值的一对明文。如果没有找到，则再增加每组明文变形的数目，直至找到。由“生日悖论”可知，其成功的概率很大。于是，攻击者找到了一则与合法明文（至少内容合法）具有相同散列值的非法明文。攻击者通过一对已知的明文和散列值，就可以任意伪造其它明文的散列值，步骤如下：第一步，对已知明文M产生散列值G；第二步，将非法明文Q按Q=Q1Q2…Qn-2进行分组，每个分组长度为64位；第三步，计算hi=EQi[hi-1]，1≤i≤n-2；第四步，产生232个不同的x，对每个x计算Ex[hn-2]，再任意产生232个不同的y，对每个y计算Dy[G]，D是对应于E的解密函数；第五步，找到一对对应的x和y，使得Ex[hn-2]=Dy[G]；第六步，生成新的明文Q′=Q1Q2…Qn-2xy。对hash函数的穷举攻击对长度为n的hash函数，穷举攻击的理论难度如下表所示单向2n弱无碰撞2n强无碰撞2n/2Merkle在1989年提出了散列函数的通用结构：a.将原始消息M分成固定长度的分组(Block)Mi；b.对最后一个分组ML填充，并附上原始消息M的长度，使其长度等于固定长度；c.设定链接变量(chainingvalue)的初始值CV0；d.定义压缩函数f，CVi=f(CVi-1,Mi-1)；e.循环操作L次，最后一个CVL为散列值。IV=initialvalue初始值CV=chainingvalue链接值Mi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度)bM0nIV=CV0fbM1nfbML-1nCVL-1fCV1nnCVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Mi-1)(1iL)H(M)=CVLMD5SHA-1RIPEMD-160Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年，RonRivest完成MD5(RFC1321)现行美国标准SHA-1以MD5的前身MD4为基础输出：128位分组长度：512位算法细节：填充→轮函数Step1:填充，M→M’|M’|448mod512|M’||M|→如果|M|448mod512，则|M’|=|M|+512填充内容:100…0M=“abcde”=0110000101100010011000110110010001100101=(6162636465)16，|M|=40=(28)16M’=M||1||0(407个)=M||800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000=6162636465800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Step2:附加消息长度值，M’→M’’若|M|264,则仅取低64位低字节在前(little-endian)|M’’|为512的倍数:M0,M1,…,ML-1Message1000…064bit(消息长度)512n+448bitM=“abcde”=0110000101100010011000110110010001100101=(6162636465)16，|M|=40=(28)16M’’=m’||28=61626364658000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002800000000000000Step3初始化计算消息摘要时用到四个字的缓冲区(A，B，C，D)。A、B、C、D均为32位的寄存器。第一个分组进行第一轮运算时，用以下16进制数来初始化这四个寄存器：A=0x01234567B=0x89abcdefC=0xfedcba98D=0x76543210Step4压缩(算法HMD5)对512位(16个字)组进行运算，Ｍq表示输入的第q组512位数据，在各轮中参加运算。T[1,…,64]为64个元素表，分四组参与不同轮的计算。T[i]为232×abs(Sin(i))的整数部分，i是弧度。T[i]可用32位二元数表示，T是32位随机数源。CVq，128Mq512ABCD32ABCD＂fF(ABCD,X[k],T[1…16])ABCDABCD＂fG(ABCD,X[k],T[17…32])ABCDABCD＂fH(ABCD,X[k],T[33…48])ABCDABCD＂fI(ABCD,X[k],T[49…64])+++++：mod232MD5的一个512位CVq+1128分组处理MD5压缩函数轮运算MD5是四轮运算，各轮逻辑函数不同。每轮又要进行16步迭代运算，4轮共需64步完成。每步完成bb＋CLSS(a＋g(b,c,d)＋X[k]＋T[i])其中a,b,c,d：缓存器中的四个字，按特定次序变化。g：基本逻辑函数，F、G、H、I之一，算法的每一轮用其中一个。ABCDABCD+g+CLSS++X[k]T[i]CLSs：循环左移s位。X[k]：第Mq的第k个32位字。T[i]：矩阵T中第i个32位字。＋：模232加法。基本逻辑函数g每一轮使用一个基本逻辑函数g，每个基本逻辑函数的输入是三个32位的字，输出是一个32位的字，它执行位逻辑运算，即输出的第n位是其三个输入的第n位的函数基本逻辑函数g的定义符号、、和分别表示逻辑操作AND、OR、NOT和XOR基本逻辑函数g真值表bcdFGHI0000010100111001011101110001101001101001001101011100111034X[k]把当前处理的512位的分组Mq依次分成16个32位的字，分别记为X[0,1,…,15]。在每一轮的16步迭代中，每一步迭代使用一个字，迭代步数不同使用的字也不相同。因此，16步迭代恰好用完16个字。对于不同轮处理过程，使用16个字的顺序不一样第一轮中，使用顺序为X[0,1,…,15]。第二轮中使用顺序由下列置换确定:ρ2(i)=(1+5i)mod16第三轮中使用顺序由下列置换确定:ρ3(i)=(5+3i)mod16第四轮中使用顺序由下列置换确定:ρ4(i)=7imod16例如：第三轮处理过程的第i步迭代使用字X[ρ3(i)]=X[(5+3i)mod16]第8步迭代使用字X[ρ3(8)]=X[(5+3*8)]=X[13]常数表T：64个32位常数T[i]=232*abs(sin(i))的整数部分(i=1,2,…,64).T[1]=D76AA478T[2]=E8C7B756T[3]=242070DBT[4]=C1BDCEEET[5]=F57C0FAFT[6]=4787C62AT[7]=A8304613T[8]=FD469501T[9]=698098D8T[10]=8B44F7AFT[11]=FFFF5BB1T[12]=895CD7BET[13]=6B901122T[14]=FD987193T[15]=A679438ET[16]=49B40821T[17]=F61E2562T[18]=C040B340T[19]=265E5A51T[20]=E9B6C7AAT[21]=D62F105DT[22]=02441453T[23]=D8A1E681T[24]=E7D3FBC8T[25]=21E1CDE6T[26]=C33707D6T[27]=F4D50D87T[28]=455A14EDT[29]=A9E3E905T[30]=FCEFA3F8T[31]=676F02D9T[32]=8D2A4C8AT[33]=FFFA3942T[34]=8771F681T[35]=699D6122T[36]=FDE5380CT[37]=A4BEEA44T[38]=4BDECFA9T[39]=F6BB4B60T[40]=BEBFBC70T[41]=289B7EC6T[42]=EAA127FAT[43]=D4EF3085T[44]=04881D05T[45]=D9D4D039T[46]=E6DB99E5T[47]=1FA27CF8T[48]=C4AC5665T[49]=F4292244T[50]=432AFF97T[51]=AB9423A7T[52]=FC93A039T[53]=655B59C3T[54]=8F0CCC92T[55]=FFEFF47DT[56]=85845DD1T[57]=6FA87E