Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions
Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions
复制标题
DOI：
10.13154/tosc.v2018.i1.201-253
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Zhenzhen Bao;Jian Guo;Lei Wang
中科院分区：
文献类型：
--
作者：
Zhenzhen Bao;Jian Guo;Lei Wang
本文综述了针对密码散列构造的一般攻击，包括基于散列的消息认证码和散列组合器。我们调查涉及多次迭代计算相同映射的攻击。随机映射的功能图还涉及迭代地评估该映射。这些攻击实质上利用了函数图的特性。我们从大量的已知攻击中映射出这些属性的使用空间，并对不同类型的攻击进行了比较，比较了它们的优点和局限性。我们系统地阐述了循环、深度迭代映象、碰撞的概念及其在迭代哈希构造的密码分析中的作用。我们确定了这些概念之间的内在联系，使得关于它们的逐例理论可以统一到一个知识系统中，即关于随机映射的函数图的理论。我们证明了基于函数图上的统计结果可以描述循环搜索算法、链求值算法和碰撞搜索算法的性质。因此，我们可以提供不同的观点来支持以往关于个人知识的信念。在这方面，我们将对随机映射的函数图进行更复杂的分析，并在密码分析中更多地利用它的性质。
We provide a survey about generic attacks on cryptographic hash constructions including hash-based message authentication codes and hash combiners. We look into attacks involving iteratively evaluating identical mappings many times. The functional graph of a random mapping also involves iteratively evaluating the mapping. These attacks essentially exploit properties of the functional graph. We map the utilization space of those properties from numerous proposed known attacks, draw a comparison among classes of attacks about their advantages and limitations. We provide a systematic exposition of concepts of cycles, deep-iterate images, collisions and their roles in cryptanalysis of iterated hash constructions. We identify the inherent relationship between these concepts, such that case-by-case theories about them can be unified into one knowledge system, that is, theories on the functional graph of random mappings. We show that the properties of the cycle search algorithm, the chain evaluation algorithm and the collision search algorithm can be described based on statistic results on the functional graph. Thereby, we can provide different viewpoints to support previous beliefs on individual knowledge. In that, we invite more sophisticated analysis of the functional graph of random mappings and more future exploitations of its properties in cryptanalysis.