Sémantiquement sécurisé

La sécurité d'une méthode de chiffrement va dépendre, certes de la méthode employée, mais surtout du temps et des moyens mis en œuvre par l'attaquant.

En effet on a vu que seule une clé égale à la taille du message pouvait garantir une confidentialité parfaite, or ceci est irréalisable en pratique puisque deux ordinateurs doivent pouvoir communiquer de façon sécurisée sans s'être au préalable rencontré : toute méthode réaliste de chiffrement va laisser fuiter de l'information.

Enfin comme la taille des clés est finie un algorithme brute force arrivera toujours in fine à casser décrypter le message chiffré. Selon les moyens et les personnes impliquées (d'un adolescent dans sa chambre à un état) cela pourra prendre plus ou moins de temps.

Sécurisé en temps

L'intérêt de la $(t, \epsilon)$-sécurité est qu'elle peut se mesurer expérimentalement. Par exemple si un algorithme brute force teste le déchiffrement pour toutes les clés de taille $s$ possibles et met $t$ secondes pour en tester une, sa probabilité de réussite au bout de $T$ seconde sera de $T \cdot (t/2^s)$. Ceci nous donne une borne maximum pour toute méthode de chiffrement :

Il est crucial de garder ceci en tête pour toujours vérifier que la méthode brute force ne soit pas utilisable en pratique. Pour cela on commence par déterminer la durée de vie du message chiffré :

La notion de $(t, \epsilon)$-sécurité est indissociable de l'algorithme qui décrypte et donc de sa complexité. Si l'algorithme est polynomial le ratio entre ce qu'il peut tester (de l'ordre de $\mathcal{O}(n^k)$) et l'espace à tester (de l'ordre de $\mathcal{O}(2^n)$) va très rapidement tendre vers $0$ ($10/2^{10}$ vaut déjà $10^{-3}$) et si l'algorithme est exponentiel il prendra rapidement trop de temps.

Paramètre de sécurité

Lorsque l'on calcule la complexité des algorithmes de décryptage on le fait (comme toujours) par rapports à la taille de ses entrées. Les entrées correspondent aux différents paramètres de la méthode de chiffrement :

Ce paramètre de sécurité permet d'exprimer la $(t, \epsilon)$-sécurité non plus en fonction du temps, mais comme un nombre d'opérations.

Tout comme le passage de la complexité temporelle (mesurable) à la complexité en nombre d'opérations (calculable) permet une étude plus théorique des performances d'un algorithme, le paramètre de sécurité va nous permettre de comparer les algorithme de déchiffrement de façon générale et abstraite :

Par exemple l'algorithme brute force pour lequel on ne lui accorde qu'un temps d'exécution polynomial, disons $\mathcal{O}(s^d)$, aura un avantage de $\epsilon = \mathcal{O}(\frac{s^d}{2^{s}})$ qui devient exponentiellement petit lorsque la taille de la clé $s$ augmente !

L'augmentation de la taille des clés va certes avoir un effet sur le temps du chiffrage mais ce sera surtout sur l'avantage d'un algorithme de décryptage que cela se fera sentir, s'il est exponentiellement petit par rapport au paramètre de sécurité :

Autre exemple, où la vitesse de calcul ne bénéficie pas forcément à l'adversaire :

Cette méthode permet de formaliser :

• l'utilisation de clés assez grandes pour que l'attaque brute force nécessite un temps exponentiel non réalisable
• l'utilisation d'adversaires dont les algorithmes de décryptage sont polynomiaux,
• que donner de l'information à un attaquant est acceptable s'il est exponentiellement petit par rapport à la taille de la clé.

C'est cette dernière notion que nous allons maintenant formaliser.

Sémantiquement Sécurisée

Si on ne possède que des fonctions négligeable pour décrypter un code on ne peut donc pas arriver à grand chose, ce qui permet d'être en sécurité :

La sécurité sémantique stipule qu'une méthode doit être sécurisé quelque soit l'algorithme efficace utilisé. Pour obtenir ce genre de résultat sans connaître tous les algorithmes possibles on utilise une modélisation statistique cherchant à mesurer l'écart entre la distribution produite par la méthode et la loi uniforme.

Classiquement ceci se formalise par la modélisation sous la forme d'un jeu.

Jeu de la reconnaissance

La confidentialité peut s'écrire sous la forme d'un jeu à deux joueurs :

• un adversaire qui essaie de trouver une information
• un testeur qui fournit des données à l'adversaire.

L'adversaire doit choisir parmi deux réalisations, la première issue d'une variable aléatoire $x \xleftarrow{D0} \{0, 1\}^t$ et la seconde de la variable aléatoire $x \xleftarrow{D1} \{0, 1\}^t$.

Le schéma du jeu est alors le suivant :

     testeur                              adversaire
    ---------                            ------------
    |       |                            |          |
 b  |  D0   |   x tiré selon D0 si b=0   |    D0    |   A(x) = b'
--->|  D1   |   x tiré selon D1 si b=1   |    D1    | ------------->
    |       | -------------------------> |          |
    ---------                            ------------

Et se déroule ainsi :

1. un bit $b \in \{0, 1\}$ est fournit au testeur choisi de façon uniforme
2. selon $b$ choisit soit une réalisation de $x \xleftarrow{D0} \{0, 1\}^t$ soit de $x \xleftarrow{D1} \{0, 1\}^{t}$
3. le testeur envoie $x$ à l'adversaire
4. l'adversaire répond un bit $b'$, résultat d'un algorithme efficace (ie. polynomial)
5. l'adversaire :
   • gagne si $b = b'$
   • perd si $b \neq b'$

Ce jeu explicite le fait que toute la cryptographie se résume à savoir si la suite générée par notre méthode de chiffrement est assez proche de l'aléatoire pour que l'on ne puisse pas, en pratique, en exploiter les différences.

L'adversaire possède un avantage si la probabilité que A(x)=b' coïncide avec $b$ soit supérieure à 1/2. Comme $P[b=1] = P[b=0] = 1/2$ cet avantage vaut :

Si l'adversaire $A$ n'a pas d'idée de comment gagner au jeu, il peut toujours répondre au hasard : au pire il a 50% de chance de gagner et $\epsilon(A) = 0$. Au contraire s'il ne se trompe jamais son avantage vaut $\epsilon(A) = 1$.

Pour se fixer les idée commençons par un exemple. On suppose que l'on cherche à différentier deux mots de $\{0, 1\}^t$, le premier issu a distribution constante de réalisation $\mathbb{0}$ ($D0$), le second d'une loi uniforme ($D1$). Comme :

• la probabilité d'obtenir n'importe quel mot de $\{0, 1\}^t$ vaut $1/2^t$ pour la loi uniforme,
• la probabilité d'obtenir $\mathbb{0}$ vaut 1 pour la fonction constante

On peut utiliser l'algorithme efficace $A$ suivant :

• $A(x)=0$ si $x=\mathbb{0}$
• $A(x)=1$ sinon

Dont l'avantage vaut :

Comme la seule façon de se tromper si $b=1$ est lorsque le mot $\mathbb{0}$ est tiré avec une probabilité $1/2^t$ et que l'on ne se trompe jamais si $b=0$ on a :

On est presque toujours assuré de gagner !

Le corollaire ci-après montre que l'avantage est également la différence entre gagner ou perdre en choisissant tout le temps $D0$ ou $D1$. C'est cette définition que nous utiliserons dans tous les autres jeux que nous définirons :

De là :

On cherchera toujours à obtenir un comportement sémantiquement sécurisé. Ceci est facilité par la remarque ci-dessous :

Jeu du chiffrement

Pour une méthode de chiffrement, trouver les distribution à tester peut se faire avec le jeu suivant où l'attaquant choisi deux mots à tester. Si la méthode est sémantiquement sécurisé cela signifie que la différence de distribution est négligeable et est donc une approximation réaliste de la confidentialité parfaite.

Le jeu consiste alors en 6 étapes :

1. le testeur choisit uniformément une clé $k$
2. un bit $b \in \{0, 1\}$ est fournit au testeur choisi de façon uniforme
3. l'adversaire choisit deux messages $m_0$ et $m_1$ de même taille à donner au testeur
4. le testeur renvoie à l'adversaire $E(k, m_b)$
5. l'adversaire répond un bit $b'$
6. l'adversaire :
   • gagne si $b = b'$
   • perd si $b \neq b'$

     testeur                      adversaire
    ---------        m0, m1      ------------
 b  |       | <----------------- |          |  A(c) = b'
--->|   k   |    E(k,mb) = c     |          | -------------------->
    |       | -----------------> |          |
    ---------                    ------------

Le jeu du chiffrement est un cas particulier du cas du jeu de la reconnaissance puisque l'on cherche à différentier la loi suivie par $E(k, m_0)$ de celle suivi par $E(k, m_1)$ lorsque $k$ est distribué de façon uniforme. Ce type d'attaque, bien qu'elle ne permet pas de déchiffrer les messages permet tout de même d'avoir des informations sur le type de message chiffré, par exemple si la réponse est positive (m0 = "oui") ou négative (m1 = "non").

Par exemple supposons que nous chiffrons/déchiffrons nos messages avec l'algorithme de Vigenère et que l'on chiffre des messages avec des clés de longueur $\vert k \vert\ = 2$. L'adversaire pourrait choisir m0 = "aa" et m1 = "ab" et décider de répondre 1 si c[1] ≠ c[0]. L'avantage de cet algorithme va être énorme puisque :

• $\Pr[b' = 1 \;\mid\; b = 1] = 1- \Pr[b' = 0 \;\mid\; b = 1]$. On ne peut répondre $b'=0$ alors que $b=1$ que si la lettre $a$ se chiffre avec la même lettre que $b$ ce qui arrive 26 fois (choisir la première lettre de $k$ entraîne sa deuxième). Donc $\Pr[b' = 1 \;\mid\; b = 1] = 1- 26/26^2 = 1-1/26$
• $\Pr[b' = 0 \;\mid\; b = 0] = 1$ on ne se trompe jamais si c'est m0 qui est encodé.

Pour notre algorithme on a donc un avantage de $\epsilon(A) = 1-1/26 \geq 95\%$ ce qui est très bon ! Attention, cela ne veut pas dire que le chiffrement de Vigenère est mauvais, juste que connaître la taille de la clé permet de reconnaître le chiffrement de messages connus.

Puisque l'adversaire peut choisir les 2 mots, il va prendre ceux ayant statistiquement le plus de différence : un avantage nul signifie que tous les mots sont équivalents :

Construction de méthode de chiffrement

Les méthodes sémantiquement sécurisées permettent construire une méthode de chiffrement bloc par bloc : si chaque bloc est sémantiquement sécurisé l'ensemble le sera aussi. Illustrons le en montrant que l'on peut créer un chiffre de Vernam sémantiquement sécurisé en partant d'un générateur de nombre aléatoire biaisé, du moment que le biais est négligeable.

Soit la distribution de Bernoulli biaisée $B$ telle que $B(1) = 1/2 + \epsilon/2$. et $B^t$ la distribution sur $\{0, 1\}^t$ où chaque bit est tiré indépendamment avec $B$. On essaie de comparer cette distribution au tirage uniforme $U$. L'avantage d'un algorithme permettant de discriminer les deux distribution est alors :

Étape 1 : génération de la clé

Le meilleur algorithme, appelons-le $A$, permettant de distinguer $B^t$ et $U$ va répondre $B^t$ si $B^t(x) > (1/2)^t$ et $U$ sinon. On ne suppose pas que cet algorithme soit efficace. Si $b=1$ signifie choisir la distribution de Bernoulli biaisée alors :

Où $\delta(x) = 1$ si $B^t(x) > (1/2)^t$ et $0$ sinon. De là :

Et donc :

En utilisant le fait que $\max(a, b) = \frac{1}{2}\cdot (a+b+|b-a|)$ on obtient :

Une autre astuce nous permet d'écrire tout cela de façon plus simple. Si $x = x_1\dots x_t$, on a en effet $B^t(x) = B(x_1) \cdot\dots\cdot B(x_i) \cdot\dots\cdot B(x_t)$ et donc :

Et en utilisant le fait que $A^n-B^n = (A-B)\sum_{0\leq i <n}(A^{n-i}B^i)$ on obtient :

Si $\epsilon$ est négligeable devant $t$ alors $(1+2\epsilon)^t= 1+2t\epsilon +o(\epsilon)$. On a alors que :

L'avantage est négligeable si $\epsilon$ l'est aussi.

Étape 2 : chiffrement

On peut utiliser ce qui précède pour créer un chiffrement statistiquement sécurisé en utilisant un chiffre de Vernam avec notre générateur aléatoire. Montrons que si $U$ est la loi uniforme sur $\{0, 1\}^t$ et $m$ un élément de $\{0, 1\}^t$, alors la loi de distribution associée à la variable aléatoire $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m$ est sémantiquement sécurisé.

Soit $C^t$ la loi de distribution associée à la variable aléatoire $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m$. Tout comme précédemment, le meilleur algorithme a comme avantage :

On effectue le même calcul que précédemment puisque lon a aussi $(1/2+\epsilon)^t\leq C^t(x) \leq (1/2+\epsilon)^t$ et on obtient $A\leq \frac{t\epsilon}{2} +o(\epsilon)$ si $\epsilon$ est négligeable.

Étape 3 : jeu de la reconnaissance

On en conclut que si $m_1$ et $m_2$ sont deux éléments de $\{0, 1\}^t$ alors les lois de distributions associées aux variables aléatoires $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m_1$ et $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m_2$ sont statistiquement sécurisées. En effet en notant $C^t$ et $D^t$ les lois de distributions associées à $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m_1$ et $(x \xleftarrow{B^t} \{0, 1\}^t) \oplus m_2$, on aura :

Comme ce calcul a été fait avec $m_0$ et $m_1$ quelconque, ce chiffrement est sémantiquement sécurisé pour des attaques de types Chosen-plaintext attackers.

Conclusion

Si on fait bien les choses (on verra qu'on peut se tromper si on ne fait pas attention), on peut construire une méthode de chiffrement sémantiquement sécurisée en chaînant des blocs de biais négligeable, tout comme en algorithmie une composition d'algorithmes de complexités polynomiales reste polynomiale.

Ceci va être utilisé intensivement par la suite où l'on construira chaque bloc de la méthode de chiffrement indépendamment les une des autres : si chaque bloc ne donne qu'un avantage négligeable toute la chaîne également.