Faculté informatique et communications IC, Section des systèmes de communication, Institut de systèmes de communication ISC (Laboratoire de sécurité et de cryptographie LASEC)

Statistical cryptanalysis of block ciphers

Junod, Pascal ; Vaudenay, Serge (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3179.

Ajouter à la liste personnelle
    Summary
    Since the development of cryptology in the industrial and academic worlds in the seventies, public knowledge and expertise have grown in a tremendous way, notably because of the increasing, nowadays almost ubiquitous, presence of electronic communication means in our lives. Block ciphers are inevitable building blocks of the security of various electronic systems. Recently, many advances have been published in the field of public-key cryptography, being in the understanding of involved security models or in the mathematical security proofs applied to precise cryptosystems. Unfortunately, this is still not the case in the world of symmetric-key cryptography and the current state of knowledge is far from reaching such a goal. However, block and stream ciphers tend to counterbalance this lack of "provable security" by other advantages, like high data throughput and ease of implementation. In the first part of this thesis, we would like to add a (small) stone to the wall of provable security of block ciphers with the (theoretical and experimental) statistical analysis of the mechanisms behind Matsui's linear cryptanalysis as well as more abstract models of attacks. For this purpose, we consider the underlying problem as a statistical hypothesis testing problem and we make a heavy use of the Neyman-Pearson paradigm. Then, we generalize the concept of linear distinguisher and we discuss the power of such a generalization. Furthermore, we introduce the concept of sequential distinguisher, based on sequential sampling, and of aggregate distinguishers, which allows to build sub-optimal but efficient distinguishers. Finally, we propose new attacks against reduced-round version of the block cipher IDEA. In the second part, we propose the design of a new family of block ciphers named FOX. First, we study the efficiency of optimal diffusive components when implemented on low-cost architectures, and we present several new constructions of MDS matrices; then, we precisely describe FOX and we discuss its security regarding linear and differential cryptanalysis, integral attacks, and algebraic attacks. Finally, various implementation issues are considered.
    Résumé
    Depuis le développement de la cryptologie dans les mondes industriel et académique, les connaissances et l'expertise publique ont crû demanière soutenue, notamment en raison de l'omniprésence des moyens de communication électronique dans la vie de tous les jours. Les algorithmes de chiffrement par blocs sont ainsi des briques de base incontournables de la sécurité de nombreux systèmes. Récemment, de nombreuses avancées ont été publiées dans le domaine de la cryptographie à clef publique, que ce soit dans la compréhension des modèles de sécurité en jeu, ou dans les preuves mathématiques de sécurité appliquées à des systèmes bien précis. Malheureusement, le monde de la cryptographie symétrique reste clairement en retrait, bien que la situation évolue lentement. Les algorithmes de chiffrement par blocs, ou par flot, tendent ainsi à compenser leur manque de "sécurité prouvée" par d'autres atouts, tels qu'un débit de chiffrement élevé et une certaine facilité d'implantation. Dans la première moitié de cette thèse, nous tentons d'ajouter une (modeste) brique à l'édifice de la sécurité prouvée des algorithmes de chiffrement par blocs en analysant (théoriquement et expérimentalement) les mécanismes statistiques sous-jacents à la cryptanalyse linéaire de Matsui ainsi qu'à des modèles d'attaques plus abstraits. Pour atteindre ce but, nous interprétons le problème comme un test d'hypothèses statistiques en utilisant notamment le paradigme de Neyman-Pearson. Nous généralisons ensuite le concept de distingueur linéaire et nous en discutons la puissance. Nous introduisons également le concept de distingueur séquentiel, basé sur l'échantillonage séquentiel, ainsi que celui de distingueur à aggrégats, qui permet de construire des distingueurs certes sub-optimaux, mais néanmoins efficaces. Finalement, nous proposons une série de nouvelles attaques contre des versions réduites de l'algorithme IDEA. Dans la seconde moitié, nous proposons une nouvelle famille d'algorithmes de chiffrement par blocs, baptisée FOX. Pour cela, nous étudions sur des architectures à bas coût l'efficacité de composants de diffusion optimaux, et nous proposons plusieurs nouvelles constructions de matrices MDS. Enfin, nous décrivons précisément FOX, nous étudions sa sécurité vis-à-vis des attaques linéaires, différentielles, intégrales et algébriques, et nous discutons finalement les aspects liés à son implantation.