Construction de Luby-Rackoff

En cryptologie, la construction de Luby-Rackoff est une technique permettant de construire des permutations dont on peut prouver qu'elles se comportent pratiquement comme des permutations pseudo-aléatoires, si on suppose l'existence de fonctions pseudo-aléatoires. De telles permutations jouent un rôle important dans la conception de cryptosystèmes, notamment des algorithmes de chiffrement par bloc, en ce qu'elles facilitent grandement l'analyse de leur sécurité. Il est toutefois important de noter que la construction de Luby-Rackoff est un modèle idéalisé[1],[Note 1].

La construction s'appuie sur les théorèmes de Luby-Rackoff[2], énoncés en 1988 par Michael Luby et Charles Rackoff[3], et dont l'importance dépasse cette seule utilisation[4],[5].

Théorème de Luby-Rackoff — Un réseau de Feistel, instancié avec une fonction pseudo-aléatoire, réalise une permutation calculatoirement indistinguable d'une permutation pseudo-aléatoire dès que la profondeur du réseau dépasse 3.

Théorème fort de Luby-Rackoff — Le théorème précédent reste vrai face à un adversaire doté d'un oracle d'inversion, pour un réseau de Feistel de longueur au moins 4.

Les longueurs, de 3 et 4 respectivement, sont optimales[6],[4]. D'un point de vue théorique, ce résultat montre que les fonctions pseudo-aléatoires (VRF) suffisent pour construire des permutations pseudo-aléatoires. Comme par ailleurs l'existence de générateurs pseudo-aléatoires (PRNG) permet classiquement de construire des VRF[7], on obtient une chaîne de réductions : .

Depuis leur première preuve en 1988, les théorèmes de Luby-Rackoff ont été simplifiés et étendus de plusieurs manières[8],[1],[9],[10],[11],[12]. Toutefois, les progrès dans la cryptanalyse des chiffrements à base de réseau de Feistel[2], des questions de performance, de nouveaux modèles d'attaque, et la découverte de nouvelles constructions pour le chiffrement par bloc (comme la construction de Lai-Massey[13]) ont contribué à réduire la popularité des réseaux de Feistel utilisés dans la construction de Luby-Rackoff.

Notes et références

Notes
  1. Un exemple notable est la cryptanalyse initiale de DEAL, qui est basé sur une construction de Luby-Rackoff de profondeur 7 ou 8.

Références
  1. (en) Johannes Gehrke, Daniel Kifer, Ashwin Machanavajjhala et Arjen K. Lenstra, « Luby-Rackoff Ciphers », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_590, lire en ligne), p. 736–737
  2. (en) Valerie Nachef, Jacques Patarin et Emmanuel Volte, Feistel Ciphers, (DOI 10.1007/978-3-319-49530-9, lire en ligne)
  3. (en) M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, vol. 17, no 2, pp. 373--386, April 1988.
  4. (en) Jacques Patarin, « New Results on Pseudorandom Permutation Generators Based on the Des Scheme », dans Advances in Cryptology — CRYPTO ’91, Springer Berlin Heidelberg, (ISBN 9783540551881, DOI 10.1007/3-540-46766-1_25, lire en ligne), p. 301–312
  5. (en) Moni Naor et Omer Reingold, « On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract) », STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM,‎ , p. 189–199 (ISBN 0897918886, DOI 10.1145/258533.258581, lire en ligne, consulté le )
  6. (en) William Aiello et Ramarathnam Venkatesan, « Foiling Birthday Attacks in Length-Doubling Transformations », dans Advances in Cryptology — EUROCRYPT ’96, Springer Berlin Heidelberg, (ISBN 9783540611868, DOI 10.1007/3-540-68339-9_27, lire en ligne), p. 307–320
  7. (en) Oded Goldreich, Shafi Goldwasser et Silvio Micali, « How to construct random functions », Journal of the ACM (JACM), vol. 33, no 4,‎ , p. 792–807 (ISSN 0004-5411, DOI 10.1145/6490.6503, lire en ligne, consulté le )
  8. (en) Ueli M. Maurer, « A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators », dans Advances in Cryptology — EUROCRYPT’ 92, Springer Berlin Heidelberg, (ISBN 9783540564133, DOI 10.1007/3-540-47555-9_21, lire en ligne), p. 239–255
  9. (en) Jacques Patarin, « Luby-Rackoff: 7 Rounds Are Enough for Security », dans Advances in Cryptology - CRYPTO 2003, Springer Berlin Heidelberg, (ISBN 9783540406747, DOI 10.1007/978-3-540-45146-4_30, lire en ligne), p. 513–529
  10. (en) Ueli Maurer, Yvonne Anne Oswald, Krzysztof Pietrzak et Johan Sjödin, « Luby-Rackoff Ciphers from Weak Round Functions? », dans Advances in Cryptology - EUROCRYPT 2006, Springer Berlin Heidelberg, (ISBN 9783540345466, DOI 10.1007/11761679_24, lire en ligne), p. 391–408
  11. (en) Gilles Piret, « Luby–Rackoff Revisited: On the Use of Permutations as Inner Functions of a Feistel Scheme », Designs, Codes and Cryptography, vol. 39, no 2,‎ , p. 233–245 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-005-3562-2, lire en ligne, consulté le )
  12. (en) David Goldenberg, Susan Hohenberger, Moses Liskov et Elizabeth Crump Schwartz, « On Tweaking Luby-Rackoff Blockciphers », dans Advances in Cryptology – ASIACRYPT 2007, Springer Berlin Heidelberg, (ISBN 9783540768999, DOI 10.1007/978-3-540-76900-2_21, lire en ligne), p. 342–356
  13. (en) Serge Vaudenay, « On the Lai-Massey Scheme », dans Advances in Cryptology - ASIACRYPT’99, Springer Berlin Heidelberg, (ISBN 9783540666660, DOI 10.1007/978-3-540-48000-6_2, lire en ligne), p. 8–19
  • Portail de la cryptologie
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.