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

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

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

S'il existe $\epsilon _{1},\epsilon _{2}>0$ tels que pour tout $\tau \in {\mathcal {T}}_{1}$ on a[9] - [26] :

{\frac {\Pr[t_{\mathrm {r} }=\tau ]}{\Pr[t_{\mathrm {i} }=\tau ]}}\geq 1-\epsilon _{1}\qquad {\text{et}}\qquad \Pr[t_{\mathrm {i} }\in {\mathcal {T}}_{2}]\leq \epsilon _{2}

avec $t_{\mathrm {r} }\sim T_{\mathrm {r} }$ et $t_{\mathrm {i} }\sim T_{\mathrm {i} }$ , alors ${\mathsf {Adv}}(D)\leq \epsilon _{1}+\epsilon _{2}$ , qui est ce que l'on cherche à démontrer. Pour cela, la technique des coefficients H consiste à introduire une quantité $H$ définie comme suit. Fixons un entier positif N, notons $I_{N}$ l'ensemble des chaînes de N bits et soit $a=(a_{i})_{1\leq i\leq m}$ une séquence d'éléments deux à deux distincts de $I_{N}$ . Soit $b=(b_{i})_{1\leq i\leq m}$ une séquence d'éléments de $I_{N}$ . On note $H(a,b)$ — ou simplement $H$ si le contexte de $a_{i}$ et $b_{i}$ est clair — le nombre d'éléments $k\in K$ tels que:

\forall i,1\leq i\leq m,\quad G(k)(a_{i})=b_{i}

où $K$ est un ensemble fixé (dont les éléments seront appelés les « clés ») et $G$ est la fonction dont nous voulons étudier la sécurité, selon la situation étudiée. Pour chaque clé $k\in K$ , $G(k)$ est ainsi une fonction de $I_{N}$ dans $I_{N}$ . Ainsi, $H$ compte le nombre de clés qui envoient toutes les entrées $a_{i}$ vers les valeurs $b_{i}$ . Si on parvient à borner $H$ , alors on obtient en appliquant le résultat ci-dessus une borne sur l'avantage de l'attaquant.

Premières applications

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

Soit $\alpha$ et $\beta$ deux nombres réels, $\alpha >0$ et $\beta >0$ . Si pour des valeurs aléatoires $a_{i},b_{i},1\leq i\leq m$ , de $I_{N}$ telles que les $a_{i}$ sont des éléments deux à deux distincts, avec probabilité $\geq 1-\beta$ nous avons $H\geq |K|(1-\alpha )/2^{Nm}$ ; alors une attaque avec $m$ clairs (aléatoires) connus possède un avantage borné ${\mathsf {Adv}}^{\text{KPA}}\leq \alpha +\beta$ , dans le jeu consistant à distinguer $G$ d'une fonction aléatoire. Ici comme dans la suite, cela signifie distinguer $G(k)$ lorsque $k$ est tiré uniformément au hasard dans $K$ d'une fonction $f$ tirée uniformément parmi les fonctions de $I_{N}$ dans $I_{N}$ .

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

Soit $\alpha$ et $\beta$ deux nombres réels, $\alpha >0$ et $\beta >0$ . Si pour toutes les séquences $a=(a_{i}),1\leq i\leq m$ , de $m$ éléments deux à deux distincts de $I_{N}$ , il existe un sous-ensemble $E(a)$ de $I_{N}^{m}$ tel que $|E(a)|\geq (1-\beta )\cdot 2^{Nm}$ et tel que pour toutes les séquences $b=(b_{i}),1\leq i\leq m$ de $E(a)$ nous avons $H\geq |K|(1-\alpha )/2^{Nm}$ ; alors dans une attaque non adaptative avec $m$ clairs choisis nous avons : ${\mathsf {Adv}}^{\text{CPA1}}\leq \alpha +\beta$ , dans le jeu constitant à distinguer $G$ d'une fonction aléatoire.

Sécurité contre une attaque adaptative à clairs choisis

Soit $\alpha$ et $\beta$ deux nombres réels, $\alpha >0$ et $\beta >0$ . Soit $E$ un sous-ensemble de $I_{N}^{m}$ tel que $|E|\geq (1-\beta )\cdot 2^{Nm}$ . Si pour toutes les séquences $a_{i},1\leq i\leq m$ , d'éléments deux à deux distincts de $I_{N}$ et pour toutes les séquences $b_{i},1\leq i\leq m$ , de $E$ nous avons $H\geq |K|(1-\alpha )/2^{Nm}$ ; alors pour une attaque adaptative avec $m$ clairs choisis nous avons : ${\mathsf {Adv}}^{\text{CPA2}}\leq \alpha +\beta$ , dans le jeu constitant à distinguer $G$ d'une fonction aléatoire.

Attaques à clairs et chiffrés choisis

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

Soit $\alpha$ un nombre réel, $\alpha >0$ . Si pour toutes les séquences d'éléments deux à deux distincts $a_{i},1\leq i\leq m$ , et pour toutes les séquences d'éléments deux à deux distincts $b_{i},1\leq i\leq m$ , nous avons $H\geq |K|(1-\alpha )/2^{Nm}$ ; alors dans une attaque adaptative avec $m$ clairs ou chiffrés choisis nous avons ${\mathsf {Adv}}^{\text{CCA2}}\leq \alpha +{\frac {m(m-1)}{2\cdot 2^{N}}}$ , où cette fois l'avantage est considété dans le jeu constitant à distinguer $G$ d'une permutation aléatoire de $I_{N}$ .

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

Il est possible de généraliser ce résultat ainsi : soit $\alpha$ et $\beta$ deux nombres réels, $\alpha >0$ et $\beta >0$ . S'il existe un sous-ensemble $E$ de $(I_{N}^{m})^{2}$ tel que :

pour tout $(a,b)\in E$ , nous avons $H\geq |K|(1-\alpha )/2^{Nm}$ ;
pour chaque attaque adaptative à clairs et chiffrés choisis sur une permutation aléatoire $f$ , la probabilité que $(a,b)\in E$ est $\geq 1-\beta$ où ici $(a,b)$ désigne les $b_{i}=f(a_{i})$ ou $a_{i}=f^{-1}(b_{i})$ , $1\leq i\leq m$ , successifs qui vont apparaître ;

Alors pour chaque attaque adaptative à clairs et chiffrés choisis avec $m$ clairs choisis nous avons : ${\mathsf {Adv}}^{\text{PRF}}\leq \alpha +{\frac {m(m-1)}{2\cdot 2^{N}}}$ , dans le jeu consistant à distinguer $G$ d'une permutation aléatoire.

Généralisations

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 $H\geq |K|(1-\alpha )/2^{Nm}$ par $H\leq |K|(1+\alpha )/2^{Nm}$ . 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ù $H$ est en moyenne nettement inférieure à la borne, plutôt que les exceptions se produisant quand $H$ lui est nettement supérieure.

Notes et références

Liens externes

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

Notes

En particulier, on ne suppose pas D limité dans ses capacités calculatoires.
Les distributions $T_{\mathrm {r} }$ et $T_{\mathrm {i} }$ 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

(en) Jacques Patarin, « The “Coefficients H” Technique », dans Selected Areas in Cryptography, Springer Berlin Heidelberg, 2009 (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, n^o 4,‎ 1^er septembre 2003, 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)
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, 30 septembre 2016 (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, 2004 (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, 11 août 1991 (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, 1991 (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/,‎ 1^er janvier 1991 (lire en ligne, consulté le 27 août 2018)
(en) Gilles Piret, « Luby–Rackoff Revisited: On the Use of Permutations as Inner Functions of a Feistel Scheme », Designs, Codes and Cryptography, vol. 39, n^o 2,‎ mai 2006, 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)
(en) Shan Chen et John Steinberger, « Tight Security Bounds for Key-Alternating Ciphers », dans Advances in Cryptology – EUROCRYPT 2014, Springer Berlin Heidelberg, 2014 (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, 2001 (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,‎ 1997 (ISBN 0-89791-912-2, DOI 10.1145/266420.266452, lire en ligne, consulté le 13 mars 2020)
Jacques Patarin, « About Feistel Schemes with Six (or More) Rounds », dans Fast Software Encryption, Springer Berlin Heidelberg, 1998 (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,‎ 2003 (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, 2004 (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, n^o 4,‎ 1^er septembre 2003, p. 249–286 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-003-0220-6, lire en ligne, consulté le 13 mars 2020)
Daniel J. Bernstein, « How to Stretch Random Functions: The Security of Protected Counter Sums », Journal of Cryptology, vol. 12, n^o 3,‎ juin 1999, p. 185–192 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s001459900051, lire en ligne, consulté le 13 mars 2020)
Mridul Nandi, « The Characterization of Luby-Rackoff and Its Optimum Single-Key Variants », dans Progress in Cryptology - INDOCRYPT 2010, Springer Berlin Heidelberg, 2010 (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, 2014 (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, 2015 (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, 2014 (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, 2008 (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, n^os 3-4,‎ 1^er janvier 2016 (ISSN 1862-2976 et 1862-2984, DOI 10.1515/jmc-2016-0030, lire en ligne, consulté le 13 mars 2020)
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, 2016 (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, 2017 (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, 2018 (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 », 2015
(en) Valérie Nachef, Jacques Patarin et Emmanuel Volte, Feistel Ciphers, Springer, 2018

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.