Les représentations équivalentes d'un LFSR et leur impact en cryptanalyse

National audienceLe LFSR filtré est un modèle de chiffrement à flot à coût réduit, qui est encore actuellement très utilisé dans des systèmes réels soit tout seul soit comme partie d'un générateur plus complexe. De nombreuses attaques existent déjà sur ce type de systèmes comme les attaques par corrélation ou les attaques algébriques. Rønjom et Cid ont constaté que, dans certains cas, les représentations équivalentes des LFSR filtrés obtenues par un changement de racine primitive pouvaient aboutir à un nouveau type de cryptanalyse. Ils ont aussi décrit une attaque qui s'applique quand la fonction de filtrage est une composante d'une fonction monôme x → Tr(λx r) sur le corps fini F 2 n où n est la longueur du LFSR. Beaucoup de questions se posent en conséquence de cet article : la possibilité de généraliser cette attaque à d'autres fonctions de filtrage et la recherche d'autres attaques exploitant ces représentations équivalentes. L'utilisation des représentations équivalentes m'a permis de mettre en évidence trois nouveaux types de faiblesses potentielles pour les LFSR filtrés et ainsi de donner de nouveaux critères à prendre en compte pour ce type de système