PICSI

Principe.   Le principe des attaques par compromis temps-mémoire a été introduit en 1980 par Hellman [5] contre les chiffrements par blocs, puis en 1995 contre les chiffrements à flot par Babbage [1] et Golic [4]. Ces techniques ont pour objet d'inverser une fonction à sens unique, c'est-à-dire une fonction f d'un ensemble E vers un ensemble F pour laquelle il est facile de calculer l'image d'un élément de E, mais très difficile de trouver l'antécédent d'un élément y de F. Pour trouver une valeur de x telle que f(x)=y, on peut évidemment utiliser l'un des deux algorithmes suivants :

• la recherche exhaustive, qui consiste à calculer les images par f de tous les éléments x de E jusqu'à en trouver un qui donne y ; cette technique est très coûteuse en temps de calcul et doit être répétée pour chaque nouvelle valeur de y ;
• l'attaque par dictionnaire, qui consiste à calculer à l'avance les images de tous les éléments x de E et à stocker en mémoire tous les couples (x, f(x)) en les triant suivant la valeur de f(x). A chaque fois qu'une valeur de y est donnée, il suffit de chercher dans la table une valeur de x telle que f(x)=y. Cette technique nécessite également le calcul de tous les f(x) mais ce calcul est fait indépendemment de y et une fois pour toutes. On dit qu'il s'agit d'une étape de précalcul. La phase de calcul proprement dite, c'est-à-dire celle qui trouve x à partir de y est extrêmement rapide, ce qui est très avantageux par rapport à la méthode précédente. Toutefois, l'inconvénient majeur est ici la taille de la mémoire utilisée, puisqu'il faut stocker tous les couples (x, f(x)).

Les attaques par compromis temps-mémoire sont donc des algorithmes en deux étapes : une étape de précalcul permettant de construire une table, et une étape de calcul qui consiste à inverser la fonction de façon plus rapide que la recherche exhaustive à l'aide de la table. L'objet de ces algorithmes est évidemment de trouver un bon compromis entre la taille de la table construite (la mémoire) et le temps nécessaire pour trouver l'antécédent d'un élément y (le temps de calcul). Toutefois, lorsque l'on attaque un chiffrement à clef secrète, on dispose souvent en pratique de plusieurs éléments y à inverser, et il suffit parfois d'inverser l'un d'entre eux pour retrouver la clef. Le nombre d'entrées simultanées de la phase de calcul est donc un paramètre supplémentaire qui permet généralement d'obtenir un meilleur compromis. On parle alors d'attaques par compromis temps-mémoire-données [2,3].
Algorithme général.   L'algorithme général décrit par Biryukov et Shamir dans [2] pour inverser une fonction à sens unique

f : {0,1}n → {0,1}l,     l ≥ n

procède donc de la manière suivante.

Précalcul. Considérons h1, h2, …, hr, r fonctions simples et indépendantes de {0,1}l vers {0,1}n (typiquement, si l = n, il peut s'agir de permutations des bits, ou si l > n, de suppressions de certains bits du vecteur de sortie). Pour i de 1 à r         Choisir m éléments x1, …, xm aléatoires.         Pour j de 1 à m               Calculer zj = [hi °f]t (xj)               en itérant t fois la fonction hi °f.               Stocker (xj, zj) dans la table Ti, triée suivant les valeurs de zj Calcul. Soit y1, …, yD un ensemble de D valeurs de {0,1}m dont l'une au moins doit être inversée. Pour k de 1 à D         Pour i de 1 à r               y′k ← hi(yk)               Pour u de 1 à t                    y′k ← hi°f(y′k)                    Rechercher si y′k figure dans la table Ti.                    Si (x,y′k) est dans la table, alors X=[hi °f]t−u−1(x)                    est très probablement un antécédent de yk.

En effet, on peut vérifier, en notant g_i = h_i °f que g_i^u °h_i appliquée à y_i et à f(X) produit la même valeur :

giu °hi (f(X)) = giu+1 (X)     = giu+1 °git−u−1(x)     = git(x)     = y′k

puisque le couple (x,y′_k) est dans la table T_i. Par ailleurs, d'après la définition de y′_k, on a

giu °hi(yk) = y′k .

Soit N=2ⁿ la taille de l'espace de départ de la fonction f. Pour que l'algorithme ait une bonne chance de trouver l'antécédent d'un des D points y_k, il suffit qu'un des éléments y′_k calculés à partir de y_k figure dans la table correspondant. Il faut donc que les tables couvrent une fraction [1/D] de l'ensemble de départ. L'ensemble des points couverts par les tables est égal à rmt. Il faut donc

rmt = N D  ,

si l'on suppose que tous les points couverts par chacune des tables sont distincts. Cette condition est assurée, d'après le paradoxe des anniversaires, si la taille de chaque table est raisonnablement petite au regard de la racine carrée du nombre d'états possibles, c'est-à-dire si

m t2 ≤ N .

On peut toutefois calculer plus précisément la probabilité de succès de l'attaque à partir d'une borne inférieure sur le nombre de points distincts couverts par les tables [7,Pages 57-58]. L'ensemble de ces conditions permet donc d'exprimer la quantité de mémoire M nécessaire, le temps de calcul T et le temps de précalcul P en fonction des paramètres D, t, m et r de l'algorithme :

M = rm,         T=rtD,         P = rmt = N D

avec

mt2 = N .

On peut isoler un certain nombre de points (M,T,P) intéressants sur cette courbe.

• L'attaque proposée par Babbage [1] et Golic [4] utilise r=t=1 : on ne considère qu'une seule fonction h (qui est l'identité si la fonction à sens unique considérée est une bijection). Dans ce cas, les différents paramètres de complexité de l'attaque sont
  

  M=T=D=P = N[1/2] .

  Ceci signifie que l'on peut inverser la fonction en une complexité (en temps, en mémoire et en donnée) de l'ordre de la racine carrée de la taille de son ensemble de départ.
• L'attaque proposée par Biryukov et Shamir dans [2] part du principe réaliste que la quantité de données est souvent le facteur limitant de l'attaque, et qu'il est raisonnable d'envisager un coût de précalcul plus élevé que le temps de calcul. Ils se placent alors sous l'hypothèse que le nombre de tables est égal à r=[t/D]. Il s'agit de la généralisation pour une valeur de D quelconque de l'hypothèse initiale de Hellman [5]. La complexité de l'attaque est alors définie par la courbe
  

  TM2D2 = N2 et P = N D

  avec 1 ≤ D² ≤ T. Un point particulier est donné par
  

  T=M = N[1/2],     D = N[1/4] et P = N[3/4] .

D'autres points intéressants dans divers contextes pratiques sont définis dans [3].
Application aux chiffrements à flot.   Les attaques par compromis temps-mémoire peuvent être appliquées de deux manières différentes aux algorithmes de chiffrement à flot.

• Dans une attaque dont le but est de retrouver l'état interne du générateur pseudo-aléatoire [1,4], la fonction à sens unique considérée est la fonction qui, à l'état initial de taille n, associe les n premiers bits de suite chiffrante produits par le générateur. A partir de D bits consécutifs connus de suite chiffrante, on construit alors D−n fenêtres de n bits consécutifs de la suite. Il suffit alors de retrouver l'état interne qui correspond à l'antécédent d'une de ces fenêtres. Pour cela, avec les paramètres r=t=1, l'attaque nécessite
  

  M=T=P = 2[n/2]

  et
  

  D = 2[n/2] + n bits consécutifs de suite chiffrante .

  Une conséquence majeure de cette attaque est que l'état interne d'un générateur pseudo-aléatoire doit toujours être au minimum deux fois plus long que la clef secrète, sinon l'attaque par compromis temps-mémoire fournit une cryptanalyse plus efficace que la recherche exhaustive de la clef.
• Dans le cas d'un chiffrement à flot utilisant des valeurs initiales (IV) de taille v pour la synchronisation du système, il est également possible de considérer la fonction à sens unique qui, à tout couple formé par la clef secrète et l'IV, associe les (k+v) bits premiers de la suite chiffrante, où k est la taille de la clef [6]. On voit alors, en utilisant l'algorithme de Biryukov et Shamir, que la connaissance de
  

  D = 2[1/4](k+v)

  bits de suite chiffrante permet de retrouver la clef secrète en complexité
  

  T=M = 2[1/2](k+v) et P = N[3/4](k+v) .

  En particulier, si la taille de l'IV, v, est strictement inférieure à celle de la clef secrète k, l'attaque peut être considérée comme plus rapide que la recherche exhaustive de la clef, même si le coût du précalcul est, lui, supérieur. Il est important de noter que cette attaque s'applique notamment dans le cas où le chiffrement à flot correspond à un chiffrement par bloc en mode OFB ou CTR pour lequel la taille des blocs est strictement inférieure à celle de la clef secrète (c'est le cas par exemple du DES).

Application aux chiffrements par blocs.   Même si elles ont été à l'origine conçues pour attaquer les algorithmes par blocs, les attaques par compromis temps-mémoire-données sont souvent moins efficaces dans ce contexte que contre les chiffrements à flot, car la quantité de données D disponible est beaucoup plus limitée. Usuellement, la fonction à sens unique considérée est la fonction qui, à une clef secrète donnée, associe le chiffré d'un texte clair unique choisi par l'attaquant. Dans ce cas, l'attaque consiste à retrouver la clef secrète utilisée à partir de la connaissance du chiffré de ce message clair. On a donc D=1, et on obtient une attaque de complexité

M=T = 2[k/2]

où k est la longueur de la clef secrète, mais dont le précalcul est aussi coûteux que la recherche exhaustive (ce qui présente malgré tout un avantage). Toutefois, il existe certains contextes dans lesquels on dispose de textes chiffrés par différentes clefs, ce qui conduit à un meilleur compromis entre les différentes complexités [3].

 

Références

[1]

S.  Babbage. << A space/time trade-off in exhaustive search attacks on stream ciphers >>. European Convention on Security and Detection, 408. IEEE Conference Publication, 1995.

[2]

A.  Biryukov, A.  Shamir. << Cryptanalytic time-memory-data trade-offs for stream ciphers >>. Advances in Cryptology - ASIACRYPT 2000, 1976 Lecture Notes in Computer Science, 1-14. Springer-Verlag, 2000.

[3]

A.  Biryukov, S.Mukhopadhyay,, P.Sarkar. << Improved Time-Memory Trade-offs with Multiple Data >>. Selected Areas in in Cryptography - SAC 2005, Lecture Notes in Computer Science. Springer-Verlag, 2005.

[4]

J.  Golic. << Cryptanalysis of alleged A5 stream cipher >>. Advances in Cryptology - EUROCRYPT'97, 1233 Lecture Notes in Computer Science, 239-255. Springer-Verlag, 1997.

[5]

M. E. Hellman. << A cryptanalytic time-memory trade-off >>. IEEE Transactions on Information Theory, 26(4):401-406, 1980.

[6]

J.  Hong, P.  Sarkar. << New Applications of Time Memory Data Tradeoffs >>. Advances in Cryptology - ASIACRYPT 2005, 3788 Lecture Notes in Computer Science, 353-372. Springer-Verlag, 2005.

[7]

S.  Vaudenay. A classical introduction to cryptography: applications for communications security. Springer, 2005.