PICSI

Il est évident qu'un registre à décalage à rétroaction linéaire seul produit une suite aux piètres propriétés cryptographiques. En effet, la connaissance du polynôme de rétroaction permet de deviner, à partir de L bits consécutifs de la suite produite, tous les bits suivants, où L est la longueur du registre utilisé (ou plus précisément sa complexité linéaire). Même lorsque le polynôme de rétroaction est secret (ce qui est relativement rare car il est généralement câblé dans les implémentations matérielles), l'algorithme de Berlekamp-Massey permet de déterminer la suite à partir de la connaissance de 2L bits consécutifs. Pour engendrer une suite pseudo-aléatoire au moyen de LFSRs de taille raisonnable et bénéficier de leur simplicité d'implémentation, il est donc indispensable d'introduire une composante non-linéaire dans le système. Ceci peut être fait au moyen de deux constructions classiques : la construction par combinaison de LFSRs et la construction dite du LFSR filtré. On suppose bien entendu dans toute la suite que les LFSRs utilisés dans ces constructions sont définis par des polynômes de rétroaction primitifs.

Combinaison de LFSRs

Principe.   Un générateur par combinaison de LFSRs est composé de n LFSRs qui fonctionnent en parallèle, et dont les sorties sont combinées au moyen d'une fonction booléenne à n variables. C'est la sortie de cette fonction f à l'instant t qui fournit le bit correspondant de suite chiffrante :

st = f(xt1, xt2, …, xtn) .

Figure 1:  Générateur pseudo-aléatoire par combinaison de LFSR
Par exemple, le générateur proposé par Geffe en 1973 [1] (cf. Figure 2) est composé de trois LFSRs de longueurs distinctes combinés par la fonction

f(x1,x2,x3) = x1x2 + x2x3 + x3 .

Figure 2:  Générateur de Geffe
Les systèmes par combinaison de registres visent généralement les implémentations matérielles dans lesquelles les différents LFSRs peuvent évoluer en parallèle. Ils sont évidemment peu adaptés aux implémentations logicielles dans la mesure où les registres y sont mis à jour l'un après l'autre. Dans un contexte logiciel, on leur préférera donc souvent un LFSR filtré d'état interne de grande taille. En effet, le fait de diviser l'état interne en plusieurs parties mises à jour indépendamment ne présente aucun avantage en terme d'implémentation, et est souvent à l'origine de failles de sécurité, notamment d'attaques de type diviser pour mieux régner comme les attaques par corrélation. Propriétés statistiques.   La suite chiffrante s obtenue en sortie d'un générateur par combinaison de LFSRs est également une suite récurrente linéaire. Sa période et sa complexité linéaire dépendent à la fois des LFSRs utilisés et de la forme algébrique normale, c'est-à-dire de l'écriture polynômiale, de la fonction de combinaison. En effet, si l'on considère deux suites u et v de complexité linéaire Λ(u) et Λ(v), c'est-à-dire produites par des LFSRs de longueur Λ( u) et Λ(v), on a :

• la suite u+v = (u_t+v_t)_{t ≥ 0} est une suite récurrente linéaire, dont la complexité linéaire satisfait
  

  Λ(u+v) ≤ Λ(u) + Λ(v) ,

  avec égalité si et seulement si les polynômes minimaux de u et de v sont premiers entre eux. De plus, en cas d'égalité, la période de u+v est le PPCM des périodes de u et de v.
• la suite uv = (u_tv_t)_{t ≥ 0} est une suite récurrente linéaire, dont la complexité linéaire satisfait
  

  Λ(uv) ≤ Λ(u) Λ(v) ,

  avec égalité dès que les polynômes minimaux de u et de v sont primitifs et que Λ(u) ≠ Λ( v) et sont tous deux supérieurs ou égaux à 2. Il existe d'autres conditions suffisantes d'égalité, moins restrictives que la précédente (cf. par exemple [3,7,2].

Ainsi, la suite chiffrante s qui résulte de la combinaison par f de n LFSRs binaires dont les polynômes de rétroaction sont primitifs vérifie la propriété suivante [7] : si les longueurs des LFSRs L₁,…, L_n sont toutes distinctes et supérieures à 2 (et que l'état initial de chacun des LFSRs est non nul), alors la complexité linéaire de s est égale à

Λ(s) = f(L1, L2, …, Ln)

où le polynôme représentant f est ici évalué sur les entiers. Par exemple, le générateur de Geffe décrit à la Figure 2, composé de trois LFSRs de longueurs L₁, L₂ et L₃, engendre une suite de complexité linéaire

Λ(s) = L1L2 + L2L3 + L3 .

Sécurité.   La sécurité d'un générateur par combinaison de LFSRs dépend fortement de la forme de la fonction f utilisée pour assembler les différents registres. Cette fonction doit en particulier posséder un certain nombre de propriétés cryptographiques, notamment être équilibrée, et avoir un degré, un ordre de non-corrélation et une non-linéarité élevés (voir la fiche La sécurité des générateurs par combinaison de LFSRs pour plus de détails). Toutefois, une analyse précise de la complexité de différentes attaques publiées récemment montre qu'il semble difficile à l'heure actuelle de concevoir un générateur par combinaison de LFSRs qui offre une sécurité suffisante. Il paraît notamment nécessaire d'ajouter à cette construction d'autres composantes, par exemple, de la mémoire dans la fonction de combinaison, comme dans E0 ou un mécanisme de contrôle irrégulier de l'horloge comme dans A5/1.

LFSR filtré

Principe.   Un LFSR filtré est composé d'un unique LFSR dont l'état interne est filtré au moyen d'une fonction non-linéaire f. Ainsi, si on note (u_t)_{t ≥ 0} la suite engendrée par le LFSR, la suite chiffrante s produite par le LFSR filtré à l'instant t est définie par

st = f(ut+γ1, ut+γ2, …, ut + γn)

où le nombre de variables d'entrées de f, n, est inférieur ou égal à la longueur du LFSR et (γ_i)_{1 ≤ i ≤ n} est une suite décroissante d'entiers positifs qui définit les positions des bits de l'état interne pris en entrée de la fonction de filtrage.

 

Figure 3:  Générateur pseudo-aléatoire par LFSR filtré
Propriétés statistiques.   La suite chiffrante s obtenue en sortie d'un LFSR filtré est également une suite récurrente linéaire. Sa période et sa complexité linéaire sont liées à la longueur du LFSR utilisé et au degré de la fonction de filtrage f. Pour un LFSR binaire de longueur L et dont le polynôme de rétroaction est primitif, la complexité linéaire de s satisfait [4,5]

Λ(s) ≤ deg(f) ∑ i=0  binomial(L,i) ,

et la période de s est un diviseur de 2^L−1. De plus, si L est un nombre premier de grande taille, on a

Λ(s) ≥ binomial(L,deg(f))

pour la plupart des fonctions de filtrage f [6]. Tout LFSR filtré est équivalent à une combinaison de LFSRs. En effet, si l'on considère la combinaison par la fonction f de n copies du LFSR utilisé dans le générateur filtré, mais dont les états initiaux sont décalés de γ_i positions vers la droite, on voit que la sortie de ce générateur par combinaison est identique à la sortie du registre filtré.
Sécurité.   De manière générale, la sécurité d'un générateur par LFSR filtré dépend fortement du polynôme de rétroaction du registre et du choix de la fonction de filtrage f. Ils devront nécessairement respecter un certain nombre de critères, sinon le générateur sera vulnérable à certaines attaques bien connues. En particulier, la fonction f doit être équilibrée, avoir un degré, une non-linéarité et une immunité algébrique élevés et un ordre d'immunité aux corrélation au moins égal à 1. Par ailleurs, le polynôme de rétroaction du LFSR doit être relativement dense et ne doit pas posséder de multiples creux de degré faible. Enfin, les positions d'entrées de la fonction de filtrage, (γ_i)_{1 ≤ i ≤ n}, doivent être choisies de telle sorte que tous les écarts |γ_i − γ_j| soient premiers entre eux, ou si cela n'est pas possible, il est indispensable de minimiser le nombre d'écarts |γ_i − γ_j| ayant un diviseur commun (voir la fiche La sécurité des LFSRs filtrés pour plus de détails).

 

Références

[1]

P.R. Geffe. << How to protect data with ciphers that are really hard to break >>. Electronics, 99-101, 1973.

[2]

R.  Göttfert, H.  Niederreiter. << On the minimal polynomial of the product of linear recurring sequences >>. Finite Fields and Their Applications, 1(2):204-218, 1995.

[3]

T.  Herlestam. << On functions of linear shift register sequences >>. F.  Pichler, , Advances in Cryptology - EUROCRYPT '85, 219 Lecture Notes in Computer Science, 119-129. Springer-Verlag, 1986.

[4]

E.L. Key. << An analysis of the structure and complexity of nonlinear binary sequence generators >>. IEEE Transactions on Information Theory, 22:732-736, 1976.

[5]

J.L. Massey. << The ubiquity of Reed-Muller Codes >>. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - AAECC-14, 2227 Lecture Notes in Computer Science, 1-12. Springer-Verlag, 2001.

[6]

R.A. Rueppel. Analysis and Design of stream ciphers. Springer-Verlag, 1986.

[7]

R.A. Rueppel, O.J. Staffelbach. << Products of Linear Recurring Sequences with Maximum Complexity >>. IEEE Transactions on Information Theory, 33(1):124-131, 1987.