A New Correlation Cube Attack Based on Division Property
基于可分性的一种新相关cube攻击
背景
田甜等人发表在ACISP2023：原文
- 随着Trivium初始化轮数 ↑ ，超多项式的规模 ↑
- 即使目前可以恢复这样的超多项式，如何利用大规模超多项式进行攻击？
- 与立方攻击相比，相关立方攻击利用超多项式和一组特定的低次多项式（基）的条件相关性，可以实现较大规模的超多项式用于密钥恢复攻击
主要贡献
一种新的相关立方攻击方法
- 将超多项式 𝑝 表示为 𝑓𝑔⊕ℎ ， 𝑓 只包含秘密变量
- 寻找 ℎ 有偏差的cube，则在一定条件下，𝑝=𝑓𝑔
- 计算所有可能的 𝑓 和 𝑝 的相关概率，然后利用 𝑝 和 𝑓 之间的相关性获得密钥信息
改进一： 寻找 ℎ 有偏差的cube，简化超多项式的ANF
改进二： 所有可能的 𝒇：在低轮出现的所有可能低次多项式（基的非唯一确定性）
1 | 偏差：在公共变量一些条件下，对于大部分秘密变量的取值， ℎ 的取值为常数 |
问题关键 — 寻找好的cube
- 基测试：通过可分性，基于MILP模型寻找，加一些条件后（基=0）超多项式为零常数的cube
- 进一步筛选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.