Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
Time-Space Tradeoffs for Sponge Hashing: Attacks and Limitations for Short Collisions
复制标题
海绵哈希的时空权衡：短碰撞的攻击和限制
DOI：
10.1007/978-3-031-15982-4_5
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ilan Komargodski
中科院分区：
文献类型：
--
作者：
Cody R. Freitag;Ashrujit Ghoshal;Ilan Komargodski
Sponge hashing是流行的Merkle-Damg Hashing设计的一种新颖的替代方案。海绵结构在各种应用中越来越受欢迎，也许最值得注意的是，它是SHA-3哈希标准的基础。Sponge哈希由两个数字r和c（分别为比特率和容量）以及r + c比特的固定大小排列来参数化。在这项工作中，我们研究了海绵哈希实例化与随机排列的对手与任意S位的辅助意见输入的随机排列，使T在线查询的碰撞阻力。Coretti等人最近的工作（1998年）表明，这样的对手可以发现具有优势Θ（ST 2 / 2 c + T 2 / 2 r）的冲突（相对于随机c位初始化向量）。虽然上述攻击在某些参数范围内正式破坏了碰撞抵抗，但其实际相关性有限，因为所产生的碰撞非常长（大约T个块）。针对寻找短碰撞的任务，研究了当参数B ≥ 1时寻找B -块碰撞的复杂性.我们给出了一些新的攻击和限制。最值得注意的是，我们给出了一个新的攻击，结果在一个单一的块碰撞，并具有优势
Sponge hashing is a novel alternative to the popular Merkle-Damg˚ard hashing design. The sponge construction has become increasingly popular in various applications, perhaps most notably, it underlies the SHA-3 hashing standard. Sponge hashing is parametrized by two numbers, r and c (bitrate and capacity, respectively), and by a fixed-size permutation on r + c bits. In this work, we study the collision resistance of sponge hashing instantiated with a random permutation by adversaries with arbitrary S - bit auxiliary advice input about the random permutation that make T online queries. Recent work by Coretti et al. (CRYPTO ’18) showed that such adversaries can find collisions (with respect to a random c -bit initialization vector) with advantage Θ( ST 2 / 2 c + T 2 / 2 r ). Although the above attack formally breaks collision resistance in some range of parameters, its practical relevance is limited since the resulting collision is very long (on the order of T blocks). Focusing on the task of finding short collisions, we study the complexity of finding a B -block collision for a given parameter B ≥ 1. We give several new attacks and limitations. Most notably, we give a new attack that results in a single-block collision and has advantage
Merkle-Damgård 哈希函数中的时空权衡和短碰撞
DOI：
10.1007/978-3-030-56784-2_6
发表时间：
2020
期刊：
Annual International Cryptology Conference CRYPTO 2020: Advances in Cryptology – CRYPTO 2020
影响因子：
--
作者：
NLN, Akshima;Cash, David;Drucker, Andrew;Wee, Hoeteck
通讯作者：
Wee, Hoeteck
数据结构与密码学的结合：带预处理的 3SUM
DOI：
10.1145/3357713.3384342
发表时间：
2020
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Golovnev, Alexander;Guo, Siyao;Horel, Thibaut;Park, Sunoo;Vaikunathan, Vinod.
通讯作者：
Vaikunathan, Vinod.