Jacques Patarin | ![]() |
![]() |
Date de l'exposé : 14 octobre 2005
La sécurité des schémas de Feistel aléatoires
Les schémas de Feistel fournissent une méthode standard pour construire des permutations pseudo-aléatoires, ou encore pour construire des algorithmes de chiffrement par blocs. Depuis le célèbre résultat de Luby et Rackoff sur les schémas de Feistel aléatoires à 3 et 4 tours (1989) les preuves de sécurité et les attaques sur ces schémas ont été améliorées à plusieurs reprise.Dans cet exposé je vais présenter mes trois articles sur le sujet. Ces articles portent sur :
1) Les meilleures attaques connues
2) Les preuves de sécurités en admettant un résultat de combinatoire
3) La preuve du résultat de combinatoire que nous utilisons en 2).
La conclusion principale est :
a) Qu'un schéma de Feistel aléatoire en 5 tours est indistinguable d'une permutation aléatoire sur 2n bits tant que le nombres de messages choisis est petit devant 2^n. (Au lieu de 2^(n/2) pour 4 tours et Luby et Rackoff).
b) Que néanmoins on recommande de prendre au minimum 6 tours car à partir de 6 tours il semble (c'est non prouvé) que le nombre de calculs à faire pour distinguer est en 2^2n, alors que pour 5 tours il est en 2^n. (Au lieu de 2^(n/2) pour 4 tours).