Block ciphers are widely used building blocks for secure communication systems; their purpose is to ensure confidentiality of the data exchanged through such systems, while achieving high performance. In this context, a variety of aspects must be taken into account. Primarily, they must be secure. The security of a block cipher is usually assessed by testing its resistance against known attacks. However as attacks may exist that are currently unknown, generic security proofs are also tried to be obtained. On the other hand, another attack methodology is also worth considering. Contrary to the others, it aims at the implementation of the algorithm rather than the cipher itself. It is known as side-channel analysis. Finally, performance of a block cipher in terms of throughput is very important as well. More than any other cryptographic primitive, block ciphers allow a tradeoff to be made between security and performance. In this thesis, contributions are given regarding these various topics. In the first part of the thesis, we deal with two particular types of attacks, namely the square attack and key schedule cryptanalysis. We also consider security proofs in the so-called Luby-Rackoff model, which deals with adversaries having unbounded computation capabilities. More precisely, we are interested in the Misty structure, when the round functions are assumed to be involutions. The second part of the thesis is devoted to design and implementation aspects. First, we present a fault attack on substitution-permutation networks, which requires as few as two faulty ciphertexts to retrieve the key. We also study the security of DeKaRT, which is an algorithm intended to protect smart cards against probing attacks. Finally we present the design of ICEBERG, a block cipher deliberately oriented towards good performance in hardware, and give an adequate analysis of its security.

Cette thèse est dédiée à la cryptanalyse de l'AES (Advanced Encryption Standard) qui est l'un des systèmes de chiffrement par bloc les plus répandu dans le monde. Nous y présentons une nouvelle technique pour résoudre un type particulier d'équations spécialement conçu pour attaquer l'AES. Cette technique est basée sur l'algèbre linéaire ainsi que sur la technique de la " Rencontre par le Milieu " et offre pour un système donné, plusieurs algorithmes de résolution de complexités différentes mais prédictibles. Ainsi nous avons conçu un programme pour trouver l'algorithme le plus rapide. Dans un premier temps nous l'avons appliqué directement aux systèmes d'équations décrivant un nombre réduit de tours d'AES et avons trouvé de nouvelles attaques lorsque la quantité de couples clair/chiffré est très limitée, améliorant celles trouvées manuellement par d'autres chercheurs. La technique étant générale nous avons pu utiliser le programme pour étudier d'autres modèles comme celui des attaques par fautes et celui des attaques à clé choisie ainsi que d'autres primitives cryptographiques comme la fonction d'authentification Pelican-MAC et le système de chiffrement par flot LEX. Enfin nous présentons une généralisation des attaques de Demirci et Selçuk publiées à la conférence FSE2008 ainsi qu'un algorithme qui nous a permis de trouver les meilleures attaques de cette classe, avec certaines parmi les meilleures connues à ce jour. Cet algorithme repose sur l'utilisation du précédent programme afin de déterminer le nombre de valeurs prises par des sous-ensembles d'octets de clé ou des états internes ainsi que la complexité de les énumérer.

Les algorithmes de chiffrement symétriques (ou à clef secrète) sont<br />très largement répandus car ils sont les seuls à atteindre les débits<br />de chiffrement requis par la plupart des applications et à permettre<br />une mise en oeuvre sous forme d'un circuit de taille<br />raisonnable. Dans ce contexte, les travaux présentés dans ce mémoire<br />ont pour objet la conception de nouvelles attaques sur les algorithmes<br />symétriques et leur formalisation afin de mettre en évidence les<br />propriétés structurelles qui les rendent opérationnelles. Cette<br />approche conduit à de nouveaux critères de conception et à la<br />construction d'objets qui permettent de leur résister de manière<br />certaine. Cette étude s'articule notamment autour de l'idée que, pour<br />résister de manière sûre aux cryptanalyses connues et pour atteindre<br />de bonnes performances, un chiffrement symétrique doit utiliser des<br />objets aux propriétés exceptionnelles, dont la structure algébrique<br />forte ouvre paradoxalement une brèche exploitable dans une nouvelle<br />attaque. Ce principe est ici décliné pour les deux familles<br />d'algorithmes symétriques, les chiffrements à flot et les chiffrements<br />par blocs.

Les travaux de cette thèse portent sur les critères de sécurité des<br />algorithmes de chiffrement à clé secrète et ont été menés suivant deux<br />axes. Le premier concerne la sécurité des chiffrements symétriques<br />itératifs par blocs contre les attaques par distingueur sur le dernier<br />tour. Les résultats portent en particulier sur la généralisation d'une<br />attaque différentielle d'ordre supérieur menée sur l'algorithme<br />MISTY1. L'origine de cette attaque ainsi que de sa généralisation a pu<br />être expliquée grâce aux propriétés du spectre de Walsh des fonctions<br />de non-linéarité maximale utilisées. Ainsi il a été possible<br />d'élaborer une attaque générique sur tous les chiffrements de Feistel<br />à cinq tours utilisant des fonctions dont le spectre de Walsh est<br />divisible par une grande puissance de 2 car cette propriété permet<br />d'obtenir une borne supérieure sur le degré de la composition de<br />telles fonctions, nettement plus faible que la borne<br />triviale. Cette attaque suggère ainsi un nouveau critère de sécurité<br />qui porte sur la divisibilité du spectre de Walsh des fonctions de<br />tour utilisées dans les chiffrements itératifs par blocs. La deuxième<br />partie de la thèse porte sur l'étude des fonctions booléennes<br />symétriques, et en particulier sur l'existence éventuelle de<br />propriétés cryptographiques. À partir d'une propriété structurelle de<br />périodicité d'une représentation d'une fonction booléenne symétrique,<br />les propriétés de degré algébrique, d'équilibre, de résilience, de<br />critère de propagation et de non-linéarité ont été étudiées, ce qui a<br />permis d'améliorer les résultats existants. Par ailleurs, le calcul<br />explicite du spectre de Walsh des fonctions booléennes symétriques de<br />degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les<br />fonctions symétriques équilibrées de degré inférieur ou égal à 7,<br />indépendamment du nombre de variables.