Coefficient H

Technique de preuve cryptographique

En cryptologie, la technique des coefficients H[1], aussi appelée technique de décorrélation[2], est une méthode permettant de prouver la sécurité de constructions cryptographiques, en particulier les algorithmes de chiffrement par bloc. Elle constitue une alternative aux preuves par jeux, qui reposent souvent sur des arguments hybrides[3], et aux preuves d'indifférentiabilité qui nécessitent un simulateur[4].

La technique a été introduite par le cryptologue français Jacques Patarin en 1991[5],[6],[7] pour l'analyse des constructions de Luby-Rackoff (dont DES est l'archétype), et formalisée autour de 2008[1],[2],[8]. Cette technique a notamment permis d'étudier précisément la sécurité des constructions d'Even-Mansour[3],[9] (dont AES est un exemple) et les codes d'authentification CBC-MAC[10].

L'objectif de la technique des coefficients H est de borner l'avantage d'un adversaire dont l'objectif est de distinguer deux systèmes aléatoires. En général, l'un des systèmes correspond à l'objet réel dont on souhaite prouver la sécurité (par exemple un chiffrement par bloc) et l'autre système est un modèle idéalisé (par exemple une permutation pseudo-aléatoire). L'analyse porte sur une étude combinatoire des échanges entre l'adversaire et chaque système (réel ou idéal), appelés dans ce contexte « transcriptions ». L'ensemble des transcriptions est réparti en deux catégories : les transcriptions « bonnes » (qui correspondent sommairement à un bon accord entre l'objet réel et l'objet idéal) et les « mauvaises ». Ces dernières correspondent à des situations dans lesquelles l'objet étudié se comporte de façon différente de son homologue idéalisé : si elles sont trop nombreuses cela facilite le travaille d'un attaquant.

Il est alors possible de fournir une borne sur l'avantage adversarial, ou dans de nombreux cas lorsqu'une telle borne ne peut être obtenue, de construire explicitement une attaque puisqu'on obtient immédiatement un distingueur.

Histoire et variantesModifier

La technique des coefficients H a été formalisée, avec ce nom, en 2008 par Jacques Patarin[1]. Cependant on en retrouve l'usage dans plusieurs travaux antérieurs [6],[11],[12],[13],[14], y compris dans sa thèse[7] puis celle de Serge Vaudenay[15]. De façon indépendante, Daniel Bernstein introduit en 1999 sous le nom de « théorème d'interpolation » un résultat qui est en fait une variante de la technique des coefficients H[16],[17]. Les origines fragmentaires, en français, et le manque de clarté dans les premiers travaux présentant la technique ont beaucoup freiné son adoption[9]. À partir de 2014, plusieurs travaux ont donc revisité l'approche, clarifiant et simplifiant substantiellement la présentation et permettant une utilisation de la technique dans plus de contextes que ce qui était faisable auparavant[18],[19],[20].

Quelques unes des constructions qui ont pu bénéficier d'une analyse au moyen de cette technique includent entre autres : les chiffrement de Feistel[13], MHCBC et MCBC[21], la construction d'Even-Mansour[9], CBC-MAC[22], EWCDM[23], OCB3[24], GCM-SIV[25].

Présentation de la techniqueModifier

Soit D un adversaire tentant de distinguer entre un modèle idéal et un objet réel[Note 1]. On note   l'ensemble des transcriptions possibles,   (resp.  ) la distribution de probabilités des transcriptions issues de l'objet réel (resp. issues du modèle idéal)[Note 2]. L'ensemble   est partitionné en deux sous-ensembles disjoints  [Note 3].

S'il existe   tels que pour tout  on a[26],[27] :

 
avec   et  , alors  , qui est ce que l'on cherche à démontrer.

Pour cela, la technique des coefficients H consiste à introduire une quantité   définie comme suit. Fixons un entier positif N, notons   l'ensemble des chaînes de N bits et soit  une séquence d'éléments deux à deux distincts de  . Soit   une séquence d'éléments de  . On note   — ou simplement   si le contexte de   et   est clair — le nombre d'éléments   tels que:

 
  est un ensemble fixé (dont les éléments seront appelés les « clés ») et   est la fonction dont nous voulons étudier la sécurité, dépendant de la situation étudiée. Pour chaque clé  ,   est ainsi une fonction de   dans  . Ainsi,   compte le nombre de clés qui envoient toutes les entrées   vers les valeurs  . Si on parvient à borner  , alors on obtient en appliquant le résultat ci-dessus une borne sur l'avantage de l'attaquant.

Premières applicationsModifier

Les théorèmes qui suivent constituent des cas importants, et sont les bases de la technique générale de preuve. L'objectif est de prouver des résultats de sécurité de générateurs de fonctions et de permutations. Les preuves sont mentionnées dans [1],[7],[28]. Avec cette technique, on obtient un jeu de conditions suffisantes pour établir la sécurité contre différentes classes d'adversaires. Des améliorations de la technique permettent d'obtenir des conditions nécessaires, et ainsi des bornes optimales[9]. Nous noterons ici KPA les attaques à clairs connus, CPA1 les attaques à clairs choisis non adaptatives, CPA2 les attaques à clairs choisis adaptatives et CCA2 les attaques à clairs et chiffrés choisis adaptatives.

Sécurité contre une attaque à clairs connusModifier

Soit   et   deux nombres réels,   et  . Si pour des valeurs aléatoires  , de   telles que les   sont des éléments deux à deux distincts, avec probabilité   nous avons  ; alors une attaque avec   clairs (aléatoires) connus possède un avantage borné  , dans le jeu consistant à distinguer   d'une fonction aléatoire. Ici comme dans la suite, cela signifie distinguer   lorsque   est tiré uniformément au hasard dans   d'une fonction   tirée uniformément parmi les fonctions de   dans  .

Sécurité contre une attaque à non adaptative clairs choisisModifier

Soit   et   deux nombres réels,   et  . Si pour toutes les séquences  , de   éléments deux à deux distincts de  , il existe un sous-ensemble   de   tel que   et tel que pour toutes les séquences   de   nous avons  ; alors dans une attaque non adaptative avec   clairs choisis nous avons :  , dans le jeu constitant à distinguer   d'une fonction aléatoire.

Sécurité contre une attaque adaptative à clairs choisisModifier

Soit   et   deux nombres réels,   et  . Soit   un sous-ensemble de   tel que  . Si pour toutes les séquences  , d'éléments deux à deux distincts de   et pour toutes les séquences  , de   nous avons  ; alors pour une attaque adaptative avec   clairs choisis nous avons :  , dans le jeu constitant à distinguer   d'une fonction aléatoire.

Attaques à clairs et chiffrés choisisModifier

Sécurité contre une attaque adaptative à clairs et chiffrés choisisModifier

Soit   un nombre réel,  . Si pour toutes les séquences d'éléments deux à deux distincts  , et pour toutes les séquences d'éléments deux à deux distincts  , nous avons   ; alors dans une attaque adaptative avec   clairs ou chiffrés choisis nous avons  , où cette fois l'avantage est considété dans le jeu constitant à distinguer   d'une permutation aléatoire de  .

Autre théorème plus général pour les attaques à clairs et chiffrés choisisModifier

Il est possible de généraliser ce résultat ainsi : soit   et   deux nombres réels,   et  . S'il existe un sous-ensemble   de   tel que :

  1. pour tout  , nous avons  ;
  2. pour chaque attaque adaptative à clairs et chiffrés choisis sur une permutation aléatoire  , la probabilité que   est   où ici   désigne les   ou  ,  , successifs qui vont apparaître ;

Alors pour chaque attaque adaptative à clairs et chiffrés choisis avec   clairs choisis nous avons :  , dans le jeu consistant à distinguer   d'une permutation aléatoire.

GénéralisationsModifier

Il y a beaucoup de variantes et de généralisations des théorèmes rappelés ci-dessus. Par exemple, les résultats sont aussi vrais si nous changeons   par  . Cependant, pour une utilisation cryptographique la première forme est généralement préférée, car il est plus souvent facile en pratique d'évaluer les exceptions où   est en moyenne nettement inférieure à la borne, plutôt que les exceptions se produisant quand   lui est nettement supérieure.

Notes et référencesModifier

Liens externesModifier

  • (en) Ashwin Jha et Nmridul Nandi, A Survey on Applications of H-Technique: Revisiting Security Analysis of PRP and PRF, 2019. ePrint IACR

NotesModifier

  1. En particulier, on ne suppose pas D limité dans ses capacités calculatoires.
  2. Les distributions   et   dépendent a priori de D, puisqu'elles dépendent des requêtes formulées par ce dernier.
  3. Le choix de cette partition n'est pas dicté par la technique et différentes partitions donnent des résultats différents. Une des difficultés consiste donc à trouver une bonne partition pour pouvoir appliquer la méthode.

RéférencesModifier

  1. a b c et d (en) Jacques Patarin, « The “Coefficients H” Technique », dans Selected Areas in Cryptography, Springer Berlin Heidelberg, (ISBN 9783642041587, DOI 10.1007/978-3-642-04159-4_21, lire en ligne), p. 328–345
  2. a et b (en) Serge Vaudenay, « Decorrelation: A Theory for Block Cipher Security », Journal of Cryptology, vol. 16, no 4,‎ , p. 249–286 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-003-0220-6, lire en ligne, consulté le 27 août 2018)
  3. a et b Benoît-Michel Cogliati, Le schéma d'Even-Mansour paramétrable : preuves de sécurité à l'aide de la technique des coefficients H, Université Paris-Saclay, (lire en ligne)
  4. (en) Ueli Maurer, Renato Renner et Clemens Holenstein, « Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology », dans Theory of Cryptography, Springer Berlin Heidelberg, (ISBN 9783540210009, DOI 10.1007/978-3-540-24638-1_2, lire en ligne), p. 21–39
  5. (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
  6. a et b (en) Jacques Patarin, « Pseudorandom permutations based on the D.E.S. scheme », dans EUROCODE '90, Springer Berlin Heidelberg, (ISBN 9783540543039, DOI 10.1007/3-540-54303-1_131, lire en ligne), p. 193–204
  7. a b et c Jacques Patarin, « Etude des generateurs de permutations pseudo-aleatoires bases sur le schema du D.E.S. », http://www.theses.fr/,‎ (lire en ligne, consulté le 27 août 2018)
  8. (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 27 août 2018)
  9. a b c et d (en) Shan Chen et John Steinberger, « Tight Security Bounds for Key-Alternating Ciphers », dans Advances in Cryptology – EUROCRYPT 2014, Springer Berlin Heidelberg, (ISBN 9783642552199, DOI 10.1007/978-3-642-55220-5_19, lire en ligne), p. 327–350
  10. (en) Serge Vaudenay, « Decorrelation over Infinite Domains: The Encrypted CBC-MAC Case », dans Selected Areas in Cryptography, Springer Berlin Heidelberg, (ISBN 9783540420699, DOI 10.1007/3-540-44983-3_14, lire en ligne), p. 189–201
  11. Jacques Patarin, « Improved security bounds for pseudorandom permutations », Proceedings of the 4th ACM conference on Computer and communications security - CCS '97, ACM Press,‎ (ISBN 0-89791-912-2, DOI 10.1145/266420.266452, lire en ligne, consulté le 13 mars 2020)
  12. Jacques Patarin, « About Feistel Schemes with Six (or More) Rounds », dans Fast Software Encryption, Springer Berlin Heidelberg, (ISBN 978-3-540-64265-7, lire en ligne), p. 103–121
  13. a et b Jacques Patarin, « Luby-Rackoff: 7 Rounds Are Enough for 2 n(1 − ε) Security », dans Advances in Cryptology - CRYPTO 2003, Springer Berlin Heidelberg,‎ (ISBN 978-3-540-40674-7, lire en ligne), p. 513–529
  14. Jacques Patarin, « Security of Random Feistel Schemes with 5 or More Rounds », dans Advances in Cryptology – CRYPTO 2004, Springer Berlin Heidelberg, (ISBN 978-3-540-22668-0, lire en ligne), p. 106–122
  15. Serge Vaudenay, « Decorrelation: A Theory for Block Cipher Security », Journal of Cryptology, vol. 16, no 4,‎ , p. 249–286 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-003-0220-6, lire en ligne, consulté le 13 mars 2020)
  16. Daniel J. Bernstein, « How to Stretch Random Functions: The Security of Protected Counter Sums », Journal of Cryptology, vol. 12, no 3,‎ , p. 185–192 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s001459900051, lire en ligne, consulté le 13 mars 2020)
  17. Mridul Nandi, « The Characterization of Luby-Rackoff and Its Optimum Single-Key Variants », dans Progress in Cryptology - INDOCRYPT 2010, Springer Berlin Heidelberg, (ISBN 978-3-642-17400-1, lire en ligne), p. 82–97
  18. Shan Chen et John Steinberger, « Tight Security Bounds for Key-Alternating Ciphers », dans Advances in Cryptology – EUROCRYPT 2014, Springer Berlin Heidelberg, (ISBN 978-3-642-55219-9, lire en ligne), p. 327–350
  19. Bart Mennink, « Optimally Secure Tweakable Blockciphers », dans Fast Software Encryption, Springer Berlin Heidelberg, (ISBN 978-3-662-48115-8, lire en ligne), p. 428–448
  20. Nicky Mouha, Bart Mennink, Anthony Van Herrewege et Dai Watanabe, « Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers », dans Selected Areas in Cryptography -- SAC 2014, Springer International Publishing, (ISBN 978-3-319-13050-7, lire en ligne), p. 306–323
  21. Mridul Nandi, « Two New Efficient CCA-Secure Online Ciphers: MHCBC and MCBC », dans Progress in Cryptology - INDOCRYPT 2008, Springer Berlin Heidelberg, (ISBN 978-3-540-89753-8, lire en ligne), p. 350–362
  22. Ashwin Jha et Mridul Nandi, « Revisiting structure graphs: Applications to CBC-MAC and EMAC », Journal of Mathematical Cryptology, vol. 10, nos 3-4,‎ (ISSN 1862-2976 et 1862-2984, DOI 10.1515/jmc-2016-0030, lire en ligne, consulté le 13 mars 2020)
  23. Benoît Cogliati et Yannick Seurin, « EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC », dans Advances in Cryptology – CRYPTO 2016, Springer Berlin Heidelberg, (ISBN 978-3-662-53017-7, lire en ligne), p. 121–149
  24. Ritam Bhaumik et Mridul Nandi, « Improved Security for OCB3 », dans Advances in Cryptology – ASIACRYPT 2017, Springer International Publishing, (ISBN 978-3-319-70696-2, lire en ligne), p. 638–666
  25. Priyanka Bose, Viet Tung Hoang et Stefano Tessaro, « Revisiting AES-GCM-SIV: Multi-user Security, Faster Key Derivation, and Better Bounds », dans Advances in Cryptology – EUROCRYPT 2018, Springer International Publishing, (ISBN 978-3-319-78380-2, lire en ligne), p. 468–499
  26. (en) Shan Chen et John Steinberger, « Tight Security Bounds for Key-Alternating Ciphers », dans Advances in Cryptology – EUROCRYPT 2014, Springer Berlin Heidelberg, (ISBN 9783642552199, DOI 10.1007/978-3-642-55220-5_19, lire en ligne), p. 327–350
  27. (en) Bart Mennink, « Introduction to provable security : IACR School on Design and Security of Cryptographic Algorithms and Devices »,
  28. (en) Valérie Nachef, Jacques Patarin et Emmanuel Volte, Feistel Ciphers, Springer,