Générateurs d’Aléa et Sécurité : Loi des Présences

Générateurs d’Aléa et Sécurité : Loi des
Présences

Sécurité cryptographique

Les principes de Kerckhoffs

À la fin du XIXe siècle, Auguste Kerckhoffs a posé des principes dont les plus importants sont les suivants : 1) « Le procédé de chiffrement ne doit pas être obligatoirement secret, et il doit pouvoir être en mesure de tomber entre les mains de l’ennemi sans inconvénient ». 28 Autrement dit, ce principe de Kerckhoffs requiert que la sécurité repose uniquement sur le secret de la clé partagée ; l’algorithme doit être public, ce qui permet d’établir des normes internationales :  Il est beaucoup plus facile pour les correspondants d’un réseau de garder le secret d’une clé courte que celui d’un algorithme.  Il est plus facile de changer la clé, en cas de compromission, que de remplacer l’algorithme.  Dans un réseau, il est plus facile aux correspondants d’utiliser le même algorithme, avec plusieurs clefs, plutôt que d’employer, chacun en ce qui le concerne, un algorithme différent. 2) « Un procédé de chiffrement doit être pratiquement, sinon mathématiquement indécryptable » Autrement dit, « il n’est pas nécessaire d’utiliser un schéma de chiffrement parfaitement secret, mais il suffit, à la place, d’utiliser un schéma de chiffrement qui ne peut pas être cassé dans un délai raisonnable avec une probabilité raisonnable de succès ». Aujourd’hui, les principes de Kerckhoffs sont compris comme des principes qui, non seulement préconisent que la sécurité ne doit pas dépendre du secret des algorithmes utilisés, mais, également, exigent que ces algorithmes soient rendus publics.

Les principes fondamentaux de la cryptographie moderne

Selon [2], trois principes fondamentaux sont établis : 1) La formalisation de la sécurité : Toute définition de la sécurité doit prendre la forme générale suivante : « Un schéma cryptographique est sûr si aucun attaquant, disposant d’une puissance spécifiée, ne peut réaliser une cassure spécifiée ». De ce point de vue, un schéma de chiffrement est sûr si tout attaquant qui dispose d’un texte chiffré ne parvient pas à retrouver la clé secrète, ne peut obtenir aucune information utile sur le texte clair à partir du texte chiffré, et ne peut calculer une quelconque fonction du texte clair à partir du texte chiffré. 2) L’énoncé précis et la validation des hypothèses : Si la sécurité inconditionnelle d’un schéma ne peut pas être prouvée et doit s’appuyer sur une hypothèse, une démonstration mathématique que « la construction est sûre si l’hypothèse est vraie » peut être fournie seulement s’il y a un exposé précis de ce qu’est cette hypothèse. 3) L’établissement de preuves rigoureuses de sécurité pour les actions à entreprendre : pour la simple raison que la sécurité d’un schéma cryptographique ne peut être contrôlée de la même manière que le logiciel. L’approche de la réduction cryptographique : Il faut noter que la plupart des preuves de sécurité en cryptographie moderne utilisent ce qu’on appelle « l’approche réductionniste » : « Étant donné qu’une hypothèse X est vraie, la construction Y est sûre conformément à la définition donnée « . La preuve de sécurité (appelée aussi sécurité prouvée ou sécurité par réduction) montre comment réduire un problème donné par l’hypothèse X au problème qui consiste à casser la construction Y. Plus précisément, la preuve de sécurité, en général, consiste à démontrer que s’il existe un attaquant 29 qui est capable de casser un système donné, et d’en compromettre ainsi la sécurité, alors grâce à cet attaquant on peut construire un autre attaquant capable de casser un système réputé cryptographiquement sûr. Nous considérons l’attaquant comme un algorithme efficace, appelé (la réduction), qui sort un résultat relatif au problème de sécurité posé. Il simule l’environnement de l’attaquant, et à l’aide d’un ou de plusieurs appels à l’attaquant, résout le problème algorithmique difficile. Figure 2.1 : Preuve de sécurité par la réduction Dans cette figure, à partir d’un attaquant A1 qui résout un problème P1, en temps (t1) avec une probabilité (ε1), on construit un attaquant A2 qui résout le problème P2 en temps (t2) avec une probabilité (ε2), et on réduit le problème P2 au problème P1 :  Problème P1 = « casser la construction Y »  Problème P2=« problème difficile (sous hypothèse X : factorisation, log discret en cryptographie à clés publiques) »  ∃ un attaquant A1 ⇒ ∃ un algorithme de résolution de P2  -∄ algorithme de résolution de P2 ⇒ ∄ attaquant A1  La réduction A2 simule parfois les oracles auxquels l’attaquant a accès (ex : oracle de déchiffrement) 

 Le Secret parfait (Sécurité inconditionnelle) 

 Définition « Un schéma de chiffrement II = (G, Ek, Dk), sur un espace des messages (X), est parfaitement secret si pour toute distribution de probabilités sur (X), tout message x ϵ X et tout texte chiffré y ϵ Y avec Pr [Y =y) > 0, alors : Pr [X= x | Y= y] = Pr [X = x] ». (1) Autrement dit, les distributions sur les messages clairs et les textes chiffrés sont indépendantes. Cette définition du secret parfait (c’est-à-dire de la sécurité inconditionnelle) peut être formulée d’une manière différente comme suit : 

 Indistinguabilité parfaite: « Un schéma de chiffrement II = (G, Ek, Dk) sur l’espace des messages (X) est parfaitement secret si et seulement si pour toute distribution de probabilité sur (X), tout couple de messages clairs (xo, x1) ϵ X et tout message chiffré y ϵY : Pr [Y=y | X=x0] = Pr [Y=y | X=x1] ». (2) Selon cette nouvelle formulation, pour deux messages clairs (x0, x1) ϵ X, les distributions Y(x0) et Y (x1) sont identiques : le texte chiffré ne fournit aucune information sur le message clair. Cette propriété est appelée « indistinguabilité parfaite » parce qu’il est impossible de distinguer un chiffré de x0 d’un chiffré de x1, du fait que la distribution sur le texte chiffré est la même dans chaque cas. 

 Indistinguabilité adverse

L’Indistinguabilité adverse formalise l’incapacité de l’attaquant (A) à distinguer le chiffrement d’un message clair donné du chiffrement d’un autre message clair, l’attaquant pouvant être considéré comme un algorithme réalisable qui sort un résultat relatif au problème de sécurité posé. Soient un schéma de chiffrement II = (G, E k, D k), une expérience notée SK impliquant la clé secrète et un attaquant (A) qui ne reçoit qu’un texte chiffré (y), et qui tente de rétablir le message clair correspondant ainsi que l’exécution de l’expérience notée SK II, A. La sortie de l’expérience est égale à ‘’1 ‘’ ou ‘’0’’ : ce qui veut dire que si SK II, A = 1, (A) a réussi, sinon il a échoué. Il est alors noté : « qu’un schéma de chiffrement II = (G, E k, D k) sur un espace de messages X est parfaitement secret si Ɐ l’attaquant A : Pr [SK II, A = 1] = ½ » (3)

Le One-Time-Pad : un système inconditionnellement sûr 

Appelé aussi crypto système de Vernam , du nom de son inventeur Gilbert Vernam ( 1917), qui fut Ingénieur à l’American Telephone and Telegraph Compagny, le One-Time-pad (OTP) ou Chiffrement à clé-une-fois, a été amélioré (1920) par Joseph O. Mauborgne, Chef du Service des Chiffres de l’Armée Américaine qui y rajouta la notion de clé aléatoire. Le One-Time-pad (OTP) offre un secret parfait : il utilise les procédés de substitution poly alphabétique (Substitution à double clé type ou genre Vigenère) avec des clés principales apériodiques qui doivent remplir les trois critères suivants : – Les clés doivent être au moins aussi longues que les messages à chiffrer. – Les caractères composant chaque clé doivent être choisis de façon totalement aléatoire (utilisation d’un générateur aléatoire ou pseudo aléatoire) – Toutes les clés sont équiprobables et chaque clé, ne doit être utilisée qu’une et une seule fois, après quoi elle est détruite (masque jetable). Si ces critères sont strictement respectés, le système permet d’atteindre un niveau de sécurité théorique absolue selon Claude Shannon (1949) et le décryptement est impossible.

 THEOREME DE SHANNON

Soit Π = (G, E k, D k) un schéma de chiffrement sur un espace de messages X, avec |X| = |K| = |Y|. Ce schéma est parfaitement secret si et seulement si : 1. Toute clé k ϵ K est choisie avec une probabilité égale 1 |𝐾| par algorithme (G) 2. Ɐ x ϵ X et Ɐ y ϵ Y, ∃ ! k ϵ K tel que y= E k (x). On prouve que la probabilité de connaître le message clair étant donné le texte chiffré est égale à la probabilité de connaître le clair. En utilisant l’entropie de Shannon : H (X/Y) = H (X) (X et Y sont indépendants). où H(X) représente l’entropie c.-à-d. le degré d’incertitude devant lequel se trouve le décrypteur, par rapport au clair, lorsqu’il détient le cryptogramme : H(X) = – ∑𝑥 𝑃(𝑋 = 𝑥) 𝑙𝑜𝑔2 𝑃(𝑋 = 𝑥) et H (X/Y)= H(X, Y)-H(Y) ≤ H(X) avec H(X, Y) = – ∑𝑥,𝑦 𝑃(𝑋 = 𝑥, 𝑌 = 𝑦) 𝑙𝑜𝑔2 𝑃(𝑋 = 𝑥, 𝑌 = 𝑦) (4) THEOREME : Si un système cryptographique est parfaitement secret, alors H(K) ≥ H(X). Ce qui veut dire qu’il y’a au moins autant d’incertitude sur les clés que sur les messages clairs. Le système est inconditionnellemnt sûr. (Cela signifie que même si l’attaquant disposait d’une puissance de calcul infinie, il ne pourrait jamais décrypter le message. Le mot « sécurité inconditionnelle » prend alors tout son sens). 2.4 La sécurité calculatoire (ou la sécurité pratique) [2, 6-9 ,10] [2] signale que la notion de secret parfait, introduite par Claude Shannon, 25 ans après l’invention de Vernam, est extrêmement forte ; les critères sont contraignants, pour la construction des crypto systèmes cryptographiquement sûrs, et cette notion n’est donc pas adaptée à des applications pratiques, notamment commerciales. Les exigences ont donc été revues, ce qui a permis d’introduire la notion de sécurité calculatoire, appelée aussi la sécurité pratique (moins forte et plus accessible que le secret parfait) sachant que la puissance de l’attaquant est illimitée. La plupart des crypto systèmes symétriques (DES, 3DES, IDEA, AES…etc) et des crypto systèmes à clés publiques (RSA, ElGamal, …etc.) sont concernés par la sécurité calculatoire. Cette approche calculatoire intègre deux assouplissements de la notion de secret parfait : a) la sécurité n’est assurée que contre les attaquants efficaces qui travaillent dans un temps raisonnable (le calcul se fait par un algorithme polynomial c.-à-d. un algorithme dont le nombre moyens d’opérations s’écrit p(n) où (p) est un polynôme et (n) la taille de la chaîne binaire initiale) ; b) et, ces attaquants peuvent potentiellement réussir à casser le schéma avec une très faible probabilité (ce qui certainement ne se produira jamais) Deux approches communes de la sécurité calculatoire ont été établies pour obtenir une théorie cohérente : l’approche concrète et l’approche asymptotique. 

L’approche concrète

L’approche concrète quantifie la sécurité d’un schéma de chiffrement donné en limitant explicitement la probabilité de succès maximale de n’importe quel attaquant pendant au plus une certaine durée de temps spécifiée. En d’autres termes, si (t, ε) sont deux constantes positives avec ε ≤1, alors concrètement la sécurité est définie comme suit : « Un schéma est (t, ε)-sûr si tout attaquant qui dispose d’un temps d’exécution égal au plus à (t) réussit à le casser avec une probabilité égale au plus à (ε) ». Compte tenu de cette définition, les Schémas de chiffrement à clefs secrètes modernes offrent une sécurité optimale dans le cas suivant : « Si la longueur de la clé est (n), un attaquant qui dispose d’un temps d’attaque (t) peut réussir à casser le schéma avec une probabilité égale au plus à (t / 2n ) ». 

L’approche asymptotique (sécurité asymptotique) 

La sécurité asymptotique est définie comme suit : « Un schéma de chiffrement est sûr si tout attaquant PPT (Probabilistic Polynomial Time – Algorithme en temps polynomial probabiliste.), réussit à le casser avec seulement une probabilité de succès négligeable ». Cette approche repose sur la théorie de la complexité : le temps de décryptement dont dispose l’attaquant ainsi que sa probabilité de succès sont des fonctions de certains paramètres plutôt que des nombres concrets. En générant, par exemple, des clés lors de l’utilisation d’un schéma de chiffrement, les utilisateurs choisissent une valeur (n) comme paramètre de sécurité, qu’ils supposent connue de tout attaquant du système. Le temps de décryptement dont dispose l’attaquant, le temps de chiffrement/déchiffrement des utilisateurs et la probabilité de succès de l’attaquant sont donc tous considérés comme des fonctions de (n).

 Calcul efficace 

 Le calcul efficace est un calcul qui peut être réalisé en temps polynomial probabiliste (PPT). Un algorithme probabiliste est celui qui a la capacité de réaliser des résultats de « tirage au sort, au hasard » ; il peut être vu comme un algorithme qui a accès à une source d’aléas qui délivre des bits aléatoires, uniformément répartis avec une probabilité d’apparition de 1 2 .

 Probabilité de succès négligeable

 En sécurité cryptographique, la notion de « petite probabilité de succès », est assimilée à une probabilité de succès aussi petite que n’importe quel polynôme inverse en (n). Une fonction qui croît plus lentement que tout polynôme inverse est appelée « fonction négligeable ». 33 DEFINITION : Une fonction (f) est négligeable si pour tout polynôme p (·), il existe un entier N tel que pour tous les entiers n> N, alors f (n) < 1 𝑝(𝑛) . On note généralement une fonction arbitraire négligeable par (negl).  Ainsi, si un attaquant peut réussir à casser un schéma de chiffrement avec une probabilité égale à 1 𝑝(𝑛) pour certains polynômes (positifs) (p), alors le schéma n’est pas sûr.  Cependant, si la probabilité pour que le schéma de chiffrement puisse être cassé est asymptotiquement plus petite que 1 𝑝(𝑛) quel que soit le polynôme (p), alors le schéma est sûr. Cela est dû au fait que la probabilité de succès de l’attaquant est tellement petite qu’elle est considérée comme insignifiante. Cette probabilité sont appelée « probabilités de succès négligeable ». 

La sécurité des crypto systèmes à clés secrètes 

(Sécurité sémantique – Indistinguabilité) Nous consacrons ce paragraphe à la sécurité des crypto systèmes à clés secrètes, catégorie à laquelle nous avons classé les générateurs de bits pseudo aléatoires (PRBG), et nous allons présenter deux définitions équivalentes de la sécurité de ces cryptos systèmes : la sécurité sémantique et l’indistinguabilité des chiffrements.

La sécurité sémantique

La définition de « la sécurité sémantique » est analogue à celle du « secret parfait » de Shannon : elle énonce qu’il est calculatoirement impossible à l’attaquant d’obtenir des informations sur le texte en clair à partir du texte chiffré. Il est impossible à l’attaquant d’extraire le moindre bit d’information sur le clair à partir du chiffré ; le texte chiffré n’apporte aucune information sur le texte en clair. 

 Définition (Sécurité sémantique) : Un schéma de chiffrement à clef secrète Π = (G, E k, D k) est sémantiquement sûr si pour tout attaquant (A) en temps polynomial probabiliste, pour toute fonction (f) sur l’espace des messages (X) et pour toute distribution de probabilité (X n), l’avantage de l’attaquant : AdvA= |Pr [A (E k (x)) = f (x)] – Pr [A’ (E k (x’)) = f (x)] | (5) est une fonction négligeable (negl(n)). Nous signalons que : – L’attaquant (A) du schéma de chiffrement à clé secrète 𝛱 = (G, E k, D k), contre la sécurité sémantique, est un algorithme qui doit retrouver une information f(x) sur le message clair (x) à partir du cryptogramme E k (x). – X = (X1, X2…) est une distribution telle que pour le paramètre de sécurité (n), le message clair est choisi en fonction de la distribution Xn. 34 – Pour tout (n), toutes les chaînes binaires dans Xn ont la même longueur. – G (1n ) choisit la clé k ← {0, 1} n toujours uniformément au hasard. Dans la définition, l’expression de l’avantage exprime qu’il n’y a pas de différence de probabilité de succès notable de l’algorithme (A) pour retrouver l’information f(x) qu’on lui fournisse le message chiffré E k (x) correspondant au clair (x) ou le message chiffré E k (x’) correspondant à un autre message clair (x’). Le cryptogramme E k (x) ne fournit aucune information sur la valeur de f (x). La sécurité sémantique est atteinte si l’avantage de l’attaquant est négligeable pour toute distribution de probabilité sur les messages clairs. 

 Conclusion

 Malheureusement, la définition de la sécurité sémantique est complexe et difficile à appliquer. Cependant, il y’a heureusement une définition équivalente qui est « l’indistinguabilité », et qui est beaucoup plus simple et accessible. Les définitions étant équivalentes, nous pouvons adopter celle liée à « l’indistinguabilité », étant données que les garanties de sécurité sont celles offertes par la sécurité sémantique. 

L’indistinguabilité 

 Rappels Dans la formalisation de l’indistinguabilté énoncée aux paragraphes 2.3.1.1 et 2.3.1.2, nous avons considéré une expérience d’indistinguabilité SK II, A dans laquelle l’attaquant (A) sort deux messages xo et x1 et le chiffrement de l’un de ces messages, choisi au hasard, en utilisant une clé générée de façon aléatoire. La formalisation 2.3.1.2 exprime qu’un schéma de chiffrement II est sûr si aucun attaquant (A) ne peut déterminer lequel des messages clairs (x0, x1) a été chiffré, avec une probabilité de succès meilleure que 1/2 (probabilité de tirage au sort). En d’autres termes, un schéma de chiffrement à clé secrète possède une propriété d’indistinguabilité si un attaquant (A) est incapable de dire si le texte chiffré qu’on lui présente provient de l’un ou de l’autre message clair, sachant que ce texte chiffré est établi à partir de l’un de ces deux messages clairs. 

 Définition (Indistinguabilité) 

Un schéma de chiffrement à clef secrète Π = (G, E k, D k) possède la propriété d’indistinguabilité si pour tout attaquant (A) en temps polynomial probabiliste et pour tout couple de messages (x0, x1), il vient : AdvA= |Pr [A (E k (x0)) =1] – Pr [A’ (E k (x1)) = 1] | (6) est une fonction négligeable ((negl(n)). Nous signalons que : – G (1 n ) choisit toujours la clé k ← {0, 1} n uniformément au hasard 35 – L’attaquant (A) d’un schéma de chiffrement à clé secrète 𝛱 = (G, E k, D k) contre la propriété de l’indistinguabilité est un algorithme à qui on fournit le cryptogramme E k (xi) d’un message clair (xi) choisi aléatoirement dans un ensemble de deux messages distincts de même longueur { x0, x1} et qui doit fournir à la sortie l’indice i ∊ { 0, 1}. Un des deux messages clairs est chiffré et le message chiffré est donné à l’attaquant. Il doit déterminer lequel des deux messages clairs a été chiffré. Si l’algorithme polynomial probabiliste exécuté ne permet pas de répondre avec une probabilité de succès significativement plus grande que le tirage au sort (½), il n’a aucun avantage. Et dans ce cas, on dit que le système est indistinguable vis à vis d’une attaque du niveau de puissance considéré. La propriété de l’indistinguabilité énonce que tout attaquant échoue pour tout couple de messages clairs (x0, x1). 2.5.2.3. Définition équivalente (Indistinguabilité) : Un schéma de chiffrement à clé secrète Π = (G, Ek, Dk) produit des chiffrements indistinguables, si pour tout attaquant (A), en temps polynomial probabiliste, il existe une fonction négligeable « negl» telle que : Pr [SK II, A (n) = 1] ≤ 1 2 + negl(n) (7) lorsque la probabilité concerne les éléments aléatoires utilisés par A ainsi que les éléments aléatoires utilisés pour l’expérience (choix de la clé et de toute autre variable aléatoire utilisée dans le processus de chiffrement). En conclusion, l’indistinguabilité s’exprime de la façon suivante : « Etant donnés deux messages clairs distincts et de même longueur, et le message chiffré de l’un d’eux, l’Attaquant ne peut déterminer en temps raisonnable, avec une probabilité de succès significativement plus grande que le tirage au sort (1/2), de quel message clair provient le message chiffré ». 

Equivalence de la sécurité sémantique et de l’indistinguabilité

 Compte tenu de la conclusion 2.5.1.2, il est techniquement plus facile de travailler avec la définition de l’indistinguabilité (par exemple, pour prouver qu’un schéma de chiffrement donné est sécurisé), plutôt qu’avec la notion de sécurité sémantique. Heureusement, il a été montré [11] que les définitions sont équivalentes : THEOREME (Equivalence de la sécurité sémantique et de l’Indistinguabilité) : Un schéma de chiffrement à clé secrète est sémantiquement sûr, si et seulement si, il a la propriété d’indistinguabilité. En d’autres termes, il fournit des chiffrements indistinguables en présence d’un attaquant (A), si et seulement si, il est sémantiquement sûr en présence de cet attaquant.