Symmetric cryptanalysis ˸ from primitives to modes

Cryptanalyse symétrique ˸ des primitives aux modes Ce manuscrit présente des contributions à l'analyse de la sécurité des cryptosystèmes symétriques, ou cryptanalyse symétrique. La cryptographie fonde sa sécurité sur des primitives cryptographiques, qui peuvent être vues comme des briques permettant de construire des algorithmes plus complets grâce à leur utilisation au sein de modes. Alors que la sécurité des modes peut souvent être prouvée sous l'hypothèse que la primitive sous-jacente est sûre, la communauté cryptographique ne peut s'appuyer aujourd'hui que sur la cryptanalyse pour garantir la sécurité des primitives. En outre, les preuves de sécurité des modes ne fournissent qu'une information partielle sur leur niveau de sécurité, à savoir une borne inférieure. Les attaques définissent au contraire des bornes supérieures et sont donc complémentaires de la sécurité prouvée. Cette thèse propose à la fois des contributions à la cryptanalyse des primitives (partie I) et des modes (partie II).La partie I présente des contributions à la cryptanalyse d'une variété de primitives basées sur diverses techniques de cryptanalyse. Le chapitre 1 introduit les principales primitives symétriques et familles de cryptanalyse. Le chapitre 2 est consacré à l'une des techniques de cryptanalyse les plus largement utilisées, la cryptanalyse différentielle. Nous y proposons d'abord une analyse détaillée de l'algorithme SPEEDY. Nous introduisons ensuite un algorithme (et un outil associé) permettant d'effectuer automatiquement l'étape de recouvrement de clé des attaques différentielles. Cet outil est appliqué à RECTANGLE, GIFT, PRESENT et SPEEDY. Il permet notamment d'améliorer la meilleure attaque connue contre RECTANGLE-128. Le chapitre 3 décrit une cryptanalyse complète d'un chiffrement à flot dédié au FHE, Elisabeth-4. Notre attaque repose sur une technique classique de cryptanalyse appelée linéarisation que nous améliorons en exploitant à la fois un phénomène de défaut de rang et le caractère creux des systèmes linéaires considérés. Ces améliorations sont rendues possibles par une analyse détaillée des composants mathématiques innovants dédiés au FHE utilisés dans Elisabeth-4. Enfin, le chapitre 4 présente plusieurs attaques de recherche de collision sur des versions réduites d'instances de la fonction de hachage Keccak possédant un petit état. Cette cryptanalyse exploite une analyse algébrique de la permutation Keccak-p.La partie II est consacrée à la cryptanalyse de constructions symétriques basées sur l'itération d'une primitive publique. Puisque les preuves postulent un comportement cryptographique idéal de la primitive, il est intéressant d'analyser la sécurité des modes sous cette hypothèse. Les attaques dans ce modèle sont appelées attaques génériques. Une proportion significative de la partie II analyse la résistance de plusieurs modes à de telles attaques en utilisant un nouvel outil de cryptanalyse, les fonctions aléatoires dites exceptionnelles. Cette deuxième partie est organisée de la manière suivante. Le chapitre 5 introduit plusieurs modes construits en itérant une primitive publique et présente un état de l'art des résultats importants sur les statistiques des fonctions aléatoires ainsi que des principaux outils algorithmiques utilisés en cryptanalyse générique. Le chapitre 6 est dédié aux premières attaques génériques utilisant des fonctions aléatoires contre les modes AEAD dits `duplex'. Plus en détail, nous proposons deux attaques. La première introduit l'utilisation de fonctions exceptionnelles dans le contexte de la cryptanalyse générique. La seconde améliore la première en utilisant une nouvelle technique appelée fonctions exceptionnelles imbriquées. Dans le chapitre 7, nous améliorons une longue série d'attaques génériques contre une classe de constructions appelée `hash combiners' en utilisant des fonctions exceptionnelles (parfois imbriquées). Enfin, le chapitre 8 présente la cryptanalyse complète d'un schéma de chiffrement authentifié entièrement spécifié.