针对减宽SHA-1算法的模差分攻击分析

模差分攻击技术是SHA-1随机碰撞攻击中重要分析方法之一.针对减宽的SHA-1算法,该文得出了减宽的部分碰撞定理并给出了减宽SHA-1算法单一部分碰撞的概率,证明了模差分攻击技术同样适用于减宽的SHA-1算法.通过理论分析和计算机搜索,该文证明了对于宽为n比特的SHA-1算法,当且仅当n3时,最优扰动向量的汉明重为25;当且仅当n8时,最优扰动向量只有type-I与type-II两个等价类.

Analysis of SHA-1 with Reducing Width for Modular Differential Attack

Modular differential attack is one of the important methods in SHA-1 collision attacks. In allusion to width-reduced SHA-1 algorithm, the width-reduced local collisions theorems are deduced in this paper, and the probability of local collisions in width-reduced SHA-1 algorithm is proposed. Thus, modular differential attack is proved to be appropriate for width-reduced SHA-1 algorithm. By means of theoretical analysis and computer search, it is proved that for n-bit SHA-1 algorithm, the hamming weight of the optimum disturbance vector is 25 if and only if n>3; and when and only when n>8, the optimum disturbance vector has no other equivalence class than type- I and type-II.