流密码的cube攻击简介
2017 年美密会上由Todo 提出基于可分性的立方攻击，受益于可分性和MILP 工具，攻击者可以使用高维数的cube集合，使得立方攻击是Trivium型密码最有效的攻击方法。
发展
- 2020.12 Kai Hu, etc. ASIACRYPT 2020
An Algebraic Formulation of the Division Property: Revisiting Degree Evaluations, Cube Attacks, and Key-Independent Sums
提出单项式预测技术，改进了Trivium-840，841，842轮的理论攻击 - 2021.12 ChenDong Ye, Tian Tian. ASIACRYPT 2021
A Practical Key-Recovery Attack on 805-Round Trivium
提出构建线性超多项式的cube方法，实现了复杂度为2^41.4的Trivium-805轮实际攻击 - 2021.12 Yao Sun. FSE2021
Automatic Search of Cubes for Attacking Stream Ciphers
提出启发式算法搜索超多项式中包含平衡比特的cube，首次实现了Trivium-843轮的理论攻击和Trivium-806、Trivium-808轮的实际攻击 - 2022.3 Stéphanie Delaune, etc. SAC2021
A Simpler Model for Recovering Superpoly on Trivium
构建有向图模型恢复超多项式，通过剪枝实现消去偶数单项式路径，恢复效率较胡凯模型提高30～60倍 2023.1 Cheng Che, Tian Tian. Inscrypt 2022
An Experimentally Verified Attack on 820-Round Trivium
搜索近似带平衡bit的超多项式，给出了Trivium-815和Trivium-820时间复杂度分别为2^47.32 和2^53.17 的攻击2023.4 Junjie Cheng, Kexin Qiao. CT-RSA2023
Improved Graph-Based Model for Recovering Superpoly on Trivium
在图模型基础上找到了剪枝效率更高的加约束方法，以及提出一种寻找更多偶数路径的算法2023.8 Hao Lei, etc. ePrint2023
More Balanced Polynomials: Cube Attacks on 810- and 825-Round Trivium with Practical Complexities
对于Trivium-810，Trivium-825，提出启发式构建母cube算法实现了复杂度为2^44.17 和2^53.17 的攻击
目前，cube实际攻击的进展方面，胡凯等人在2023年亚密会实现了Trivium-825；同样在2023年亚密会，吴保峰等人以一定成功概率对轮数有进一步进展。
关键进展
难点 — 寻找好的cube
- 候选cube的数量非常多，大多数cube都不是“好”的。
- 难以评估一个cube是否“好”
An algebraic formulation of the division property: Revisiting degree evaluations, cube attacks, and key-independent sums.
胡凯 ASIACRYPT 2020
- 提出单项式预测模型，从纯代数角度解释可分性
- 计算单项式路径个数的奇偶，确定单项式是否出现在密码输出的代数表达式中，恢复超多项式
MILP模型：模型约束条件—-单项式指数间的传播关系；单项式的指数—-变量
Automatic search of cubes for attacking stream ciphers.
孙瑶 FSE2022
- 首次实现了Trivium-843轮的理论攻击，Trivium-806、Trivium-808轮的实际攻击
- 基于实验观察可以及时排除不好的cube：在整个系统中单项式路径为奇数约等于在子系统中单项式路径为奇数
- 提出启发式算法搜索超多项式中包含平衡比特的cube
- 准备一些候选cube，选择一个变量 k
- 将整个求解系统分为几个子系统
- 依次计算每个子系统的解
- 如果包含变量 k 的非线性单项式在子系统中出现奇数次，则移除该cube
- 如果单项式k出现在一些子系统中，记录出现次数
- 计算结束后，如果存在出现奇数次的cube，则该cube是好的
A Simpler Model for Recovering Superpoly on Trivium
Stéphanie Delaune, Patrick Derbez, Arthur Gontier, Charles Prud’Homme SAC 2021
- 使用有向图的结构建立约束来追踪单项式是否出现：
图的节点是变量，图的边代表变量的关系 - 模型规模降低，使用剪枝来减少求解中单项式路径的数量，减轻了枚举负担
（这篇文章改进数据结构，实现了非常快的搜索，价值比较大，值得具体研究）
总结
到目前为止，Trivium 可以抵抗已有的所有攻击方法，2023年大部分研究人员开始关注相关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.