Hash函数可以将任意长的消息压缩为固定长的摘要,是一类重要的基础密码算法,有着广泛的应用,是数字签名中的重要部件,用于抵抗存在性伪造攻击,也可用于密钥推导,构造消息认证码,伪随机数生成器等。此外Hash函数还可以构造分组密码,作为可证明安全中的随机谕示。消息认证码(MAC)通常被称为带密钥的Hash函数,是三类对称密码算法之一,广泛的应用于计算机网络和电子商务中,对消息提供完整性保护和认证,其中CBC-MAC是一个通用的标准MAC算法。2005年,王小云提出了模差分分析方法,破解了MD系列Hash函数(MD4,MD5,RIPEMD,SHA-0和SHA-1),引起了Hash函数研究的新高潮。为了应对MD5和SHA-1两大国际通用算法的破解,NIST做出了积极响应,利用两年时间完成了对Hash函数的安全现状评估,并启动了新的Hash函数征集工程(SHA-3),Hash函数的设计与分析是密码学界最为关注的热点问题之一。Hash函数研究上的突破推动了MAC的研究,MAC的研究又对Hash函数的安全性提出了新要求。SHA-3工程的参赛算法体现了近几年的研究成果,并产生了一些新的设计理念,使算法具有更高的性能。对MAC算法和Hash函数等具有迭代结构的算法,主要从结构和迭代的基本单元两部分保证其安全性。在导师的悉心指导下,首先我们利用CBC迭代结构的特点和生日攻击给出了CBC-MAC系列算法的新的区分攻击和第二原像攻击,结合SHA-3第二轮候选算法Luffa的结构特点和广义生日攻击,我们给出了其安全性分析。然后深入到算法的内部——迭代单元,我们给出了构造纯文本的有意义的MD4碰撞实例的方法,并利用相关密钥三明治矩形(Rectangle-Like Sandwich)攻击对基于Hash函数SHA-2的分组密码算法SHACAL-2给出了44轮的密钥恢复。(1)CBC-MAC系列算法的区分和第二原像攻击CBC-MAC是基于分组密码的密码分组链接(CBC)模式构造的消息认证码,被很多国际组织和机构定为标准,如标准ANSI X9.9、FIPS PUB 113和ISO／IEC9797,是金融贸易中使用最广的消息认证码。1995年,Preneel和van Oorschot提出了区分迭代MAC和随机函数的一般方法,利用生日攻击得到内部碰撞,并进行识别。然而,我们注意到,当只要一个分组是变量的情况下,CBC-MAC系列算法具有无碰撞性。主要因为它所基于的分组密码的置换特性。因此,我们可以利用无碰撞性区分基于分组密码的MAC算法和随机函数。在CBC-MAC算法中,用其中一个分组作为变量,其余的分组作为常量,该MAC算法也应该是无碰撞的。该区分攻击也适合于其他基于分组密码的MAC算法如EMAC、XCBC和CMAC等。2009年,王小云等提出了利用生日攻击识别满足特殊差分的内部几乎碰撞的新方法,即利用生日攻击,通过收集足够多的消息对,产生内部的几乎碰撞,然后利用特殊的差分路线,将内部的几乎碰撞识别出来。在上述思想的启发下,我们提出了新的CBC-MAC系列算法的第二原像攻击。主要利用CBC的迭代结构,将第二原像攻击的复杂度转换为生日攻击的复杂度。具体如下,给定具有两个分组的消息M1‖M2,我们想要构造一个新的消息M′‖M′2,使他们具有相同的MAC值,即EK(M′1)(?)M′2=EK(M′1)(?) M2。根据CBC模式,我们知道EK(M1)(?)=EK(M′1)(?)M2,随机选择M′1,M′2,利用生日攻击,寻找一个碰撞,即MACK(M1‖M′2)=MACK(M′1‖M′2)。在此基础上,我们对现有的一些MAC算法的迭代结构进行总结,提出了一种通用的模型gf1·f2：{0,1}b1×{0,1}b2→{0,1}n，其中b1,b2≥n,f1：{0,1}b1,→{0,1}n和f2：{0,1}b2→{0,1}n是两个映射,x∈{0,1}b1,y∈{0,1}b2是相互独立的。为了方便描述,将gf1·f2正简记为g。函数g具有异或结构,通过转换,可以利用Yuval的生日攻击,对函数g求其第二原像。如果一个MAC算法,记为C,可以转换为以下形式其中.f是置换,g(x,y)=f1(x)(?)f2(y),x和y相互独立,mf是消息分组的级联。对于任何大于两个分组的消息,存在一个算法构造它的第二原像,具有生日攻击的复杂度。我们的第二原像攻击是Brincat和Mitchell攻击[4]的扩展,不仅可以构造CBC-MAC、EMAC、XCBC等算法的第二原像,也适用于MT-MAC、PMAC和基于三个密钥的CBC模式的MAC等算法的第二原像攻击。(2)SHA-3参赛算法Luffa的安全性分析Luffa算法是SHA-3第二轮候选算法之一,在高端平台上具有很高的性能。Luffa算法基于变种的sponge结构,基于sponge结构的Hash函数虽然被Bertoni等证明当迭代的基本算法是随机置换时与随机函数是不可区分的[6],但多数基于sponge结构的Hash算法,利用简化的分组密码算法和简单的置换作为基本算法,实际上并不能达到理想的安全强度。变种的sponge结构在消息注入方式上和最后的Hash值的输出方式上做了些修改。在SHA-3的候选算法中也有许多算法是基于变种的sponge结构,其安全性有待进一步研究。本文给出了Luffa的伪碰撞,伪第二原像和伪原像攻击。Luffa算法基于变种的sponge结构,其消息注入函数MI可看作是由初始值(IV)决定的消息扩展函数,将256比特的消息输入扩展为整个状态值w个256比特的字,然后对状态值进行w个256比特的置换,其中w取决于Hash值的长度,对Luffa-224/256,Luffa-384,Luffa-512,w分别为3,4,5。IV是w个256比特的字,消息是256比特的字,因此MI将w+1个256比特的字压缩为w个256比特的字。若将初始值看作是变量H=(H0,H1,H2),则MI的碰撞即为Hash函数的碰撞。因为MI是线性变换,将MI的输出差分置为零,我们可以求出输入变量H和M的差分关系。经过计算发现,改变5比特的IV,可以获得Luffa-256的伪碰撞和伪第二原像。对Luffa-384,计算伪碰撞和伪第二原像需要改变7比特的IV。计算Luffa-512的伪碰撞和伪第二原像,IV存在一个12比特的差分。这些攻击可用于构造利用密钥作为初始值的MAC的相关密钥攻击。Luffa-256的伪原像计算是非常容易的,将初始值看作变量,可以直接对Hash函数求逆。Luffa-384／512的Hash值由两次空迭代的输出值级联而成Z0‖Z1,直接求逆并不容易,因为它有两个等式需要满足。我们结合Luffa算法的特性和扩展的广义生日攻击给出了Luffa-384/512的伪原像攻击。以Luffa-512为例,我们以最后一次迭代函数的线性变换MI的输出X0,X1,X2,X3,X4作为输入,根据Luffa函数的定义,我们可以得到两个等式：因为等式(1)比较简单,容易控制,我们可以进行分割攻击。固定变量的一部分比特,使等式的一部分比特关系成立,用另一部分控制使剩下的比特关系和等式(2)成立,经过权衡我们可以让等式(1)的低128比特成立,即当i=0,1,2,3时,令Xi的低128比特是固定的常量CST,X4的低128比特是CST(?)l128(0xf(?)Z0)。用这5个变量的高128比特满足如下等式利用扩展的Wagner的广义生日攻击对等式(3)和(4)进行求解。对Luffa-384,寻找到一个伪原像需要264次迭代运算和267字节的存储,对Luffa-512,复杂度是2128次迭代运算和2132字节存储。(3)有意义的MD4碰撞攻击MD4算法是Rivest在1990年针对32位计算机设计的一个非常有效的Hash算法。在1996年,Dobbertin给出了MD4全算法的碰撞攻击,并构造了纯文本模式下的有意义的碰撞,但在碰撞开始的地方具有4个随机的字。2005年,王小云等提出了模差分分析方法,可以有效构造MD系列Hash函数的碰撞,如MD4,RIPEMD,MD5,SHA-0和SHA-1,而且这这些技术可以用于寻找MD4的变种的第二原像[10],引起人们对Hash函数的强烈关注。一些研究人员结合文件格式的冗余利用随机碰撞构造有意义的碰撞：如证书伪造,PS文件,PDF, TIFF和MS Word 97文档等有意义的碰撞的构造。其主要方法是将随机碰撞插入到文档的控制命令中,(如PS文件的“if-then-els0”命令),这样这些文档的Hash值是一样的,但显示的内容完全不一样。这些碰撞在实际中都可能造成严重威胁。虽然MD4算法已经被破解,但在一些需要追求压缩效率的环境中,仍然可能被应用。根据文件编码格式构造有意义的碰撞也是非常重要的。但这种有意义的碰撞比随机碰撞构造更为复杂,因为它对消息要求更苛刻。为了让字符可以被计算机表示,利用字符编码将每一个字符映射为一个可被计算机表示的数值,这些数值可以是单字节的形式也可以是多字节的形式。本文的分析是基于单字节编码方式的。利用王小云提出的模差分和消息修改方法,对构造纯文本文件的有意义的MD4碰撞进一步分析和探讨。结合具体的编码方式对MD4的碰撞路线进行了分析,效率高的随机碰撞路线并不一定可用于构造纯文本文件的有意义的碰撞。需要考虑差分位置对单词和句子的影响,如果消息字的模减差分包含如下形式±27,±215,±223,±231,则碰撞消息对M和M′将有一个存在非可视字符,不适合构造有意义的碰撞差分路线。结合编码格式,我们对MD4的碰撞路线进行研究,综合考虑差分路线所有的条件及分布情况。条件数越少,越稀疏,一个文本消息对成为碰撞的可能性就越大。其中于红波等给出的差分路线有助于我们构造有意义的碰撞。我们选择的差分路线的消息差分为M=(m0,m1,...,m15),因为i=7,15,23,31,M和M′将有一个存在非可视字节。当i=17,26时,差分路线有更多的条件。因此我们排除下面的差分路线,其中i=±k,k=7,15,17,23,26,31。我们研究了路线条件与消息字节相应比特的对应关系,当消息字差分△-m4为±20+8k七和±22+8k时,k=0,1,2,3,在第一轮只有一个条件对应消息字节的第8比特,其他差分形式与第8比特关联的比较多。因为与消息字节的第8比特关联,需要借助比特进位进行消息修改,修改成功后仍然有意义的概率比其他比特低,因此我们以消息差分△-m4=1为例,给出了句子结构的构造方式,在句子构造的时候,可以选择人名、价格、编号等,使消息有足够的自由度进行第一轮修改。然后从m0到m15,边修改边检测,逐步确定消息字具体的值。1.先确定前6个字m0到m5,根据消息差分,确定存在差分的字符的形式如数字或字母。2.确定m6到m13八个字,利用简单消息修改结合进位技术,同时对句子进行检测,避免出现不可视字符、无意义的单词和不连贯的句子。3.利用m14,m15两个字让第2、3轮共38个条件成立,在搜索的过程中用m14,m15进行高级消息修改降低寻找碰撞的复杂度。其中a5,6,a5,18,a5,29,d5,6d5,13,c5,13和c5,18这7个条件可以通过高级消息修改使之以高概率成立。我们给出的构造纯文本文件的有意义MD4碰撞的方法,概率为2-33.77,并给出一个基于ISO Latin-1字符集的有意义的MD4碰撞。基于该碰撞敌手可以进行一些伪造和诈骗活动。(4)改进的44轮SHACAL-2的相关密钥攻击SHACAL-2加密算法是NESSIE工程获选的分组密码算法之一,由Handschuh和Naccache设计,该算法基于NIST的Hash函数标准SHA-256的压缩函数,明文作为链接变量,密钥作为消息,因此其分组长度是256比特,密钥长度是512比特。SHA-2的碰撞路线可以用于该分组算法的分析,SHA-2存在一些局部碰撞,可以利用局部碰撞构造长的碰撞路线。Wagner在1999年提出了飞去来器(Boomerang)攻击,使用两个独立的差分特征进行自适应的选择明密文攻击,每个差分特征覆盖密码算法的一半。Kelsey等改进为选择明文的攻击,称加强的飞去来器(Amplified Boomerang)攻击(Biham等独立提出,称为矩形(Rectangle)攻击)。因此可以结合SHA-2的两个局部碰撞构造矩形区分器,进而进行攻击。因为SHA-2的局部碰撞构造中,消息上存在差分,因此该矩形攻击是在相关密钥的情况下进行的。2008年,Lu等给出了相关密钥的35轮的矩形区分器,概率为2-460,利用该区分器,进行了44轮的恢复密钥攻击,2009年韦永壮等将35轮矩形区分器的概率提高为Lu等的16倍。三明治矩形攻击[23]是Dunkelman等提出的,是飞去来器攻击的扩展。三明治(Sandwich)攻击在飞去来器的基础上增加了一个中间层,可以对有些飞去来器攻击进行改进。我们采用相关密钥三明治矩形攻击,改进了44轮SHACAL-2的相关密钥攻击。我们将35轮的SHACAL-2分为3个部分E=E1(?)EM(?)E0,其中E0为前24轮(0-24),EM为24-25轮,E1为25-35轮。以前的相关密钥飞去来器攻击,一般选取Eo为前25轮,而我们只选择前24轮为E0,然后利用中间轮EM进行扩充。因为利用第25轮的输出差分不能转换为E1的输入差分,这是一种不可能的情况。但是利用第24轮的输出差分可以直接转换为E1的输入差分,概率为1。第24轮的输出差分是0,因为SHACAL-2的轮函数是非平衡的Feistel结构,只需要第25轮更新的字A25和E25满足E1的输入差分。因为E1中ΔA25=0和ΔE25=0,所以当一个对满足E1的输入差分的条件下,另一个对也满足。我们利用模减差分和异或差分的混合表示方式以及采用差分集合代替单个差分提高差分路线E1的概率,在我们的分析中Eo的输入输出差分都是异或差分,E1的输入差分是异或差分,输出差分是模减差分。我们给出了El中差分路线成立的充分条件,在密钥恢复的过程中,利用模减差分和差分路线的条件进行过滤,增加了密钥过滤的强度。本文构造的35轮相关密钥三明治矩形区分器的概率为2-430,是Lu等的35轮区分器的230倍。利用我们的区分器给出了相关密钥情况下44轮SHACAL-2的密钥恢复攻击,复杂度为2217个选择明文,2476.92次44轮SHACAL-2加密,2222字节存储。