PICSI

Les générateurs pseudo-aléatoires dédiés sont les seules constructions qui permettent d'atteindre un débit de chiffrement supérieur à celui d'un algorithme par blocs (de l'ordre de quelques cycles du processeur par octet en logiciel), ou qui puissent être implémentés par un circuit électronique de petite taille et à faible consommation.

État de l'art.   Au contraire des générateurs utilisant un algorithme par blocs, les contraintes liées à leur mise en uvre, dans un environnement logiciel ou matériel, interviennent ici directement dans la conception. Ces contraintes, combinées aux exigences de sécurité, rendent la tâche relativement difficile. Ainsi, à l'heure actuelle, très peu de générateurs dédiés sont considérés comme sûrs, au sens où ils ne sont vulnérables à aucune attaque plus rapide que la recherche exhaustive de la clef secrète. Quelques propositions récentes, SNOW 2.0 et MUGI, ont été prises en compte dans la dernière version de travail de la norme internationale de chiffrement ISO/IEC 18033-4, mais leur conception reste trop récente pour pouvoir se prononcer sur leur sécurité à long terme. De façon générale, la conception de nouveaux générateurs pseudo-aléatoires dédiés est actuellement un sujet de recherche extrêmement actif ; on peut ainsi mentionner le projet eSTREAM lancé par le réseau européen ECRYPT [2] suite auquel une trentaine de nouveaux générateurs dédiés ont été proposés en avril 2005 et dont la sécurité et les performances doivent encore faire l'objet d'une évaluation approfondie.
Modèle général d'un générateur pseudo-aléatoire dédié.   Un générateur pseudo-aléatoire dédié est un automate à états finis qui engendre à chaque instant un ou plusieurs bits déterminés par la valeur de son état interne. Son fonctionnement, décrit à la figure , est généralement modélisé par trois fonctions différentes.

Figure 1: Modèle d'un générateur pseudo-aléatoire dédié

• une procédure d'initialisation qui détermine l'état initial du générateur pseudo-aléatoire à partir de la clef secrète et de la valeur initiale. Notons que l'initialisation est parfois divisée en deux phases : l'une, dite de chargement de clef, calcule une certaine quantité qui ne dépend que de la clef (et non de la valeur initiale), l'autre, dite d'injection d'IV ou de re-synchronisation, détermine l'état initial du générateur à partir de la valeur calculée précédemment et de la valeur initiale. Le fait de découper de la sorte la phase d'initialisation permet de réduire le coût de la procédure qui consiste à changer la valeur initiale sans modifier la clef. Il s'agit en effet d'une opération beaucoup plus fréquente en pratique que le changement de clef, notamment pour les protocoles de communication pour lesquels la longueur des paquets échangés est relativement petite. Par exemple, dans le communications GSM, on change l'IV tous les 228 bits alors que la clef reste inchangée tout au long de la conversation.
• une fonction de transition (notée Φ sur la figure ) qui fait évoluer l'état interne du générateur entre l'instant t et (t+1). Cette fonction peut dépendre de la clef, de la valeur initiale et du temps, mais elle est fixe dans l'immense majorité des générateurs destinés à une mise en uvre matérielle pour des raisons évidentes de simplicité et d'encombrement.
• une fonction de filtrage (notée f sur la figure ) qui, à chaque instant, produit un ou plusieurs bits de suite à partir de l'état interne courant. Tout comme la fonction de transition, la fonction de filtrage peut varier avec la clef, la valeur initiale et le temps, mais elle est généralement fixe pour les raisons évoquées précédemment.

Il est important de noter que, si l'état interne est composé de n bits, on reviendra nécessairement à un état interne déjà rencontré après au plus 2ⁿ tops d'horloge, ce qui implique que la suite produite a une période inférieure ou égale à 2ⁿ. Toute utilisation doit donc imposer un changement de clef ou de valeur initiale dès que 2ⁿ bits ont été produits. Dans de nombreuses applications, le nombre maximal de bits produits sans changement de clef ou de valeur initiale est généralement limité à une valeur bien inférieure, mais d'un point de vue théorique, on considère des attaques qui peuvent nécessiter jusqu'à 2^k bits connus de suite chiffrante, où k est le nombre de bits de la clef secrète.
Les contraintes imposées par les attaques génériques.   Chacun des composants d'un générateur pseudo-aléatoire dédié doit être choisi avec précaution. En particulier, les critères fondamentaux suivants sont dictés par la nécessité de résister à des attaques classiques qui s'appliquent à tous les générateurs de ce type.

• La taille de l'état interne doit être suffisamment grande pour parer la recherche exhaustive, mais aussi les attaques dites par compromis temps-mémoire (voir la fiche consacrée à ces attaques pour plus détails). Celles-ci imposent en particulier que la taille de l'état interne doit être au minimum le double de la taille de la clef secrète.
• La fonction de filtrage doit assurer que la sortie du générateur est uniformément distribuée. Par exemple, dans le cas où un seul bit est produit à chaque unité de temps, il faut que ce bit prenne les valeurs 0 et 1 avec la même probabilité. Pour cela, la fonction de filtrage doit être équilibrée, ce qui signifie que le nombre de vecteurs x dont l'image par f vaut y est le même quelle que soit la valeur de y. Dans le cas contraire, la suite produite par le générateur est biaisée, au sens qu'elle contient plus de 0 que de 1, ce qui permet de la distinguer d'une suite aléatoire dès lors que l'on connaît de l'ordre de
  

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

  bits de la suite engendrée, le nombre d'opérations à effectuer pour mener à bien cette attaque par distingueur étant du même ordre.
• La fonction de transition Φ doit garantir que la suite chiffrante possède une période élevée quel que soit l'état initial. Sinon, il devient facile de distinguer la suite produite d'une suite aléatoire.
• L'une des deux fonctions au moins, Φ ou f, doit être non linéaire. Sinon, la suite produite dépend linéairement des bits de l'état initial. Dans ce cas, la connaissance de n bits de suite chiffrante, où n est la taille de l'état interne, fournit un système de n équations à n inconnues (les bits de l'état initial), que l'on peut résoudre simplement au moyen d'un pivot de Gauss. Cette attaque permettrait de retrouver l'état initial du générateur en n³ opérations, ce qui est très inférieur à la complexité de la recherche exhaustive de la clef.