A New Correlation Cube Attack Based on Division Property

基于可分性的一种新相关cube攻击

背景

田甜等人发表在ACISP2023:原文

  • 随着Trivium初始化轮数 ↑ ,超多项式的规模 ↑
  • 即使目前可以恢复这样的超多项式,如何利用大规模超多项式进行攻击?
  • 与立方攻击相比,相关立方攻击利用超多项式和一组特定的低次多项式(基)的条件相关性,可以实现较大规模的超多项式用于密钥恢复攻击

主要贡献

一种新的相关立方攻击方法

  1. 将超多项式 𝑝 表示为 𝑓𝑔⊕ℎ , 𝑓 只包含秘密变量
  2. 寻找 ℎ 有偏差的cube,则在一定条件下,𝑝=𝑓𝑔
  3. 计算所有可能的 𝑓 和 𝑝 的相关概率,然后利用 𝑝 和 𝑓 之间的相关性获得密钥信息

改进一: 寻找 ℎ 有偏差的cube,简化超多项式的ANF
改进二: 所有可能的 𝒇:在低轮出现的所有可能低次多项式(基的非唯一确定性)

1
偏差:在公共变量一些条件下,对于大部分秘密变量的取值, ℎ 的取值为常数

问题关键 — 寻找好的cube

  1. 基测试:通过可分性,基于MILP模型寻找,加一些条件后(基=0)超多项式为零常数的cube
  2. 进一步筛选h有偏差的cube

改进三: 可分性在相关cube攻击中的首次应用

论文主要结果

对于844轮Trivium,可以恢复4比特密钥信息,平均时间复杂度为2^45

  • 使用了28个cube,cube大小为37-38,总时间复杂度2^76,优于之前的2^78

可以看到文中方法是有成功率的

密钥比特 4.06 3.88 3.61 3.18 2.83
成功率 71.1% 77.3% 89.1% 93.0% 97.7%

总结

在cube攻击中,随着Trivium初始轮数的增加,超多项式的规模逐渐增大。即使目前可以恢复大规模超多项式的ANF,但如何利用这些超多项式进行攻击是待解决的问题。与cube攻击相比,相关cube攻击利用超多项式和一组特定的低次多项式(基)之间的条件相关性,可以将大规模超多项式用于密钥恢复攻击。作者提出了一种新的相关cube攻击方法。如果超多项式 𝑝 可以表示为 𝑓𝑔⊕ℎ ( 𝑓 只包含秘密变量),则作者通过寻找超多项式包含 𝑓且 ℎ 有偏差的cube,利用 𝑝 和 𝑓 之间的相关性获取密钥信息。对于844轮的Trivium,该方法可以恢复4比特密钥信息,平均时间复杂度为2^45。这篇文章提供了一种利用复杂超多项式进行攻击的思路,基于相关性的cube攻击变体值得进一步研究。


上述内容仅用于非领域人员快速了解,具体实现逻辑及细节不做展示
Welcome to MinZhang’s space! If you have any questions about the following issues, you can contact me on GitHub or email- zhangmin2022@iie.ac.cn.