A new one-bit diFFerence collision attack on HAVAL-128  

作　　者：ZHANG WenYing LI YanYan WU Lei 

机构地区：[1]School of Information Science and Engineering,Shandong Normal University,Jinan 250014,China [2]State Key Lab of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China [3]Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology,Jinan 250014,China

出　　处：《Science China(Information Sciences)》2012年第11期2521-2529,共9页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant No. 60970004,61173134,61272434);the Natural Science Foundation of Shandong Province (Grant No. ZR2011FQ032,ZR2012FM004);the Project of Shandong Province Higher Educational Science and Technology Program (Grant No. J11LG33);the Project of Senior Visiting Scholar of Shandong Province

摘　　要：Abstract In this paper, we give a new fast attack on HAVAL-128. Our attack includes many present methods of constructing hash collisions. Moreover, we present a neighborhood modification. We propose a new difference path different from the previous ones. The conclusion is that, when the output of each step satisfies our condition, the message rn can collide with m＇ = m ＋ △m, where△m = （0, 0, 0, 0, 231, 0,..., 0）. There is only one bit difference between m and m＇. Two pairs of collision examples for HAVAL-128 are given. In order to improve the probability of collision, we use four tricks of message modification. The attack＇s running time is less than 225.83 2-pass HAVAL computations, which is the best result for one-bit collision of HAVAL so far.Abstract In this paper, we give a new fast attack on HAVAL-128. Our attack includes many present methods of constructing hash collisions. Moreover, we present a neighborhood modification. We propose a new difference path different from the previous ones. The conclusion is that, when the output of each step satisfies our condition, the message rn can collide with m＇ = m ＋ △m, where△m = （0, 0, 0, 0, 231, 0,..., 0）. There is only one bit difference between m and m＇. Two pairs of collision examples for HAVAL-128 are given. In order to improve the probability of collision, we use four tricks of message modification. The attack＇s running time is less than 225.83 2-pass HAVAL computations, which is the best result for one-bit collision of HAVAL so far.

关 键 词：CRYPTOGRAPHY hash function HAVAL-128 COLLISION message modification 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构] TQ441.41[自动化与计算机技术—计算机科学与技术]