题目：哈希组合器的安全现状

报告人：王磊，上海交通大学计算机系 特别研究员

报告时间：2017年10月28日19:30-20:30

报告地点：知新楼B1201

摘要：哈希函数是现代密码学基础算法，可保障数据完整性和认证性，广泛应用于实际生活。一个安全的哈希函数至少要满足三个基本的安全性质： 抗碰撞性(Collision Resistance)、抗原像攻击(Preimage resistance)、抗第二原像攻击(Second Preimage Resistance)。哈希函数设计理论已经成为了密码学的重要研究方向。其中一个设计思路是哈希组合器，即将两个（或多个）哈希函数作为底层组件，调用这些组件，构造一个新的哈希函数。哈希组合器的研究目标主要有两个。

安全放大性 (Security Amplification)：组合器的安全性强于其底层的任何一个哈希函数；

安全鲁棒性 (Security Robustness): 组合器的安全性具有风险对冲性，只要其底层的任何一个哈希函数是安全的，组合器就是安全的。

密码学家对于哈希组合器的研究大致分为三个方向：黑盒组合器(black-box combiner)的理论研究；基于理想安全哈希函数的组合器设计理论；经典哈希组合器的安全分析。

本次报告主要综述若干经典哈希组合器的安全现状，包括并行构造：Concatenation Combiner和XOR Combiner；以及串行结构：Hash Twice和Zipper Hash。具体内容遵从时间轴从Joux提出的多碰撞技术一直到我们最近提出的函数图形多循环技术，逐次介绍这些分析技术的发展过程以及在哈希组合器的安全分析应用。标记和为两个-bit哈希函数，这些哈希组合器的定义和安全分析现状概述如下。

Concatenation Combiner: 将两个哈希函数的输出连接在一起：，所以这个组合器的输出长度是底层哈希函数输出长度的两倍。Joux在CRYPT04提出了多碰撞技术，在此基础上提出了对Concatenation Combiner的碰撞攻击、（第二）原像攻击，复杂度分别为和。这有效的证明了Concatenation Combiner不具有抗碰撞性、抗原像攻击的安全放大性。Dinur在EUROCRYPT17基于函数图形学的分析技术，提出了对Concatenation Combiner的第二原像攻击，(最优)复杂度是。

XOR Combiner: 将两个哈希函数的输出进行异或操作：。Leurent和Wang等人在EUROCRYPT15基于碰撞提出了对XOR Combiner的原像攻击，复杂度为。Dinur在EUROCRYPT16提出了基于函数图形学的原像攻击，复杂度为。随后我们在CRYPTO17提出了多循环技术，将原像攻击的复杂度进一步降低为。

Hash Twice: 将第一个哈希函数的输出和消息作为第二个哈希函数的输入：。 Andreeva等人在SAC09上利用可扩展消息分析技术，提出了对Hash Twice的第二原像攻击，（最优）复杂度为。

Zipper Hash: 将第一个哈希函数的输出和变形后的消息作为第二个哈希函数的输入：, 其中是逆转的分块顺序。我们在CRYPTO17上基于函数图形学提出了对Zipper Hash的第二原像攻击，（最优）复杂度为。

报告人简介：王磊，上海交通大学计算机系特别研究员，博士生导师。2006年和2011年分别毕业于上海交通大学和日本电气通信大学，获得学士学位和博士学位。随后在新加坡南洋理工大学从事博士后研究，2015年7月至今任职于上海交通大学。主要从事对称密码算法的安全分析、设计和理论研究工作，包括哈希函数、分组密码、消息认证码和加密认证码。已被国际密码学会IACR三大年会CRYPTO、EUROCRYPT、ASIACRYPT录用15篇论文。代表性成果包括破解俄罗斯、韩国国家标准密码算法和ISO国际标准密码算法、发现零售金融业服务设备的安全缺陷、因特网电邮认证协议的安全漏洞等，获得俄罗斯国家标准杂凑函数Streebog安全分析竞赛（唯一的）一等奖，受邀在2011年RSA Conference信息安全国际论坛、2014年密码前沿论坛、2015年中国密码学会年会、2016年亚洲对称密码前沿讨论会、2017年密码算法学术会议等做特邀报告。受邀担任EUROCRYPT14、FSE16-18、ASIACRYPT17程序委员会成员，加密认证码国际研讨会DIAC15的程序委员会主席，亚洲对称密码前沿讨论会ASK15、ASK12组织委员会主席。