LFSR : Linear Feedback Shift Register
Aléa
LFSR : Linear Feedback Shift Register, registre à décalage à rétroaction linéaire. « Un générateur de suites d'allure aléatoire qui livre son secret à quiconque prend la peine d'en lire deux fois sa longueur », par analogie avec un tour de prestidigitation impeccable au premier passage et limpide au second.
Fonctionnement : Un registre de n bits se décale d'une position à chaque coup d'horloge ; le bit entrant est le XOR de certaines cases, désignées par un polynôme de rétroaction. Avec un polynôme primitif, le registre parcourt les 2^n - 1 états non nuls avant de se répéter. L'état tout à zéro, lui, reste à zéro pour l'éternité, ce qui est une forme de stabilité.
Coût : Quelques bascules et portes XOR suffisent, d'où son succès dans le matériel : calcul des CRC, embrouilleurs des liaisons série et Ethernet, codes de Gold du GPS, générateurs de motifs de test.
Faiblesse : L'algorithme de Berlekamp-Massey retrouve le polynôme et l'état d'un LFSR de longueur L à partir de 2L bits consécutifs de sortie. La complexité linéaire d'une suite, longueur du plus petit LFSR capable de la produire, sert d'ailleurs à mesurer cette faiblesse.
En cryptographie : Utilisé seul, il ne protège rien. Les chiffrements à flot l'enrobent de non-linéarité : combinaison de plusieurs registres, filtrage, horloge irrégulière comme l'A5/1 du GSM (Global System for Mobile Communications), trois LFSR à horloge majoritaire depuis longtemps cassés, ou association à un NLFSR comme dans Grain.
Ce qui arrive si on s'en passe
Employé seul comme générateur d'aléa ou comme chiffrement, un LFSR rend tout prévisible : quelques dizaines d'octets de flux connu, un en-tête de fichier ou de protocole par exemple, suffisent pour reconstruire son état et produire toute la suite, passée et future. Les jetons, identifiants de session ou clés qui en sont tirés se devinent alors à coup sûr, alors même que les tests statistiques les déclaraient impeccables. Il faut le réserver à ce qu'il fait bien, détection d'erreurs et séquences de test, et confier l'aléa de sécurité à un générateur cryptographique.
Explication de la marmotte
Un LFSR est une petite machine électronique qui fabrique une longue suite de 0 et de 1 qui a l'air tirée au hasard. Elle est très simple et très rapide, c'est pourquoi on la trouve dans beaucoup d'appareils. Mais cette suite obéit à une règle mathématique simple : en observant un petit morceau, on peut retrouver la règle et prédire toute la suite. Elle est donc utile pour vérifier des données ou tester un circuit, mais elle ne doit jamais servir seule à protéger un secret.