Improving Key Recovery to 784 and 799 Rounds of Trivium Using Optimized Cube Attacks

Abstract : Dinur and Shamir have described cube attacks at EUROCRYPT '09 and they have shown how efficient they are on the stream cipher Trivium up to 767 rounds. These attacks have been extended to distinguishers but since this seminal work, no better results on the complexity of key recovery attacks on Trivium have been presented. It appears that the time complexity to compute cubes is expensive and the discovery of linear superpoly also requires the computation of many cubes. In this paper, we increase the number of attacked initialization rounds by improving the time complexity of computing cube and we show attacks that go beyond this bound. We were able to find linear superpoly up to 784 rounds, which leads to an attack requiring 2 39 queries. Using quadratic superpoly, we were also able to provide another attack up to 799 rounds which complexity is 2 40 queries and 2 62 for the exhaustive search part. To achieve such results, we find a way to reduce the density of the polynomials, we look for quadratic relations and we extensively use the Moebius transform to speed up computations for various purposes.
Type de document :
Communication dans un congrès
Fast Software Encryption - 20th International Workshop, 2013, Mar 2013, Singapore, Singapore. Springer, LNCS 8424, pp.16, 2014, FSE 2013. 〈10.1007/978-3-662-43933-3_26〉
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01094308
Contributeur : Pierre-Alain Fouque <>
Soumis le : vendredi 12 décembre 2014 - 09:45:57
Dernière modification le : mercredi 16 mai 2018 - 11:23:29
Document(s) archivé(s) le : vendredi 13 mars 2015 - 10:25:42

Fichier

FV13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre-Alain Fouque, Thomas Vannet. Improving Key Recovery to 784 and 799 Rounds of Trivium Using Optimized Cube Attacks. Fast Software Encryption - 20th International Workshop, 2013, Mar 2013, Singapore, Singapore. Springer, LNCS 8424, pp.16, 2014, FSE 2013. 〈10.1007/978-3-662-43933-3_26〉. 〈hal-01094308〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

79