Improved Indifferentiability Security Analysis of chopMD Hash Function
Improved Indifferentiability Security Analysis of chopMD Hash Function
复制标题
DOI：
10.1007/978-3-540-71039-4_27
复制
发表时间：
2008-02
期刊：
影响因子：
--
通讯作者：
D. Chang;M. Nandi
中科院分区：
文献类型：
--
作者：
D. Chang;M. Nandi
经典的设计原理Merkle-Damg&Rd[13，6]通过Joux的多碰撞攻击、KELELY-Schneier第二原像攻击等方法进行了详细的分析。为基于压缩函数的散列函数引入了一个称为“不可微性”的强安全性概念。经典的设计原则对这种强安全概念也是不安全的，而choMD散列是安全的，其安全界大约是σ2/2，其中σ是被截断的比特的数目，并且是由一个区分器查询的消息块的总数。在n= 2s的情况下，其中是压缩函数的输出大小，用于获得有效界限的值σ是2s/2，这是生日复杂度，其中散列输出大小为1比特。在本文中，我们给出了一种改进的choMD的安全界。改进后的界为(3(n−S) + 1)q/2s+q/2n−S− 1+σ2/2n+ 1其中q为查询总数。在n= 2s的情况下， MD是不可微安全的iFq= O(2s/(3s+σ= 1))和iFq O(2n/2)，超过了生日复杂度。给出了一种基于压缩函数的n位Hash函数的设计原理，并证明了该Hash函数的不可微安全界大致为(3n+ 1)σ/2n。因此，只要攻击者的查询复杂度(查询消息块个数)分别小于2n/(3n+ 1)和2n(r− 1)/r，新的哈希函数设计就是二次原像多冲突安全的。
The classical design principle Merkle-Damgård [13,6] is scrutinized by many ways such as Joux’s multicollision attack, Kelsey-Schneier second preimage attack etc. In TCC’04, Maureret al. introduced a strong security notion called as “indifferentiability” for a hash function based on a compression function. The classical design principle is also insecure against this strong security notion whereas chopMD hash is secure with the security bound roughlyσ2/2swheresis the number of chopped bits andσis the total number of message blocks queried by a distinguisher. In case ofn= 2swherenis the output size of a compression function, the valueσto get a significant bound is 2s/2which is the birthday complexity, where the hash output size iss-bit. In this paper, we present an improved security bound for chopMD. The improved bound shown in this paper is (3(n−s) + 1)q/2s+q/2n−s− 1+σ2/2n+ 1whereqis the total number of queries. In case ofn= 2s, chopMD is indifferentiably-secure ifq= O(2s/(3s+ 1)) andσ= O(2n/2) which are beyond the birthday complexity. We also present a design principle for ann-bit hash function based on a compression functionand show that the indifferentiability security bound for this hash function is roughly (3n+ 1)σ/2n. So, the new design of hash function is second-preimage andr-multicollision secure as long as the query complexity (the number of message blocks queried) of an attacker is less than 2n/(3n+ 1) or 2n(r− 1)/rrespectively.