On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing
On Time-Space Tradeoffs for Bounded-Length Collisions in Merkle-Damgård Hashing
复制标题
关于 Merkle-Damgård 哈希中有限长度碰撞的时空权衡
DOI：
10.1007/s00037-023-00243-y
复制
发表时间：
2023
影响因子：
1.4
通讯作者：
Ilan Komargodski
中科院分区：
文献类型：
--
作者：
Ashrujit Ghoshal;Ilan Komargodski
我们研究了预处理对手在随机预言机模型中广泛使用的Merkle-Damgård（MD）哈希中发现有界长度冲突的能力。具体来说，我们考虑的对手与任意S位的意见，随机预言机，并可以使最多T查询。我们的目标是描述这样的对手的优势，在发现一个B块碰撞的MD哈希函数使用范围大小为N的随机预言机作为压缩函数（给定一个随机盐）。对于B的非常大的值（本质上是$$\Omega（T）$$ Ω（T））以及对于B = 1、2，完全理解这个问题的答案。对于$$B\approx T$$ B\T，Coretti等人（EUROCITY PT '18）给出了$$\tilde\Theta（ST^2/N）$$ Θ ~（ST 2 / N）的匹配上界和下界。Akshima等人（NATO '20）观察到Coretti等人的攻击可以适用于B > 1的任何值，给出具有优势$$\tilde\Omega（STB/N + T^2/N）$$ Ω ~（ST B / N + T2/ N）的攻击。不幸的是，他们只能证明这种攻击对于B = 2是最优的。他们的证明涉及到一个压缩论证和详尽的案例分析，正如他们声称的那样，天真地试图将他们的界推广到更大的B值（即使B = 3），将导致需要分析的案例数量激增，使其难以管理。由于缺乏更一般的上界，他们提出了STB猜想，指出对于任何B >1，最好的可能优势是O（STB/N + T^2/N）O ~（ST B / N + T2/ N）。在这项工作中，我们证实了STB猜想在许多新的参数设置。例如，在一个结果中，我们表明，猜想成立的所有常数值的B，显着扩展Akshima等人的结果。此外，使用组合性质的图，我们能够确认猜想，即使是超常数值的B，只要一些限制S。例如，我们对所有$$B \le T^{1{/}4}$$ B ≤ T 1 / 4证实了这个猜想，只要$$S \le T^{1{/}8}$$ S ≤ T 1 / 8。从技术上讲，我们在MD哈希中开发了有界长度碰撞的结构特征，使我们能够给出一个压缩参数，其中需要处理的情况数量不会爆炸。
We study the power of preprocessing adversaries in finding bounded-length collisions in the widely used Merkle-Damgård (MD) hashing in the random oracle model. Specifically, we consider adversaries with arbitrary S -bit advice about the random oracle and can make at most T queries to it. Our goal is to characterize the advantage of such adversaries in finding a B -block collision in an MD hash function constructed using the random oracle with range size N as the compression function (given a random salt). The answer to this question is completely understood for very large values of B (essentially $$\Omega(T)$$ Ω ( T ) ) as well as for B = 1, 2. For $$B\approx T$$ B ≈ T , Coretti et al. (EUROCRYPT '18) gave matching upper and lower bounds of $$\tilde\Theta(ST^2/N)$$ Θ ~ ( S T 2 / N ) . Akshima et al. (CRYPTO '20) observed that the attack of Coretti et al. could be adapted to work for any value of B > 1, giving an attack with advantage $$\tilde\Omega(STB/N + T^2/N)$$ Ω ~ ( S T B / N + T 2 / N ) . Unfortunately, they could only prove that this attack is optimal for B = 2. Their proof involves a compression argument with exhaustive case analysis and, as they claim, a naive attempt to generalize their bound to larger values of B (even for B = 3) would lead to an explosion in the number of cases needed to be analyzed, making it unmanageable. With the lack of a more general upper bound, they formulated the STB conjecture, stating that the best-possible advantage is $$\tilde O(STB/N + T^2/N)$$ O ~ ( S T B / N + T 2 / N ) for any B >1. In this work, we confirm the STB conjecture in many new parameter settings. For instance, in one result, we show that the conjecture holds for all constant values of B , significantly extending the result of Akshima et al. Further, using combinatorial properties of graphs, we are able to confirm the conjecture even for super constant values of B , as long as some restriction is made on S . For instance, we confirm the conjecture for all $$B \le T^{1{/}4}$$ B ≤ T 1 / 4 as long as $$S \le T^{1{/}8}$$ S ≤ T 1 / 8 . Technically, we develop structural characterizations for bounded-length collisions in MD hashing that allow us to give a compression argument in which the number of cases needed to be handled does not explode.
关于哈希 ElGamal 的内存紧张性
DOI：
10.1007/978-3-030-45724-2_2
发表时间：
2020
期刊：
Advances in Cryptology - EUROCRYPT 2020
影响因子：
--
作者：
Ghoshal, Ashrujit;Tessaro, Stefano
通讯作者：
Tessaro, Stefano
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