Codes de Reed-Muller et cryptanalyse du registre filtré.
Résumé
This thesis deals with the cryptanalysis of a simple but important stream cipher: the filter generator. A first approach to break such cipher is to use algebraic attacks. For these attacks, it is important to compute efficiently the algebraic immunity of the Boolean function used as a filter. This quantity is closely related to the behavior of Reed-Muller codes over the erasure channel. Using this relation, we discovered new results that are best stated in the error correcting codes framework. We thus build a new bound on the probability to be able to correct a fixed number of erasures. This bound implies that the algebraic immunity of a random function is optimal or close from it. We also detail a new decoding method based on sparse linear algebra algorithm like Wiedemann's one. It leads to one of the most efficient algorithm to compute the algebraic immunity of a given function. A second approach is to use probabilistic attacks. For most of them, we need to compute small weight multiples of the LFSR. We propose a new algorithm that use discrete logarithm and is particularly efficient for multiples of weight 4. We then describe a new attack that use these multiples to detect the time positions for which the inputs of the filter are all zero. At the time being, this attack is one of the most efficient.
Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.