Modèle du chiffre idéal

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En cryptologie, le modèle du chiffre idéal ou ICM[Note 1] est un cadre idéalisé dans lequel on peut espérer prouver la sécurité de certains algorithmes. Il suppose l'existence d'un oracle qui se comporte comme un chiffrement par bloc aléatoire, c'est-à-dire choisi uniformément au hasard parmi tous les chiffrements par bloc dont les paramètres (taille de clé et de l'entrée) sont identiques. Ce oracle est supposé public, et tous les participants à un jeu de sécurité peuvent l'interroger pour chiffrer le message de leur choix avec la clé de leur choix. Il est également possible d'effectuer des requêtes de déchiffrement, ici encore avec une clé choisie par le demandeur. Ce modèle cherche à abstraire les détails liés aux choix d'implémentation d'un chiffrement par bloc particulier dans une analyse de sécurité[1].

Le modèle du chiffre idéal remonte aux travaux de Claude Shannon en 1949[2],[3].

Ce modèle souffre toutefois de limitations similaires à celui de l'oracle aléatoire : il existe des constructions prouvées sûres dans ce modèle, qui sont complètement cassées dès que l'on remplace le chiffre idéal par n'importe quel chiffre concret[3]. Il s'est en fait avéré que les deux modèles sont équivalents[4],[5],[6]. Une autre limitation du modèle est liée à l'existence d'adversaires non uniformes, c'est-à-dire capables d'effectuer un calcul préliminaire « hors ligne » avant de s'attaquer au cryptosystème. Face à de tels adversaires, les estimations de sécurité produites dans le modèle du chiffre idéal sont trop optimistes[7].

Dans certains contextes, on suppose que la clé de chiffrement est fixée, c'est-à-dire que l'oracle se comporte comme une permutation — on parle alors du « modèle de la permutation idéale ».

Exemples importants[modifier | modifier le code]

  • La sécurité de MDC-2 contre le calcul de collisions a été démontrée dans le modèle du chiffre idéal[8].
  • La sécurité de MDC-4 contre le calcul de collisions et de préimages a été démontrée dans le modèle du chiffre idéal[9].
  • La sécurité de la construction d'Even-Mansour est démontrée dans le modèle de la permutation idéale[10].
  • La sécurité de DES-X a été démontrée dans le modèle du chiffre idéal[11].
  • La sécurité du surchiffrement a été analysée dans le modèle du chiffre idéal[12].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Pour l'anglais ideal cipher model.

Références[modifier | modifier le code]

  1. (en) Dan Boneh et Victor Shoup, « A Graduate Course in Cryptography : Block Ciphers (chap. 4.7) », sur toc.cryptobook.us, (consulté le 20 août 2018)
  2. (en) C. E. Shannon, « Communication Theory of Secrecy Systems* », Bell System Technical Journal, vol. 28, no 4,‎ , p. 656–715 (ISSN 0005-8580, DOI 10.1002/j.1538-7305.1949.tb00928.x, lire en ligne, consulté le 20 août 2018)
  3. a et b (en) John Black, « The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function », dans Fast Software Encryption, Springer Berlin Heidelberg, (ISBN 9783540365976, DOI 10.1007/11799313_21, lire en ligne), p. 328–340
  4. (en) Yevgeniy Dodis et Prashant Puniya, « On the Relation Between the Ideal Cipher and the Random Oracle Models », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783540327318, DOI 10.1007/11681878_10, lire en ligne), p. 184–206
  5. (en) Jean-Sébastien Coron, Jacques Patarin et Yannick Seurin, « The Random Oracle Model and the Ideal Cipher Model Are Equivalent », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540851738, DOI 10.1007/978-3-540-85174-5_1, lire en ligne), p. 1–20
  6. (en) Thomas Holenstein, Robin Künzler et Stefano Tessaro, « The equivalence of the random oracle model and the ideal cipher model, revisited », STOC '11 Proceedings of the forty-third annual ACM symposium on Theory of computing, ACM,‎ , p. 89–98 (ISBN 9781450306911, DOI 10.1145/1993636.1993650, lire en ligne, consulté le 20 août 2018)
  7. (en) Sandro Coretti, Yevgeniy Dodis et Siyao Guo, « Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models », dans Lecture Notes in Computer Science, Springer International Publishing, (ISBN 9783319968834, DOI 10.1007/978-3-319-96884-1_23, lire en ligne), p. 693–721
  8. (en) John P. Steinberger, « The Collision Intractability of MDC-2 in the Ideal-Cipher Model », dans Advances in Cryptology - EUROCRYPT 2007, Springer Berlin Heidelberg, (ISBN 9783540725398, DOI 10.1007/978-3-540-72540-4_3, lire en ligne), p. 34–51
  9. (en) Bart Mennink, « On the collision and preimage security of MDC-4 in the ideal cipher model », Designs, Codes and Cryptography, vol. 73, no 1,‎ , p. 121–150 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-013-9813-8, lire en ligne, consulté le 20 août 2018)
  10. (en) Shimon Even et Yishay Mansour, « A construction of a cipher from a single pseudorandom permutation », dans Advances in Cryptology — ASIACRYPT '91, Springer Berlin Heidelberg, (ISBN 9783540573326, DOI 10.1007/3-540-57332-1_17, lire en ligne), p. 210–224
  11. (en) Joe Kilian et Phillip Rogaway, « How to Protect DES Against Exhaustive Key Search (an Analysis of DESX) », Journal of Cryptology, vol. 14, no 1,‎ , p. 17–35 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s001450010015, lire en ligne, consulté le 20 août 2018)
  12. (en) Yuanxi Dai, Jooyoung Lee, Bart Mennink et John Steinberger, « The Security of Multiple Encryption in the Ideal Cipher Model », dans Advances in Cryptology – CRYPTO 2014, Springer Berlin Heidelberg, (ISBN 9783662443705, DOI 10.1007/978-3-662-44371-2_2, lire en ligne), p. 20–38