Quelques algorithmes de cryptanalyse du registre filtré
Résumé
Les systèmes de chiffrement à flot (stream ciphers) sont couramment utilisés puisqu'ils permettent un chiffrement rapide des données tout en consommant peu d'énergie. Leur principe de fonctionnement est relativement simple: un générateur de pseudo-aléa produit une séquence binaire qui est X-orée au message clair, engendrant ainsi le message chiffré (cryptogramme). Le destinataire, muni d'un générateur identique, déchiffre le message reçu en lui appliquant la même opération. La sécurité de ce système repose entièrement sur la difficulté de produire la séquence pseudo-aléatoire: toute personne en mesure de la générer pourra en effet déchiffrer le cryptogramme qu'elle aura intercepté. L'objet de cette thèse était de proposer de nouvelles attaques sur de tels systèmes. Plus précisément, nous nous sommes intéressés à la cryptanalyse à clair connu des registres filtrés: le générateur de pseudo-aléa est, dans ce cas, constitué d'un unique registre à décalage linéaire (LFSR) filtré par une fonction booléenne. La structure de ces deux composantes est supposée entièrement connue du cryptanalyste, lequel dispose, par ailleurs, de quelques bits de la séquence pseudo-aléatoire. Seule l'initialisation du registre à décalage est secrète et conditionne entièrement la sortie du générateur: elle constitue donc la clé secrète du système de chiffrement et notre objet sera précisément de la déterminer. Le document sera organisé de la façon suivante: dans un premier chapitre, nous décrivons la structure du système de chiffrement qu'est le registre filtré, et nous intéressons aux théories auxquelles ses différentes constituantes renvoient naturellement. Nous proposons, dans un second chapitre, un état de l'art des attaques non-algébriques du registre filtré. Suit un chapitre qui présente les fondements du décodage itératif et quelques résultats de simulation permettant d'évaluer l'impact de différents paramètres du système, celui du canal booléen notamment. Nous décrivons ensuite une nouvelle attaque dont le principe s'inspire de celui du décodage itératif, qui utilise non plus des contraintes linéaires mais celles de la fonction booléenne. Le quatrième chapitre est dédié aux attaques par treillis: nous présentons en premier lieu une attaque déterministe, qui, lorsque les conditions d'application sont réunies, permet de cryptanalyser le registre filtré très efficacement, et sans aucune probabilité d'erreur. Les conditions d'application de cet algorithme étant assez restrictives, nous avons étendu son principe à des systèmes moins spécifiques, perdant de ce fait le caractère déterministe de l'attaque originelle. Enfin, dans un dernier chapitre, nous avons développé deux algorithmes: le "SOJA" et le "Probability-Matching". Tous deux exploitent conjointement la structure de la fonction booléenne et l'existence d'équations vectorielles, le SOJA afin de générer des probabilités a posteriori sur les bits de la séquence d'entrée, le Probability-Matching afin d'identifier des vecteurs d'entrée de la fonction présentant des propriétés remarquables.
Domaines
Loading...