PICSI

La classification des différents types de générateurs pseudo-aléatoires dédiés est une tâche délicate dans la mesure où leur conception est largement liée à l'environnement applicatif auquel le générateur est destiné. On peut toutefois distinguer trois grandes familles suivant le type de fonction de transition employé. Mais ces classes peuvent elles-mêmes parfois être subdivisées suivant que le générateur vise une mise en uvre logicielle ou matérielle.

• Les chiffrements à transition linéaire. L'utilisation d'une fonction de transition linéaire est en effet un choix naturel en termes de simplicité d'implémentation, dans la mesure où la fonction de filtrage garantit que la suite produite ne dépend pas linéairement de l'état initial du générateur). Parmi les fonctions de transition linéaires, celles qui sont mises en uvre au moyen de registres à décalage à rétroaction linéaire (LFSR) sont privilégiées à la fois pour le faible coût de leur implémentation matérielle et parce que l'on dispose de nombreux résultats théoriques sur les propriétés statistiques des suites produites. Les générateurs utilisant des registres à décalage à rétroaction linéaire sont sans aucun doute ceux qui ont fait l'objet des études les plus nombreuses. Ces systèmes peuvent être destinés soit à un environnement matériel, soit à un environnement logiciel. Mais, on utilise généralement dans ce dernier cas des registres à décalage à rétroaction linéaire non plus binaires, mais opérant sur un alphabet plus grand (typiquement sur des octets ou des mots de 32 bits). Parmi les générateurs à base de LFSR d'utilisation courante, on peut mentionner E0, déployé dans la norme Bluetooth, A5/1 utilisé pour chiffrer les communications des téléphones mobiles dans la norme GSM ou SNOW 2.0 qui, lui, vise des applications logicielles, est qui est inclus dans la dernière version de la norme ISO/IEC 18033. Les progrès récents dans le domaine de la cryptanalyse, notamment les attaques dites algébriques proposées dernièrement, mettent toutefois en évidence des faiblesses inhérentes à de nombreux générateurs de ce type. De multiples précautions liées à l'émergence de ces attaques doivent donc être prises lors de la conception de générateurs utilisant une fonction de transition linéaire.
• Les chiffrements à transition non-linéaire. Afin d'éviter les faiblesses pouvant résulter du caractère linéaire de la fonction transition, certaines conceptions récentes privilégient une évolution non-linéaire. Toutefois, la fonction de transition choisie doit garantir que les états internes du générateur ne forment pas une suite de faible période, et ce quel que soit la valeur de l'état initial. Contrairement aux fonctions linéaires, il est relativement difficile d'obtenir de tels résultats théoriques pour des fonctions non-linéaires. Cette difficulté peut être contournée si la taille de l'état interne du générateur n'est pas limitée drastiquement par des contraintes d'implémentation (c'est le cas des applications logicielles destinées aux ordinateurs usuels). Dans ce cas, même en l'absence de résultats théoriques, on peut estimer qu'il est très peu probable qu'un état initial engendre une suite de faible période si l'état interne est suffisamment grand. L'exemple type est celui de RC4, générateur proposé par R. Rivest et utilisé dans de nombreuses applications (SSL/TLS,...), dont l'état interne correspond à un tableau de 512 octets dont les valeurs sont modifiées de façon non-linéaire à chaque itération de l'algorithme (voir la fiche concernant RC4 pour une description précise).
  Toutefois, dans les applications matérielles, les contraintes sur la taille du circuit correspondant imposent que l'état interne du générateur ne soit pas trop grand, autrement dit que sa taille n'excède pas sensiblement le double de la longueur de la clef (qui est la taille minimale pour résister aux attaques par compromis temps-mémoire). Dans ce cas, il est indispensable de disposer de résultats théoriques sur la période de la fonction de transition. A l'heure actuelle, très peu de fonctions offrent ces garanties et les générateurs pseudo-aléatoires les utilisant sont encore au stade de développement. On peut mentionner certains registres à décalage à rétroaction non-linéaire, les registres à décalage à rétroaction avec retenues [3,1] et les T-fonctions [4,5], cette toute dernière proposition récente s'avérant peu souhaitable tant à cause de certaines faiblesses liées à son emploi que de sa lenteur même en logiciel [6].
• Les conceptions hybrides. Dans certains générateurs pseudo-aléatoires, l'état interne est divisé en deux parties, l'une étant mise à jour par une fonction linéaire, l'autre par une fonction non-linéaire. Lorsque la partie qui évolue de manière non-linéaire est beaucoup plus petite que l'autre, elle est généralement assimilée à une mémoire interne. Autrement dit, le générateur est souvent classé comme un générateur à transition linéaire avec mémoire. C'est le cas par exemple des générateurs SNOW 2.0 et E0, qui sont usuellement qualifiés de systèmes à transition linéaire. Toutefois, il existe des générateurs dans lesquels les parties à évolution linéaire et non-linéaire de l'état interne sont de tailles similaires. On trouve dans cette catégorie le générateur MUGI conçu par la société Hitachi et qui figure dans la dernière version de travail de la norme ISO/IEC 18033-4 au même titre que SNOW 2.0.

Références

[1]

F.  Arnault, T.P. Berger. << F-FCSR: design of a new class of stream ciphers >>. Fast Software Ecryption - FSE 2003, 3557 Lecture Notes in Computer Science, 83-97. Springer-Verlag, 2005.

[2]

ECRYPT - European Network of Excellence in Cryptology. << The eSTREAM Stream Cipher Project >>. http://www.ecrypt.eu.org/stream/, 2005.

[3]

A.  Klapper, M.  Goresky. << Feedback shift registers, 2-adic span and combiners with memory >>. Journal of Cryptology, 10(2), 1997.

[4]

A.  Klimov, A.  Shamir. << A new class of invertible mappings >>. CHES 2002, 2523 Lecture Notes in Computer Science, 470-483. Springer-Verlag, 2002.

[5]

A.  Klimov, A.  Shamir. << Cryptographic applications of T-functions >>. Selected Areas in Cryptography - SAC 2003, 3006 Lecture Notes in Computer Science. Springer-Verlag, 2004.

[6]

H.  Molland, T.  Helleseth. << A Linear Weakness in T-functions >>. Proceedings of the 2005 IEEE International Symposium on Information Theory - ISIT 2005. IEEE, 2005.