Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 4
Cours de Cryptographie par H.
Ouadfel V - Sécurité Sémantique
CHAPITRE Sécurité 5 Sémantique
1 Sécurité calculatoire La notion de sécurité inconditionnelle exige d’utiliser des méthodes de chiffrement qui ont l’inconvénient de nécessiter des clés à usage unique et au moins aussi longues que les messages à chiffrer. Le masque jetable est optimal en ce sens que la taille de la clé est exactement égale à celle du message clair. A l’ère des communications électroniques où l’usage des méthodes de chiffrement touche presque tous les aspects de la vie moderne, le coût de la sécurité inconditionnelle est trop important pour être pratique, ce qui a ouvert la voie vers de nouvelles notions de sécurité où l’on serait capable d’utiliser des clés de tailles modérées un grand nombre de fois sans pour autant compromettre la sécurité de la communication au-delà d’un seuil jugé satisfaisant. On parle alors de sécurité calculatoire. Cette notion est définie compte tenu d’un adversaire qui disposerait d’une puissance de calcul importante mais finie par opposition au modèle de la sécurité inconditionnelle où l’adversaire serait doté d’une puissance de calcul infinie. On parle alors d’adversaire « efficace » pour signifier que l’adversaire est limité dans le temps qui lui est alloué pour mener son attaque contre la construction cryptographique en question. Dans le cas de la sécurité inconditionnelle, les messages qu’on pouvait chiffrer étaient implicitement tous de même taille. Le fait est que les messages qu’on peut chiffrer en réalité sont en général de tailles différentes. Malgré cela, la définition de la sécurité calculatoire sera définie contre des attaques qui excluent le gain d’information lié à la taille des messages chiffrés car il est difficile de dissimuler une telle information. Il faudra prévoir d’autres mécanismes pour le faire.
2 Modèle empirique Dans un tel modèle, la définition de la sécurité dépend d’un couple de nombres (t, ). Le paramètre t définit la durée maximale autorisée pour que l’adversaire A achève ses calculs et retourne un résultat. Ce paramètre dépend du type d’attaque qu’on souhaite contrecarrer, les ressources dont dispose l’adversaire sur le plan matériel (type et puissance de calcul de la V-1 Cours de Cryptographie par H. Ouadfel V - Sécurité Sémantique
machine ou des machines utilisées, la configuration en séries ou en parallèles de ces
machines, etc.) et sur le plan logiciel (système d’exploitation, langage de programmation, etc.). Le seuil définit l’avantage concédé à l’adversaire pour mener son attaque. Ce paramètre dépend du niveau de sécurité qu’on souhaite achever. En pratique, on aimerait que soit plus petit que 2-30 et même, des fois, plus petit que 2-60 suivant les applications. On parle alors d’un seuil négligeable. Le problème avec ce modèle est l’incertitude liée à la définition du premier paramètre t qui dépend de beaucoup de paramètres et qui s’apprête mal au développement théorique.
3 Modèle asymptotique Dans ce modèle, plus adapté au développement théorique, les paramètres t() et () sont des fonctions de : un paramètre qui définit le niveau de sécurité de la construction cryptographique. Il s’agit d’un nombre entier qu’on peut identifier en première approximation avec la taille n de la clé de chiffrement. En pratique, ce paramètre est confiné dans un intervalle de valeurs bien déterminées.
3.1 Comportement de t()
Dans ce modèle, l’efficacité de l’adversaire est définie selon la théorie de la complexité où l’adversaire est simulé par un algorithme A qui s’exécute en temps polynomial en la valeur de , c'est-à-dire, de temps t() O(d) pour un certaine constante d >0. Cela signifie que le temps d’exécution asymptotique t() de A (i.e., pour assez large) est majoré par une certaine puissance de .
3.2 Comportement de ()
Le seuil () est une fonction qu’on aimerait pouvoir décrire comme négligeable ou non dans le sens asymptotique du terme. Une fonction négligeable correspond à une fonction qui multipliée par n’importe quel polynôme unitaire p() de ne dépasse jamais la borne supérieure 1 au voisinage de l’infini. Par opposition une fonction non-négligeable, sera telle que le produit p()() dépassera la borne 1 au moins un nombre infini dénombrable de fois au voisinage de l’infini. Formellement :
3.2.1 Fonction négligeable (resp. non-négligeable)
La fonction : Z+ → R+ est dite négligeable si et seulement si :
V-2 Cours de Cryptographie par H. Ouadfel V - Sécurité Sémantique
d >0, 0 Z+, 0, () < 1/ d
Par opposition une fonction est non-négligeable si et seulement si : d >0, 0 Z+, 0, () 1/ d Exemples : () = 1/ 2 est une fonction négligeable, car, d, d/2 0 au voisinage de l’infini (l’exponentielle domine les polynômes) () = 1/ 1000 est une fonction non-négligeable (il suffit de choisir d = 1000) 1 / 2 si λ est pair ( ) est une fonction non-négligeable (il suffit de choisir d = 1000) 1 / 1000 si λ est impair
4 Sécurité sémantique Cette notion de sécurité calculatoire repose sur l’hypothèse que l’adversaire « efficace » dispose d’un message chiffré unique pour essayer de gagner une quelconque information sur le message clair correspondant. Reprenant le schéma utilisé précédemment pour définir la confidentialité parfaite au travers de l’expérience EXP(b). On apportera les changements suivants à ce schéma pour relaxer la condition de confidentialité parfaite jugée trop forte : Les attaques considérées seront restreintes à celles qui essayent de distinguer entre des messages clairs m0 et m1 de même taille. L’adversaire A, identifié avec un algorithme de calcul efficace, dispose de ressources finies et est donc limité dans le temps qui dépend du niveau de sécurité souhaité. On n’exige plus que l’attaquant soit incapable de gagner une quelconque information sur le message clair chiffré mais seulement qu’il ne puisse pas le faire avec un avantage non négligeable.
4.1 Jeu Adversaire - Challenger
Rappelons les étapes de l’expérience EXP(b) qui dépend du bit b {0, 1} compte tenu des changements énoncés plus haut: 1. L’adversaire A soumet au Challenger deux messages m0 et m1 de son choix mais de tailles égales. 2. Le Challenger choisit un niveau de sécurité , génère au hasard une clé k et choisit un bit b, puis, chiffre le message mb avec la clé k et envoie le message chiffré c = E(k, mb) à l’adversaire A. 3. Ce dernier examine c et retourne une estimation b’ du bit b (cf. schéma ci-dessous).
V-3 Cours de Cryptographie par H. Ouadfel V - Sécurité Sémantique
Challenger Transmission : Adversaire
Sécurité : Z+ (m0, m1) m0, m1 M Clé : k R K |m0| = |m1| Bit : b R {0, 1} c = E(k, mb) Expérience : EXP(b) b’ {0, 1}
4.2 Définition asymptotique de la sécurité sémantique
Rappelons la notation Wb = {EXP(b) = 1} pour désigner l’événement qui consiste pour A de retourner le bit b’ = 1 dans l’expérience EXP(b). On définit l’avantage de A par rapport à la sécurité sémantique de la construction cryptographique E = (E, D, G) par : AvSS(A, E) = |Pr(W0) - Pr(W1)| Définition _________________________________________________________________ On dira que la méthode de chiffrement est sémantiquement sûre si et seulement si : A : Algorithme « efficace », AvSS(A, E) ) où ) est une fonction négligeable. ___________________________________________________________________________ Autrement dit, quelque soit l’adversaire efficace A, il retournera b’= 1 dans l’une et l’autre des expériences, EXP(0) et EXP(1), avec des probabilités respectives dont l’écart ne dépasse jamais une fonction négligeable ). Ainsi, aucun adversaire efficace A ne peut distinguer avec un avantage non négligeable celui d’entre m0 et m1 qui a été chiffré. Exemple : Un système de chiffrement inconditionnellement sûr est sémantiquement sûr. En effet, nous avons vu que l’avantage qu’à un adversaire (efficace ou non) contre un tel chiffrement est nul. Le masque jetable est un exemple concret d’un système de chiffrement sémantiquement sûr (puisque inconditionnellement sûr).
