密码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)是困难的9HM1YM2生日攻击复杂度H-1Y搜索攻击MYMH防止伪造电子签名保护口令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‚1997SHA-2(NIST,’02)SHA-0(NIST,’93)MD4RIPEMDMD5(Rivest‚‘92)RIPEMD-160(Dobbertinetc96)SHA-1(NIST,’95)HAVALWang/Yu,2004Wang/Yu‚2005Wang‚1998Preneel,2003Wang‚1998Wang‚1998Dobbertin‚1996国际通用Hash函数的碰撞攻击13SHA-3(NIST,’12)比特进位比特追踪多明文分组碰撞理论明文雪崩控制解决不可能差分问题Hash函数碰撞攻击理论体系（1996-2005）数学特征比特追踪法比特进位比特控制方程多明文分组碰撞理论明文雪崩控制解决不可能差分问题14数学特征32313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321323130292827262524232221201918171615141312111098765432132313029282726252423222120191817161514131211109876543213231302928272625242322212019181716151413121110987654321基本方法：比特追踪法提出比特进位产生非零比特差分以抵消雪崩效应152271217227121722712172271推导出控制雪崩的Hash函数数学特征提出比特追踪法快速寻找攻击路线系统的消除雪崩数学控制方法建立控制雪崩条件方程确定碰撞路线的前提条件MD5碰撞攻击方法与技术提出控制MD5强雪崩效应的多种技术引入长比特进位的差分路线（17比特进位）代替不超过5个比特进位基本原则通过条件控制解决了大量的长比特进位引起的不可能差分16基本方法：明文修改技术将概率条件转化成确定条件的两种明文修改技术基本明文修改，第一圈以1的概率成立高级明文修改，第二圈高概率成立：多重数学控制技术M1M1M1IVIVRound1Round1Round3Round3M2Round2Round2M2M2ΔY1ΔY2ΔY3ΔH=0collision经过基本明文修改Δ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，他引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三个算