PICSI

Principe

Dans l'étude de la sécurité des algorithmes, nous avons présenté dans des attaques par distingueur qui comparent un système de chiffrement C à un système de chiffrement idéal C^* à l'aide d'une procédure de test (le distingueur) fournissant, pour un nombre q de requêtes au chiffrement C ou au chiffrement C^*, une réponse positive avec des probabilités différentes respectivement notées p et p^*. Si on obtient un avantage (|p−p^*|) suffisamment grand, cela signifie que l'on peut différencier C et C^* et donc ättaquer" l'algorithme C. Ce type d'études permet d'établir des bornes inférieures sur la probabilité de distinguer, avec un nombre de clairs et une complexité donnée, un algorithme cryptographique d'un chiffrement idéal. Luby et Rackoff dans [2] ont introduit une notion légèrement différente permettant de calculer des bornes supérieures sur la probabilité de distinguer, avec un nombre de clairs donné et des ressources de calcul illimitées, une construction cryptographique d'un chiffrement idéal : au lieu de distinguer des systèmes de chiffrement, ils ont utilisé la notion de distingueur sur des fonctions ou plus précisément ils ont comparé une fonction idéale à un schéma composé de fonctions idéales afin d'évaluer la qualité des schémas utilisés en chiffrement. Le principal exemple qu'ils ont développé est l'étude théorique d'un schéma de Feistel à trois étages. Ici, une fonction cryptographique dépendant de la clé peut être vue comme une fonction aléatoire associée avec une valeur de clé choisie aléatoirement. Ils prouvent la sécurité de ce schéma en comparant les distributions de probabilités entre la fonction de chiffrement engendrée par ce schéma et une fonction idéale. Ils démontrent ainsi une borne supérieure de sécurité sur l'avantage du distingueur obtenu. Après la publication de cet article, beaucoup d'autres études utilisant les principes de cette preuve de sécurité ont été menées. On peut citer ici la thèse de J. Patarin entièrement consacrée à ce sujet [3] qui replace la sécurité dans le modèle de Luby-Rackoff dans le cadre de la sécurité inconditionnelle définie par Shannon,... D'autres auteurs se sont également intéressés à d'autres schémas dérivés de celui de Feistel en prouvant leur sécurité dans le modèle de Luby-Rackoff ou à des modes opératoires d'algorithmes par blocs[1].

 

Références

[1]

M. Bellare, J. Kilian, and P. Rogaway. The security of cipher block chaining. In Advances in Cryptology -CRYPTO'94, Santa Barbara, Californie, États-Unis, pages 341-355. Lecture Notes in Computer Science 839, Springer-Verlag, 1994.

[2]

M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17, no. 2:373-386, 1988.

[3]

J. Patarin. Etudes des Générateurs de Permutations Pseudo-aléatoires Basés sur le Schéma du DES. PhD thesis, Université Paris VI, 1991.