Key Filtering in Cube Attacks from the Implementation Aspect

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

背景

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

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

主要贡献

(一)什么是可行的攻击
对应:cube求和,穷搜,密钥恢复查表,建立真值表,暴力搜索界

  1. 在之前的攻击中,认为 $\alpha$ 很大,忽略后半部分的时间复杂度!
  2. 实际上如果使用了大规模超多项式,这部分不应该被忽略
  3. 对于可以快速实现加密的流密码,即 $\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.