SHA-1差分路径搜索算法和连接策略研究

作者：曾光; 李婧瑜; 杨阳^*

来源：软件学报, 2022, 33(12): 4784-4803.

DOI：10.13328/j.cnki.jos.006378

• 密码学
• Hash函数
• SHA-1算法
• 差分路径

Hash函数SHA-1的攻击技术研究一直受到密码分析者的广泛关注,其中,差分路径构造是影响攻击复杂度大小的重要环节.提出了带比特条件的全轮差分路径构造方法,统一了第1轮差分路径构造和后3轮的差分路径构造.该方法既与原有第1轮路径构造相容,又能省去后3轮路径约简、消息约简等繁琐技术环节,具有良好的兼容性.此外,综合考虑状态差分、布尔函数差分与比特条件之间的制约关系,提出了带比特条件的前向扩展、后向扩展和中间连接这3个子算法,并提出3个指标——比特条件的更新次数、扩展结果的相容性和候选集合的正确率对中间连接的成功率进行评价,结合提前终止策略,提出了最优的中间连接算法.理论分析结果表明,该方法有助于提高SHA-1差分路径构造的成功率.最后,采用该算法进行路径搜索,可以得到正确的可用于碰撞搜索的差分路径.

• 单位
  中国人民解放军战略支援部队信息工程大学; 中国科学院软件研究所; 华为技术有限公司