Another Look at Complementation Properties

Abstract : In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied. Our main result is a self-similarity property on the Sha-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several Sha-3 candidates. Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher's 64 rounds. We also apply our techniques to ESSENCE and PURE.
Type de document :
Communication dans un congrès
Seokhie Hong and Tetsu Iwata. Fast Software Encryption, 17th International Workshop : FSE 2010, 2010, Seoul, South Korea. Springer, 6147, pp.347-364, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13858-4_20〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00556674
Contributeur : Pierre-Alain Fouque <>
Soumis le : vendredi 21 janvier 2011 - 15:01:08
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : mardi 6 novembre 2012 - 11:56:17

Fichier

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

Identifiants

Collections

Citation

Charles Bouillaguet, Orr Dunkelman, Gaëtan Leurent, Pierre-Alain Fouque. Another Look at Complementation Properties. Seokhie Hong and Tetsu Iwata. Fast Software Encryption, 17th International Workshop : FSE 2010, 2010, Seoul, South Korea. Springer, 6147, pp.347-364, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13858-4_20〉. 〈inria-00556674〉

Partager

Métriques

Consultations de la notice

319

Téléchargements de fichiers

110