Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
复制标题
Merkle-Damgård 哈希函数中的时空权衡和短碰撞
DOI：
10.1007/978-3-030-56784-2_6
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Wee, Hoeteck
中科院分区：
文献类型：
--
作者：
NLN, Akshima;Cash, David;Drucker, Andrew;Wee, Hoeteck
我们研究了在随机预言机模型中，对手使用任意S位辅助建议输入对随机预言机和T查询进行碰撞发现。最近的研究表明，这样的对手可以找到冲突（相对于随机IV）的优势， ð 2/200 ），其中n是输出长度，超出由因子S限定的生日。这些攻击被证明是最佳的。我们观察到，产生的碰撞时间很长，大约为T个区块，这将限制它们的实际意义。我们证明了几个相关的结果，以改善这些攻击，找到更短的碰撞。首先，我们展示了一个简单的攻击，找到B块长的冲突，实现优势（ ð 2019年12月20日 ) .然后我们研究这种攻击是否是最优的。我们表明，现有技术的基础上的比特固定模型（用于 ð 2/200 界）可证明不能达到这个界限，并朝着一般的结果，我们证明有定性的跳跃，在寻找长度1，长度2，和无限长的碰撞的最佳攻击。也就是说，最佳攻击实现（最多对数因子）的数量级为（1/2 公司简介 ）/200 ， ð /200 和 ð 2/200 优势我们还给出了一个上限的优势，通过一个新的分析树的增长随机功能图，可能是独立的兴趣的限制类的短碰撞发现攻击。
We study collision-finding against Merkle-DamgÃĨrd hashing in the random-oracle model by adversaries with an arbitrary S-bit auxiliary advice input about the random oracle and T queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage ð š(ð ð 2/2ð ) , where n is the output length, beating the birthday bound by a factor of S. These attacks were shown to be optimal. We observe that the collisions produced are very long, on the order of T blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find shorter collisions. We first exhibit a simple attack for finding B-block-long collisions achieving advantage ð šĖ (ð ð ð ĩ/2ð ) . We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the ð ð 2/2ð bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length 1, length 2, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) on the order of (ð +ð )/2ð , ð ð /2ð and ð ð 2/2ð advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.
登录
查看更多内容
NP 最坏情况和平均情况复杂性的相对分离
DOI：
10.1109/ccc.2011.34
发表时间：
2011
期刊：
2011 IEEE 26th Annual Conference on Computational Complexity
影响因子：
--
作者：
R. Impagliazzo
通讯作者：
R. Impagliazzo
反函数的严格时间/空间权衡
DOI：
10.1145/103418.103473
发表时间：
1991
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
A. Fiat;M. Naor
通讯作者：
M. Naor
修复混凝土裂缝：重新审视带有辅助输入的随机预言
DOI：
10.1007/978-3-319-56614-6_16
发表时间：
2017
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Y. Dodis;Siyao Guo;Jonathan Katz
通讯作者：
Jonathan Katz
随机预言和不均匀性
DOI：
10.1007/978-3-319-78381-9_9
发表时间：
2018
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Sandro Coretti;Y. Dodis;Siyao Guo;J. Steinberger
通讯作者：
J. Steinberger
针对单向函数和 PRG 的攻击的时空权衡
DOI：
--
发表时间：
2010
期刊：
Annual International Cryptology Conference
影响因子：
--
作者：
Anindya De;L. Trevisan;Madhur Tulsiani
通讯作者：
Madhur Tulsiani