Avantage (cryptologie)

mesure de l'efficacité d'une attaque cryptographique distinguant deux situations

En cryptologie, la notion d'avantage mesure la capacité d'un adversaire a distinguer entre un objet cryptographique réel et un modèle idéalisé (ou plus généralement, entre deux situations). Essentiellement, l'avantage mesure à quel point l'adversaire fait « mieux que le hasard » dans cet exercice[1]. La notion a été introduite en 1982 par les cryptologues Shafi Goldwasser et Silvio Micali pour définir formellement la sécurité sémantique du chiffrement à clé publique[2].

L'avantage dépend du jeu de sécurité considéré, des pouvoirs de l'adversaire (généralement formalisés au moyen d'oracles), de la classe d'adversaires étudiée et éventuellement d'autres paramètres. En règle générale, on cherche à prouver que l'avantage est une fonction négligeable du paramètre de sécurité, ce qui garantit que l'objet cryptographique réel et son modèle idéalisé ne peuvent pas être distingués par un attaquant.

Plusieurs techniques classiques permettent d'obtenir une borne sur l'avantage dans un jeu donné, comme les arguments hybrides ou les coefficients H.

DéfinitionModifier

Soit   une classe d'adversaires[Note 1]. Pour tout  , on note   l'adversaire doté d'un accès aux oracles  .

On donne en plus à l'adversaire accès soit à (un oracle de) la véritable fonction cryptographique d'intérêt, soit à (un oracle de) la version idéalisée de celle-ci. L'objectif de l'adversaire est de distinguer entre ces deux situations, et de retourner 1 dans le premier cas et 0 dans le second[Note 2]. On définit alors l'avantage[3],[4],[5] :

 
  (resp.  ) est la fonction réelle (resp. idéale) considérée. Alternativement, on peut définir l'avantage en termes de distributions (ou de jeux) :
 
où cette fois on mesure la capacité de l'adversaire à distinguer entre une variable distribuée selon une loi D et une variable distribuée selon une loi D'.

La définition peut être ajustée en précisant les oracles ou les conditions de succès, afin de se spécialiser aux différents objets pseudo-aléatoires (PRNG, PRF, PRP...), donnant les notions de sécurité correspondante (sécurité sémantique etc.). Dans le cas général l'avantage dépend du nombre de requêtes effectuées auprès des oracles,  .

ExemplesModifier

Tirage biaiséModifier

Considérons une pièce de monnaie, assimilée à une variable aléatoire suivant une loi de Bernoulli de probabilité p. Le modèle idéal correspondant est une variable aléatoire de probabilité 1/2, et l'avantage adversarial dans ce contexte est alors  . Autrement dit, dès lors que   n'est pas négligeable, un adversaire pourra amplifier l'écart en répétant l'expérience et distinguer s'il a affaire à une pièce réelle ou idéale.

Argument hybrideModifier

Dans un argument hybride, on définit une séquence de jeux dans lesquels ont remplace progressivement un objet réel par un modèle idéalisé. Lorsque l'avantage entre deux tels jeux est négligeable, on peut ainsi petit à petit ramener la sécurité d'un système complexe réel à celle d'un système idéal.

Fonction pseudo-aléatoireModifier

On considère une famille de fonctions F prenant en entrée une clé k et une valeur x, et retournant une chaîne y de taille fixée. Le modèle idéal considéré est celui d'une fonction aléatoire g, et l'adversaire doit distinguer entre la fonction aléatoire et une fonction   dont la clé a été tirée uniformément au hasard parmi toutes les clés possibles. Cela correspond à l'avantage[6] :

 
lorsque cet avantage est négligeable, on dit que les fonctions F sont pseudo-aléatoires.

Notes et référencesModifier

NotesModifier

  1. En règle générale, on considère les machines de Turing probabilistes, éventuellement dotées d'une chaîne de référence, qui sont les modèles les plus pertinents en cryptologie.
  2. Naturellement, le rôle de 1 et 0 est ici symétrique, et le choix de quelle fonction correspond à 1 n'influence pas la définition.

RéférencesModifier

  1. (en) Phillip Rogaway, « On the Role Definitions in and Beyond Cryptography », dans Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making, Springer Berlin Heidelberg, (ISBN 9783540240877, DOI 10.1007/978-3-540-30502-6_2, lire en ligne), p. 13–32
  2. (en) Shafi Goldwasser et Silvio Micali, « Probabilistic encryption & how to play mental poker keeping secret all partial information », STOC '82 Proceedings of the fourteenth annual ACM symposium on Theory of computing, ACM,‎ , p. 365–377 (ISBN 0897910702, DOI 10.1145/800070.802212, lire en ligne, consulté le 28 août 2018)
  3. (en) David Wu, « Introduction du cryptography », sur crypto.stanford.edu
  4. (en) Mihir Bellare, « Modern Cryptography », sur cseweb.ucsd.edu (consulté le 28 août 2018)
  5. (en) Jonathan Katz et Yehuda Lindell, Introduction to modern cryptography : Principles and Protocols, Chapman & Hall/CRC, , 552 p. (ISBN 978-1-58488-551-1 et 1584885513, OCLC 137325053, lire en ligne)
  6. (en) Mihir Bellare, « Pseudo-random functions », sur cseweb.ucsd.edu