On the Indifferentiability of the Grøstl Hash Function
On the Indifferentiability of the Grøstl Hash Function
复制标题
论Grøstl哈希函数的不可微性
DOI：
10.1007/978-3-642-15317-4_7
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Preneel
中科院分区：
文献类型：
--
作者：
E. Andreeva;Bart Mennink;B. Preneel
Maurer等人引入的不可微性概念是哈希函数安全性的一个重要准则。具体来说，它确保哈希函数没有结构设计缺陷，从而保证在经过验证的范围内免受通用攻击的安全性。在这项工作中，我们证明了第二轮SHA-3候选哈希函数Grostl的不可微性。Grostl结合了宽管迭代和chop-Merkle-Damgard迭代的特点，并在内部使用两种不同的排列P和Q。假设P和Q是随机的l位排列，其中l为Grostl的迭代状态大小，我们证明了区分器区分Grostl与随机oracle的优势上界为O((Kq)4/2l)，其中区分器最多进行Q次查询，查询长度最多为K个块。这个结果意味着Grostl的行为就像一个随机的oracle，直到q = O（2n/2）个查询，其中n是输出大小。此外，我们证明了Grostl的输出变换，以及‘Grostail’（最终压缩函数和输出变换的组合），与随机oracle明显可微。这就排除了依赖于最终状态变换的理想性的不可微性证明。
The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the proven bounds. In this work we prove the indifferentiability of Grostl, a second round SHA-3 hash function candidate. Grostl combines characteristics of the wide-pipe and chop-Merkle-Damgard iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Grostl, we prove that the advantage of a distinguisher to differentiate Grostl from a random oracle is upper bounded by O((Kq)4/2l), where the distinguisher makes at most q queries of length at most K blocks. This result implies that Grostl behaves like a random oracle up to q = O(2n/2) queries, where n is the output size. Furthermore, we show that the output transformation of Grostl, as well as 'Grostail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This rules out indifferentiability proofs which rely on the idealness of the final state transformation.