密码杂凑算法综述

王小云于红波

1(清华大学高等研究院 北京 100084)2(密码技术与信息安全教育部重点实验室(山东大学) 济南 250100)3 (清华大学计算机系 北京 100084)



密码杂凑算法综述

王小云1,2于红波3

1(清华大学高等研究院 北京 100084)2(密码技术与信息安全教育部重点实验室(山东大学) 济南 250100)3(清华大学计算机系 北京 100084)

(xiaoyunwang@mail.tsinghua.edu.cn)

密码杂凑算法是现代密码学中的基本工具，它能够将任意长度的消息压缩成固定长度的摘要.杂凑值又称为杂凑码、消息摘要或数字指纹.通常密码杂凑算法被非正式地称为杂凑算法.杂凑算法的重要性就是能够赋予每个消息唯一的“数字指纹”，即使更改该消息的一个字母，对应的杂凑值也会变为截然不同的“指纹”.杂凑算法在现代密码学中有着极其重要的作用，它最常用的用途是用在数字签名和数据完整性保护中.杂凑算法是数字签名的核心技术，通常用公钥密码算法如RSA进行数字签名时，一般不是对消息直接签名，而是对消息的杂凑值进行签名，这样既可以减少计算量，提高效率，也可以破坏数字签名算法的某些代数结构，保障其安全性.杂凑算法还是许多密码算法密码系统安全的基本前提条件，它可以用来设计消息认证码以及众多可证明安全协议，还广泛应用于口令保护协议、电子支付协议、广播认证协议等密码协议中.因此对杂凑算法进行研究在密码学领域具有重要的意义.

密码杂凑算法；碰撞攻击；原像攻击；MD5算法；SHA-1算法；SHA-3算法

密码杂凑算法在现代密码学中起着重要作用，它可以将任意长度的消息压缩成固定长度的摘要.给定1个消息计算其杂凑值是容易的，但是找到具有相同杂凑值的2个不同消息则是困难的，许多密码体制的安全性正是基于这一属性.

最早的杂凑算法不用于密码学，而源于1953年IBM的历史性讨论，其思想就是把消息的关键词打乱，并且使用这部分信息作为查找的索引，通过构造杂凑表进行存储和查找，Knuth[1]对这类杂凑算法进行了综合描述.1979年，Merkle[2]第1次给出了单向杂凑算法的实质性定义，包含抗原像和第二原像的安全属性，以提供安全可靠的认证服务.1980年，Davies和Price[3]将杂凑算法用于电子签名，用于抵抗RSA等数字签名中的存在性伪造攻击，标志着密码杂凑算法的开始.1987年，Damgård[4]首次给出抗碰撞的杂凑算法的正式定义，指出了抗碰撞性和抗第二原像性，并用于设计安全的电子签名方案.由于杂凑算法的高效性和无代数结构特性，常被用作伪随机数生成器，成为带随机谕示的可证明安全密码体制的一项核心技术.

除了数据压缩、易于计算这2个基本属性之外，杂凑算法还应该满足下面3个安全属性：

1) 单向性(抗原像攻击).给定输出值y，计算输入值x，使y=H(x)是困难的，其理想的计算复杂度是搜索攻击的复杂度.

2) 抗第二原像攻击(弱抗碰撞性).给定输入值x，计算另一个输入值x′，使H(x)=H(x′)是困难的，理想的计算复杂度是搜索攻击的复杂度.

3) 抗碰撞攻击(强抗碰撞性).寻找x≠x′，使H(x)=H(x′)是困难的.理想的复杂度为生日攻击的复杂度.

随着杂凑算法分析技术的进步，自2004年以来出现了一些新的理论分析结果，如长消息的第二原像攻击[5]和集群攻击[6]等.这些分析技术也可以用于其他密码体制的分析，尤其在消息认证码的理论分析方面，可以进行区分攻击、伪造攻击等.为了避开杂凑算法和基于杂凑算法的消息认证码的上述攻击，美国国家标准技术研究所(NIST)在全球范围内征集新的杂凑算法安全属性，经过一年的研究，补充了抗长度扩展攻击的安全属性：

4) 抗长度扩展攻击.给定H(IV,M)，对于任意的消息M′，当仅知道M的长度时，直接利用H(IV,M)计算H′=H(IV,M‖padM‖M′)是困难的.

杂凑算法是密码学的3类基础算法之一(加密算法、数字签名算法和杂凑算法)，主要用于数据的完整性校验、基于口令的身份认证、提高数字签名的有效性和安全性、密钥推导、构造基于密码杂凑算法的消息认证码和构造确定性随机比特生成器等，对杂凑算法进行研究对理论和实际是有重要意义的.

1 杂凑算法设计技术

杂凑算法在密码学中具有重要的地位，如何设计出快速安全的杂凑算法一直是密码学重要的研究问题.直接设计一个算法能够将任意长度的消息压缩成固定长度的杂凑值并不是一件容易的事情.已有的杂凑算法都是基于压缩函数(或置换函数)的迭代结构设计的.每个压缩函数的输入为一固定长度的消息分组，而且每个消息分组采用相似的操作.

基于迭代压缩函数的杂凑算法设计整体结构如下：

1) 对消息进行填充，使得成为消息分组长度的整数倍；填充方法有多种，可以参照文献[7-8]；

2) 对填充后的消息按消息分组长度进行分组；

3) 使用压缩函数对每个消息分组依次进行迭代压缩；

4) 对最后一个消息分组的输出进行变换得到杂凑算法的输出.

杂凑算法的设计包括迭代结构的设计以及压缩函数的设计.

1.1 杂凑算法的迭代结构设计

在CRYPTO 1989上，Merkle[9]和Damgård[10]独立给出了构造杂凑算法的迭代结构，后被称为MD结构(Merkle-Damgård structure).MD结构基于压缩函数的迭代，任何抗碰撞性的压缩函数在MD结构下都能拓展为抗碰撞的杂凑算法，将如何构造抗碰撞杂凑算法的问题转化成如何构造抗碰撞压缩函数的问题.MD结构是使用最广泛的杂凑算法构造方法.在CRYPTO 1990上，Rivest[11]设计了第1个基于MD结构的专用的杂凑算法MD4算法.此后又出现了基于MD结构的MD5[12]、HAVAL[13]、SHA-1[7]、SHA-2系列[8]、RIPEMD系列[14]以及我国商用杂凑标准SM3[15]等.MD结构杂凑算法如图1所示：

图1 MD结构杂凑算法图

随着杂凑算法分析方法的不断成熟，MD结构算法暴露出了一些典型的问题，比如长度扩展攻击、二次碰撞攻击、多碰撞攻击[16]和长消息第二原像攻击等.为了克服MD结构带来的问题，一些改进的MD结构随之出现.比如，Liskov[17]在SAC 2006上提出了Zipper结构等.但这些改进通常比较复杂，实现效率低.同时，为了抵抗生日攻击和多碰撞攻击，Lucks[18]在ASIACRYPT 2005上提出了宽管道和双管道的结构.该结构要求将压缩函数的初始值加倍，来防止生日攻击、多碰撞攻击，但这可能导致压缩函数扩散变慢.RIPEMD系列算法即为典型的双管道算法，这些算法并联使用2个尺寸相同的窄管道杂凑算法，对每个消息分组并行压缩2次，对最终的压缩结果再进行压缩得到杂凑值.在EUROCRYPT 2015上，Leurent和Wang[19]证明了通过这种方法构造的杂凑算法抵抗原像攻击的能力有所减弱.

宽管道和双管道结构杂凑算法如图2、图3所示：

图2 宽管道结构杂凑算法图

图3 双管道结构杂凑算法图

图4 HAIFA结构杂凑算法图

针对MD结构杂凑算法易受第二原像攻击的弱点，Biham和Dunkelman[20]在2006年的杂凑算法研讨会上提出了HAIFA结构，在压缩函数的输入中增加随机盐值(salt)和已杂凑比特(bh).SHA-3征集活动第3轮(最终轮)的候选算法之一的BLAKE[21]算法即是典型的HAIFA结构杂凑算法.HAIFA结构杂凑算法如图4所示.

在ECRYPT 2007上，由Bertoni等人[22]提出了基于大状态置换的海绵体结构(sponge structure)的杂凑算法，海绵体结构杂凑算法通常包含吸收(sbosbing)和压缩(squeezing)2个过程，如图5所示.

图5 海绵体结构杂凑算法图

目前，海绵体结构已经成为继MD结构后被使用最广泛的结构，如SHA-3标准KECCAK[23]使用海绵体结构，轻量级杂凑算法PHOTON[24]，QUARK[25]，SPONGENT[26]等都使用海绵体结构设计.

1.2 杂凑算法压缩函数的设计

1.2.1 基于分组密码的杂凑算法的设计

杂凑算法有2种基本的构造方法：基于分组密码的构造方法和直接构造法(定制杂凑算法).最早的杂凑算法设计方式是基于成熟的分组密码.最简单的转换方法是利用密码分组链接(CBC)或密码反馈(CFB)模式，将密钥替换为初始值，对消息的分组逐次加密，最后的密文即是杂凑值.这种杂凑算法都是基于成熟的分组密码，其安全性分析侧重于结构的分析.

当杂凑值长度等于分组密码的分组大小时，通常对杂凑算法的每个输入分组Mi进行一次迭代加密，最后的密文就是杂凑值.这类迭代结构概括如下：H0=IH，IH是一个随机的初始值.Hi=EA(B)⊕C，其中A,B,C∈{Mi,Hi,Mi⊕Hi,c}，c是一个常量.Preneel等人[27]对总共的64种情况给出了详细的分析，其中12种结构是安全的，能够抵抗直接攻击(direct attack)、置换攻击(permutation attack)、前向攻击(forward attack)和后向攻击(backward attack)这4种攻击，仅有4种结构能够抵抗除这4种攻击以外的固定点攻击(fixed point attack).最常用的几种基于分组密码的结构包括DM(Davies-Meyer)结构、MMO(Matyas-Meyer-Oseas)结构和Miyaguchi-Preneel结构等.如杂凑算法MDC-2、MDC-4、旧的俄罗斯标准GOST R34.11-94等都是基于分组密码算法的DM结构；SHA-3候选算法Skein是基于分组密码算法的MMO结构.

1.2.2 定制杂凑算法的设计

1990年，美国密码学家Rivest[11]针对32位计算机系统，设计了杂凑算法MD4.该算法不基于分组密码等任何的密码学本原，称为定制杂凑算法(dedicated hash function)，MD4具有高速的软件实现效率.Rivest[12]又设计了MD4的加强算法MD5，2个算法的杂凑值长度均为128 b.HAVAL是1992年由Zheng(郑玉良)等人[13]设计，主要利用高度非线性的轮函数代替MD4和MD5普遍采用的简单的轮函数.基于MD4的设计技术，NIST[7]设计了安全杂凑算法SHA系列，包括SHA-0，SHA-1，其杂凑值的长度都是160 b.SHA系列算法继承了MD4的设计特色，进一步使用了消息扩展算法来加强算法的安全性.2002年NIST又推出SHA-2系列杂凑算法[8]，其输出长度可取224 b，256 b，384 b，512 b，分别对应SHA-224，SHA-256，SHA-384，SHA-512.SHA-2系列杂凑算法比之前的杂凑算法具有更强的安全强度和更灵活的输出摘要长度.与此同时，著名的欧洲密码工程RIPE(RACE integrity primitives evaluation)设计了RIPEMD[28]，该算法基于2条并行的MD4结构.随后，Dobbertin等人[14]又设计了其强化变种版本RIPEMD-128和RIPEMD-160.这些杂凑算法都是在MD4设计思想的基础上，介入了新的设计理念，以提高算法的安全性，统称为MDx系列杂凑算法.

1.2.3 杂凑算法标准

现代密码学的发展离不开各类国际密码组织的推动.在这些密码组织的推动下，杂凑算法的设计和分析得到了长足的发展.

RIPE工程是由欧洲1988年发起的，通过公开征集的方式开发一些基本的密码算法，对欧盟宽带通信信息进行完整性保护并提供认证服务.主要征集身份识别算法、杂凑算法、消息认证算法和数字签名算法，由RIPE进行评估.第1次征集共有31个提交方案，经过2个阶段的评估，最终有7个方案获选.在此基础上启动了第2次征集，并于1992年结束，确定了杂凑算法RIPEMD.

NESSIE(new european schemes for signature, integrity, and encryption)工程是欧盟信息社会技术(IST)发展规划所支持的项目之一，开始于2000年1月，历时3年，2002年12月结束.该工程面向国际征集数字签名、杂凑算法和分组密码等各类密码算法.与RIPE工程一样，NESSIE工程的征集和筛选过程都是公开透明的，最终获选的杂凑算法是Whirlpool和SHA-2系列.

NIST[7]于1993年推出了SHA-0和SHA-1算法.SHA-1于1995年被确定为NIST标准.2002年，NIST[8]推出了强度更高、输出杂凑值长度224 b,256 b，384 b，512 b这4种长度可选的SHA-2系列算法.2004年至2005年我国密码学家王小云等人破解了国际通用系列杂凑算法，包括MD5[29]，SHA-1[30]，RIPEMD[31]，HAVAL[31]等，引起国际密码社会的强烈反响.为了应对MD5与SHA-1的破解，NIST于2007年至2012年开展了公开征集新一代杂凑算法标准SHA-3[32].SHA-3竞赛征集到了64个算法，这些候选算法各具特色，体现了很多新的设计理念.进入SHA-3最终轮的5个候选算法都采用了不同于MD结构的新型结构，KECCAK采用了海绵体结构，BLAKE采用HAIFA结构，Skein采用基于密文的唯一分组迭代(unique block iteration)链接模式，Grøstl和JH基于宽管道的MD改进结构.在内部变换中，KECCAK采用基于3维数组的比特级逻辑运算；BLAKE和Skein基于ARX运算；Grøstl采用AES类的设计；JH使用了扩展的多维AES结构.经过5年的遴选，KECCAK凭借其优美的设计、足量的安全冗余、出色的整体表现、高效的硬件效率和适当的灵活性最终胜出，成为SHA-3标准.

在杂凑函数的设计方面，2010年12月国家密码管理局公布了由王小云等人设计的我国商用密码杂凑算法SM3[15]，该算法结构简洁、软硬件实现效率高、安全强度高，其总体性能优于国际上广泛使用的杂凑函数标准SHA-256.目前SM3算法作为我国杂凑算法密码行业标准和国家标准已经被广泛推广使用.

1.2.4 轻量级杂凑算法的设计

近年来轻量级杂凑算法的设计已经成为杂凑算法设计以及密码学领域研究的热点.2008年，Shamir[33]设计了第1个能应用于RFID协议的轻量级MAC算法SQUASH，该算法只要求抵抗64b的原像攻击，而不需要抵抗碰撞攻击.同年Bogdanov等人[34]利用分组密码Present和双块模式构造了H-PRESENT-128算法.2010年，Aumasson等人[25]基于流密码的设计理念设计了QUARK算法；Guo等人[24]利用AES类操作与广义海绵结构设计了PHOTON算法；Bogdanov等人[26]基于分组密码Present和海绵结构设计了SPONGENT算法.2014年我国学者Wu(吴文玲)等人[35]设计了轻量级杂凑算法LHash.这些轻量级杂凑算法都采用了海绵体结构，安全冗余度很高.

2 杂凑算法分析技术

一个安全的杂凑算法需要满足3个性质：抗原像性、抗第二原象性和抗碰撞性.而近几年人们在评估杂凑算法安全性时，不仅考虑这3个经典的安全要求，同时还会考虑其在近似碰撞、差分区分器、反弹攻击及飞去来器(boomerang)区分器等攻击方面的抵抗性能，并认为若给定杂凑算法表现不同于期望的随机函数，则就被视为该杂凑函数的一个安全弱点.

对杂凑算法的攻击分为通用的杂凑算法攻击方法(该攻击方法不依赖于具体的杂凑算法)，以及针对一类或者是某个具体杂凑算法的攻击方法.

2.1 杂凑算法通用攻击方法

杂凑算法的用途之一就是口令认证，它是基于杂凑算法抗第二原像攻击的属性.破解口令最有效的办法就是遍历搜索.但由于其解空间太大，要么需要时间太长，要么空间要求过高.在这种情况下时间-存储折中攻击(TMTO)[33]被提出并广泛用于在可接受时间内破解密码.时间-存储折中攻击(TMTO)是1980年由Hellman[36]提出的，该方法分为预计算过程和在线密钥检索2个阶段.在预计算阶段，通过迭代系列起始点建立密钥的链表，构建TMTO表来存储链表的头结点和尾结点，供在线检索使用，如图6所示.在线密钥检索阶段是对给定的口令的杂凑值，通过检索TMTO表来寻找对应的密钥.TMTO方法通过预计算来达到在查找过程时间和存储的折中.这种时间-存储折中的方法是一种概率模型，无法确保100%成功率，成功率的大小将取决于分配的时间和内存的大小.为了降低同一表中出现杂凑值的合并和碰撞的概率，通常TMTO方法采用多个小的表进行存储和搜索，每张小表采用不同的约减函数.

图6 TMTO表建立过程

为了避免同一个表中可能存在合并和碰撞，且这些合并和碰撞仍然是检索表时额外计算开销的主要原因.2003年，Oechslin[37]提出的彩虹表法成功解决了这一问题，提升了时间-存储折中攻击的效率.在彩虹表法中，针对同1条密钥链，彩虹表使用1组约减函数而非1个约减函数，当2条链发生碰撞时，它们只有在碰撞发生在2条链的同一个位置时才会合并.如果碰撞并不在同一个位置发生，那么2条链的下一次生成将会使用不同的约减函数，因此它们不会合并.

LM-Hash(LAN manager hash)[38]是微软用于保存网络操作系统以及Windows操作系统口令而设计的杂凑算法.这个函数基于DES算法[39]，但设计上存在一定的缺陷，微软在Windows Vista及之后的版本不再使用该杂凑算法作为默认的口令存储函数，然而该算法在研究时间-存储折中攻击时仍然具有典型的意义.NTLM-Hash[40](简称NT-Hash)主要应用于Windows的网络环境中，它基于杂凑算法MD4，该杂凑算法最早在Windows NT 4.0 SP4中被广泛使用，随后又被应用于Windows 2000中，虽然已经被Kerberos[41]取代不再作为默认的认证协议，但仍然在很多没有采用Kerberos协议的服务器和客户端通信中被使用.应用时间-存储折中攻击，可以有效地攻击基于分组密码DES实现的LM-Hash和基于杂凑算法MD4实现的NT-Hash.

时间-存储折中攻击的实施并不依赖于具体的杂凑算法，因此基于彩虹表的时间-存储折中攻击改进算法对当前通用的杂凑算法如MD5，SHA-1，SHA-2等均适用，是一种通用的杂凑算法的攻击方法.

为避免彩虹表攻击，密码系统应该对杂凑值采用加盐值机制，即在密码之后追加随机数使密码的杂凑值无法被反查.盐值需要额外存储，并且最好是根据每个密码随机生成不同的盐值.

2.2 针对具体算法的攻击

2.2.1 杂凑算法的碰撞攻击

由于碰撞攻击能够深入到压缩函数的内部，很多缩减轮的分析具有实际的攻击复杂度，能够更好地反映杂凑算法的安全强度.

最早对杂凑算法MD4和MD5进行分析的有den Boer，Bosselaers[42-43]，Vaudenay[44].随后Dobbertin[45]提出了一种新的分析方法，并于1996年成功破解了MD4；1998年，证明了MD4前2轮不是单向的(共3轮)[46]；在MD5攻击方面，1996年给出了自由初始值下的MD5的碰撞实例[47]，也就是说在初始值可以自由选择的情况下，能够找到2个不同的消息具有相同的杂凑值.1998年，Chabaud和Joux[48]给出了SHA-0全算法的理论分析结果.

在2004年美密会上，我国密码学家Wang(王小云)等人[31]首次公布了MD4，MD5，HAVAL-128，RIPEMD的碰撞实例.他们提出的模差分分析方法又称比特追踪法，建立了现有杂凑算法碰撞攻击的理论与技术，破解了包括MD5和SHA-1在内的系列国际通用杂凑算法，动摇了杂凑算法及相关密码应用的理论根基，引发了杂凑算法研究的热潮，有力推动了杂凑算法分析与设计技术的进一步发展.

模差分是一种精确差分，它不同于一般差分攻击里面使用的异或差分，它能够准确地表达整数模减差分和异或差分这2种信息.利用模差分方法对杂凑算法进行分析有4个步骤：第1步是选择合适的消息差分，它决定了攻击成功的概率；第2步是针对选择的消息差分寻找可行的差分路线，这是模差分分析关键一步，也是最难的一步，它需要聪明的分析、熟练的技术、持久的耐心；第3步是推导出保证差分路线可行的充分条件，在寻找差分路线的过程中，链接变量的条件被确定下来，一个可行的差分路线就意味着从路线上推导出来的所有链接变量的条件相互之间没有冲突；最后1步就是使用消息修改技术，使得被修改的消息满足尽可能多的充分条件.

使用模差分方法，通过提炼MD4和RIPEMD的轮函数的特征建立统一的数学分析模型，Wang(王小云)等人[49]在2005年首次给出了RIPEMD的实际攻击以及改进的MD4的实际攻击.同年，Wang(王小云)等人[50]又提出了首个针对杂凑算法MD4的新的第二原像攻击方法，该方法直接导致国际密码领域开展基于MD4，HAVAL，SHA-0的消息认证码的分析.

由于MD5具有强雪崩效应，Wang(王小云)等人[29]使用更复杂的比特进位控制和高级的消息修改技术来控制雪崩，找到MD5的1个明文分组的高概率的几乎碰撞.进一步，结合MD迭代结构的特点，提出利用多个明文分组构造碰撞的理论，从而给出了MD5的实际的碰撞攻击.而国际密码学家Biham等人[51]在同一时间独立提出多明文分组碰撞理论，提高了SHA-0的攻击效率.基于Wang(王小云)等人[29]对MD5的碰撞攻击方法，Stevens[52]于2007年给出了对MD5算法在选择前缀下的实际碰撞攻击结果.2009年，Stevens等人[53]又将选择前缀的MD5碰撞攻击结果用于伪造X.509数字证书，该伪造的中间结点证书能够通过合法服务器的认证，这对实际应用安全造成了直接的威胁.2012年5月，被俄罗斯专家发现的火焰病毒就是基于Wang(王小云)等人[29]的MD5的碰撞差分路线伪造的数字证书.该病毒能够通过键盘输入、记录音频对话和获取截屏画面等收集数据，数据收集完毕后自行销毁，不会留下任何痕迹.

1997年，Wang(王小云)等人[54]通过建立SHA-0的代数分析模型，首次破解了SHA-0.但2005年Wang(王小云)等人[30]分析SHA-1时发现，已有的对MD5和SHA-0的碰撞攻击方法还不足以用来破解SHA-1，主要是由于SHA-1的所有可能的碰撞路线中均存在不可能差分现象.Wang(王小云)等人[30]通过先扩散雪崩然后再控制雪崩的技术，将不可能差分转化成了可能差分，从而首次给出SHA-1全算法的理论碰撞攻击结果，复杂度为269次运算.后来，Wang(王小云)等人[55]又找到了一条新的差分路线，将碰撞攻击的复杂度提高到263次运算.该结果被很多密码学进一步改进，其中Stevens等人[56]给出的碰撞攻击结果复杂度为261次运算.但到目前为止，没有SHA-1的实际碰撞攻击出现.对缩减轮SHA-1的实际碰撞攻击结果中最好的是76轮(共80轮)的SHA-1的伪碰撞攻击结果[57].

模差分方法已经成为杂凑算法分析的最重要、最通用的方法，该方法也成为针对基于MD系列杂凑算法的消息认证码攻击的主流方法[58].近几年，模差分方法还成功用于对分组密码和流密码算法的安全性分析[59-60].Wang(王小云)等人[29-30]对杂凑算法MD5和SHA-1的破解导致NIST专门举办2次研讨会并宣布系列政策应对杂凑算法破解的威胁，启动了新一代杂凑算法SHA-3标准的设计工程.

SHA-2是目前广泛使用的杂凑算法标准，近5年对缩减轮SHA-2的碰撞类攻击取得了重要研究进展，文献[61-62]结合比特追踪法与自动化搜索技术，给出了SHA-256512缩减到38轮的伪碰撞理论分析.在对SHA-3的公开分析中，Dinur等人[63]给出了可实现复杂度的KECCAK-224和KECCAK-256的4轮碰撞攻击和5轮的近似碰撞攻击.Duc等人[64]给出了KECCAK的反弹攻击结果.但是SHA-3共有24轮，这些分析结果均不能对SHA-3算法构成威胁.在区分器方面，Duan等人[65]给出了SHA-3置换函数的24轮的零和区分攻击，复杂度为21579.

2.2.2 杂凑算法原像攻击

是否抗原像攻击是评估密码杂凑算法安全性的3个主要属性之一.在SAC 2008上，Aoki和Sasaki[66]首次将中间相遇攻击[67]应用到密码杂凑算法的原像攻击中，给出了单个消息分组的完整MD4算法和63轮MD5算法的原像攻击，同时改进了穷举搜索完整MD5算法原像的复杂度.提出了分段-链接技术(splice-and-cut technique)，将反馈运算看成特殊的轮操作，这样压缩函数在结构上形成一个环，从环的任何位置断开都是相似的，从而构造出压缩函数的伪原像攻击，再结合伪原像转化为原像的方法[68]，将单个消息分组的伪原像攻击转化成多个消息分组的原像攻击.

此后，中间相遇攻击成为杂凑算法原像攻击最重要的方法，同时也出现了很多技术对其进行改进，比如初始化结构体技术(initial structure technique)[69]、完全二分结构体技术(biclique technique)[70]、局部碰撞技术(local-collision approach)[71]、部分固定技术(partial-fixing technique)[66]、间接匹配技术(indirect-partial-matching technique)[72]和概率匹配技术等.带完全二分结构体的中间相遇攻击如图7所示，其中IWⅠ，IWⅡ表示独立消息字(initial words).

图7 带完全二分结构体的中间相遇攻击图示

基于中间相遇攻击的原像攻击在结构上可分为起始部分、相互独立部分和匹配部分.为了增加原像攻击的轮数，可以从增加这3部分的轮数入手.

为了增加起始部分的轮数，主要采用初始化结构体技术和完全二分结构体技术，完全二分结构体技术是初始化结构体技术的推广.首先在压缩函数中寻找一个预计算部分，预计算部分被称为初始化结构体或者完全二分结构体.初始化结构体技术和完全二分结构体技术使本身相互交错的独立消息字在预计算部分2端交换位置,以满足基本中间相遇攻击的独立性要求(如图7所示).

为了增加匹配部分的轮数，主要采用部分固定技术、间接匹配技术和概率匹配技术.这些技术依赖于对独立消息字中自由比特位置的选取和匹配部分压缩函数的性质.部分固定技术在选取独立消息字自由比特位置时结合匹配起始位置的压缩函数特性，使不确定的比特在匹配起始位置具有某些特性，从而使2个方向可计算的比特位置能匹配.间接匹配技术则是通过压缩函数的性质等，将直接的匹配转化成另外一种等价形式的匹配.概率匹配技术则是使匹配以小于1的概率成立，这样一方面可以增加攻击的轮数，另一方面会增加攻击的复杂度.

在CRYPTO 2012上，Knellwolf和Khovratovich[73]从差分的角度看待中间相遇攻击，提出了差分中间相遇攻击，将SHA-1的原像攻击由48轮提高到60轮(伪原像攻击).差分中间相遇攻击将对链接变量的匹配转化成对差分的匹配，能与已有的技术相融合，对消息线性拓展和轮函数较弱的杂凑算法具有良好的攻击效果.

在CRYPTO 2015上，Espitau等人[74]将差分中间相遇攻击推广到高阶差分中间相遇攻击，将SHA-1的原像攻击提高到64轮(伪原像攻击).高阶差分中间相遇攻击将差分中间相遇攻击中差分的匹配形式进行扩充，以达到高阶的形式，从而增加了原像攻击的轮数.高阶差分中间相遇攻击的消息划分更多，攻击中需要搜索一些划分的组合，相同自由度的情况下较差分中间相遇攻击需要的链接变量的列表数多，空间占用大，但攻击复杂度相同.例如，在与差分中间相遇攻击的自由度相同时，二阶差分中间相遇攻击需要在2个独立部分分别创建3个列表，并且需要穷搜6个列表中的4个，差分的匹配条件也更复杂.

2.2.3 其他新型的攻击

自2009年以来，出现了多种针对杂凑算法攻击的方法.如对SHA-3候选算法的分析和评估过程中，有很多创新性的分析技术出现，其中包括反弹攻击(rebound attack)[75]、循环移位攻击(rotational attack)[76]、零和区分攻击(zero-sum attack)[77]、飞去来器区分攻击[78]等.反弹攻击由Mendel等人[75]在FSE 2009上提出，对基于AES类的杂凑算法如Whirlpool，Grøstl，ECHO，JH等攻击非常有效；循环移位攻击则用来对部分基于ARX类杂凑算法进行区分攻击，如缩减轮的Skein和SIMD等，这种攻击方法与算法中使用的常数有关；零和区分攻击由Aumasson等人[77]提出，主要用来分析Luffa和KECCAK等代数次数比较低的杂凑算法.

在所有新的分析方法中，反弹攻击是最具有代表性的分析方法.反弹攻击被提出的目的是为了高效地寻找杂凑算法的碰撞.对基于分组密码或置换的杂凑算法的安全性影响较大，特别是AES类算法，比如ISOIEC标准算法中的Whirlpool和SHA-3候选算法Grøstl等.反弹攻击通常从被分析算法的中间状态差分开始向前和向后拓展，该攻击又被称为中间起始(start from middle)攻击.

在亚密2009上，Lamberger等人[79]利用Whirpool在密钥上的信息量冗余对反弹攻击进行了改进，提出了9.5轮Whirpool的几乎碰撞和距今为止唯一的全轮Whirpool压缩函数的区分器攻击.在FSE 2010上，Gilbert等人[80]针对AES类置换提出大S盒技术(super-sbox)，推动了反弹攻击技术的发展.随后，反弹攻击技术又被用于其他结构的杂凑算法中，比如MD结构的Skein[76]和海绵体结构的KECCAK[81]等.

同时，反弹攻击技术和其他分析技术相结合，推动了分组密码分析技术的发展.比如，Bouillaguet等人[82]利用反弹攻击技术改进了Dunkelman等人[83]提出的AES的中间相遇区分器，给出了AES-128，AES-192，AES-256的新结果.随后，Li(李雷波)等人[84]又改进了AES-192和AES-256的分析结果.目前，结合反弹攻击技术和中间相遇攻击是AES在单密钥模式下的最有效的攻击技术.

3 结束语

自20世纪90年代，Rivest[11-12]设计了杂凑算法MD4，MD5以来，杂凑算法的分析与设计一直是密码领域关注的热点.2004年Wang(王小云)等人[29-30]破解MD5和SHA-1，引发了杂凑算法研究的热潮，杂凑算法的分析和设计技术近10年来取得了突破性的进展.在杂凑算法分析方面，Wang(王小云)等人[29-30]提出的模差分分析方法是分析MDx系列杂凑算法碰撞攻击的通用方法.基于对模差分方法的广泛研究，Mendel等人[75]提出的反弹攻击是分析AES类杂凑算法碰撞的有效工具.而在杂凑算法的设计方面，最具有代表性的就是SHA-3标准的设计.SHA-3具有优秀的设计、高效的软硬件实现效率以及灵活的适应性，标志着国际杂凑算法的设计技术达到了一个新的高度.SHA-3基于大状态的置换函数设计，已有的杂凑算法的分析方法如模差分方法和反弹攻击等对SHA-3算法不能提供有效的攻击方法，目前对SHA-3最好的分析只有5轮(共24轮)的理论碰撞攻击结果，SHA-3安全冗余度很高.我国发布的杂凑算法标准SM3安全性冗余高、实现效率与国际杂凑算法标准SHA-256相当，标志着我国杂凑算法的设计技术也走在了国际的前列.寻找新的针对SHA-3类杂凑算法的分析方法，设计一个在软硬件效率和灵活性方面能够超越SHA-3的杂凑算法是未来在杂凑算法分析和设计领域研究的方向.

[1]Knuth D E. Sorting and searching[M]The Art of Computer Programming, volume 3. Massachusetts: Addison-Wesley, 1973

[2]Merkle R C. Secrecy, authentication, and public key systems[D]. Stanford , CA: Stanford University, 1979

[3]Davies D W, Price W L. The application of digital signatures based on public key cryptosystems[R]. Atlanta Ga: National Physical Lab, 1980

[4]Damgård I B. Collision free hash functions and public key signature schemes[G]LNCS 304: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1987: 203-216

[5]Kelsey J, Schneier B. Second preimages on n-bit hash functions for much less than 2nwork[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 474-490

[6]Kelsey J, Kohno T. Herding hash functions and the nostradamus attack[G]LNCS 4004: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2006: 183-200

[7]National Institute of Standards and Technology. FIPS 180-2 Secure Hash Standard[SOL]. 2002[2015-08-10].http:csrc.nist.govpublicationsfipsfips180-2fips180-2.pdf

[8]National Institute of Standards and Technology. FIPS 180-3 Secure Hash Standard[SOL]. 2008[2015-08-10]. http:csrc.nist.govpublicationsfipsfips180-3fips180-3_final.pdf

[9]Merkle R C. One way hash functions and DES[G]LNCS 435: Proc of Advances in Cryptology—CRYPTO’89. Berlin: Springer, 1990: 428-446

[10]Damgård I B. A design principle for hash functions[G]LNCS 435: Advances in Cryptology—CRYPTO’89. New York: Springer, 1990: 416-427

[11]Rivest R L. The MD4 message digest algorithm[G]LNCS 537: Advances in Cryptology—CRYPT0’90. Berlin: Springer, 1991: 303-311

[12]Rivest R L. The MD5 message digest algorithm[SOL]. RFC 1321, 1992[2015-08-10].https:www.ietf.orgrfcrfc1321.txt

[13]Zheng Yuliang, Pieprzyk J, Seberry J. HAVAL—A one-way hashing algorithm with variable length of output[G]LNCS 718:Proc of the Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1992: 81-104

[14]Dobbertin H, Bosselaers A, Preneel B. RIPEMD-160: A strengthened version of RIPEMD[G]LNCS 1039: Proc of the 3rd Int Workshop on Fast Software Encryption. Berlin: Springer, 1996: 71-82

[15]国家密码管理局. SM3密码杂凑算法[EBOL]. 2010 [2015-08-10]. http:www.oscca.gov.cnUpFile20101222141857786.pdf

[16]Joux A. Multicollisions in iterated hash functions. Application to cascaded constructions[G]LNCS 3152: Proc of the 24th Annual Int Cryptology Conf. Berlin: Springer, 2004: 306-316

[17]Liskov M. Constructing an ideal hash function from weak ideal compression functions[G]LNCS 4356: Revised Selected Papers of the 13th Int Workshop on Selected Areas in Cryptography. Berlin: Springer, 2007: 358-375

[18]Lucks S. A failure-friendly design principle for hash functions[G]LNCS 3788: Proc of the 11th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2005: 474-494

[19]Leurent G, Wang Lei. The sum can be weaker than each part[G]LNCS 9056: Proc of the 34th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2015: 345-367

[20]Biham E, Dunkelman O. A framework for iterative hash functions: HAIFA[OL]. (2006-08-25) [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsDUNKELMAN_talk.pdf

[21]Aumasson J P, Henzen L, Meier W, et al. SHA-3 proposal BLAKE, Version 1.3[EBOL]. (2010-12-16) [2015-08-10]. https:131002.netblakeblake.pdf

[22]Bertoni G, Daemen J, Peeters M, et al. Sponge functions[OL]. 2007[2015-08-10]. http:events.iaik.tugraz.atHashWorkshop07slidesVanAssche_Sponge.pdf

[23]Bertoni G, Daemen J, Peeters M, et al. The KECCAK SHA-3 submission[EBOL]. (2011-01-14) [2015-09-22]. http:keccak.noekeon.orgKeccak-submission-3.pdf

[24]Guo Jian, Peyrin T, Poschmann A: The PHOTON family of lightweight hash functions[G]LNCS 6841: Proc of the 31st Annual Cryptology Conf. Berlin: Springer, 2011: 222-239

[25]Aumasson J P, Henzen L, Meier W, et al. QUARK: A lightweight hash[G]LNCS 6225: Proc of the 12th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2010: 1-15

[27]Preneel B, Govaerts R, Vandewalle J. Hash functions based on block ciphers: A synthetic approach[G]LNCS 773: Proc of the 13th Annual Int Cryptology Conf. Berlin: Springer, 1994: 368-378

[28]RACE integrity primitives evaluation. Integrity primitives for secure information systems: Final report of RACE integrity primitives evaluation RIPE-RACE, 1040[R]. Berlin: Springer, 1992

[29]Wang Xiaoyun, Yu Hongbo. How to break MD5 and Other hash functions[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 19-35

[30]Wang Xiaoyun, Yin Y L, Yu Hongbo. Finding collisions in the full SHA-1[G]LNCS 3621: Proc of the 25th Annual Int Cryptology Conf. Berlin: Springer, 2005: 17-36

[31]Wang Xiaoyun, Feng Dengguo, Lai Xuejia, et al. Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD[OL]. 2004 [2015-08-10]. https:eprint.iacr.org2004199.pdf

[32]National Institute of Standards and Technology. SHA-3 competition[EBOL]. (2005-04-15) [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsFR_Notice_Nov07.pdf

[33]Shamir A. SQUASH—A new MAC with provable security properties for highly constrained devices such as RFID tags[G]LNCS 2086: Proc of the 15th Int Workshop on Fast Software Encryption. Berlin: Springer, 2008: 144-157

[34]Bogdanov A, Leander G, Paar C, et al. Hash functions and RFID tags: Mind the gap[G]LNCS 5154: Proc of the 10th Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2008: 283-299

[35]Wu Wenling, Wu Shuang, Zhang Lei, et al. LHash: A lightweight hash function[G]LNCS 8567: Proc of the 9th Int Conf on Information Security and Cryptology. Berlin: Springer, 2013: 867

[36]Hellman M E. A cryptanalytic time-memory trade-off[J]. IEEE Trans on Information Theory, 1980, 26(4): 401-406

[37]Oechslin P. Making a faster cryptanalytic time-memory trade-off[G]LNCS 2729: Proc of the 23rd Annual Int Cryptology Conf. Berlin: Springer, 2003: 617-630

[38]Microsoft TechNet. Operating system installation: The LMHash[OL]. (2015-05-12) [2015-08-10]. https:technet.microsoft.comen-uslibrarydd277300.aspx#ECAA

[39]National Bureau of Standards. FIPS 46-3: Data Encryption Standard[SOL]. 1999[2015-08-10].http:csrc.nist.govpublicationsfipsfips46-3fips46-3.pdf

[40]Schneier B. Cryptanalysis of microsoft’s point-to-point tunneling protocol (PPTP)[C]Proc of the 5th ACM Conf on Computer and Communications Security. New York: ACM, 1998: 132-141

[41]Neuman B C, Ts’O T. Kerberos: An authentication service for computer networks[J]. IEEE Communications Magazine, 1994, 32(9): 33-38

[42]den Boer B, Bosselaers A. An attack on the last two rounds of MD4[G]LNCS 576: Advances in Cryptology—CRYPTO’91. Berlin: Springer, 1992: 194-203

[43]den Boer B, Bosselaers A. Collisions for the compression function of MD5[G]LNCS 765: Proc of Workshop on the Theory and Application of Cryptographic Techniques. Berlin: Springer, 1994: 293-304

[44]Vaudenay S. On the need for multipermutations: Cryptanalysis of MD4 and SAFER[G]LNCS 1008: Proc of the 2nd Int Workshop on Fast Software Encryption. Berlin: Springer, 1995: 286-297

[45]Dobbertin H. Cryptanalysis of MD4[G]LNCS 1039: Proc of the 3rd Int Workshop on Fast Software Encryption. Berlin: Springer, 1996: 53-69

[46]Dobbertin H. The first two rounds of MD4 are not one-way[G]LNCS 1372: Proc of the 5th Int Workshop on Fast Software Encryption. Berlin: Springer, 1998: 284-292

[47]Dobbertin H. Cryptanalysis of MD5 compress[OL]. (1996-05-02) [2015-08-10]. http:cseweb.ucsd.edu～bsydobbertin.ps

[48]Chabaud F, Joux A. Differential collisions in SHA-0[G]LNCS 1462: Proc of the 18th Annual Int Cryptology Conf. Berlin: Springer, 1998: 56-71

[49]Wang Xiaoyun, Lai Xuejia, Feng Dengguo, et al. Cryptanalysis of the hash functions MD4 and RIPEMD[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer,2005: 1-18

[50]Yu Hongbo, Wang Gaoli, Zhang Guoyan, et al. The second-preimage attack on MD4[G]LNCS 3810: Proc of the 4th Int Conf on Cryptology and Network Security. Berlin: Springer, 2005: 1-12

[51]Biham E, Chen R, Joux A, et al. Collisions of SHA-0 and reduced SHA-1[G]LNCS 3494: Proc of the 24th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 36-57

[52]Stevens M, Lenstra A, De Weger B. Chosen-Prefix collisions for MD5 and colliding X.509 certificates for different identities[G]LNCS 4515: Proc of the 26th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2007: 1-22

[53]Stevens M, Sotirov A, Appelbaum J, et al. Proc of short chosen-prefix collisions for MD5 and the creation of rogue CA certificate[G]LNCS 5677: Proc of the 29th Annual Int Cryptology Conf. Berlin: Springer, 2009: 55-69

[54]Wang Xiaoyun, The collision attack on SHA-0[OL]. 1997[2015-08-10]. http:www.infosec.sdu.edu.cnperson_wangxiaoyun2.htm

[55]Wang Xiaoyun, Yao A C, Yao F. Cryptanalysis on SHA-1[OL]. 2005 [2015-08-10]. http:csrc.nist.govgroupsSThashdocumentsWang_SHA1-New-Result.pdf

[56]Stevens M. New collision attacks on SHA-1 based on optimal joint local-collision analysis[G]LNCS 7881: Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 245-261

[57]Karpman P, Peyrin T, Stevens M. Practical free-start collision attacks on 76-step SHA-1[G]LNCS 9215: Proc of the 35th Annual Cryptology Conf. Berlin: Springer, 2015: 623-642

[58]Fouque P, Leurent G, Nguyen P Q. Full key-recovery attacks on HMACNMAC-MD4 and NMAC-MD5[G]LNCS 4622: Proc of the 27th Annual Int Cryptology Conf. Berlin: Springer, 2007:13-30

[59]Raddum H. Algebraic analysis of the Simon block cipher family[G]LNCS 9230: Proc of the 4th Int Conf on Cryptology and Information Security. Berlin: Springer, 2015: 157-169

[60]Knellwolf S, Meier W, Naya-Plasencia M. Conditional differential cryptanalysis of NLFSR-based cryptosystems[G]LNCS 6477: Proc of the 16th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2010: 130-145

[61]Mendel F, Nad T, Schläffer M. Improving local collisions: New attacks on reduced SHA-256[G]LNCS 7881: Proc of the 32nd Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2013: 262-278

[62]Eichlseder M, Mendel F, Schläffer M. Branching heuristics in differential collision search with applications to SHA-512[C]LNCS 8540: Revised Selected Papers of the 21st Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 473-488

[63]Dinur I, Dunkelman O, Shamir A. New attacks on Keccak-224 and Keccak-256[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 442-461

[64]Duc A, Guo Jian, Peyrin T, et al. Unaligned rebound attack: Application to Keccak[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 402-421

[65]Duan Ming, Lai Xuejia. Improved zero-sum distinguisher for full round Keccak-f permutation[J]. Chinese Science Bulletin, 2012, 57(6): 694-697

[66]Aoki K, Sasaki Y. Preimage attacks on one-block MD4, 63-step MD5 and more[G]LNCS 5381: Proc of the 15th Int Workshop on Selected Areas in Cryptography (SAC 2008). Berlin: Springer, 2009: 103-119

[67]Diffie W, Hellman M E. Special feature exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer, 1977, 10(6): 74-84

[68]Menezes A J, Van Oorschot P C, Vanstone S A. Handbook of Applied Cryptography[M]. Boca Raton: CRC Press, 1996

[69]Sasaki Y, Aoki K. Finding preimages in Full MD5 faster than exhaustive search[G]LNCS 5479: Proc of the 28th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2009: 134-152

[70]Khovratovich D, Rechberger C, Savelieva A. Bicliques for preimages: Attacks on Skein-512 and the SHA-2 family[G]LNCS 7549: Proc of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 244-263

[71]Sasaki Y, Aoki K. Preimage attacks on 3, 4, and 5-pass HAVAL[G]LNCS 5350: Proc of the 14th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2008: 253-271

[72]Aoki K, Guo J, Matusiewicz K, et al. Preimages for step-reduced SHA-2[G]LNCS 5912: Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 578-597

[73]Knellwolf S, Khovratovich D. New preimage attacks against reduced SHA-1[G]LNCS 7417: Proc of the 32nd Annual Cryptology Conf. Berlin: Springer, 2012: 367-383

[74]Espitau T, Fouque P A, Karpman P. Higher-order differential meet-in-the-niddle preimage attacks on SHA-1 and BLAKE[G]LNCS 9215: Proc of the 35th Annual Cryptology Conf. Berlin: Springer, 2015: 683-701

[75]Mendel F, Rechberger C, Schläffer M, et al. The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl[G]LNCS 5665: Proc of the 16th Int Workshop on Fast Software Encryption. Berlin:Springer, 2009: 260-276

[77]Aumasson J P, Meier W. Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[OL]. 2009[2015-08-10]. https:131002.netdatapapersAM09.pdf

[78]Wagner D. The boomerang attack[C]Proc of the 6th Int Workshop on Fast Software Encryption. Berlin: Springer, 1999: 156-170

[79]Lamberger M, Mendel F, Rechberger C, et al. Rebound distinguishers: Results on the full Whirlpool compression function[G]LNCS 5912: Proc of the 15th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2009: 126-143

[80]Gilbert H, Peyrin T. Super-Sbox cryptanalysis: Improved attacks for AES-like permutations[G]LNCS 6147: Revised Selected Papers of the 17th Int Workshop on Fast Software Encryption. Berlin: Springer, 2010: 365-383

[81]Duc A, Guo Jian, Peyrin T, et al. Unaligned rebound attack: Application to Keccak[G]LNCS 7549: Revised Selected Papers of the 19th Int Workshop on Fast Software Encryption. Berlin: Springer, 2012: 402-421

[82]Bouillaguet C, Derbez P, Dunkelman O, et al. Low-data complexity attacks on AES[J]. IEEE Trans on Information Theory, 2012, 58(11): 7002-7017

[83]Biryukov A, Dunkelman O, Keller N, et al. Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds[G]LNCS 6110: Proc of the 29th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010: 299-319

[84]Li Leibo, Jia Keting, Wang Xiaoyun. Improved single-key attacks on 9-Round AES-192256[G]LNCS 8540: Revised Selected Papers of the 21st Int Workshop on Fast Software Encryption. Berlin: Springer, 2014: 127-146

王小云

教授，博士生导师，主要研究方向为密码理论与技术.

xiaoyunwang@mail.tsinghua.edu.cn

于红波

博士，副教授，主要研究方向为密码学.

yuhongbo@mail.tsinghua.edu.cn

Survey of Hash Functions

Wang Xiaoyun1,2and Yu Hongbo3

1(InstituteforAdvancedStudy,TsinghuaUniversity,Beijing100084)2(KeyLaboatoryofCryptologicTechnologyandInofrmationSecurity(ShandongUniversity),MinistryofEducation,Jinan250100)3(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

One of the fundamental primitives in modern cryptography is the cryptographic hash functions, often informally called hash functions. They are used to compress messages of arbitrary length to fixed length hash values which are also called hash codes, message digests or digital fingerprints. A primary motivation for cryptographic hash functions is that they serve as compact representative images of input messages, which they can uniquely identify. Changing a single letter will change most of the digits in the hash code. The most common cryptographic uses of hash functions are with digital signature and for data integrity. Hash functions are frequently used in digital signature schemes to compress large messages for processing by public-key cryptosystems such as RSA. They are also used to design message authentication codes (MACs) and many secure cryptographic protocols. Hash functions occur as components in various cryptographic applications (e.g. protection of pass-phrases, protocols for payment, broadcast authentication etc.), where usually their property as a computational one-way function is used. So the study of the hash functions is of great significance in the cryptanalysis field.

cryptographic hash function; collision attack; preimage attack; MD5 algorithm; SHA-1 algorithm; SHA-3 algorithm

2015-09-20

国家“九七三”重点基础研究发展计划基金项目(2013CB834205)；国家自然科学基金项目(61133013,61373142)

TP309