PICSI

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
La sécurité d'un générateur par combinaison de LFSRs dépend fortement de la forme de la fonction utilisée pour assembler les différents registres. Les multiples propriétés que doivent vérifier les différents composants du système, en particulier la fonction f, sont dictées par les attaques suivantes. On suppose ici, conformément aux principes de Kerckhoffs, que toutes les spécifications du générateur à l'exception de l'état initial des registres, c'est-à-dire les polynômes de rétroaction et la fonction f, sont connues du cryptanalyse. Toutefois, certaines techniques proches des attaques par distingueur classiques permettent de retrouver ces paramètres à partir de la seule connaissance de la suite chiffrante dès lors que la source produisant les messages clairs est biaisée [1].
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 somme des longueurs des LFSRs utilisés soit au moins le double de la taille de la clef secrète.
Attaque statistique par biais sur la sortie.   La fonction 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). Il est donc impératif que cette complexité linéaire soit très élevée, sinon il suffirait de connaître Λ(s) bits consécutifs de la suite chiffrante pour déterminer les bits suivants. Comme on se place en général dans les conditions où

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

on voit donc aisément que la complexité linéaire de s est d'autant plus élevée que le degré de f est grand. La fonction f doit donc être de degré élevé, au sens où le polynôme à n variables qui la représente doit contenir au moins un monôme qui fait intervenir un grand nombre des n variables d'entrées. Notons qu'une fonction équilibrée à n variables est de degré au plus (n−1). Par ailleurs, si le degré de la fonction de combinaison est faible, le générateur pseudo-aléatoire est également vulnérable aux attaques algébriques.
Attaques par corrélation.   La fonction de combinaison doit posséder un ordre de non-corrélation élevé, et les longueurs des différents registres ne doivent pas être trop déséquilibrées afin que le système résiste aux attaques par corrélation [5]. Il s'agit en effet d'une condition indispensable pour empêcher l'adversaire de mener une recherche exhaustive sur les initialisations d'un petit nombre de registres indépendamment des autres. Il y a, là encore, un compromis [4] entre l'ordre de non-corrélation l d'une fonction booléenne équilibrée à n variables et son degré :

deg(f) + l ≤ n−1 .

Attaques par corrélation rapides.   La fonction de combinaison 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 d'une suite σ de faible complexité linéaire

ϕ(L1, …, Ln) ≤ L1 + …+ Ln .

Cette propriété est 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 [2].
Attaques par distingueur.   Il est également possible d'exploiter les corrélations entre la sortie de la fonction de combinaison et un sous-ensemble de ses entrées pour monter une attaque par distingueur. Ainsi, si la sortie de f est corrélée avec ses l premières entrées, chaque bit s_t de la suite chiffrante est égal à σ_t = x_t¹ + …+ x_t^l avec une probabilité p = [1/2] − ε avec ε ≠ 0 ; plus précisément, la valeur du biais est donnée par

ε = 1 2n+1 ^ f   (el)

où [^f](x) est le coefficient de Walsh de la fonction f en x et e_l désigne le vecteur dont les l premières coordonnées sont égales à 1 et les n−l autres s'annulent. Or, cette suite σ = x¹ + …+x^l correspond à la sortie d'un unique LFSR dont le polynôme de rétroaction P est le PPCM des polynômes de rétroaction des l premiers LFSRs du générateur (généralement, il s'agit du produit de ces polynômes puisqu'il est conseillé que ces derniers soient irréductibles). Donc, tout multiple Q(X) = 1+X^i₁…+X^i_d−1 de P constitué de d monômes fournit une relation de récurrence pour σ :

σt + σt−i1 + …+σt−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 ^ f   d   (el) .

Ainsi, à partir de tout multiple Q 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 + 1 22nd+2 ^ f   2d   (el)

bits consécutifs. Pour se prémunir contre cette attaque, il faut donc que le polynôme P correspondant au PPCM de l polynômes de rétroaction du système ne possède pas de multiples creux de petit degré. En particulier, les PPCM de plusieurs polynômes de rétroaction du générateur doivent tous comporter un nombre de termes relativement élevé. Il faut par ailleurs les coefficients de Walsh de f sont suffisamment petits, c'est-à-dire que la fonction de combinaison f ait une non-linéarité élevée.
Attaques algébriques.   La fonction f doit posséder une forte immunité algébrique [3] afin que le système résiste aux attaques algébriques (voir la fiche Attaques algébriques pour plus de détails).

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 LFSR 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.

 

Références

[1]

A.  Canteaut, E.  Filiol. << Ciphertext only reconstruction of stream ciphers based on combination generators >>. Fast Software Encryption - FSE 2000, 1978 Lecture Notes in Computer Science. Springer-Verlag, 2000.

[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]

N.  Courtois, W.  Meier. << Algebraic attacks on stream ciphers with linear feedback >>. Advances in Cryptology - EUROCRYPT 2003, 2656 Lecture Notes in Computer Science, 345-359. Springer-Verlag, 2003.

[4]

T.  Siegenthaler. << Correlation-immunity of nonlinear combining functions for cryptographic applications >>. IEEE Trans. Inform. Theory, IT-30(5):776-780, 1984.

[5]

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