PICSI

La sécurité des LFSRs filtrés

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=(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 constituant les entrées de f.

Figure 1: Générateur pseudo-aléatoire par LFSR filtré
Pour évaluer la sécurité d'un LFSR filtré, on se place usuellement dans le contexte où les spécifications du système, c'est-à-dire le polynôme de rétroaction du registre, la fonction de filtrage et les entiers (γ_i)_{1 ≤ i ≤ n} sont connus. Toutefois, même quand ces paramètres sont secrets, il est possible de reconstruire les spécifications d'un générateur par combinaison de LFSRs équivalent au LFSR filtré considéré [11]. 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 plusieurs critères cryptographiques, sinon le générateur sera vulnérable aux attaques suivantes.
Attaque par compromis temps-mémoire.   Dès lors que toutes les spécifications du système sont publiques, on peut tenter de retrouver un état interne complet du générateur par une attaque par compromis temps-mémoire (voir la fiche Attaques par compromis temps-mémoire pour plus de détails). Cette attaque impose notamment que la longueur du LFSR utilisé soit au moins le double de celle de la clef secrète.
Attaque statistique par biais sur la sortie.   La fonction de filtrage f doit être équilibrée, c'est-à-dire produire les valeurs 0 et 1 avec la même probabilité. Sinon, la suite chiffrante serait biaisée, et pourrait donc être distinguée d'une suite aléatoire avec une complexité de l'ordre de

1 |PrX[f(X)=1] − 1 2 |2 .

Attaque par l'algorithme de Berlekamp-Massey.   La suite s obtenue en sortie du générateur peut être, elle aussi, engendrée par un unique LFSR de longueur Λ(s), où Λ(s) vérifie en général [10]

Λ(s) ≥ \binomLdeg(f) .

Par conséquent, la fonction de filtrage f doit être de degré élevé. Plus précisément, la longueur du registre et le degré de f doivent toujours être suffisamment grands pour que le nombre de bits de suite chiffrante accessibles à un attaquant soit toujours beaucoup plus petit que \binomLdeg(f). Par ailleurs, si le degré de la fonction de filtrage est faible, le générateur pseudo-aléatoire est également vulnérable aux attaques algébriques.
Attaques algébriques.   La fonction f doit posséder une forte immunité algébrique afin que le système résiste aux attaques algébriques (voir la fiche Attaques algébriques pour plus de détails). En particulier, pour un registre est de longueur 2k où k est le nombre de bits de la clef secrète, il faut que

AI(f) ≥ 0.42   k 1+ log2 k    .

Comme l'immunité algébrique d'une fonction à n variables est toujours inférieure ou égale à [(n+1)/2], la condition précédente impose que le nombre n de variables d'entrées de la fonction de filtrage f doit vérifier

n ≥ 0.84   k 1+ log2 k   .

Il est indispensable de prendre une marge de sécurité importante par rapport aux deux bornes précédentes, à la fois pour prendre en compte des algorithmes de résolution de systèmes algébriques plus rapides que la linéarisation et pour se prémunir des attaques algébriques rapides. Il est donc généralement conseiller d'utiliser une fonction de filtrage d'immunité algébrique supérieure ou égale à 8. Il est également indispensable de vérifier qu'il n'existe pas de multiples de f dont le degré est légèrement supérieur à l'immunité algébrique, mais qui correspondent à des relations de la forme fg=h pour lesquelles le degré de g est strictement inférieur à l'immunité algébrique de f. En effet, l'existence de relations de ce type peut conduire à un système d'équations de degré égal à celui de g. Cette situation apparaît par exemple dans le cas du générateur par LFSR filtré Sfinks, qui est vulnérable à une attaque algébrique rapide [4].
Attaques par corrélation rapides.   La fonction de filtrage doit être de non-linéarité élevée, ce qui signifie qu'elle doit être éloignée des fonctions de degré 1. La non-linéarité est donnée par

NL(f) = min ϕ, deg(ϕ)=1  |{(x1, …, xn) ,    f(x1, …, xn) ≠ ϕ(x1, …, xn)}| .

Sinon, il existe une fonction ϕ de degré 1 qui fournit une approximation de f avec une bonne précision, ce qui signifie que la suite chiffrante s est très proche de la suite σ définie par

σt = ϕ(ut+γ1, ut+γ2, …, ut + γn)

qui correspond en fait à la suite produite par le LFSR à partir l'état initial

ui = ϕ(ui+γ1, ui+γ2, …, ui + γn),       0 ≤ i < L .

Cette propriété est notamment utilisée pour retrouver entièrement la suite approchée σ (ou éventuellement l'état initial de chacun des registres du générateur) dans les attaques par corrélation rapides [8]. Par ailleurs, la résistance du système à ces attaques est accrue quand la fonction de filtrage ne possède qu'un petit nombre de coefficients de Fourier nuls [1,7].
Attaques par inversion.   La suite (γ_i)_{1 ≤ i ≤ n} des positions filtrées doit également être choisie avec soin afin de se prémunir contre les attaques par inversion et de ses variantes [5,6,8]. La complexité de ces attaques est généralement de l'ordre de 2^M, où le paramètre déterminant M, appelé la mémoire du registre filtré, est défini par

γ1 −γn pgcdi(γi−γi+1) .

En effet, ces attaques permettent de retrouver l'état initial du registre en effectuant une recherche exhaustive qui porte uniquement sur les bits situés entre les entrées aux deux extrémités du filtre, ce qui réduit donc l'attaque à la recherche de (γ₁ −γ_n) bits. De plus, si les écarts entre les positions filtrées, c'est-à-dire les entiers (γ_i−γ_i+1), ont un diviseur commun d, l'attaque précédente peut être appliquée à la suite obtenue en décimant la sortie du LFSR, c'est-à-dire en ne considérant qu'un bit sur d. Ceci permet alors de diviser la mémoire du registre filtré par d. En conséquence, il faut choisir pour les écarts entre les positions filtrées des entiers premiers entre eux dans leur ensemble.
Attaques statistiques par auto-corrélation.   Pour que l'on ne puisse pas distinguer la suite chiffrante produite par le LFSR filtré d'une suite aléatoire, il faut en particulier que la distance entre la suite s₀ s₁ …s_N−1 et la suite obtenue en la décalant de τ positions, c'est-à-dire s_τ s_τ+1 …s_N−1 s₀ s₁ …s_τ−1 soit de l'ordre de [N/2], où N est la période de la suite chiffrante. Autrement dit, le coefficient d'auto-corrélation

C(τ) = N−1 ∑ t=0  (−1)st + st+τ

doit être petit pour toutes les valeurs de τ qui ne sont pas multiples de N. Une condition équivalente est que la probabilité

p(τ) = Pr[st = st+τ]

doit être très proche de 0,5. Sinon, on peut effectuer une attaque par distingueur qui consiste à calculer le coefficient de corrélation en τ de s sur une longueur de suite de l'ordre de

1 | p(τ)− 1 2 |2

bits. Or, les bits s_t et s_t+τ correspondent à l'image par f des bits de la suite u (c'est-à-dire de la suite produite par le LFSR) aux positions {t+γ_i,   1 ≤ i ≤ n} et {t+γ_i+τ,   1 ≤ i ≤ n}. Ainsi, certains bits de u peuvent intervenir en entrée de f à la fois à l'instant t et à l'instant t+τ. Le nombre d'entrées communes à ces deux instants est donné par la taille I(τ) de l'ensemble formé par tous les couples (i, j) avec i < j tels que γ_i − γ_j = τ. On peut alors démontrer que la probabilité p(τ) est égale à 0,5 et, par conséquent, que l'attaque est impossible si la fonction de filtrage f est sans corrélation d'ordre supérieur ou égal à I(τ) (comme f est également équilibrée, on parle de façon équivalente de fonction I(τ)-résiliente). Comme il existe un compromis entre l'ordre d'immunité aux corrélations d'une fonction et son degré algébrique, il est indispensable de minimiser la taille de tous les ensembles

{(i, j) ,   i < j,     γi − γj = τ} .

La situation optimale correspond au cas où tous ces ensembles sont vides ou réduits à un seul élément, c'est-à-dire quand toutes les différences γ_i − γ_j, i < j sont distinctes [5]. Notons que les n positions (γ_i)_{1 ≤ i ≤ n} en entrée de f ne peuvent vérifier cette condition que si la longueur du LFSR dépasse n (n−1)/2. De plus, si cette condition d'optimalité est vérifiée, il faut également que la fonction de filtrage f soit sans corrélation d'ordre 1.
Attaques par distingueur.   Le polynôme de rétroaction du LFSR doit comporter un nombre important de monômes (usuellement de l'ordre de [L/2]) et il ne doit pas posséder de multiples qui soient à la fois creux et de degré faible. En effet, tout polynôme Q(X) = 1+X^i₁ …+X^i_d−1 multiple du polynôme de rétroaction P du LFSR définit une relation de récurrence impliquant d termes de la suite u produite par le LFSR :

ut + ut−i1 + …+ut−id−1, pour tout t ≥ id−1 .

On peut alors démontrer que la probabilité que la suite chiffrante s vérifie la même relation de récurrence

st + st−i1 + …+st−id−1, pour tout t ≥ id−1

est donnée par

pd = 1 2 + 1 2nd+1   ∑ a ∈ F2n  ^ f   d   (a)  

où [^f](a) est le coefficient de Walsh de la fonction f en a. Ainsi, à partir de tout multiple de P composé de d termes et de degré D, il est possible de distinguer la suite chiffrante d'une suite aléatoire si l'on en connaît environ

D + 22nd+2 ∑ a ∈ F2n  ^ f   2d   (a)

bits consécutifs. On peut donner des bornes générales sur la complexité de ce type de cryptanalyse [9]. Par exemple, l'existence d'un polynôme à 4 termes de degré D multiple de P permet de monter une attaque par distingueur nécessitant la connaissance d'au plus

D+ 22n+2

bits de suite chiffrante et de l'ordre de 2²ⁿ⁺⁴ opérations. Si P est un polynôme primitif aléatoire de degré L, le degré minimal d'un multiple de poids d est de l'ordre de [2]

Dd = ((d−1)!)[1/d−1] 2[L/d−1] ,

et la complexité de l'algorithme de précalcul [2,3] utilisé pour trouver ce multiple est d'environ

2[L/2] .

Ainsi, pour d=4, le nombre de bits de suite chiffrante requis pour l'attaque est de l'ordre

2[L/3]+ 22n+2

ce qui rend l'attaque impossible dès que le LFSR utilisé est suffisamment long et que le polynôme de rétroaction P ne possède pas de multiples à 4 termes de degré faible. Plus généralement, cette attaque impose que le polynôme de rétroaction du LFSR ne doit pas avoir de multiples creux, et en particulier qu'il ne dit pas être lui-même creux. On conseille donc d'utiliser un polynôme primitif aléatoire. Il faut aussi que le nombre de variables n de la fonction de filtrage ne soit pas trop faible. Enfin, il est aussi indispensable de vérifier que les valeurs des coefficients de Walsh de la fonction de filtrage garantissent que cette attaque possède une complexité supérieure à celle de la recherche exhaustive de la clef secrète.

 

Références

[1]

A.  Canteaut, E.  Filiol. << On the influence of the filtering function on the performance of fast correlation attacks on filter generators >>. IEEE Symposium on information theory in the Benelux, 2002.

[2]

A.  Canteaut, M.  Trabbia. << Improved fast correlation attacks using parity-check equations of weight 4 and 5 >>. Advances in Cryptology - EUROCRYPT 2000, 1807 Lecture Notes in Computer Science, 573-588. Springer-Verlag, 2000.

[3]

P.  Chose, A.  Joux, M.  Mitton. << Fast correlation attacks: an algorithmic point of view >>. Advances in Cryptology - EUROCRYPT 2002, 2332 Lecture Notes in Computer Science, 209-221. Springer-Verlag, 2002.

[4]

N.T. Courtois. << Algebraic Attacks on Combiners with Memory and Several Outputs >>. ICISC 2004, Lecture Notes in Computer Science. Springer-Verlag, 2005. http://eprint.iacr.org/2003/125/.

[5]

J.Dj. Golic. << On the security of nonlinear filter generators >>. Fast Software Encryption - FSE'96, 1039 Lecture Notes in Computer Science, 173-188. Springer-Verlag, 1996.

[6]

J.Dj Golic, A.  Clark, E.  Dawson. << Generalized inversion attack on nonlinear filter generators >>. IEEE Transactions on Computers, 49(10):1100-1109, 2000.

[7]

F.  Jönsson, T.  Johansson. << A fast correlation attack on LILI-128 >>. Information Processing Letters, 81(3):127-132, 2002.

[8]

S.  Leveiller. << Quelques algorithmes de cryptanalyse du registre filtré >>. Thèse de doctorat, Ecole Nationale Supérieure des Télécommunications, Paris, 2004.

[9]

H.  Molland, T.  Helleseth. << An improved correlation attack against irregular clocked and filtered generator >>. Advances in Cryptology - CRYPTO 2004, 3152 Lecture Notes in Computer Science, 373-389. Springer-Verlag, 2004.

[10]

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

[11]

T.  Siegenthaler. << Decrypting a class of stream ciphers using ciphertext only >>. IEEE Trans. Computers, C-34(1):81-84, 1985.