第7章 密码学Hash函数

第七章Hash函数了解Hash密码学的Hash密码学的Hash构造Hash函数的攻击散列算法1安全目标保密性:怎样保持明文的秘密性，使得明文只能被某些人阅读？用加密的方法完整性:怎样确定一列信号在产生后没有被篡改？用什么方法？2NaïveIdeaAlice用密钥K加密消息Oscar不知道K但是,Oscar能修改密文Bob能收到什么?AliceBobOscar3散列码提供了消息结构MAC加密(明文+Hash)4Hash函数应用认证完整性数字签名保护口令文件时间戳证书5第七章Hash函数认证密码学的Hash密码学的Hash构造Hash函数的攻击散列算法6强无碰撞Hash函数定义：一个强无碰撞Hash函数是一个满足下列条件的函数h:1)压缩–h:*

n多对一映射2)容易计算

3)单向–给定y,求m使得h(m)=y在计算上不可行4)给定算法h，要找两个不同的消息m1m2,使其Hash值h(m1)=h(m2)是困难的7AliceBobJudgeIoweyouIoweyou一个用Hash的例子Alice想给Bob发送一条消息“Ioweyou”Bob可以向法官出示消息来迫使Alice付清欠款8IOU协议Alice{KUA,KRA}MEKRA[H(M)]JudgeMEKRA[H(M)]知道KUA知道KUA不知道KRA，Bob不能伪造(M,EKRA[H(M)])对

AliceBobJudgeBob能核实H(M)9如果冲突存在假设我们用:H(chars[])=(s[0]–‘a’)mod10Alice发给Bob:

“I,Alice,oweBob$2.”,EKRA[H(M)]Bob发给Judge:

“I,Alice,oweBob$200000000000.”,EKRA[H(M)]法官证实EKUA

[

EKRA[H(M)]]=H(“I,Alice,oweBob$200000000000.”)

使Alice付款10第七章Hash函数认证密码学的Hash密码学的Hash构造Hash函数的攻击散列算法11Hash定义定义：一个强无碰撞Hash函数是一个满足下列条件的函数h:1)压缩–h:*

n多对一映射2)容易计算

3)单向–给定y,求m使得h(m)=y在计算上不可行4)给定算法h，要找两个不同的消息x1x2,使其Hash值h(x1)=(x2)是困难的12Hash函数构造例1:假设n是一个大整数.设h(m)=m(modn)是介于0到n-1之间的一个整数例2:明文:“Gonow”G01000111o01101111n01101110o01101111w0111011101011110不行13Hash函数构造基于分组密码用候选单向函数构造Hash函数矩阵单向函数基于胞元自动机的算法以有限域中元素的指数运算构造用流密码构造14基于分组密码的Hash函数构造块加密IVM1M2...块加密块加密MnH15基于分组密码的Hash函数构造块加密MiHi-1Hi块加密MiHi-1Hi16用候选单向函数构造Hash函数选定一候选单向函数族

-RSA函数f(N,e)-Rabin函数fN-离散对数函数f(p,g)从单向函数族中选出一个函数进行迭代

-明文:m=m1...mt-hi=f(hi-1+mi),i=1,...t-h(m)=ht17用候选单向函数构造Hash函数例1:RSA函数f(N,e):hi=(hi-1+mi)emodN,(i=1,...,t)例2:背包法:令M1,...,Ms是二元消息数字,A=(a1,...,as)是一背包向量，ai[1,N]H(M)=M1a1+...+MsasmodN18矩阵单向函数用tt阶随机矩阵A作为密钥,按下述矩阵变换将消息M扰乱:H(M)=MTAM=i<jaijmimj19第七章Hash函数认证密码学的Hash密码学的Hash构造Hash函数的攻击散列算法20Hash函数的攻击生日攻击特殊攻击-中间相遇攻击

·攻击具有分组链接结构的Hash函数-差分攻击·攻击基于分组加密函数构造的Hash函数-修正分组攻击

·攻击基于模算术的Hash函数21结论Hash值的长度必须足够大，以便使得生日攻击不能成功MD5的Hash长度为128位，M=264；SHA-1的Hash长度为160位，则M=28022密码学的Hash对强无碰撞Hash函数:hash输出的长度应该是分组密码密钥长度的2倍64-bits太短通常128~512bitsSHA-256,SHA-384,SHA-51223第七章Hash函数消息认证密码学的Hash密码学的Hash构造Hash函数的攻击散列算法24第七章Hash函数消息认证密码学的Hash密码学的Hash构造Hash函数的攻击散列算法25Hash算法的结构bY0nfbY1nfbYL-1nCVL-1fCV1nnIV=InitialVectorCV=ChainVectorYi=TheithMessageBlockf=CompressFunctionn=HashValueLengthb=BlockLengthCVLCV0=IV=initialn-bitvalueCVi=f(CVi-1,Yi-1)(1iL)H(M)=CVLCV026

MessageKbitsL512bits=N32bitsLengthofMessage(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsHMD5IV128HMD5CV1128HMD5CVq128HMD5CVL-1128512128-bitdigestpadding(1to512bits)512512512MD527填充举例例：消息由704位组成，则在其末尾添加256位（1后面跟255个0），消息扩展到960位将消息的原始长度缩减为mod264，例：704位=1011000000位，将这个数书写为64位（在开始位置添加54个0）最后结果是一个具有1024位的消息28MD5细节Step

1)填充消息:10...0,使消息长度等于448mod512Step

2)添加明文长度(64位)Step3)初始化4个字(128bits)的寄存器(A,B,C,D)A=67452301B=EFCDAB89C=98BADCFED=10325476Step4)消息由512-bits数据块(Y0,Y1,…,YL-1)处理

4轮，每轮16次迭代

29F,T[1…16],M[i]16stepsG,T[17…32],M[2i]16stepsH,T[33…48],M[3i]16stepsI,T[49…64],M[4i]16steps++++ABCDABCDABCDABCDCVq128Yq512CVq+1128+是mod232512-bitMessageHMD54轮301轮每一轮处理16个子块。每一轮的输入如下:1)16个子块;2)寄存器ABCD中的值;3)常量T16个子块常量T一轮BACD31ABCDABCD+++移位+gM[k]T[i]1轮中的1次迭代步骤7步骤6步骤5步骤4步骤3步骤2步骤1+是mod232BB+((A+g(B,C,D)+M[k]+T[i])<<<s)32MD5压缩函数每一轮有16次迭代，每1次迭代形如：

BB+((A+g(B,C,D)+M[k]+T[i])<<<s)

g：4轮都不同的非线性函数(F,G,H,I)第一轮：F(X,Y,Z)=(XY)((¬X)Z)第二轮：G(X,Y,Z)=(XZ)(Y(¬Z))第三轮：H(X,Y,Z)=XYZ第四轮：I(X,Y,Z)=Y(X(¬Z))

M[k]=第q个512-bits数据块的第k个字

T[i]=T盒的第i个32-bits字(T[i]=232abs(sin(i)))33第一轮迭代MsT12345678910111213141516M[1]M[2]M[3]M[4]M[5]M[6]M[7]M[8]M[9]M[10]M[11]M[12]M[13]M[14]M[15]M[16]7121722712172271217227121722T[1]T[2]T[3]T[4]T[5]T[6]T[7]T[8]T[9]T[10]T[11]T[12]T[13]T[14]T[15]T[16]34第二轮迭代MsT12345678910111213141516M[2]M[7]M[12]M[1]M[6]M[11]M[16]M[5]M[10]M[15]M[4]M[9]M[14]M[3]M[8]M[13]591420591420591420591420T[17]T[18]T[19]T[20]T[21]T[22]T[23]T[24]T[25]T[26]T[27]T[28]T[29]T[30]T[31]T[32]35第三轮迭代MsT12345678910111213141516M[6]M[9]M[12]M[15]M[2]M[5]M[8]M[11]M[14]M[1]M[4]M[7]M[10]M[13]M[16]M[3]4111623411162341116234111623T[33]T[34]T[35]T[36]T[37]T[38]T[39]T[40]T[41]T[42]T[43]T[44]T[45]T[46]T[47]T[48]36第四轮迭代MsT12345678910111213141516M[1]M[8]M[15]M[6]M[13]M[4]M[11]M[2]M[9]M[16]M[7]M[14]M[5]M[12]M[3]M[10]6101521610152161015216101521T[49]T[50]T[51]T[52]T[53]T[54]T[55]T[56]T[57]T[58]T[59]T[60]T[61]T[62]T[63]T[64]37T的取值T(i)值T(i)值T(i)值T(i)值T[1]T[2]T[3]T[4]T[5]T[6]T[7]T[8]T[9]T[10]T[11]T[12]T[13]T[14]T[15]T[16]D76AA478E8C7B756242070DBC1BDCEEEF57C0FAF4787C62AA8304613FD469501698098D88B44F7AFFFFF5BB1895CD7BE6B901122FD987193A679438E49B40821T[17]T[18]T[19]T[20]T[21]T[22]T[23]T[24]T[25]T[26]T[27]T[28]T[29]T[30]T[31]T[32]F61E2562C040B340265E5A51E9B6C7AAD62F105D02441453D8A1E681E7D3FBC821E1CDE6C33707D6F4D50D87455A14EDA9E3E905FCEFA3F8676F02D98D2A4C8AT[33]T[34]T[35]T[36]T[37]T[38]T[39]T[40]T[41]T[42]T[43]T[44]T[45]T[46]T[47]T[48]FFFA39428771F681699D6122FDE5380CA4BEEA444BDECFA9F6BB4B60BEBFBC70289B7EC6EAA127FAD4EF308504881D05D9D4D039E6DB99E51FA27CF8C4AC5665T[49]T[50]T[51]T[52]T[53]T[54]T[55]T[56]T[57]T[58]T[59]T[60]T[61]T[62]T[63]T[64]F4292244432AFF97AB9423A7FC93A039655B59C38F0CCC92FFEFF47D85845DD16FA87E4FFE2CE6E0A30143144E0811A1F7537E82BD3AF2352AD7D2BBBE86D391T[i]=232abs(sin(i))38MD5分析Berson(1992):Forasingle-roundMD5,hefindscollisionusingdifferentialcryptanalysisAttackdoesnotworkfor4-roundMD5Boer&Bosselaers(1993):Foundapseudocollision(samemessage,twodifferentIV’s)Dobbertin(1996):CreatedcollisionsonMD5compressionfunctionwithchosenIVWang,Feng,Lai,Yu(2005):WorksonanyIVEasytofindmultiplecollisions39

MessageKbitsL512bits=N32bitsLengthofMessage(Kmod264)100…0Y0512bitsY1512bitsYq512bitsYL-1512bitsSHAIV160SHACV1160SHACVq160SHACVL-1160512160-bitdigestpadding(1to512bits)512512512SHA40SHA1细节Step1)AsinMD5messageispaddedsuchasitslengthisamultipleof512bitsStep2)Initialize5word(160bits)buffer(A,B,C,D,E)

A=67452301B=EFCDAB89C=98BADCFED=10325476E=C3D2E1F0Step3)Themessageisprocessedin512-bitsdataexpand16wordsinto80wordsbymixing&shiftinguse4roundsof20operationsonmessageblockandbuffer414轮SHA4differentfunctions:Totally80steps532-bitwords42SHA1压缩函数From512-bitinputblockFixedconstantCircularleftshift5bits43SHA1压缩函数Eachroundconsistsof20steps(A,B,C,D,E)(E+f(t,B,C,D)+(A<<5)+Wt+Kt),A,(B<<30),C,D)tisthestepnumberf(t,B,C,D)isanon-linearfunctionforroundWtisderivedfromthemessageblockWt=S1(Wt-16Wt-14Wt-8Wt-3)KtisaconstantvaluederivedfromthesinfunctionSkiscircularleftshiftbykbits44SHA1:f(t,A,B,C,D)StepFunctionValueComment0t19(BC)((¬B)D)IfBthenCelseD20t39BCDParitybitofB,C,andD40t59(BC)(BD)(CD