SHA-3竞赛中的hash函数新设计结构简介

SHA-3竞赛中的hash函数新设计结构简介报告人：邹剑报告时间：2010年12月18号ContentsHash函数简介1MD系列Hash函数的缺点2SHA-3竞赛简介3新的Hash函数设计结构4ContentsHash函数简介1Hash函数简介*:{0,1}{0,1}nHThisisaninputtoacrypto-graphichashfunction.Theinputisaverylongstring,thatisreducedbythehashfunctiontoastringoffixedlength.Thereareadditionalsecurityconditions:itshouldbeveryhardtofindaninputhashingtoagivenvalue(apreimage)ortofindtwocollidinginputs(acollision).1A3FD4128A198FB3CA345932h密码学中的Hash函数是将任意长度的消息压缩为固定长度摘要的函数，是现代密码学的一个重要分支。操作检测码(manipulationdetectioncode–MDC)。将长消息的正确性归约为短摘要的正确性。带密钥的叫做消息认证码(MAC)。不带密钥的叫做操作检测码(MDC)。根据摘要找到消息值困难的叫单向杂凑函数(OWHF)。找到任意两个摘要相同的消息困难的叫抗碰撞杂凑函数(CRHF)。找到第二原像困难的叫广义单向杂凑函数(UOWHF)。Hash函数简介HashFunctionMDCMACOWHFCRHFUOWHF(TCR)我们讨论的对象迭代Hash函数的一般模型在最初的“初始化”阶段，通常要先对消息进行填充，以使得全部比特长度是分组长度的倍数。分组之后的消息，加入迭代的压缩函数，每个分组消息值作为压缩函数的一个输入，其中链值（迭代的中间值）的初值记为IV，第i轮之后的链值作为第i+1轮的输入和消息值一起运算。最后一轮的链值进入输出变换，输出变换的输出即为最后的摘要。任意长度输入迭代压缩函数可选输出变换输出ContentsMD系列Hash函数的缺点2MD结构简介传统MD结构消息经过填充后分块进入压缩函数进行迭代中间链值和摘要的长度是一样的，并且在最后没有输出变换。初始迭代值为常数，最终迭代值作为摘要值输出。M1M2M3MtffffH0Ht对MD结构的通用攻击长度扩展攻击在已碰撞的消息对后面增加消息块来构造新的碰撞对。多碰撞攻击MD结构的多碰撞代价远远低于构造随机函数的多碰撞。长消息第二原象攻击通过可扩展消息构造对长消息的第二原象攻击。集群攻击攻击者选择摘要h，给定前缀P，攻击者构造出后缀S使得H(P||S)=h(指定前缀第二原象)。……长度扩展攻击MD结构不具备randomoracle的性质已知消息x的摘要h(x)，不需要知道x本身就可以对任意y获得h(x||y)的值。解决方案加入输出转换函数（即迭代完成后加入一个转换函数g）M1M2M3MtffffH0Htg多碰撞攻击多碰撞（超过两个不同的消息对应同一个摘要值）构造随机函数K-碰撞的复杂度为。构造MD结构2t个碰撞的复杂度为，远远小于理论值。解决方案使用宽管道结构1.中间状态的大小至少为摘要长度的2倍2.迭代值经过输出函数压缩为摘要长度12knk22ntContentsSHA-3竞赛简介3NIST举办SHA-3竞赛的目的1.征集下一代hash标准，替代目前的SHA-2NIST举办SHA-3竞赛的原因1.作为Hash函数标准的MD5、SHA-1受到严重的攻击2.MD结构受到了各种通用攻击NIST举办SHA-3竞赛的要求1.必须支持224,256,384,512比特的摘要，必须支持264长度的消息。SHA-3竞赛简介SHA-3竞赛简介——目前的进展截止2008年11月，一共有64个算法提交。2008年12月其中51个算法被NIST接收作为第一轮的候选算法。2009年7月，NIST公布了进入第二轮的14个算法。今年年底已经公布了进入最终轮的5个算法。最终将于2012年选出获胜算法并命名为SHA-3。645114510204060802008年11月2008年12月2009年7月2010年12月2012年第一轮第二轮最终轮SHA-3第2轮参赛算法参赛算法作者BLAKEJean-PhilippeAumassonBlueMidnightWishSveinJohanKnapskogCubeHashDanielJ.BernsteinECHOHenriGilbertFugueCharanjitS.JutlaGrøstlLarsR.KnudsenHamsiÖzgülKüçükJHHongjunWuKeccakTheKeccakTeamLuffaDaiWatanabeShabalJean-FrançoisMisarskySHAvite-3OrrDunkelmanSIMDGaëtanLeurentSkeinBruceSchneierSHA-3第3轮参赛算法参赛算法作者BLAKEJean-PhilippeAumassonGrøstlLarsR.KnudsenJHHongjunWuKeccakTheKeccakTeamSkeinBruceSchneier此次SHA-3竞赛中出现的新算法设计有两种主流的设计思路：1.基于以AES为基础模块的设计2.基于以ARX为基本模块的设计大家如果对参加第一轮的算法感兴趣可以到如下网址了解更多的细节新的Hash函数设计结构4新的Hash函数结构1.HAIFA结构其主要思想是通过在压缩函数中加入盐(salt)，同时加入迄今为止压缩过的比特数(#bits)，来实现压缩函数的抗长消息攻击等安全属性。采用HAIFA结构的函数BLAKE为标准HAIFA结构。ECHO和SHAvite3为变体。2.Sponge结构的特点使用固定置换。消息分块吸收。分块输出直到需要的长度。采用Sponge结构的函数Keccak为标准Sponge。CubeHash、JH、Luffa均为变体。rc00置换Px0SCSA置换Px1置换P置换PSCSAh0SCSAh1吸收挤压新的Hash函数结构Bertoni，Daemen，Peeters，Assche在论文“OntheIndifferentiabilityoftheSpongeconstruction”中，证明了当Sponge的构造是基于随机变换或随机置换时，Sponge与随机预言机是不可区分的，因而是可证明安全的。新的Hash函数结构3.宽管道结构宽管道结构和MD结构很相似，除了它使用的是一个“巨大的”w-比特压缩函数，而最后生成一个nw比特的输出。采用宽管道结构的函数ECHO,Fugue,Groestl,Hamsi,Keccak,SIMD。BLAKE算法为局部宽管道。新的Hash函数结构4.双管道结构双管道结构是并联两个尺寸相同的的窄管道Hash函数，除了它们都要加入消息之外，它们的链值还要互相影响。最后再用其中一个压缩成摘要。采用双管道结构的函数BMW算法新的Hash函数结构