北京交通大学-密码学-第11章-Hash函数

第11章Hash函数本章内容Hash函数概述定义用途发展现状安全性Hash函数的构造基于分组密码的Hash函数迭代型Hash函数的一般构造SHA系列Hash函数Hash函数的定义杂凑函数H是一公开函数，用于将任意长的消息M映射为较短的、固定长度的一个值H(M)，作为认证符，称函数值H(M)为杂凑值、杂凑码或消息摘要。杂凑值是消息中所有比特的函数，因此提供了一种错误检测能力，即改变消息中任何一个比特或几个比特都会使杂凑值发生改变。又称为：哈希函数、散列函数、杂凑函数。Hash函数的定义Hash函数的性质1、H可以作用于一个任意长度的数据块；2、H产生一个固定长度的输出；3、对任意给定的x，H(x)计算相对容易，无论是软件还是硬件实现；4、单向性（抗原像）（one-way）：对干任意给定的消息，计算其哈希值容易.但是，对于给定的哈希值h，要找到M使得H(M)＝h在计算上是不可行的.5、弱抗碰撞（抗二次原像）（weaklycollision-free）：对于给定的消息M1，要发现另一个消息M2，满足H(M1)＝H(M2)在计算上是不可行的.6、强抗碰撞（stronglycollision-free）：找任意一对不同的消息M1，M2，使H(M1)＝H(M2)在计算上是不可行的.前3条要求具有实用性，后3条要求具有安全性.Hash函数的定义单向性：即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息；否则,设传送数据C=M,H(M‖K),K是密钥.攻击者可以截获C，求出Hash函数的逆，从而得出H-1(C),然后从M和M‖K即可得出K.弱抗碰撞性：是保证一个给定的消息的散列码不能找到与之相同的另外的消息，即防止伪造。否则，攻击者可以截获报文M及其Hash函数值H(M),并找出另一报文M’使得H(M’)=H(M).这样攻击者可用M’去冒充M，而收方不能发现。强抗碰撞性：是对已知的生日攻击方法的防御能力。密码学上安全的杂凑函数H应具有以下性质：（1）对于任意的消息x，计算H(x)是容易的；（2）H是单向的；（3）H是强无碰撞的。注：单向性主要是防止签名消息的泄漏，而无碰撞性则是为了防止伪造攻击。Hash函数的分类根据安全水平定义1(弱无碰撞),散列函数h称为是弱无碰撞的,是指对给定消息x∈X，在计算上几乎找不到异于x的x'∈X使h(x)=h(x')。定义2(强无碰撞),散列函数h称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。注：强无碰撞自然含弱无碰撞！Hash函数的分类根据是否使用密钥改动检测码MDC(ManipulationDetectionCode)不带密钥的哈希函数主要用于消息完整性消息认证码MAC(MessageAuthenticationCode)带密钥的哈希函数主要用于消息源认证和消息完整性•下文提到的hash函数，都是指这一类，也称为哈希函数、散列函数或杂凑函数Hash函数的用途消息认证，包括消息完整性检测和消息源认证消息的存储；消息的传输。应用于数字签名。具有以下优点：提高数字签名的速度；不泄露签名所对应的消息；将对消息的签名变换与加密变换分开处理。带密钥的杂凑函数计算出的消息摘要可作为MACHash函数的其他应用常用来产生单向口令文件系统中存储的是口令的Hash值而不是口令本身；用于入侵检测和病毒检测通过保存和检查系统中文件的Hash值；Flame木马能用于构建随机函数(PRF)或用作伪随机数生成器(PRNG)Hash函数的基本用法——消息认证Hash函数的基本用法——消息认证Hash函数的基本用法——消息认证Hash函数的基本用法——数字签名Hash函数的基本用法——数字签名Hash函数的发展1978年，Merkle和Damagad设计MD迭代结构；1993年，来学家和Messay改进MD加强结构Hash函数的发展散列算法MD族是在90年代初由MITLaboratoryforComputerScience和RSA数据安全公司的Rivest设计的，MD代表消息摘要.MD2、MD4和MD5都产生一个128位的信息摘要.MD2（1989年）MD4（1990年）MD5（1991年）RIPEMD-128/160/320,由欧洲团队开发设计值得注意得是，MD4，MD5已经在2004年8月Crypto2004上，被我国密码学者王晓云等破译，即在有效的时间内找到了它们的大量碰撞。Hash函数的发展SHA系列算法是NIST根据Rivest设计的MD4和MD5开发的算法.国家安全当局发布SHA作为美国政府标准.SHA-0SHA-0正式地称作SHA，这个版本在发行后不久被指出存在弱点.SHA-1SHA-1是NIST于1994年发布的，它与MD4和MD5算法非常相似，被认为是MD4和MD5的后继者.SHA-2SHA-2实际上分为SHA-224、SHA-256、SHA-384和SHA-512算法.Hash函数的发展HAVLA1992年YuliangZheng设计了HAVAL函数，它与许多其他散列函数不同.Gost是一套苏联标准.Hash函数的发展算法输出长度(bits)初始状态长度(bits)分块长度(bits)最大消息长度字长圈数操作碰撞SHA-0160160512264-13280+,and,or,xor,rotl有SHA-1160160512264-13280+,and,or,xor,rotl263攻击SHA-256/224256/224256512264-13264+,and,or,xor,rotl,shr没有SHA-512/384512/38451210242128-16480+,and,or,xor,rotl,shr没有Hash函数的发展Hash函数的发展现状NESSIE工程推荐使用的hash算法有SHA-256/384/512和Whirlpool;日本密码研究与评估委员会推荐使用的算法有RIPEMD-160、SHA-256/384/512。ECRYPT也在hash算法研究方面举办了一系列活动。此外，NIST于2008年启动新的hash标准的征集活动。除迭代结构以外的结构适用于任何平台的压缩函数2008年10月提交文档，收到64个算法，公开56个，51个进入第一轮评估2009年10月，第二轮评估开始，剩余14个算法第三轮剩余五个算法，2012年10月2日，Keccak被选为SHA-3;针对Hash函数的攻击穷举攻击原像攻击和第二原像攻击（apreimageorsecondpreimageattack）对于给定的Hash值h，试图找到满足H(y)＝h的y；对于m位的Hash值，穷举规模大约是2m.碰撞攻击（collisionresistance）找到两个消息x≠y,满足H(x)=H(y)对于m位的Hash值，预计在2m/2次尝试后就将找到两个具有相同Hash值的数据.因此对于m位的Hash值，抗穷举攻击的强度为2m/2目前128-bits以不够,需要160-bits甚至更多.Hash函数的生日攻击比如：考虑教室有30位同学，定义函数H:{张三,李四,······|在教室里的同学}→{1,2,······,365}如果有两个同学的生日相同，则称为一个“碰撞”.直观看来，产生碰撞的可能性较小.但是,对于30个人的人群,这个事情发生的可能性大约为1/2.当人数增加时，这个可能性就增大.这个事实与我们的直观相悖,称为”生日悖论”.①问题：某个人是10月1日生日的概率为1/365.②问题：教室里有人是10月1日生日的概率是多少？③问题：某个同学与其他任何一个同学生日相同的概率为多少？④问题：教室有两个同学具有相同生日的概率是多少？我们对于一般的函数H:{0,1}m→{0,1}n进行回答.Hash函数的生日攻击Hash函数的生日攻击Hash函数的生日攻击Hash函数的生日攻击Hash函数的生日攻击即对于n位的Hash值，只要尝试2n/2次，就至少存在一对X和X’，使得H(X)＝H（X’)相同;2/5.05.05.02)2(17.1nnNNs生日攻击举例•由于两个消息的Hash值相同，所以它们产生的签名也相同，因此攻击者即使不知道加密密钥也能攻击成功。针对Hash函数的密码分析利用算法的某种性质进行攻击；Hash函数使用迭代结构将消息分组后分别进行处理密码分析的攻击集中于压缩函数f的碰撞Hash函数的构造基于数学难题的构造方法：计算速度慢，不实用利用对称密码体制来设计Hash直接设计基于分组密码的Hash函数基于分组密码的CBC工作模式杂凑函数H：定义()lyHx基于分组密码的CFB工作模式杂凑函数H：定义()lyHx上述两种基于分组密码的杂凑函数中，K可以公开，称为不带密钥的Hash函数；K也可以不公开，称为带密钥的Hash函数（MAC）。在K公开的情况下，上述两种构造杂凑函数的方法是不安全的,即容易找到碰撞。（思考题）迭代型Hash函数的一般结构迭代型Hash函数的一般结构算法中重复使用一个压缩函数ff的输入有两项，一项是上一轮输出的n比特值CVi-1，称为链接变量，另一项是算法在本轮的b比特输入分组Yi-1f的输出为n比特值CVi，CVi又作为下一轮的输入算法开始时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CVL即为最终产生的杂凑值。通常有bn，因此称函数f为压缩函数。算法可表达如下：CV0=IV=n比特长的初值；CVi=f(CVi-1,Yi-1)；1≤i≤L；H(M)=CVL迭代型Hash函数的一般结构算法的核心技术是设计难以找到碰撞的压缩函数f，而敌手对算法的攻击重点是f的内部结构f和分组密码一样是由若干轮处理过程组成对f的分析需要找出f的碰撞。由于f是压缩函数，其碰撞是不可避免的，因此在设计f时就应保证找出其碰撞在计算上是不可行的迭代型Hash函数的一般结构SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1Hash函数SHA-1是美国及许多国际组织的标准SHA-1目前还可以应用2005年，王小云用269次操作找到两个独立的消息，使它们具有相同的SHA-1值；NIST计划2010后逐步转而依赖SHA-2Hash函数；2012年10月，已经选定Keccak作为SHA-3;SHA-2Hash函数1、SHA－2的概况2002年，公布了SHA－2（FipsPUB180－2）SHA－2包括4个Hash函数：SHA－224，SHA－256，SHA－384，SHA－512目的：与AES配套，增强安全性与Sha－1比较结构相同逻辑函数相同模算术相同；SHA-2Hash函数SHA-2Hash函数SHA-512SHA-2Hash函数SHA-2Hash函数SHA-2Hash函数SHA-512轮函数SHA-2Hash函数SHA-2Hash函数SHA-2Hash函数SHA-2Hash函数SHA-512轮函数中压缩字的产生方式SHA-2Hash函数SHA-512SHA-512的结构与SHA-1相同；SHA-512的输出长度比SHA-1长，因此抗穷举攻击能力增强；SHA-512的4个逻辑函数与SHA-1变化不大；SHA-1每20轮使用一个逻辑函数；SHA-2每轮都使用一个逻辑函数；SHA-3SHA-1还没有被攻破•但因为与MD5&SHA-0具有相似的结构和基本数学运算，后两者已经被攻破；•因此认为SHA－1是不安全的，应逐步被SHA－2取代；SHA-2(特别是SHA-512)安全强度很高•但也与SHA－1具有相似的结构和