李婧瑜, 杨 阳,2, 曾 光, 李德刚

1. 中国人民解放军战略支援部队信息工程大学 数学工程与先进计算国家重点实验室, 郑州 450001

2. 中国科学院 软件研究所 可信计算与信息保障实验室, 北京 100190

1 引言

SHA-1 算法由美国国家安全局[1]设计, 1994 年被美国国家标准与技术研究院(NIST) 发布作为联邦信息处理标准(FIPS), 该算法一经提出就受到各国密码学家的广泛关注. 2005 年, 王小云教授[2]通过模差分攻击技术和消息修改技术把对SHA-1 随机碰撞攻击的复杂度降到了269, 这也是首次将SHA-1 随机碰撞攻击的复杂度降到生日攻击以下. 随后, 很多团队尝试利用该方法对减轮的SHA-1 算法进行碰撞攻击[3–6]. 直到2017 年, Stevens 与Google[7]宣布了一个成功的SHA-1 碰撞攻击, 并且发布了两份内容不同但SHA-1 散列值相同的PDF 文件作为证明. 这是目前为止对SHA-1 的最好的随机碰撞攻击结果.对SHA-1 的另一攻击手段是选择前缀碰撞攻击, 这一类的攻击最好结果由Leurent 和Peyrin[8]在2020年发布, 他们以263.4的复杂度完成了对SHA-1 的选择前缀攻击.

在对SHA-1 的随机碰撞攻击和选择前缀攻击过程中, 构造差分路径和根据差分路径寻找碰撞是两种攻击中共同的步骤. 在构造差分路径方面, 现已由早期的手动构造方法[2]发展为自动化的差分路径构造算法[9–11]. 差分路径的成立概率很大程度上决定了寻找碰撞的成功率和复杂度, 所以对概率的高精度刻画在攻击过程中是十分重要的. 在早期的SHA-1 碰撞攻击研究过程中, 往往以充分条件的个数来决定差分路径成立概率[12,13], 设由差……