Improved Graph-Based Model for Recovering Superpoly on Trivium

Liu chen, Tian tian等人发表在JSSC2023：原文

研究意义

cube攻击中，需要通过对超多项式求解来获得密钥信息，超多项式次数越低，在攻击中可能越容易求解。如果随机的选择cube，大概率得到的超多项式是比较复杂的。因此搜索cube的方法非常关键。

motivation

对于如何寻找一组理想的候选cube集合，目前没有找到特别好的方法。

  • 田甜等人提出了805轮搜索cube的方法，依赖于Möbius变换来估计次数，该方法对轮数有限制

insight

通过将一个大cube重复划分为两个不相交的子cube，来估计超多项式中高次项出现的频率，从而判断超多项式是否容易恢复

  • 一个实例如下：

    1. 将给定的cube划分为多个子cube对: 目标是对于一个给定的cube集合（例如$cube I$）想要找到超多项式次数低的子cube集合

      • $cube I$划分为很多种两个不相交子集的形式；
      • 对于每一种划分，估计两个子cube的超多项式的次数来判断超多项式是否容易恢复。
      • 在下图例子中，假如输出多项式为$h=fg$，可以计算134在f和g上的次数，计算257在f和g上的次数，以及他们的子集13，14，34等。
      • 最终对于这一种划分可以得到组合起来可能次数低的子cube集合.

    2. 统计不同子cube组合的次数估计结果:

      • 对于所有的划分情况，统计了子cube出现频率.
      • 对于不同的划分，估计的超多项式次数都比较低，其对应的超多项式比较简单的概率也越大。
      • 因此搜索到了一组大概率超多项式容易恢复的子cube

    3. 找到可能超多项式次数低的子cube：

      • 最终结果看，该方法得到的子cube对应的超多项式确实次数比较低

贡献

  • 提出了一种cube筛选算法，可以根据给定cube，得到一个超多项式次数较低的候选子cube集合。
  • 作者实现了Trivium-815轮的理论攻击，攻击复杂度为$2^{72.46}$。

评价

  • 作者的方法其实是改进了805轮搜索cube的方法中的一个步骤，大部分步骤和之前的方法是相似的，例如cube扩展的过程，初始cube的选择等。
  • 次数估计使用的Mobius变换方法没有具体介绍

总结

在基于可分性的cube攻击中，选择超多项式次数低的cube是非常关键的。因为随机的选择cube是低效的，所以搜索cube的方法很重要。作者发现目前没有特别好的方法来得到一些理想的cube，因此提出了一种cube筛选算法，可以根据给定的cube，得到一个超多项式次数较低的候选子cube集合。算法的核心思想是通过将一个大cube重复划分为两个不相交的子cube，来估计超多项式中高次项出现的频率，从而判断超多项式是否容易恢复。最终作者实现了Trivium-815轮的理论攻击，攻击复杂度为2^72.46。我认为作者主要通过cube拆分来解决次数估计时M𝑜 ̈bius变换对轮数的限制问题，作者提出的方法更像是Trivium-805轮搜索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.