Coefficient H

En cryptologie, la technique des coefficients H, aussi appelée technique de décorrélation, 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, et aux preuves d'indifférentiabilité qui nécessitent un simulateur.

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

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. Cependant on en retrouve l'usage dans plusieurs travaux antérieurs , y compris dans sa thèse puis celle de Serge Vaudenay. 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. Les origines fragmentaires, en français, et le manque de clarté dans les premiers travaux présentant la technique ont beaucoup freiné son adoption. À 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.

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, MHCBC et MCBC, la construction d'Even-Mansour, CBC-MAC, EWCDM, OCB3, GCM-SIV.

Présentation de la technique

Soit D un adversaire tentant de distinguer entre un modèle idéal et un objet réel. 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). L'ensemble ${\mathcal {T}}$ est partitionné en deux sous-ensembles disjoints ${\mathcal {T}}={\mathcal {T}}_{1}\sqcup {\mathcal {T}}_{2}$.

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

$${\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 . 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. 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 consistant à 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 consistant à 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 consistant à 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 :

1. pour tout $(a,b)\in E$, nous avons $H\geq |K|(1-\alpha )/2^{Nm}$;
2. 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