### A Simpler Model for Recovering Superpoly onTrivium

Stéphanie Delaune, Patrick Derbez, Arthur Gontier, and Charles Prud'homme

##### Abstract

The cube attack is a powerful cryptanalysis technique against symmetric cryptosystems, 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 [13,15]. 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. [13], and consistently 30 to 60 times faster than the monomial prediction-based model from Hu et al. [15].

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. SAC-2021
Contact author(s)
patrick derbez @ irisa fr
History
Short URL
https://ia.cr/2021/1191

CC BY

BibTeX

@misc{cryptoeprint:2021/1191,
author = {Stéphanie Delaune and Patrick Derbez and Arthur Gontier and Charles Prud'homme},
title = {A Simpler Model for Recovering Superpoly onTrivium},
howpublished = {Cryptology ePrint Archive, Paper 2021/1191},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1191}},
url = {https://eprint.iacr.org/2021/1191}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.