Coefficient H
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 variantes
[modifier | modifier le code]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 technique
[modifier | modifier le code]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[9],[26] :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:où 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é, selon 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 applications
[modifier | modifier le code]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],[27]. 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 connus
[modifier | modifier le code]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 choisis
[modifier | modifier le code]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 consistant à distinguer d'une fonction aléatoire.
Sécurité contre une attaque adaptative à clairs choisis
[modifier | modifier le code]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 consistant à distinguer d'une fonction aléatoire.
Attaques à clairs et chiffrés choisis
[modifier | modifier le code]Sécurité contre une attaque adaptative à clairs et chiffrés choisis
[modifier | modifier le code]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 consistant à distinguer d'une permutation aléatoire de .
Autre théorème plus général pour les attaques à clairs et chiffrés choisis
[modifier | modifier le code]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 :
- pour tout , nous avons ;
- 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éralisations
[modifier | modifier le code]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érences
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Ashwin Jha et Nmridul Nandi, A Survey on Applications of H-Technique: Revisiting Security Analysis of PRP and PRF, 2019. ePrint IACR
Notes
[modifier | modifier le code]- En particulier, on ne suppose pas D limité dans ses capacités calculatoires.
- Les distributions et dépendent a priori de D, puisqu'elles dépendent des requêtes formulées par ce dernier.
- 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érences
[modifier | modifier le code]- (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
- (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 )
- 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)
- (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
- (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
- (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
- 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 )
- (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 )
- (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
- (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
- 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 )
- 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
- 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
- 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
- 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 )
- 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 )
- 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
- 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
- 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
- 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
- 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
- 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 )
- 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
- 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
- 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
- (en) Bart Mennink, « Introduction to provable security : IACR School on Design and Security of Cryptographic Algorithms and Devices »,
- (en) Valérie Nachef, Jacques Patarin et Emmanuel Volte, Feistel Ciphers, Springer,