PICSI

Principe.   Les attaques par corrélation rapides sont des améliorations des attaques par corrélation classiques, telles que définies par Siegenthaler, dans le cas où il existe une approximation de la suite chiffrante par un générateur pseudo-aléatoire dont la sortie dépend linéairement de l'état initial. Puisque les algorithmes utilisés dans ce cas ne nécessitent plus d'effectuer une recherche exhaustive sur l'état initial, ces attaques s'appliquent même lorsque l'état interne du générateur pseudo-aléatoire n'est pas décomposable en plusieurs parties indépendantes, contrairement à l'attaque par corrélation originale.

Les algorithmes par corrélation rapides sont particulièrement appropriés pour attaquer les générateurs pseudo-aléatoires dont la fonction de transition est linéaire, notamment les générateurs utilisant des LFSR.
L'attaque par corrélation vue comme un problème de décodage.   Considérons un générateur pseudo-aléatoire engendrant une suite chiffrante s à partir d'un état interne x₀ de n bits au moyen d'une fonction de transition Φ et d'une fonction de filtrage f. Supposons qu'il existe un autre générateur de fonction de transition Ψ et de fonction de filtrage g qui, à partir du même état initial x₀, produit une suite σ(x₀) corrélée à la suite chiffrante, c'est-à-dire telle que, pour tout t,

p = Pr[st ≠ σt] = 1 2 − ε,   ε > 0 .

Cette hypothèse revient à dire que la suite chiffrante s correspond au résultat de la transmission de la suite σ(x₀) à travers un canal de communication bruité qui suit le modèle d'un canal binaire symétrique de probabilité d'erreur p (voir Figure 1).


Figure 1: Modèle de l'attaque par corrélation rapide
Grâce à cette observation, Meier et Staffelbach [8] ont montré que toute attaque consistant à retrouver l'état initial du générateur, x₀, (ou de manière équivalente la suite σ) à partir de la connaissance de la suite chiffrante s peut être vue comme un problème classique de correction d'erreurs. En effet, les N premiers bits de σ(x₀) correspondent à un mot du code correcteur d'erreurs C de longueur N formé par les 2ⁿ vecteurs (σ_t)_{t < N} obtenus pour chacun des 2ⁿ états initiaux possibles x₀. Ce code est donc défini par la donnée des fonctions Ψ et g. Les attaques par corrélation rapides consistent alors à appliquer des algorithmes de décodage au code C afin de retrouver x₀.
Décodage à maximum de vraisemblance.   Lorsque le code C ne possède pas de propriété particulière qui facilite son décodage, le seul algorithme qui permet de corriger les erreurs de transmission est l'algorithme de décodage à maximum de vraisemblance. Il consiste à énumérer les 2ⁿ mots de code possibles, et à choisir celui qui est le plus proche du mot reçu. On voit que cet algorithme est strictement équivalent à la recherche exhaustive de l'état initial x₀, autrement dit à l'algorithme d'attaque par corrélation décrit par Siegenthaler. Sa complexité en temps est de l'ordre de

2n ε2

où ([1/2] − ε) désigne la probabilité d'erreur. Il nécessite la connaissance d'environ

1 ε2

bits de suite chiffrante. Sa complexité en temps est donc inaccessible, sauf dans les cas particuliers où la suite σ ne dépend que d'un sous-ensemble des n bits de l'état initial. Toutefois, il est important de noter que, d'après le théorème fondamental de codage de canal de Shannon [9], le décodage à maximum de vraisemblance est optimal dans le sens où c'est celui qui exige la longueur minimale N nécessaire pour pouvoir décoder un code contenant 2ⁿ mots. Cette longueur minimale est donnée par la capacité du canal de communication utilisé :

Nmin = n Ccanal  .

Dans le cas d'un canal binaire symétrique avec une probabilité d'erreur p, la capacité est définie par la formule

Ccanal = 1 + p log2 p + (1−p) log2 (1−p) .

De plus, lorsque la probabilité d'erreur est proche de [1/2], c'est-à-dire p = [1/2] − ε, on peut utiliser l'approximation suivante

Ccanal ≅ ln(2) 2 ε2  .

Ainsi, le théorème de Shannon implique que la longueur de suite chiffrante nécessaire pour retrouver les n bits de l'état initial x₀ vérifie toujours

N ≥ ln(2)n 2 ε2

et que la longueur minimale correspond au nombre de bits requis pour mener une attaque par corrélation classique (c'est-à-dire au moyen d'un décodage par maximum de vraisemblance). L'objectif des attaques par corrélation rapides est donc de décoder la suite chiffrante par un algorithme beaucoup plus rapide que par une recherche exhaustive. Toutefois, ces algorithmes vont nécessiter la connaissance d'un nombre de bits de suite chiffrante beaucoup plus élevé que la valeur minimale définie précédemment. On utilisera en pratique l'algorithme de décodage qui fournit le meilleur compromis entre la complexité en temps et la complexité en donnée de l'attaque.
Algorithmes de décodage de codes linéaires.   Dans le cas où la suite σ(x₀) dépend linéairement de l'état initial x₀, c'est-à-dire dans le cas où les fonctions Ψ et g sont deux fonctions linéaires, le code correcteur définissant σ(x₀) est un code linéaire de dimension n dont on peut calculer une matrice génératrice G. C'est le cas par exemple lorsque la fonction de transition Φ du générateur attaqué (et donc la fonction Ψ) correspond à un ou plusieurs LFSRs. Le code associé peut alors être décodé au moyen d'algorithmes plus rapides que le décodage à maximum de vraisemblance. Il existe deux grandes familles d'algorithmes de décodage utilisés dans ce contexte :

• les algorithmes itératifs, qui exploitent des relations de parité creuses vérifiées par la suite σ, c'est-à-dire des relations de la forme
  

  σt + σt−a1 + …+ σt − ad−1

  où le nombre de termes d est petit (typiquement, 3 ou 4). Lorsque σ est produite par un LFSR de polynôme de rétroaction P, une relation de ce type correspond au fait que le polynôme 1+X^a₁ + …+ X^a_d−1 est un multiple de P(X). De telles relations de poids faible peuvent être utilisées dans un algorithme de décodage qui repose sur le principe du décodage itératif des codes à matrice de parité creuse (codes LDPC) introduit par Gallager [5]. Un algorithme de ce type, qui améliore celui qui a été utilisé à l'origine par Meier et Staffelbach [8], est décrit dans [2]. Lorsque l'on utilise des relations de parité de poids d, le nombre N de bits de suite chiffrante nécessaire pour mener l'attaque est :
  
  

  N ∝   1 2 ε   [2(d−2)/d−1]     2[n/d−1] .

  La phase de précalculs (c'est-à-dire qui ne dépend que des spécifications du générateur et non de la suite chiffrante) correspond à la recherche des équations de parité. Elle nécessite
  

  O( Nd−2/(d−2)! )

  opérations. Cette complexité peut être améliorée grâce à des méthodes utilisant le compromis temps-mémoire ou l'algorithme proposé dans [4], même si le facteur déterminant reste le degré d des équations de parité qui doit être faible.
  La complexité de la phase de décodage proprement dite est de l'ordre de :
  

    1 2 ε   [2d(d−2)/d−1]     2[n/d−1] .
• les algorithmes de décodage à maximum de vraisemblance d'un code de dimension inférieure dont le principe est de transformer, au moyen de manipulations sur sa matrice génératrice, le code C à décoder en un autre code linéaire C′ de dimension l plus petite, auquel on peut appliquer un décodage à maximum de vraisemblance. L'idée fondatrice, due à Chepyshov, Johansson et Smeets [3], est de s'abstraire des n −l dernières positions de l'état initial en considérant toutes les combinaisons linéaires de w colonnes de la matrice génératrice de C qui s'annulent sur ces n−l dernières positions. Ce nouveau code de dimension l est de longueur [(N^w)/(w! 2^n−l)]. Le nombre de bits N de suite chiffrante nécessaires pour décoder ce nouveau code est donc
  

  N ≅   1 2 ε   2   2[(n−l)/w] .

  La phase de précalcul permettant de générer la nouvelle matrice avec les combinaisons linéaires de w colonnes a une complexité équivalente à la recherche d'équations de parité de poids w+1. La complexité de l'attaque proprement dite, c'est-à-dire la phase de décodage à maximum de vraisemblance, sur les l premiers bits de l'état initial du LFSR est de l 2^l opérations si on utilise un algorithme de transformée de Fourier rapide. Pour retrouver les n−l bits suivants de l'état initial, il suffit alors d'appliquer la même attaque aux l bits suivants et ainsi de suite. On peut également éviter de répéter l'attaque pour chaque bloc de l bits de l'état initial en utilisant une technique dérivée de l'algorithme de Sudan pour la reconstruction de polynômes multivariés [6].

Attaques sur les générateurs à base de LFSRs.   Dans le cas particulier des différents générateurs à base de LFSR, la forme du code linéaire sous-jacent permet généralement d'améliorer les performances des algorithmes de décodage génériques.

• Combinaison de LFSRs : dans le cas où la suite chiffrante est produite par k LFSRs combinés par une fonction f à k variables, la meilleure suite σ, c'est-à-dire celle qui correspond à la probabilité d'erreur la plus faible, est celle obtenue en additionnant les sorties de (m+1) LFSRs si m est l'ordre d'immunité aux corrélations de la fonction f [2]. Cette suite σ correspond alors à la sortie d'un unique LFSR dont le polynôme de rétroaction linéaire P est le plus grand diviseur commun des (m+1) polynômes de tous les LFSRs utilisés. Quand tous ces polynômes sont primitifs, la longueur du LFSR cible est donc la somme des longueurs des (m+1) LFSRs. La suite chiffrante s correspond alors au résultat de la transmission de σ à travers un canal binaire symétrique de probabilité d'erreur p avec
  

  p = Pr[st ≠ σt] = Pr[f(x1, …, xk) = xi1 + …+ xim] = 1 2 − 1 2k+1 | ^ f   (u) |

  où u est le vecteur de k bits ayant sa i-ème composante égale à 1 si i ∈ {i₁, i₂, …i_m+1 } et où [^f] désigne la transformée de Walsh de la fonction f. Le fait de choisir pour f une fonction de non-linéarité élevée, c'est-à-dire qui soit à grande distance de toutes les fonctions de degré 1 garantit donc un taux d'erreur important, et par conséquent que les attaques par corrélation rapides ont une complexité élevée.
• LFSR filtrés : Dans le cas du registre filtré, on choisit pour σ une suite produite par un LFSR qui a le même polynôme de rétroaction que le LFSR constituant le générateur pseudo-aléatoire mais un état initial différent. Si la suite chiffrante est définie par la relation :
  

  ∀t,     st = f(vt +a1, vt +a2, …, vt +ak)

  alors, la suite σ optimale est donnée par :
  

  σt = k ∑ i=1  αi vt + ai

  où α = (α₁, …,α_k) est le vecteur qui maximise la valeur absolue de la transformée de Walsh de la fonction f. La probabilité d'erreur du canal binaire symétrique est alors de
  

  p = Pr[st ≠ σt] = NL(f) 2k

  où NL(f) désigne la non-linéarité de f. Il est à noter que, dans le cas d'un LFSR filtré, les attaques par corrélation rapides peuvent être améliorées en utilisant plusieurs LFSRs cibles simultanément (cf. [7] et [1]).

 

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]

V.  Chepyshov, T.  Johansson,, B.  Smeets. << A simple algorithm for fast correlation attacks on stream ciphers >>. Fast Software Encryption 2000, 1978 Lecture Notes in Computer Science, 181-195. Springer-Verlag, 2000.

[4]

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.

[5]

R.G. Gallager. Low-density parity-check codes. MIT Press, Cambridge, MA, 1963.

[6]

T.  Johansson, F.  Jönsson. << Fast correlation attacks through reconstruction of linear polynomials >>. Advances in Cryptology - CRYPTO'00, 1880 Lecture Notes in Computer Science, 300-315. Springer-Verlag, 2000.

[7]

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

[8]

W.  Meier, O.  Staffelbach. << Fast correlation attack on certain stream ciphers >>. J. Cryptology, 1(3):159-176, 1989.

[9]

C.E. Shannon. << A mathematical theory of communication >>. Bell Syst. Tech. J., 27, 1948.