Abstract:

According to the unbalanced distribution of the complexity of chosen-prefix collisions under the practical requirement, an improved algorithm of chosen-prefix collisions for MD5 was designed. Combined with Non-Adjacent Form (NAF), the probability related to the complexity of birthday search was deduced under certain conditions, and the relation between the balance parameter and the complexity of birthday search was established. Then based on the above results, the improved algorithm was designed through improving the form of birthday collision by introducing new message block differences. Under the practical requirement for parameters, the complexity of the improved algorithm can reduce one bit on average. The results show that, compared with the original MD5, the improved algorithm defuses imbalance of complexity distribution, reduces the complexity, and is more suitable for practical applications.

摘要：

针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题，提出了改进的MD5选择前缀碰撞算法。结合非相邻表示型(NAF)，给出了生日搜索复杂度中概率值在特定条件下的推导方式，建立了平衡参数与生日搜索复杂度之间的关系；并基于上述理论结果，通过引入新的消息差分，改进了选择前缀碰撞所需的生日碰撞形式，得到改进算法。在实际应用所需的参数条件下，改进算法相对MD5算法平均可降低1比特的复杂度。分析结果表明：相对于原MD5算法，改进算法缓和了复杂度分布的失衡现象，降低了算法复杂度，更适用于实际应用。