PICSI

Principe.   Les attaques par corrélation entrent dans la catégorie plus générale des attaques de type diviser pour régner qui s'appliquent à chaque fois que l'on peut décomposer un système en composantes plus petites, cryptographiquement faibles.

Dans le cas du chiffrement à flot, ces attaques ont été introduites en 1985 par Siegenthaler [4] contre les générateurs par combinaison de LFSRs. Mais, cette cryptanalyse est en fait valide sur tous les générateurs pseudo-aléatoires dont l'état interne est décomposable en plusieurs parties mises à jour indépendamment les unes des autres. On peut alors chercher séparément la valeur initiale de chaque partie de l'état interne. L'attaque repose sur l'existence d'éventuelles corrélations entre la sortie de la fonction de filtrage et un sous-ensemble de ses entrées qui correspond à la partie incriminée de l'état interne.
Description.   Supposons comme à la figure 1 que l'on peut séparer l'état interne du générateur à l'instant t en deux parties x_t et y_t de tailles respectives l et (n−l), mises à jour indépendamment par Φ₀ et Φ₁.




Figure 1:  Modèle de l'attaque par corrélation

Plaçons-nous dans le cas où l'attaquant cherche à retrouver la valeur de la première partie de l'état initial, x₀. Le vecteur d'entrée de la fonction de filtrage f se décompose de la même manière en deux parties, x et y. On peut alors appliquer l'attaque s'il existe une fonction g à l variables (c'est-à-dire ne dépendant que de x) qui coïncide avec la sortie de f dans plus de la moitié des cas, autrement dit si la probabilité

pg = PrX,Y[f(X,Y)=g(X)] > 1 2  .

La suite σ(x₀) produite par le générateur réduit d'état initial x₀ et de fonction de filtrage g est alors corrélée à la suite chiffrante s car, pour tout t ≥ 0,

Pr[st = σt] = pg > 1 2  .

Dans ce cas, l'attaque par corrélation consiste à effectuer une recherche exhaustive sur la partie incriminée de l'état initial, x₀, au moyen de l'algorithme suivant.

Entrée. les N premiers bits de la sortie du générateur pseudo-aléatoire, (st)t < N. Sortie. x0, vecteur de l bits correspondant à une partie de l'état initial. Algorithme   Pour chaque vecteur x0 de l bits Calculer les N bits de la suite σ(x0) définie par σt = g °Φ0t(x0) . Calculer la corrélation sur N bits entre les suites s et σ(x0) : c(s,σ(x0)) = N−1 ∑ t=0  (−1)σt + st . Retourner la valeur de x0 qui maximise c(s,σ(x0)).

Attaque par corrélation

Au lieu de retourner la valeur la plus probable pour x₀, on peut également choisir de retourner l'ensemble des valeurs pour lesquelles c(s,σ(x₀)) dépasse un certain seuil. L'attaque repose sur le fait que, lorsque la valeur de x₀ essayée ne correspond pas à la valeur effectivement employée dans l'initialisation, alors les suites s et σ(x₀) ne sont pas corrélées et la valeur moyenne de la corrélation est nulle. En revanche, lorsque la valeur essayée x₀ est correcte, on a

E[ c(s,σ(x0))] = 2N   pg − 1 2    .

Complexité.   Le nombre de bits N de suite chiffrante nécessaires pour retrouver la valeur correcte de x₀ est de l'ordre de

   1 pg − 1 2    2    .

La complexité en temps pour retrouver les l bits x₀ de l'état initial est de l'ordre de

2l (pg − 1 2 )2  ,

mais peut être réduite à

l  2l

quand les fonctions Φ₀ et g sont des fonctions linéaires, grâce à un algorithme de transformée de Fourier rapide [2]. Dans ce dernier cas, la complexité en temps de l'attaque peut être considérablement améliorée en employant les attaques dites par corrélation rapide (voir la fiche d'approfondissement sur ce sujet).
Exemple : attaque du générateur de Geffe   Considérons par exemple le générateur par combinaison de LFSR, qui suit le modèle proposé par Geffe en 1973 [3]. Il est composé de trois LFSR de longueurs respectives 7, 12 et 13 combinés par la fonction

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

Figure 2:  Générateur de Geffe
Une recherche exhaustive sur la clef secrète, qui comporte 7+12+13 = 32 bits, nécessiterait d'examiner ses 2³² = 4.294.967.296 valeurs possibles. En fait, on peut déterminer de manière indépendante les 7 premiers bits de la clef, qui correspondent à l'initialisation du premier registre. On considère les 2⁷ = 128 initialisations possibles pour ce registre. Pour chacune d'entre elles, on génère les 100 premiers bits produits par le premier registre initialisé de la sorte et on compare ces 100 bits avec les 100 premiers bits produits par le générateur. Si l'initialisation du premier registre que l'on essaie est correcte, ces deux suites de 100 bits vont coïncider sur environ 75 bits puisque la sortie du générateur est égale à la sortie du premier registre dans 75 % des cas. Par contre, si l'initialisation essayée n'est pas la bonne, les deux suites que l'on compare ne sont pas corrélées. Autrement dit, elles vont coïncider sur environ la moitié des positions. Ainsi, la connaissance des 100 premiers bits produits par le générateur suffit à déterminer l'initialisation du premier registre en 128 essais. De la même façon, on peut ensuite retrouver l'initialisation du troisième registre (de longueur 12) en 2¹² = 4096 essais en exploitant le fait que la sortie du générateur coïncide également dans 75 % des cas avec la suite engendrée par le troisième registre. Enfin, il ne reste plus qu'à retrouver les 13 bits de clef restant à déterminer (l'initialisation du deuxième registre) par une recherche exhaustive. L'attaque complète du générateur a donc nécessité 2⁷+2¹² +2¹³ = 12.416 essais au lieu des 2³² = 4.294.967.296 demandés par une recherche exhaustive de la clef.
Résistance aux attaques par corrélation.   La fonction g étant choisie par l'attaquant, celui-ci doit naturellement utiliser celle qui conduit à la plus grande corrélation, c'est-à-dire celle pour laquelle la valeur de p_g est la plus éloignée possible de 1/2. On peut démontrer que la fonction g est optimale pour l'attaque si et seulement si elle vérifie

       g(x)=1 si PrY[f(x,Y) = 1] > 1 2 g(x)=0 si PrY[f(x,Y) = 1] < 1 2

Il s'ensuit que la probabilité p_g optimale mise en jeu dans la complexité de l'attaque est donnée par

max g  pg = 1 2 + 1 2l ∑ x ∈ F2l    1 2 − PrY[f(x,Y) = 1]    .

On en déduit également le critère de sécurité garantissant qu'un générateur résiste à l'attaque par corrélation. En effet, il est impossible de mener l'attaque si la valeur correcte de x₀ ne peut pas être distinguée des autres, c'est-à-dire si la probabilité p_g est égale à 1/2 pour tous les choix possibles de la fonction g. Cela signifie exactement que la probabilité Pr_Y[f(x,Y) = 1] vaut 1/2 pour toutes les valeurs de x, autrement dit que la fonction f reste équilibrée (i.e., uniformément distribuée) quand ses l premières entrées sont fixées. Les fonctions l-résilientes (dites aussi dans ce cas sans corrélation d'ordre l) sont un exemple de fonctions vérifiant ce critère. Par exemple, pour se prémunir de l'attaque par corrélation décrite précédemment contre le générateur de Geffe, il aurait fallu choisir comme fonction de combinaison une fonction qui soit au moins 1-résiliente. Dans la fiche consacrée aux générateurs pseudo-aléatoires à base de LFSR, on trouvera plus de détails sur les critères de résistance aux attaques par corrélation dans ce cas particulier.

 

Références

[1]

A.  Canteaut. << Fast Correlation Attacks Against Stream Ciphers and Related Open Problems >>. Proceedings of the 2005 IEEE Information Theory Workshop on Theory and Practice in Information-Theoretic Security, 49-54. IEEE, 2005.

[2]

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.

[3]

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

[4]

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