Faster Multicollisions
Faster Multicollisions
复制标题
DOI：
10.1007/978-3-540-89754-5_6
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
Jean-Philippe Aumasson
中科院分区：
文献类型：
--
作者：
Jean-Philippe Aumasson
Joux的多重冲突攻击是散列函数中最引人注目的结果之一，也是最简单的结果之一：它在时间上计算迭代散列的ak-冲突，其中k！1/k·2n（k− 1）/k被认为是最优的。凯尔西和Schneier将其改进为3·2n/2，如果存储器是可用的，如果压缩函数允许容易找到的不动点。本文提出了一种简单的技术，减少这种成本为2n/2和可忽略的内存，当IV可以选择的攻击者。额外的好处是比凯尔西/Schneier攻击更短的消息和成本最优性。
Joux’s multicollision attack is one of the most striking results on hash functions and also one of the simplest: it computes ak-collision on iterated hashes in time, whereask!1/k·2n(k− 1)/kwas thought to be optimal. Kelsey and Schneier improved this to 3·2n/2if storage 2n/2is available and if the compression functions admits easily found fixed-points. This paper presents a simple technique that reduces this cost to 2n/2and negligible memory, when the IV can be chosen by the attacker. Additional benefits are shorter messages than the Kelsey/Schneier attack and cost-optimality.