Cryptographie!
Le plan de la partie : méthodes modernes de cryptographie >

Les protocoles d'identification

Besoins d'identification
  Dans de nombreux cas, on a besoin de s'identifier, c'est-à-dire de prouver qui l'on est. C'est le cas par exemple :
  • lorsqu'on souhaite accéder à son compte sur un ordinateur partagé entre plusieurs ordinateurs, ou à un réseau;
  • lors du paiement par carte bancaire; le code secret permet de vérifier que la personne qui présente la carte bancaire est bien le propriétaire de cette carte bancaire;
  • si l'on souhaite consulter à distance ses comptes bancaires;
  • lorsque deux objets électroniques distants (ordinateur et imprimante, téléphone et oreillette,…) souhaitent établir un dialogue sans fil distant;
  • si on veut prouver son identité à l'entrée dans un pays étranger. Les autorités souhaitent en particulier s'assurer que le passeport présenté n'a pas été falsifié.
Pour tous ses besoins, des protocoles cryptographiques plus ou moins sécurisés, plus ou moins contraignants, ont été inventés.
L'identification par mot de passe
  L'identification par mot de passe est sans doute la plus simple à mettre en oeuvre. On rentre sur l'ordinateur son nom d'utilisateur et son mot de passe $m$. L'ordinateur compare alors ce mot de passe à la valeur stockée dans sa base de données d'utilisateurs.

  En réalité, les choses sont un peu plus compliquées. La plupart du temps, l'ordinateur utilise une fonction $f$ à sens unique. Ceci signifie que s'il est facile de calculer $f(m)$, il est en revanche très difficile (dans l'idéal, impossible) de retrouver $m$ connaissant $f(m)$. Ce qui est stocké dans le fichier des utilisateurs n'est pas directement le mot de passe m, mais son image $f(m)$. Et lorsque l'utilisateur rentre son mot de passe $m$, l'ordinateur calcule $f(m)$ et le compare à la valeur qu'il a stockée dans sa base de données. Le principal avantage de procéder ainsi est que cela n'oblige pas à sécuriser la base de données puisqu'un attaquant, même s'il a accès à $f(m)$, ne pourra reconstituer $m$.

  Cela dit, même avec cette précaution, ce type d'identification par mot de passe simple n'offre pas une grande sécurité. Le premier problème vient de l'utilisateur lui-même. Souvent, les mots de passe utilisés sont des mots faciles à retenir. Un attaquant peut procéder à une attaque par dictionnaire, en essayant tous les mots de passe possibles dans un dictionnaire contenant par exemple les noms communs, les prénoms, des noms de ville,….

  Un autre problème est celui de la sécurité du canal de communication par lequel transite le mot de passe entre l'émetteur et le contrôleur. C'est ainsi par exemple qu'Ali Baba put ouvrir la caverne des 40 voleurs, simplement en écoutant leur mot de passe. Lorsqu'on s'identifie à distance, sur internet par exemple, il est tout à fait possible que quelqu'un intercepte toutes les communications entre l'émetteur et le récepteur. Une façon de remédier à ce problème est de faire en sorte que le mot de passe ne circule pas en clair sur le réseau. On fait alors appel aux protocoles de la cryptographie à clé publique, comme le protocole SSL par exemple.

  L'identification par mot de passe peut aussi se faire de façon physique, à l'aide d'une carte à puce ou par des empreintes digitales. On fait alors reposer la sécurité non pas sur ce qu'une personne sait, mais sur ce qu'une personne possède (carte à puce) ou sur ce qu'une personne est (empreintes digitales). Les attaques peuvent alors se faire directement sur l'intégrité de la personne, comme en lui coupant le doigt pour obtenir l'empreinte digitale!
L'identification par mot de passe à usage unique
  Pour éviter les problèmes d'interception du mot de passe, on peut faire en sorte que le mot de passe soit à usage unique : à chaque tentative d'identification, l'utilisateur doit fournir un mot de passe différent. Cela peut être mis en place à l'aide de plusieurs procédés :
  • une liste de mots de passe communiquée au préalable, et que l'on raye au fur et à mesure. Ceci ne permet qu'un nombre fini d'identifications, et il faut prendre garde de toujours être bien synchronisé. Et comme il est impossible de retenir un grand nombre de mots de passe, il faut en garder une trace écrite…qui pourrait bien être découverte!
  • un boitier qui délivre des mots de passe changeant par exemple toutes les minutes, et qui est synchronisé avec un dispositif semblable chez le récepteur. Bien sûr, le boitier peut-être confisqué et le coût est souvent prohibitif!
  • la fabriquation d'une succession de mots de passes à partir d'un mot de passe original. Pour cela, l'utilisateur se voit communiquer un mot de passe $w$ et une fonction $f$. Lors de la $n$-ième identification, il envoie comme mot de passe $f^n(w)$. Le récepteur calcule lui aussi $f^n(w)$ et compare les deux valeurs. Ceci a deux défauts : la synchronisation, et le fait que le mot de passe initial $w$ doit être conservé en clair par l'ordinateur sur lequel on essaie de s'identifier. Il faut donc veiller à sécuriser ce fichier de mots de passe.
Les protocoles défis/réponses
  Les protocoles défis/réponse sont aussi une réponse à l'écoute des canaux de communication des mots de passe. Ils fonctionnent généralement sur le principe suivant : le serveur choisit un défi (on dit aussi un challenge) auquel l'utilisateur ne peut répondre qu'en connaissant une information que lui seul (et le serveur) connait. Il donne sa réponse au serveur qui ainsi peut s'assurer de l'identité de l'utilisateur. Si les défis changent à chaque tentative d'identification, un attaquant ne pourra jamais deviner la réponse à fournir s'il essaie d'usurper l'identité d'un utilisateur.

  De façon concrète, les protocoles défis/réponses sont souvent implémentés de la façon suivante. On délivre à l'utilisateur un mot de passe $w$. A chaque tentative d'identification, le serveur lui envoie un nombre aléatoire $C$. L'utilisateur calcule alors une certaine fonction $E(w,C)$ et envoie cette réponse au serveur. Le serveur fait lui-même le calcul de $E(w,C)$. Si les réponses sont identiques, il s'est assuré de l'identité de l'utilisateur. Et comme $C$ est tiré au hasard, il y a extrêmement peu de chances que le même défi soit reposé plus tard.

  Bien sûr, dans la plupart des cas, ceci est complètement transparent pour l'utilisateur. Par exemple, lors d'une identification à distance sur internet, il rentre simplement son mot de passe. C'est le navigateur qui a reçu le nombre aléatoire $C$ et qui calcule $E(w,C).

  Le choix de la fonction $E$ est très important. Il faut que cette fonction soit à sens unique, ou au moins qu'il soit très difficile de calculer $w$ connaissant $C$ et $E(w,C)$. On choisit souvent pour $E$ ou bien un algorithme de chiffrement symétrique dans lequel le mot de passe $w$ joue le rôle de clé et $C$ le rôle de texte clair, ou une fonction de hachage. Une des faiblesses de ces procédés est qu'ils obligent à garder les mots de passe en clair sur le serveur. A nouveau, l'accès à ce fichier doit être sécurisé.

  Ces protocoles de défis/réponses sont mis en oeuvre par certaines banques pour sécuriser les transactions sur internet de leurs clients. Une sorte de calculette est envoyée à ce client et lors d'un paiement, la banque demande à ce que l'utilisateur lui envoie une information (souvent un nombre à huit chiffres) qu'il obtient en insérant sa carte dans la calculette, en entrant son code secret, puis le "défi" (souvent un nombre lui-même) proposé par la banque. Ils apparaissent aussi dans le protocole DDA utilisé lors des paiements par carte bancaire dans un terminal de paiement.
La preuve sans divulgation
  Les procédés de preuve sans divulgation sont une variante des protocoles défis/réponses. L'idée est toujours de prouver que l'on connait un secret, mais sans le divulguer, et surtout sans que le serveur ne possède lui-même ce secret. Ces protocoles sont ici plutôt fondés sur la cryptographie à clé publique. Voici un exemple simple. La maison de Nérosson et Yoshi est constituée d'une entrée et de deux pièces A et B. Ces deux pièces communiquent par une porte ne s'ouvrant qu'à l'aide d'une clé.

  Nérosson veut prouver à Yoshi qu'il possède la clé permettant de passer de passer de la pièce A à la pièce B. Pour cela, il entre dans une des deux pièces sans que Yoshi ne le voit et ne sache dans laquelle. Yoshi vient et lui demande, au hasard, de sortir par l'une des deux pièces. Si Nérosson possède la clé, il sortira toujours par la bonne pièce. Sinon, il ne possède qu'une chance sur deux de sortir par la bonne pièce. Si l'on répète l'opération une vingtaine de fois, la probabilité que Nérosson sorte toujours par la bonne pièce alors qu'il ne possède pas la clé est de $\frac 1{2^20}$, soit moins de une chance sur un million. Nérosson a ainsi prouvé à Yoshi qu'il possédait la clé, sans la montrer physiquement.

  Détaillons maintenant un procédé utilisant de l'arithmétique, le protoloce d'identification de Fiat-Shamir. L'utilisateur commence par choisir deux grands nombres premiers $p$ et $q$, et calcule leur produit $n=pq$ ($p$ et $q$ restent secrets). Il choisit ensuite au hasard un nombre entier $s$ entre $1$ et $n-1$ et calcule $v^2=s\ (\mod n)$. Le couple $(n,v)$ est sa clé publique, et $s$ sa clé secrète. Il souhaite prouver au serveur, qui connait $n$ et $v$, qu'il connait $s$ (sans que le serveur lui-même ne connaisse $s$). Le protocole se comporte alors suivant $4$ étapes :
  • l'utilisateur choisit au hasard un nombre entier $r\in\{1,\dots,n-1\}$. Il calcule $x=r^2\ (\mod n)$ et il envoie $x$ au serveur.
  • le serveur choisit un bit $e\in\{0,1\}$ au hasard lui aussi et l'envoie à l'utilisateur;
  • l'utilisateur renvoie $y=rs^e\ (\mod n)$ au serveur.
  • le serveur vérifie que $y^2=xv^e\ (\mod n)$.
  Voyons pourquoi ce protocole assure l'identification auprès du serveur. Évidemment, si l'utilisateur connait effectivement $s$, il peut faire tous les calculs et renvoie toujours la bonne réponse. S'il ne connait pas $s$, alors il ne peut pas répondre simultanément à la question renvoyer $r$ et renvoyer $rs$, sinon il pourrait calculer $s= r^{-1}rs$.

  L'utilisateur ne connaissant pas $s$ a alors deux choix. Soit il ne triche pas lors de la première étape (calcul et envoi de $x=r^2$). Alors il pourra répondre toujours correctement à la question du serveur si $e=0$. Si $e=1$, il devra choisir un nombre au hasard, et il n'a pas plus d'une chance sur $n-1$ de tomber sur $rs^{-1}$ (en fait, un peu plus car $rs^e$ n'est pas le seul nombre $y$ qui vérifie $y^2=xv^e\ (\mod n)$, mais le nombre de solutions reste très faible par rapport à $n$).

  Soit il triche lors de l'envoi de $x$. Dans ce cas, il peut parier dès le départ sur le bit $e$ que le serveur enverra :
  • s'il parie que le serveur envoie $0$, il envoie effectivement $x=r^2$, puis ensuite $y=r$.
  • s'il parie que le serveur envoie $1$, il envoie alors $x=r^2v^{-1}\ (\mod n)$, puis ensuite $y=r$ qui vérifie bien $y^2=xv^e\ (\mod n)$.
Bien sûr, le tricheur a une chance sur deux de faire le bon pari et s'il a fait le mauvais pari, il a une chance infime de donner la bonne solution.

  Dans tous les cas, donc, avec un tour de ce protocole, le tricheur a une probabilité $p<1$ de faire le bon choix (avec $p\simeq 1/2$ si $n$ est grand). En répétant ce protocole un certain nombre de fois (typiquement 20), le serveur pourra s'assurer de l'identité de l'utilisateur.

  La sécurité de ce protocole repose sur le fait que calculer une racine carrée modulo $n$, lorsque $n=pq$ est le produit de deux entiers premiers, est aussi difficile que factoriser $n$, et que la factorisation des entiers est un problème difficile (ce qui est un des paradigmes de la cryptographie à clé publique). Ce protocole est aussi sans divulgation de connaissance au sens suivant : quelle que soit la façon dont le serveur utilise le protocole, même en le détournant (par exemple, en ne choisissant pas le bit $e$ au hasard), il ne pourra rien apprendre sur la clé $v$. Bien sûr, c'est une propriété qui n'est pas si facile à prouver…
Consulter aussi