Stéphanie Delaune, Patrick Derbez, Arthur Gontier, and Charles Prud'homme. A Simpler Model for Recovering Superpoly on Trivium. In Proceedings of the 28th International Conference on Selected Areas in Cryptography (SAC'21), Lecture Notes in Computer Science, Springer, 2021.
The cube attack is a powerful cryptanalysis technique against symmetric primitives, especially for stream ciphers. One of the key step in a cube attack is recovering the superpoly. The division property has been introduced to cube attacks with the aim first to identify variables/monomials that are not involved in the superpoly. Recently, some improved versions of this technique allowing the recovery of the exact superpoly have been developed and applied on various stream ciphers by Hao et al (EuroCrypt'20) and Hu et al (AsiaCrypt'20).In this paper, we propose a new model to recover the exact superpoly of a stream cipher given a cube. We model the polynomials involved in the stream cipher as a directed graph. It happens that this structure handles some of the monomial cancellations more easily than those based on division property, and this leads to better timing results.We propose two implementations of our model, one in MILP and one in CP, which are up to 10 times faster than the original division property-based model from Hao et al. (EuroCrypt'20), and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al (AsiaCrypt'20).
@inproceedings{DDGP-sac21,
author = {St{\'e}phanie Delaune and Patrick Derbez and Arthur Gontier and Charles Prud'homme},
title = {A Simpler Model for Recovering Superpoly on Trivium},
booktitle = {{P}roceedings of the 28th International Conference on Selected Areas in Cryptography ({SAC}'21)},
OPTpages = {66--89},
year = {2021},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
abstract= {The cube attack is a powerful cryptanalysis technique against symmetric primitives, especially for stream ciphers.
One of the key step in a cube attack is recovering the superpoly. The division property has been introduced
to cube attacks with the aim first to identify variables/monomials that are \emph{not} involved in the superpoly. Recently,
some improved versions of this technique allowing the recovery of the exact superpoly have been developed and applied on
various stream ciphers by Hao et al (EuroCrypt'20) and Hu et al (AsiaCrypt'20).
In this paper, we propose a new model to recover the exact superpoly of a stream cipher given a cube.
We model the polynomials involved in the stream cipher as a directed graph. It happens that this structure handles some of the monomial cancellations more easily than those based on division property, and this leads to better timing results.
We propose two implementations of our model, one in MILP and one in CP, which are up to 10 times faster than the original
division property-based model from Hao et al. (EuroCrypt'20),
and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al (AsiaCrypt'20).},
lsv-category = {intc},
}