MDx差分攻击算法改进及GPGPU上的有效实现  

Improvement and Efficient Implementation of Differential Attack Algorithm to MDx on GPGPU

作　　者：周林[1] 韩文报[1] 祝卫华[1] 王政[1] 

机构地区：[1]解放军信息工程大学信息工程学院,郑州450002

出　　处：《计算机学报》2010年第7期1177-1182,共6页Chinese Journal of Computers

基　　金：国家自然科学基金(2007B74);国家"八六三"高技术研究发展计划项目基金(2009AA012417)资助~~

摘　　要：Hash函数广泛应用于商业、安全等领域,其中MDx系列Hash算法应用最为广泛.因此对MDx系列Hash算法的攻击在理论上和实际应用上都有重要的意义.自王小云教授提出差分攻击算法并攻破MD5、MD4等MDx系列算法以来,对该算法的研究日益受到关注.文中以攻击MD5的差分攻击算法为例,改进了Klima提出的MD5隧道差分攻击算法,分析其在GPGPU上实现的可行性和技术要求并在Visualstudio6.0的环境下利用CUDA语言开发完成.算法的CUDA程序在GeForce9800GX2平台下运行,平均每1.35s能找到一对MD5碰撞.通过同4核Core2QuadQ9000(2.0GHz)PC上的实现相比较,在GeForce9800GX2上的实现能达到11.5倍的性价比.Hash functions are widely used in business, military field etc. Among them, MD-family Hash functions are the most extensively utilized hash functions. Therefore, the attack to MD- family hash functions has important meaning in theory and in practical application. Since professor Wang proposed differential attack algorithm and succeeded to break MD5, MD4, etc MD-family algorithms, this algorithm has been paid more and more attention. This paper takes the tunnel differential attack algorithm to MD5 as example, improves the tunnel differential attack algorithm to MD5 proposed by Klima and analyzes the feasibility and technology request of differential attack algorithm＇s implementation on GPGPU. Its CUDA program run on the GeForce 9800 GX2 platform and can find a pair of MD5 collision in just 1.35 seconds average. Through comparing the software implementation on PC Core 2 Quad Q9000 （2.0GHz）, we can get nearly 11.5 times more cost-efficient by the implementation on GeForce 9800 GX2.

关 键 词：MD5 HASH函数 差分攻击 隧道技术 多消息修正方法 CUDA GPGPU Mersenne TWISTER 

分 类 号：TP331[自动化与计算机技术—计算机系统结构]