Cryptology ePrint Archive: Report 2021/1191

A Simpler Model for Recovering Superpoly onTrivium

St├ęphanie Delaune and Patrick Derbez and 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].

Category / Keywords: secret-key cryptography / Stream cipher and Cube Attack and Division Property and Trivium and MILP and CP

Original Publication (in the same form): SAC-2021

Date: received 15 Sep 2021

Contact author: patrick derbez at irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20210917:090926 (All versions of this report)

Short URL: ia.cr/2021/1191


[ Cryptology ePrint archive ]