Codes de Reed-Muller et cryptanalyse du registre filtré
Frédéric Didier
frederic.didier@gmail.com
Ph.D. Thesis, Ecole Polytechnique,
28 Novembre 2007.
Résumé
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.
Reed-Muller codes and cryptanalysis of filtered registers.
Abstract
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.