Aller au contenu

« Construction de Luby-Rackoff » : différence entre les versions

Ajouter des liens
Un article de Wikipédia, l'encyclopédie libre.
Navigation interactive dans l’historique
← Modification précédente
Contenu supprimé Contenu ajouté
VisuelWikicode
Metamorforme42 (discuter | contributions)
24 448 modifications
m Remplacement de {{Lien}} par un lien interne, suite à la création de l'article correspondant
 
(2 versions intermédiaires par 2 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
{{ébauche|cryptologie}}
{{ébauche|cryptologie}}


En [[cryptologie]], la '''construction de Luby-Rackoff''' est une technique permettant de construire des [[Permutation|permutations]] dont on peut [[Preuve de sécurité|prouver]] qu'elles se comportent pratiquement comme des [[permutation pseudo-aléatoire|permutations pseudo-aléatoires]], si on suppose l'existence de [[Fonction pseudo-aléatoire|fonctions pseudo-aléatoires]]. De telles permutations jouent un rôle important dans la conception de cryptosystèmes, notamment des [[Chiffrement par bloc|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é<ref name=":0">{{Chapitre|langue=en|prénom1=Johannes|nom1=Gehrke|prénom2=Daniel|nom2=Kifer|prénom3=Ashwin|nom3=Machanavajjhala|prénom4=Arjen K.|nom4=Lenstra|titre chapitre=Luby-Rackoff Ciphers|titre ouvrage=Encyclopedia of Cryptography and Security|éditeur=Springer US|date=2011|isbn=9781441959058|doi=10.1007/978-1-4419-5906-5_590|lire en ligne=http://www.springerlink.com/index/10.1007/978-1-4419-5906-5_590|consulté le=2018-08-24|passage=736–737}}</ref>{{,}}<ref group="Note">Un exemple notable est la cryptanalyse initiale de [[DEAL (cryptologie)|DEAL]], qui est basé sur une construction de Luby-Rackoff de profondeur 7 ou 8.</ref>.
La '''construction de Luby-Rackoff''' est une technique pour édifier des [[permutation pseudo-aléatoire|permutations pseudo-aléatoires]] à partir de [[fonction pseudo-aléatoire|fonctions pseudo-aléatoires]] basées sur le principe de conception de [[Data Encryption Standard|DES]]. Un [[algorithme de chiffrement par bloc]] peut être considéré comme une permutation pseudo-aléatoire, donc cette technique fait partie de la théorie des algorithmes de chiffrement par bloc.


La construction s'appuie sur les '''théorèmes de Luby-Rackoff<ref name=":2" />,''' énoncés en 1988 par [[Michael Luby]] et [[Charles Rackoff]]<ref>{{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.</ref>, et dont l'importance dépasse cette seule utilisation<ref name=":1">{{Chapitre|langue=en|prénom1=Jacques|nom1=Patarin|titre chapitre=New Results on Pseudorandom Permutation Generators Based on the Des Scheme|titre ouvrage=Advances in Cryptology — CRYPTO ’91|éditeur=Springer Berlin Heidelberg|date=1991-08-11|isbn=9783540551881|doi=10.1007/3-540-46766-1_25|lire en ligne=https://link.springer.com/10.1007/3-540-46766-1_25|consulté le=2018-08-24|passage=301–312}}</ref>{{,}}<ref>{{Article|langue=anglais|auteur1=|prénom1=Moni|nom1=Naor|prénom2=Omer|nom2=Reingold|titre=On the construction of pseudo-random permutations: Luby-Rackoff revisited (extended abstract)|périodique=STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing|éditeur=ACM|date=1997-05-04|isbn=0897918886|issn=|doi=10.1145/258533.258581|lire en ligne=http://dl.acm.org/citation.cfm?id=258533.258581|consulté le=2018-08-24|pages=189–199}}</ref>.
L'article initial<ref>{{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.</ref> par {{lien|Michael Luby}} et [[Charles Rackoff]] a été publié en 1988. Cette technique a engendré un domaine de recherche à partir duquel plusieurs applications et généralisations ont été développées. Au moins 170 articles de recherche citent l'article initial<ref>{{en}} [http://citeseer.ist.psu.edu/context/33251/0 Citations sur CiteSeer]</ref>.


{{Théorème|énoncé=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.|nom=Théorème de Luby-Rackoff}}{{Théorème|énoncé=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.|nom=Théorème fort de Luby-Rackoff}}
==Détails==
La méthode consiste en la [[Composition (programmation)|composition]] de trois ou quatre [[schéma de Feistel|permutations de Feistel]], chacune nécessitant l'évaluation d'une fonction pseudo-aléatoire.


Les longueurs, de 3 et 4 respectivement, sont optimales<ref>{{Chapitre|langue=en|prénom1=William|nom1=Aiello|prénom2=Ramarathnam|nom2=Venkatesan|titre chapitre=Foiling Birthday Attacks in Length-Doubling Transformations|titre ouvrage=Advances in Cryptology — EUROCRYPT ’96|éditeur=Springer Berlin Heidelberg|date=1996|isbn=9783540611868|doi=10.1007/3-540-68339-9_27|lire en ligne=https://link.springer.com/10.1007/3-540-68339-9_27|consulté le=2018-08-24|passage=307–320}}</ref>{{,}}<ref name=":1" />. 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<ref>{{Article|langue=anglais|auteur1=|prénom1=Oded|nom1=Goldreich|prénom2=Shafi|nom2=Goldwasser|prénom3=Silvio|nom3=Micali|titre=How to construct random functions|périodique=Journal of the ACM (JACM)|volume=33|numéro=4|date=1986-08-10|issn=0004-5411|doi=10.1145/6490.6503|lire en ligne=http://dl.acm.org/citation.cfm?id=6490.6503|consulté le=2018-08-24|pages=792–807}}</ref>, on obtient une chaîne de [[Réduction (complexité)|réductions]] : <math>\mathrm{PRNG} \leq \mathrm{VRF} \leq \mathrm{PRP}</math>.
==Généralisations==
Entre autres, [[Moni Naor]] et [[Omer Reingold]] ont simplifié l'approche initiale dans un article de [[1999]]<ref>{{en}} M. Naor and O. Reingold, ''On the construction of pseudo-random permutations: Luby-Rackoff revisited'', Journal of Cryptology, vol. 12, 1999. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/lr.ps Article en ligne en format postscript]</ref>.
⚫
==Notes ==
⚫
<references/>


Depuis leur première preuve en 1988, les théorèmes de Luby-Rackoff ont été simplifiés et étendus de plusieurs manières<ref>{{Chapitre|langue=en|prénom1=Ueli M.|nom1=Maurer|titre chapitre=A Simplified and Generalized Treatment of Luby-Rackoff Pseudorandom Permutation Generators|titre ouvrage=Advances in Cryptology — EUROCRYPT’ 92|éditeur=Springer Berlin Heidelberg|date=1992-05-24|isbn=9783540564133|doi=10.1007/3-540-47555-9_21|lire en ligne=https://link.springer.com/10.1007/3-540-47555-9_21|consulté le=2018-08-24|passage=239–255}}</ref>{{,}}<ref name=":0" />{{,}}<ref>{{Chapitre|langue=en|auteur1=|prénom1=Jacques|nom1=Patarin|titre chapitre=Luby-Rackoff: 7 Rounds Are Enough for <math>2^{n(1-\epsilon)}</math> Security|auteurs ouvrage=|titre ouvrage=Advances in Cryptology - CRYPTO 2003|lieu=|éditeur=Springer Berlin Heidelberg|année=|date=2003|pages totales=|isbn=9783540406747|doi=10.1007/978-3-540-45146-4_30|lire en ligne=https://link.springer.com/10.1007/978-3-540-45146-4_30|consulté le=2018-08-24|passage=513–529}}</ref>{{,}}<ref>{{Chapitre|langue=en|prénom1=Ueli|nom1=Maurer|prénom2=Yvonne Anne|nom2=Oswald|prénom3=Krzysztof|nom3=Pietrzak|prénom4=Johan|nom4=Sjödin|titre chapitre=Luby-Rackoff Ciphers from Weak Round Functions?|titre ouvrage=Advances in Cryptology - EUROCRYPT 2006|éditeur=Springer Berlin Heidelberg|date=2006|isbn=9783540345466|doi=10.1007/11761679_24|lire en ligne=https://link.springer.com/10.1007/11761679_24|consulté le=2018-08-24|passage=391–408}}</ref>{{,}}<ref>{{Article|langue=en|prénom1=Gilles|nom1=Piret|titre=Luby–Rackoff Revisited: On the Use of Permutations as Inner Functions of a Feistel Scheme|périodique=Designs, Codes and Cryptography|volume=39|numéro=2|date=2006-05|issn=0925-1022|issn2=1573-7586|doi=10.1007/s10623-005-3562-2|lire en ligne=https://link.springer.com/10.1007/s10623-005-3562-2|consulté le=2018-08-24|pages=233–245}}</ref>{{,}}<ref>{{Chapitre|langue=en|prénom1=David|nom1=Goldenberg|prénom2=Susan|nom2=Hohenberger|prénom3=Moses|nom3=Liskov|prénom4=Elizabeth Crump|nom4=Schwartz|titre chapitre=On Tweaking Luby-Rackoff Blockciphers|titre ouvrage=Advances in Cryptology – ASIACRYPT 2007|éditeur=Springer Berlin Heidelberg|date=2007-12-02|isbn=9783540768999|doi=10.1007/978-3-540-76900-2_21|lire en ligne=https://link.springer.com/10.1007/978-3-540-76900-2_21|consulté le=2018-08-24|passage=342–356}}</ref>. Toutefois, les progrès dans la cryptanalyse des chiffrements à base de réseau de Feistel<ref name=":2">{{Ouvrage|langue=en|auteur1=|prénom1=Valerie|nom1=Nachef|prénom2=Jacques|nom2=Patarin|prénom3=Emmanuel|nom3=Volte|titre=Feistel Ciphers|passage=|lieu=|éditeur=|date=2017|pages totales=|isbn=|doi=10.1007/978-3-319-49530-9|lire en ligne=https://link.springer.com/10.1007/978-3-319-49530-9|consulté le=2018-08-24}}</ref>, 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]]<ref>{{Chapitre|langue=en|prénom1=Serge|nom1=Vaudenay|titre chapitre=On the Lai-Massey Scheme|titre ouvrage=Advances in Cryptology - ASIACRYPT’99|éditeur=Springer Berlin Heidelberg|date=1999|isbn=9783540666660|doi=10.1007/978-3-540-48000-6_2|lire en ligne=https://link.springer.com/10.1007/978-3-540-48000-6_2|consulté le=2018-08-24|passage=8–19}}</ref>) ont contribué à réduire la popularité des réseaux de Feistel utilisés dans la construction de Luby-Rackoff.
⚫
{{Portail|cryptologie|informatique théorique}}

==Notes et références ==

⚫
=== Notes ===
⚫
<references group="Note" />

=== Références ===
⚫
<references/>{{Palette|Sécurité prouvable}}{{Portail|cryptologie|informatique théorique}}
[[Catégorie:Algorithme de chiffrement par bloc]]
[[Catégorie:Algorithme de chiffrement par bloc]]
[[Catégorie:Cryptologie]]

Dernière version du 25 janvier 2022 à 20:46

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

[modifier | modifier le code]

Notes

[modifier | modifier le code]
  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

[modifier | modifier le code]
  1. ↑ a et b (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. ↑ a et b (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. ↑ a et b (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
v · m
Modèles de sécurité
Outils et techniques de preuve
Hypothèses calculatoires
Propriétés de sécurité
Modèles d'attaques
  • Attaque sans message (NMA)
  • Clairs/messages choisis (CPA/CMA)
  • Chiffrés choisis (CCA)
  • Chiffrés choisis de façon adaptative (CCA2)
  • Attaque par sondes (ISW)
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Construction_de_Luby-Rackoff&oldid=190233002 ».