Key Filtering in Cube Attacks from the Implementation Aspect

从实现角度的cube攻击中的密钥筛选

背景

郝泳霖等人发表在 CANS2023：原文

cube攻击：超多项式恢复 -> cube求和 -> 密钥筛选 -> 穷搜
较高轮数使用的超多项式几乎包含所有秘密变量
密钥筛选阶段 $复杂度\approx2^𝑛$
整体攻击可能高于暴力攻击的复杂度 $复杂度可能>2^𝑛$

主要贡献

（一）什么是可行的攻击：
对应：cube求和，穷搜，密钥恢复查表，建立真值表，暴力搜索界

$C_{new}=\sum_{j=1}^{l-1}2^{|I_j|}+2^{n-l}+\frac{2}{\alpha}\sum_{j=1}^{l-1}2^{|J_j|}+\frac{\beta}{\alpha} < 2^n$ $\alpha ：一次加密oracle查询的复杂度$

在之前的攻击中，认为 $\alpha$ 很大，忽略后半部分的时间复杂度！
实际上如果使用了大规模超多项式，这部分不应该被忽略
对于可以快速实现加密的流密码，即 $\alpha$ 比较小时，攻击不可行

按照该流程对已有攻击的复杂度重新计算，当$\alpha \approx$ 一次查表，大部分高轮数已有攻击是不可行的

（二）cube攻击被分为两类：

依赖于实现的cube攻击：$\alpha >>$ 一次查表，才是可行的
与实现无关的cube攻击：$\alpha \approx$ 一次查表，仍然可行

贡献1： 从实现角度对cube攻击分类；指出现有使用大规模超多项式的cube攻击大多为依赖于实现的

（三）流密码的cube攻击：

传统策略：使用超多项式较复杂的低维cube，忽略了大规模超多项式密钥筛选阶段的复杂度
作者：使用超多项式次数低、包含变量少的高维cube，在整体的复杂度计算中优于已有结果

贡献2： 基于上述策略首次提出了对Kreyvium的898、899和900轮的攻击结果且该攻击与实现无关
贡献3： 多个cube的攻击效率不一定优于单个cube，有时应该限制使用的cube数量

1
2
3

Trivium-843：使用3个cube，第3个等式只能过滤掉1/8的密钥
- 使用等式筛选密钥：1.17*2^79
- 穷搜：          0.5*2^79

论文主要结果

明确了严格的复杂度计算应该包含哪些部分，如何计算这些问题，在之前的攻击中给出的是模糊不清的
将所有cube攻击分类
首次给出了对Kreyvium的898、899和900轮的攻击结果

总结

在使用大规模超多项式的cube攻击中，超多项式几乎包含所有秘密变量，密钥筛选阶段的时间复杂度接近2^𝑛，因此作者发现密钥筛选阶段的时间复杂度不应该被忽略，并从实现角度将所有cube攻击分为两类。依赖于实现的cube攻击只有当一次加密oracle查询远比一次查表更复杂时才是可行的，而与实现无关的cube攻击在一次加密oracle查询相当于一次查表的极端情况下仍然可行，现有的高轮数下的cube攻击大多都是依赖于实现的cube攻击。cube攻击中的传统策略是使用超多项式较复杂的低维cube，相反的，基于上述观察作者使用了超多项式次数低、包含秘密变量少的高维cube，首次给出了对Kreyvium的898、899和900轮的攻击结果且这些攻击与实现无关。本文从实现角度严格计算了整体攻击的时间复杂度，指出了之前攻击中忽略的问题，对判断攻击是否成立具有实际意义。

上述内容仅用于非领域人员快速了解，具体实现逻辑及细节不做展示
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.