MD4和MD5碰撞攻击相关技术研究

发布时间：2018-07-09 16:04

本文选题：Hash + MD5　；参考：《解放军信息工程大学》2014年硕士论文

【摘要】：Hash函数作为现代信息安全理论中的重要工具之一,为确保信息交互过程的可靠性发挥着重大的作用。随着MD5的攻破以及有语义的MD5选择前缀碰撞算法的提出,对Hash函数的安全性分析及研究成为了焦点。近几年,MD5作为被广泛应用的Hash函数,因选择前缀碰撞算法的提出和应用以及火焰病毒的发现而受到关注,同时MD5的安全性也受到了质疑。然而,由于一些现实因素的影响,MD5仍在信息安全系统中发挥着作用。MD4作为MD5和SHA-1等Hash函数的设计基础,对于它的分析可为后续的Hash函数研究提供一定的指导。本文主要对MD4和MD5碰撞攻击的相关技术及算法进行了分析,取得了以下结果:1、对文[17]中MD4差分路径自动化构造算法进行了改进。通过考察MD4算法及其差分路径自动化构造算法的原理,分析了具体差分路径自动化构造算法中影响差分路径重量的各因素,最后通过充分利用第32比特位上差分的特殊性,有效控制了搜索抵消目标差分过程中不必要的有符号差分进位扩展,搜索构造得到了新的差分路径。相对于文[17]中差分路径,新差分路径的差分重量减少了6,充分条件数减少了14个。2、针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题,提出了改进的MD5选择前缀碰撞算法。首先结合非相邻表示型(NAF),给出了生日搜索复杂度中概率值在特定条件下的推导方式,并将推导所得值与文[37]中给出的模拟值进行了比较,验证了推导过程的正确性,同时建立了平衡参数与生日搜索复杂度之间的关系。其次,针对选择前缀碰撞算法在被应用于伪造X.509证书时其计算复杂度几乎完全由生日搜索复杂度决定的现象,结合上述关于平衡参数的理论结果,通过引入新的消息差分,改进了选择前缀碰撞所需的生日碰撞形式,得到改进算法。结果在实际应用所需的参数条件下,改进算法平均可降低1比特的复杂度。3、给出了Hash函数连续近似碰撞块检测算法。基于Marc Stevens给出的最后一块近似碰撞块检测算法,得到连续近似碰撞块检测算法。结果成功实现了对火焰病毒证书的检测,仅在0.06秒内得到4块连续近似碰撞块,并首次给出了近似碰撞采用的所有差分路径,最后基于所得碰撞信息,对火焰病毒证书的伪造过程与Stevens提出的选择前缀碰撞算法进行了初步比较。
[Abstract]:As one of the important tools in modern information security theory, Hash function plays an important role in ensuring the reliability of information interaction process. With the breakthrough of MD5 and the proposed of semantic MD5 prefixes collision algorithm, the security analysis and research of Hash function become the focus. In recent years, as a widely used Hash function, MMD5 has attracted much attention because of the proposed and applied prefix collision algorithm and the discovery of flame virus. At the same time, the security of MD5 has also been questioned. However, due to the influence of some practical factors, MD5 still plays an important role in the information security system. MD4 is the basis of the design of Hash functions such as MD5 and SHA-1. The analysis of MD5 can provide some guidance for the further study of Hash function. In this paper, the related techniques and algorithms of MD4 and MD5 collision attacks are analyzed, the following results are obtained: 1, and the algorithm of constructing MD4 differential path automation in [17] is improved. By investigating the principle of MD4 algorithm and its differential path automation construction algorithm, this paper analyzes the factors that affect the weight of differential path in the specific differential path automatic construction algorithm. Finally, by making full use of the particularity of the difference on the 32nd bit, The unnecessary signed difference carry expansion is effectively controlled in the process of searching and canceling the target difference, and a new difference path is obtained by the search construction. Compared with the difference path in [17], the differential weight of the new differential path is reduced by 6, and the sufficient condition number is reduced by 14. 2. In view of the imbalance of the complexity distribution of the MD5 prefixed collision algorithm in practical application, An improved MD5 prefix collision algorithm is proposed. First of all, combining with non-adjacent representation (NAF), the derivation method of probability value in birthday search complexity under certain conditions is given, and the derived value is compared with the simulated value given in [37], which verifies the correctness of the derivation process. At the same time, the relationship between the balance parameter and birthday search complexity is established. Secondly, aiming at the phenomenon that the computational complexity of selecting prefix collision algorithm is almost determined by birthday search complexity when it is applied to fake X.509 certificates, combined with the theoretical results of equilibrium parameters mentioned above, a new message difference is introduced. The birthday collision form needed to select prefix collision is improved, and the improved algorithm is obtained. Results under the condition of practical application, the improved algorithm can reduce the complexity of 1 bit by 1 bit on average. The Hash function continuous approximate collision block detection algorithm is presented. Based on Marc Stevens' last approximate collision block detection algorithm, a continuous approximate collision block detection algorithm is obtained. Results the Flame virus certificate was successfully detected and four successive approximate collision blocks were obtained in only 0.06 seconds. All the differential paths used in the approximate collision were given for the first time. Finally, based on the resulting collision information, all the differential paths used in the approximate collision were given for the first time. The forging process of flame virus certificate is compared with Stevens' algorithm of selecting prefix collision.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TN918.1

【参考文献】