NLFSR : Nonlinear Feedback Shift Register
Aléa
NLFSR : Nonlinear Feedback Shift Register, registre à décalage à rétroaction non linéaire. « Le LFSR auquel on a enfin appris à mentir », par analogie avec un témoin dont les réponses ne se déduisent plus des précédentes par une simple règle de trois.
Principe : Le bit réinjecté n'est plus un simple XOR de cases du registre mais une fonction booléenne non linéaire de celles-ci, contenant par exemple des produits (ET logiques) entre bits. L'algorithme de Berlekamp-Massey, qui démonte un LFSR à partir de 2L bits de sortie, ne s'applique plus directement.
Contrepartie : La théorie qui garantit la période maximale d'un LFSR n'a pas d'équivalent général : un NLFSR peut tomber dans des cycles courts selon son état initial. Les conceptions sérieuses l'associent donc à un LFSR qui assure la période, pendant que le NLFSR apporte la non-linéarité.
Exemples : Grain, retenu en 2008 dans le portefeuille matériel du projet européen eSTREAM, et sa variante Grain-128a couplent un LFSR et un NLFSR. Trivium, du même portefeuille, repose sur trois registres à mise à jour non linéaire. KeeLoq, chiffrement par bloc de télécommandes de portails et de voitures, est construit sur un NLFSR de 32 bits ; des attaques algébriques et par canaux auxiliaires publiées à partir de 2007 l'ont cassé, preuve qu'une rétroaction non linéaire ne dispense pas d'une conception analysée.
Usage actuel : Ces registres vivent surtout dans le chiffrement léger pour circuits contraints : étiquettes, capteurs, cartes. Grain-128AEAD figurait parmi les finalistes de la compétition du NIST (National Institute of Standards and Technology) sur la cryptographie légère, remportée par Ascon en 2023.
Ce qui arrive si on s'en passe
Remplacer un LFSR par un NLFSR maison ne suffit pas à fabriquer un chiffrement : une fonction de rétroaction mal choisie laisse des cycles courts, des corrélations exploitables ou des équations que les attaques algébriques résolvent sans peine. KeeLoq, qui protégeait des millions de télécommandes, a montré qu'une construction propriétaire non analysée publiquement finit analysée quand même, par d'autres et à leur profit. Il faut s'en tenir aux conceptions publiées et étudiées, comme Grain, ou à des algorithmes légers normalisés comme Ascon.
Explication de la marmotte
Un NLFSR est un cousin du LFSR, cette petite machine qui fabrique des suites de 0 et de 1. La différence, c'est que la règle qui calcule le bit suivant est plus compliquée et ne se devine pas avec une simple formule. La suite devient ainsi beaucoup plus difficile à prédire. On s'en sert dans des chiffrements conçus pour de tout petits appareils, comme des capteurs ou des étiquettes électroniques, à condition d'utiliser des modèles étudiés publiquement par des spécialistes.