Les algorithmes cryptographiques actuels se répartissent en deux grandes familles : les algorithmes symétriques et les algorithmes asymétriques. En 1991, S. Even et Y. Mansour ont proposé une construction simple d'un algorithme de chiffrement par blocs en utilisant une permutation aléatoire. Récemment, surtout pour répondre aux nouveaux enjeux de la cryptographie à bas coût, plusieurs algorithmes ont été proposés dont la construction est basée sur le schéma Even-Mansour. Les travaux réalisés dans cette thèse ont pour objet l'analyse de ce type d'algorithmes. À cette fin, nous proposons une nouvelle attaque générique sur le schéma Even-Mansour. Ensuite, afin de montrer l'importance particulière du modèle multi-utilisateurs, nous appliquons cette attaque générique dans ce modèle. Ces deux attaques sur Even-Mansour introduisent deux nouvelles idées algorithmiques : les chaînes parallèles et la construction d'un graphe qui illustre les liens entre les clés des utilisateurs du modèle multi-utilisateurs. Finalement, basés sur ces idées, nous proposons des attaques sur les algorithmes de chiffrement par blocs DESX et PRINCE et sur le code d'authentification de message Chaskey. / Current cryptographic algorithms are divided into two families: secret-key algorithms (or symmetric algorithms) and public-key algorithms. Secret-key cryptography is characterized by the sharing of the same key K used by both legitimate users of the cryptosystem. Bloc ciphers are one of the main primitives of symmetric cryptography. In 1991, S. Even and Y. Mansour proposed a minimal construction of a bloc cipher which uses a random permutation. Recently, in the context of lightweight cryptography, many algorithms based on the Even-Mansour scheme have been proposed. In this thesis, we focus on the analysis of this type of algorithms. To this purpose, we propose a generic attack on the Even-Mansour scheme. To show the particular importance of the multi-user model, we adapt our attack to this context. With these attacks, we introduce two new algorithmic ideas: the parallel chains and the construction of graph which represents the relations between the keys of the users of the multi-user model. Finally, we use these ideas and we present attacks on the bloc ciphers DESX and PRINCE and on the message authentication code (MAC) Chaskey.

Dans cette thèse, on s'intéresse à des schémas de chiffrement par blocs, c'est-à-dire que le chiffrement (et le déchiffrement) envoie un bloc de n bits sur un bloc de n bits. Il y a essentiellement deux grandes structures utilisées pour un schéma de chiffrement par blocs : la structure de Feistel (utilisée pour le DES) et la structure SPN (utilisée pour l'AES). L'étude de la sécurité de ces différents structures et schémas a permis de nombreuses avancées autant pratiques que théoriques. Nous présentons dans cette thèse des preuves de sécurité pour le schéma d'Even-Mansour itéré, le schéma paramétrable CLRW et le schéma de Feistel à clés alternées. Ces preuves utilisent une technique probabiliste, appelée coupling, introduite en cryptographie en 2002 par Mironov. Nous présentons cette technique dans le cadre des probabilités, puis la façon d'utiliser le coupling pour prouver la sécurité des schémas cités précédemment. Nous présentons également une étude de la sécurité du schéma d'Even-Mansour à deux tours pour certaines minimisations (même clés de tours ou même permutations internes par exemple) et, pour conclure, une comparaison des différentes techniques d'indistinguabilité / In this thesis, we study blockciphers, meaning that the encryption (and decryption) sends a block of n bits on a block of n bits. There is essentially two main structures used for a blockcipher: the Feistel structure (used for DES) and the SPN structure (used for AES). The study of the security of these structures and schemes has led to many practical and theoretical advances. We present in this thesis proofs of security for the iterated Even-Mansour scheme, the tweakable blockcipher CLRW and the key-alternating Feistel cipher. These proofs use a probabilistic technique, called coupling, introduced in cryptography in 2002 by Mironov. We present this technique in the context of probabilities, then we present how to use the coupling to prove the security for the schemes mentioned above. We also present an analysis of the security of the Even-Mansour cipher with two rounds and some properties (same round keys or same internal permutations for example) and, finally, we compare the different techniques to prove indistinguishability

Les algorithmes de chiffrement par blocs paramétrables constituent une généralisation des algorithmes de chiffrement par blocs classiques qui, en plus d'une clé et d'un message à chiffrer ou déchiffrer, admettent un paramètre additionnel, nommé tweak en anglais. Le rôle de ce paramètre additionnel est d'apporter une variabilité à l'algorithme de chiffrement, sans qu'il soit nécessaire de changer la clé ou de garder le tweak secret. Ce dernier doit également pouvoir être contrôlé par l'adversaire sans dégradation de la sécurité. Dans cette thèse nous nous intéressons à une classe particulière d'algorithmes de chiffrement par blocs, les algorithmes de chiffrement par blocs à clé alternée. Plusprécisément, nous étudions la sécurité du schéma d'Even-Mansour, qui constitue une abstraction de la structure de ces algorithmes dans le modèle de la permutation aléatoire, et cherchons à rendre ce schéma paramétrable tout en conservant de fortes garanties de sécurité. À cette fin, nous introduisons une nouvelle construction générique, baptiséeTEM, qui remplace les clés de tours de la construction d'Even-Mansour par une valeur qui dépend de la clé et du tweak, et en étudions la sécurité dans deux cas : lorsque le mixage de la clé et du tweak est linéaire ou lorsqu'il est très non-linéaire. Nos preuves de sécurité utilisent la technique des coefficients H, introduite par Jacques Patarin danssa thèse de doctorat, qui permet de transformer des problèmes cryptographiques en problèmes combinatoires sur des groupes finis. / Tweakable block ciphers are a generalization of classical block ciphers which, in addition to a key and a plaintext or a ciphertext, take an additionnal parameter called a tweak. The goal of this new parameter is to bring variability to the block cipher without needing to change the key or to keep the tweak secret. The tweak should also be adversariallycontrollable without sacrificing security. In this thesis we study a particular class of block ciphers, namely key-alternating ciphers. More precisely, we study the security of the Even-Mansour scheme, which is an abstraction of these ciphers in the random permutation model, and seek to bring tweakability to this scheme while keeping strong security guarantees. To this end, we introduce a new generic construction, dubbed TEM, which replaces the round keys from the Even-Mansour construction by a value depending on both the key and the tweak, and study its security in two cases: when the tweak and key mixing is linear or highly non-linear. Our security proofs rely on the H-coefficients technique, a technique introduced by Jacques Patarin in his PhD thesis which transforms cryptographic problems into combinatorial problems in finite groups.