密码Hash函数的分析与设计-王小云

王

小

云清华大学高等研究院

密码Hash函数的分析与设计Hash函数碰撞攻击引发的安全问题报告提纲2Hash函数与密码学Hash函数的碰撞攻击

国内外Hash函数新算法的设计报告提纲3Hash函数碰撞攻击引发的安全问题Hash函数的碰撞攻击国内外Hash函数新算法的设计Hash函数与密码学密码学与信息安全4信息通讯由单一的点到点通讯演化为全球化网络通讯密码算法被广泛用于有线和无线安全通讯，为全球约1万亿通讯设备提供安全保障密码学是信息安全的支撑，是网络通信与数据保密的重要保障5现代密码学发展历程古典密码：从两千多年前的Casear密码到二战被破译的德军密码Enigma1949年：Communicationtheoryofsecrecysystems，Shannon1976年：美国公布DES标准算法，在新的分析技术推动下，发展到以AES为代表的对称密码学（包括流密码）

同年，Diffie与Hellman公钥密码学的提出，公钥加密与数字签名技术得到发展基础密码算法对称加密算法（DES、AES等）公钥密码算法：公钥加密、电子签名，RSA、ECC等Hash函数（MD5、SHA-1等）检测传输中消息是否被篡改防止伪造电子签名和消息认证码作为安全组件设计多种密码体制和安全通信协议Hash函数与密码学6Hash函数是密码学的基本工具Hash函数可证明安全密码体制数字签名数据完整性检测Hash函数与密码学7SSH(远程登陆)Smartcard(智能卡)/邮件(S/MIME，PGP)SSL通讯协议IPSec(VPN)8Hash函数简介Hash函数：又称杂凑函数、散列函数、数字指纹等，将任意长的消息压缩为一个固定长度的摘要数学表示：Y=H(M),{0,1}*{0,1}n计算机中的Hash表，用于存储和查找，源于1953年IBM的历史性讨论密码学中的Hash函数称为密码Hash函数，具有特定的安全属性：1979-1987，Merkle，Davies，Price和Damgard等Hash函数101011100101001101110100010101128、160或256位的01串Hash函数简介密码Hash函数H：Y=H(M)抗原像攻击：给定任意Hash值Y，恢复消息M是困难的抗第二原像攻击：给定消息M1

，计算另一个消息M2

使H(M1)=H(M2)是困难的抗碰撞性：找到不同的消息(M1,M2)有相同的指纹，即H(M1)=H(M2)是困难的9H

M1Y

M2生日攻击复杂度H-1Y搜索攻击

MY

MH防止伪造电子签名保护口令M的安全防止伪造电子签名Hash函数简介消息101011100101001101110100010101128比特MD5101011100101001101110100010101160

比特SHA-1国际通用Hash函数算法：MD5&SHA-1MD5---R.Rivest：图灵奖得主，RSA第一设计者SHA-1---NIST/NSA：美国国家标准技术研究所10报告提纲11Hash函数碰撞攻击引发的安全问题Hash函数与密码学国内外Hash函数新算法的设计Hash函数的碰撞攻击Hash函数碰撞攻击分析结果1996年Dobbertin给出了MD4碰撞实例和MD5的伪碰撞实例1998年Chabaud和Joux找到SHA-0碰撞路线，攻击复杂度是2612003年，Rompay和Preneel等给出HAVAL-128的碰撞实例12DobbertinJoux王小云于1997年用代数分析方法找到SHA-0碰撞路线，复杂度258，1998年改进为245；1998年给出HAVAL-128的碰撞，复杂度仅为211次运算PreneelChabaud/Joux,1998Wang/Yu‚1997

SHA-2

(NIST,’02)SHA-0

(NIST,’93)MD4RIPEMDMD5

(Rivest‚‘92)RIPEMD-160

(Dobbertinetc96)SHA-1

(NIST,’95)HAVAL

Wang/Yu,2004Wang/Yu‚2005Wang‚1998Preneel,2003Wang‚1998Wang‚1998Dobbertin‚1996国际通用Hash函数的碰撞攻击13

SHA-3

(NIST,’12)比特进位

比特追踪

多明文分组碰撞理论

明文雪崩控制解决不可能差分问题Hash函数碰撞攻击理论体系（1996-2005）数学特征

比特追踪法比特进位比特控制方程多明文分组碰撞理论明文雪崩控制解决不可能差分问题14数学特征32313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321基本方法：比特追踪法提出比特进位产生非零比特差分以抵消雪崩效应152271217227121722712172271推导出控制雪崩的Hash函数数学特征提出比特追踪法快速寻找攻击路线系统的消除雪崩数学控制方法建立控制雪崩条件方程确定碰撞路线的前提条件MD5碰撞攻击方法与技术提出控制MD5强雪崩效应的多种技术引入长比特进位的差分路线（17比特进位）代替不超过5个比特进位基本原则通过条件控制解决了大量的长比特进位引起的不可能差分16基本方法：明文修改技术将概率条件转化成确定条件的两种明文修改技术基本明文修改，第一圈以1的概率成立高级明文修改，第二圈高概率成立：多重数学控制技术

经过基本明文修改ΔY1以1的概率成立经过高级明文修改ΔY2为高概率差分ΔY3为一事先选定的高概率差分17三圈Hash函数经明文修改后，M1和M2构成高概率碰撞明文修改技术其他应用原像攻击Rebound攻击MAC密钥恢复攻击MD5碰撞攻击方法与技术多明文分组碰撞思想提出两个明文分组构成MD5碰撞攻击的一般模式解决了两个明文分组的差分对接问题，以实现分割攻击18

两个明文分组的碰撞

多个明文分组的碰撞Hash函数的安全性等价于压缩函数的安全性，通常寻找一个消息分组的碰撞SHA-1的碰撞攻击方法与技术SHA系列算法数学分析模型代数模型：推出产生碰撞路线的两个明文差分特征，明文差分的空间{0,1}512,SHA-0的碰撞路线仅有2条根据明文差分特征，SHA-1产生碰撞需要70多个明文方程成立19SHA-1碰撞攻击方法与技术SHA-1不可能差分路线20SHA-1碰撞攻击方法与技术解决不可能差分问题：将不可能差分转化为可能差分，发现高概率的SHA-0、SHA-1碰撞路线21提出了不破坏大量明文比特方程的比特修改技术分析70多个含有512个变量的方程，找到50-60个可以用来明文修改的比特给出两个明文分组构成碰撞的攻击模型完成明文特征的对接，实现分割攻击增加了大量的控制方程Hash函数碰撞攻击主要论文XiaoyunWang,YiqunYin,HongboYu,FindingCollisionsintheFullSHA-1,Crypto2005.【BestPaper】WebofScience他引296次，GoogleScholar引用1178次XiaoyunWang,HongboYu,YiqunLisaYin,EfficientCollisionSearchAttacksonSHA-0,Crypto2005.WebofScience他引94次，GoogleScholar引用368次XiaoyunWang,HongboYu,HowtoBreakMD5andOtherHashFunctions,Eurocrypt2005.【BestPaper】WebofScience他引309次，GoogleScholar引用1111次XiaoyunWang,XuejiaLaietc,CryptanalysisoftheHashFunctionsMD4andRIPEMD,Eurocrypt2005.【BestPaper】WebofScience他引139次，GoogleScholar引用446次XiaoyunWang,XuejiaLaietc,CollisionsforHashFunctions，/2004WebofScience他引101次，GoogleScholar引用378次22WebofScience他引1000余次，GoogleScholar引用3000余次Hash函数碰撞攻击MD5破解论文获汤姆森路透卓越研究奖(中国)[2001-2006年中国所有领域共有24篇论文获选]国际通用Hash函数的破解项目2008年国家自然科学二等奖2006年陈嘉庚科学奖，求是杰出科学家奖

23碰撞攻击的进一步研究24基于MD5碰撞的实际攻击Steven等伪造了基于MD5的数字证书,Crypto09SHA-1碰撞实例的搜索Cannière和Rechberger等给出64、70步的碰撞实例,Asiacrypt06等约减轮SHA-2碰撞的碰撞攻击Mendel等给出28步SHA-2的碰撞实例，和38步SHA-2的伪碰撞分析,Eurocrypt13等自动化分析工具的研究Leurent给出一类Hash函数的自动化分析，给出32轮Skein的碰撞攻击,Asiacrypt12等荷兰Cramer团队丹麦Knudsen团队奥地利IAIK团队法国巴黎高师团队25碰撞攻击的进一步研究Wang，Ecryptworkshop宣布，2005基于MD4的密钥前缀、密钥后缀和密钥封装三类MACContini,Yin,Asiacrypt2006HMAC/NMAC-MD4/SHA-0的部分密钥恢复攻击Fouque,Leurent,Nguyen,Crypto2007HMAC/NMAC-MD4的完整密钥恢复攻击相关密钥条件下NMAC-MD5的完整密钥恢复攻击Wang,Ohta,Kunihiro,Eurocrypt2008相关密钥下NMAC-MD5的外部密钥恢复攻击等应用到新的密码分析领域HMAC：NIST标准，ISO标准，RFC2104HMAC-MD5用于Ipsec和TLS协议MAC算法的新型碰撞攻击，Eurocrypt2009,Crypto2009,FSE2009MD5-MAC、ALPHA-MAC、PELICAN三个算法子密钥恢复攻击HMAC/MD5的区分攻击

完成人：王小云、于红波等26碰撞攻击的进一步研究应用到新的密码分析领域MD5-MAC：Preneel设计，ISO标准ALPHA/PELICAN：AES设计者Daemen与Rijmen设计PP’IVIV’伪碰撞碰撞报告提纲27Hash函数与密码学Hash函数的碰撞攻击国内外Hash函数新算法的设计Hash函数碰撞攻击引发的安全问题基于MD5随机碰撞的证书伪造X.509数字证书是国际电信联盟(ITU-T)制定的PKI(公钥密码基础设施)标准X.509定义了(但不仅限于)公钥证书、证书吊销清单、属性证书和证书路径验证算法等证书标准28采用MD5和RSA算法对证书签名X.509数字证书结构基于MD5随机碰撞的证书伪造2005年Lenstra,Wang等给出同一个用户拥有不同公钥证书的伪造2008年Sotirov,Stevens等在CCC大会上演示了通过MD5碰撞伪造的证书可以被浏览器当作是有效的、可信的证书

29源证书(part1)伪造证书(part1)源证书(part2)伪造证书(part2)基于MD5随机碰撞的证书伪造美国计算机应急小组（US-CERT）：发表了题为“MD5vulnerabletocollisionattacks”，指出现有主要计算机系统均不可避免密码专家认为该攻击适合于任何计算机系统30MD5的碰撞弱点，使攻击者能够生成密码口令或者其他不合法的数据都能被认证。软件开发商，认证中心，网站和用户应该避免使用MD5算法，以前的研究已经证明，从密码学的角度认为被破解的算法不再适合将来的应用2009年10大黑客技术排名第一基于MD5随机碰撞的证书伪造31CA1010100101101100010101001011011000证书1证书2使用证书1获取CA签名使用证书2建立可通过浏览器认证的网站基于MD5随机碰撞的实际攻击StefanLucks和Magnus给出相同签名的PS格式文件源文件目标文件（碰撞）325421a523481fac6a2a1c832e72c7b8a5…fulfilledallthe

requirements…Ihighlyrecommendhiringher.Sincerely,JuliusCaesar…fullaccesstoallconfidentialandsecretInformation…Sincerely,JuliusCaesarMD5原理：编辑软件的冗余命令等嵌入MD5随机碰撞，也可用于PDF,TIFFandWord97文件2012年5月，被俄罗斯安全专家发现攻击范围搜集数据任务完成，自行毁灭，

不留踪迹火焰病毒(Worm.Win32.Flame)33传送截获键盘输入记录音频对话获取截屏画面监测网络流量火焰病毒中的关键密码技术34微软终端服务器许可服务证书签名的代码(MD5)伪造证书签名的病毒代码(MD5)“火焰”采用选择前缀MD5碰撞攻击的新变体伪造证书，主体路线使用王小云等在Eurocrypt05给出的路线Block1Block2Block3Block4报告提纲35Hash函数碰撞攻击引发的安全问题Hash函数与密码学Hash函数的碰撞攻击

国内外Hash函数新算法的设计国内通用密码Hash算法的设计2002-2005期间：国家通用杂凑函数算法设计国家密码基金支持多家科研单位参入设计SM3密码杂凑函数算法被采纳国内密码行业标准2010年密码科技进步一等奖（省部级）广泛应用于政府、金融等社会和经济领域设计者：王小云，李峥，王永传，于红波，谢永泉，张超，罗鹏，吕述望36国际密码Hash函数SHA-3设计

新算法设计背景：MD5、SHA-1破解密码专家的担忧与建议Science\NoticeofAMS评论Hash函数碰撞攻击理论的认可37Science的评论38“学术界将不得不非常认真的考虑这一问题”，麻省理工大学的密码学家RonRivest说，“显然，我们不得不替换掉SHA-1”“Theresearchcommunityisgoingtohavetothinkveryhardaboutthis,”saysMassachusettsInstituteofTechnologycryptographerRonRivest.“WeclearlyhavetoreplaceSHA-1.”NoticeofAMS(美国数学学会)的评论39在2004年美密会上，王小云等由于对MD5的碰撞攻击得到了长久的欢呼……她们的攻击是对MD5的最后一击，意味着MD5出局AtacryptographymeetinginSantaBarbara,California,XiaoyunWang,DenggouFeng,XuejiaLai,andHongboYureceivedastandingovationforworkshowingcollisionattacksonMD5…….TherehadalreadybeenamoveawayfromMD5,butthiswasthefinalblow.In2005thesituationgotworse.Wang,incollaborationwithYiqunLisaYinandHongboYu,showedacollisionattackonSHA-1thattook269steps(insteadoftheexpected280)[14];thenWang,incollaborationwithAndrewYaoandFrancesYao,demonstratedacollisionattackonSHA-1thatrequiredonly263steps[15].2005年情况更糟，王小云，尹依群，于红波等对SHA-1进行碰撞攻击，复杂度为269，随后，王，姚等又对结果进行了改进，复杂度为263。NIST对MD5和SHA-1破解的评论40However,duetoadvancesintechnology,NISTplanstophaseoutofSHA-1infavorofthelargerandstrongerhashfunctions(SHA-224,SHA-256,SHA-384andSHA-512)by2010.由于技术的进步，NIST决定在2010年逐步撤出SHA-1的使用。Duetoadvancesincomputingpower,NISTalreadyplannedtophaseoutSHA-1infavorofthelargerandstrongerhashfunctions(SHA-224,SHA-256,SHA-384andSHA-512)by2010.NIST对SHA-1破解的应对措施Inrecentyears,……andseriousattackshavebeenpublishedagainstSHA-1.Inresponse,……NISThasdecidedtodeveloponeormoreadditionalhashfunctionsthroughapubliccompetition,similartothedevelopmentprocessoftheAdvancedEncryptionStandard(AES).NISTacceptsthatProf.WanghasindeedfoundapracticalcollisionattackonSHA-1.FederalagenciesshouldstopusingSHA-1fordigitalsignatures,digitaltimestampingandotherapplicationsthatrequirecollisionresist