MD-64算法的相关密钥-矩形攻击

该文针对MD-64分组密码算法在相关密钥-矩形攻击下的安全性进行了研究。分析了算法中高次DDO (Data Dependent Operations)结构、SPN结构在输入差分重量为1时的差分转移规律，利用高次DDO结构的差分特性和SPN结构重量为1的差分路径构造了算法的两条相关密钥-差分路径，通过连接两条路径构造了算法的完全轮的相关密钥-矩形区分器，并对算法进行了相关密钥-矩形攻击，恢复出了32 bit密钥。攻击算法所需的数据复杂度为262相关密钥-选择明文，计算复杂度为291.6次MD-64算法加密，存储复杂度为266.6 Byte存储空间，成功率约为0.961。分析结果表明，MD-64算法在相关密钥-矩形攻击条件下的安全性无法达到设计目标。

Related-key Rectangle Attack on MD-64

The security of MD-64 block cipher under related-key rectangle attack is studied. Firstly, when the weight of input difference is 1, the differential properties of high order DDOs (Data Dependent Operations) and SPN structures are researched. By the differential properties of high order DDOs and the high probability differential of SPN structures, two related-key differentials are constructed. Secondly, a full round related-key rectangle distinguisher of MD-64 is constructed by connecting two related-key differentials. Thirdly, a related-key rectangle attack is proposed on MD-64, and 32 bits of the master key is recovered with 262 related-key chosen- plain-text, 291.6 encryptions of MD-64 block cipher, and a storage complexity of 266.6 Byte. The success rate of this attack is about 0.961. Analysis results show that MD-64 can not reach the design target under related-key rectangle attack.