Protocoles cryptographiques

Outre la confidentialité d’échanges, les techniques cryptographiques fournissent des solutions pour certains problèmes pratiques, comme l’authentification, la signature. On donne quelques exemples rapides.

Fonctions de hachage

On souhaite avoir une notion d’empreinte digitale, c’est-à-dire d’une information partielle qui, en pratique, caractérise un tout.

Une fonction de hachage est une fonction qui prend une chaîne de longueur quelconque et renvoie une empreinte de taille \(\ell\) fixée

\[h: (\F_2)^\ast \to \F_2^\ell\]

de sorte que

  • le calcul de l’empreinte est très rapide

  • le problème du calcul de préimage : « étant donné \(x\in\F_2^\ell\), trouver \(m\) tel que \(x=h(m)\) » est calculatoirement infaisable

  • le problème de collision : « trouver \(m\neq m'\) tels que \(h(m)=h(m')\) » est également infaisable en pratique

Ces conditions impliquent que \(\ell\) doit valoir au moins de l’ordre de \(128\) bits pour rendre impossibles les recherches de collisions avec optimisation temps-mémoire (paradoxe des anniversaires).

Exemples : SHA-1, SHA-3, MD5, RC4 (cassé)

On utilise de telles fonctions pour assurer l’intégrité de données numériques (en particulier lors de téléchargements).

Construction

On peut fabriquer une fonction de hachage à l’aide d’un cryptosystème fonctionnant sur des blocs de taille \(\ell\), par exemple en itérant le chiffrement sur le message nul en prenant les blocs du message comme clefs successives. Si le chiffrement est sûr, la fonction obtenue l’est également.

Ainsi, le système Unix utilisait DES comme fonction de hachage pour ses mots de passe, ce qui est beaucoup trop faible de nos jours.

En pratique, on emploie des fonctions construites spécialement, comme SHA3.

Signature

La signature d’un document est une empreinte qu’une seule personne sait produire, mais que chacun peut constater et authentifier. La signature sert à prouver qu’une personne est l’auteur, ou a connaissance d’un document (cf. chèque ou recommandé), pour éviter à la fois

  • les fausses attributions : prétendre être l’auteur d’un document

  • la répudiation : prétendre ne pas en être l’auteur ou ne pas en avoir connaissance.

Si \(m\) est un document électronique, et Alice a mis en place un cryptosystème asymétrique et choisi une fonction de hachage publique \(h\), la valeur

\[s = d(h(m))\]

est une signature du document \(m\) que

  • seule Alice peut avoir produite, puisque cela nécessite la fonction de déchiffrement donc la clef privée

  • n’importe qui peut vérifier, en effectuant la vérification \(e(s) = h(m)\)

Exemple

Les pdf créés par le logiciel payant Adobe Acrobat sont signés, et donnent droit à l’utilisation de certaines fonctions supplémentaires du logiciel de lecture gratuit Adobe Reader.

En 2009, la partie chiffrement était solide. Toutefois, l’utilisation d’une fonction de hachage trop faible, et la prise en compte d’une partie seulement du document pour calculer le haché permettait de créer des documents munis d’une fausse signature, simplement en ajoutant au document des commentaires qui le rendent compatible avec une signature valide extraite d’un document authentique.

Echange de clefs

Pour se mettre d’accord sur une clef secrète pour un chiffrement symétrique, Alice et Bob peuvent peuvent procéder de la manière suivante, en utilisant un système de type El Gamal de groupe \(G=\langle g\rangle\) pour lesquels ils ont des clefs \(A=g^a\) et \(B=g^b\) :

  • l’un et/ou l’autre tire une valeur \(r\) aléatoire (publique)

  • Alice peut calculer la clef \(k=rB^a\)

  • Bob peut calculer la clef \(k=rA^b\).

Ce protocole est dû à Diffie et Hellman, il marque la première irruption d’un mécanisme asymétrique en cryptographie.

Authentification

Une entité désire authentifier Alice pour la laisser accéder à des services. On suppose qu’une authentification initiale a permis d’initialiser le système de manière sûre, et on s’intéresse aux authentifications ultérieures.

Mot de passe

C’est la méthode la plus courante, on a initialisé un mot de passe dans des circonstances où l’identité n’est pas mise en doute (création de compte, envoi par la poste…), et l’utilisateur entre simplement son mot de passe.

Toutefois, il est inutile et dangereux que l’entité dispose du mot de passe d’Alice : employés indélicats ou compromission de la base de donnée risquent de divulguer le mot de passe.

Il suffit de mémoriser le haché du mot de passe, et de vérifier que les hachés coïncident lors d’une identification. Si la fonction de hachage est sûre, on ne perd rien en sécurité.

Un autre danger cependant : en pratique, l’entropie des mots de passe choisis par les humains est très insuffisante (mots du dictionnaire avec variantes prévisibles). De sorte que munis de hachés, une attaque par force brute permet de retrouver facilement tous les mots de passe faciles, en comparant aux hachés classiques.

Cette stratégie fonctionne mal en général pour un mot de passe donné, mais sur les grandes bases de mots de passe obtenues lors des piratages récents (Sony, Unix, Apple) cela permet toujours de casser plus de 20mots de passe.

Voir par exemple un logiciel comme « John the ripper »

Parade: sel et hachage lent

Voir https://security.stackexchange.com/questions/211/how-to-securely-hash-passwords/31846#31846

Une parade consiste à stocker non pas le mot de passe \(m\), mais un couple de type \((r, h(r,m))\)\(r\) est une chaîne aléatoire qui paramètre la fonction de hachage.

De cette manière, le calcul de l’authentification n’est pas très différent, mais deux mêmes mots de passe n’apparaissent jamais de la même manière dans la base, et une attaque par force brute se ramène à l’attaque d’un seul mot de passe, beaucoup plus incertaine et coûteuse.

Par ailleurs, on utilise volontairement une fonction \(h\) lente et coûteuse en mémoire : c’est un inconvénient pour le serveur qui authentifie des utilisateurs, mais cela handicape encore plus l’attaquant qui tente une recherche par force brute.

Phishing

Si une fausse entité réussit à se faire passer pour la vraie, Alice lui fournit son mot de passe. Avec la technique des mots de passe, il n’y a malheureusement pas de parade…

Clef publique/clef privée

Si Alice dispose d’un couple clef publique/clef privée et que l’entité a noté la clef publique, la procédure suivante permet d’authentifier Alice

  • l’entité envoie une chaîne aléatoire \(r\)

  • Alice renvoie \(d(r)\)

  • l’entité vérifie que \(e(d(r))=r\).

Toutefois, une fausse entité peut utiliser ce protocole pour avoir accès à la fonction de déchiffrement d’Alice (en envoyant des chiffrés \(r\) bien choisis). Il vaut mieux symétriser l’échange (pour qu’Alice vérifie en même temps l’authenticité de l’entité) et ajouter de l’aléa, de sorte que ni Alice ni l’entité ne choisissent ce qui va être déchiffré.

On peut procéder par exemple ainsi :

  • Alice et l’entité choisissent chacun \(r_a\) et \(r_e\) aléatoires, et envoient les hachés \(h(r_a)\) et \(h(r_e)\) ;

  • ils envoient ensuite \(r_a\) et \(r_e\), et chacun vérifie que cela correspond aux hachés annoncés ;

  • Alice et l’entité calculent \(d_{a,e}(r_a+r_e)\) et l’envoient ;

  • Alice et l’entité vérifient chacun que \(e_{a,e}(d_{a,e}(r_a+r_e))=r_a+r_e\).

La phase d’envoi des hachés n’est là que pour s’assurer qu’aucune des parties ne puisse choisir sa chaîne \(r_a\) ou \(r_e\) en fonction de celle de l’autre, soit pour accéder à la fonction de déchiffrement, soit pour répondre en imitant des échanges espionnés antérieurement (on s’engage par avance sur une valeur sans pour autant la donner).

Preuves sans apport d’information

Comme on le voit avec l’authentification par mot de passe, il est problématique que l’authentification rende nécessaire la divulgation d’une information secrète. Il serait préférable qu’on puisse vérifier de manière fiable la connaissance d’une telle information sans que rien n’en soit révélé.

Par exemple, dans un système ElGamal, si quelqu’un veut vérifier qu’Alice dispose de sa clef privée \(a=\Log(A,g)\), on peut procéder ainsi

  • Alice tire \(r\) au hasard et envoie \(R=g^r\)

  • la personne tire \(x\) au hasard et l’envoie à Alice

  • Alice envoie \(y=r+ax\)

  • la personne vérifie l’égalité \(g^{y} = RA^x\)

Ce faisant, l’entité n’a accès à rien d’autre que des données publiques, et pourtant seule Alice peut calculer la bonne valeur \(y\).

Blockchains

Une blockchain permet à une communauté de certifier des données sans recourir à une autorité de confiance (état, banque).

L’objectif est d’inclure les données dans une chaîne d’informations de sorte que la communauté dans son ensemble ait intérêt à vérifier la validité des données.

Pour cela, le principe est de répartir l’information dans des blocs, de sorte que

  • il soit très facile de vérifier la validité des blocs

  • il soit coûteux de fabriquer un bloc

  • la création d’un bloc soit récompensée.

Un bloc est composé :

  • d’un lien vers le bloc précédent

  • de l’information qu’on veut ajouter à la chaîne

  • d’un code de validation

Le code de validation doit être déterminé de sorte que le bloc soit valide, c’est-à-dire que son haché vérifie une propriété (commencer par x zéros).

C’est cette étape qui est très coûteuse, puisqu’on ne sait pas trouver de préimage aux fonctions de hachage on en est réduit à essayer des codes au hasard jusqu’à ce que l’un convienne.

Voir l’excellente démonstration [blo18].

La blockchain évolue en parallèle, tout le monde essaie de rajouter des blocs. On risque vite d’avoir plein de blockchains différentes. Toutefois puisque

  • chacun a intérêt à avoir la même blockchain que les autres

  • on privilégie la chaîne la plus longue

  • il est très coûteux d’ajouter des blocs

les choses se stabilisent bien en pratique. Quand une entité réussit à ajouter un bloc, elle le publie et les autres ont intérêt à l’adopter et à prolonger la même chaîne plutôt que prendre le risque de lancer une chaîne concurrente qui sera délaissée.

Le cas intéressant est quand deux propositions de blocs valides sont publiées à peu près en même temps : la communauté se scinde temporairement entre ceux qui cherchent à prolonger l’une et l’autre chaîne. Cette situation ne dure pas : dès l’ajout du bloc suivant une chaîne aura de l’avance, ce qui va attirer plus de mineurs et accélérer encore sa progression sur les blocs suivants. La communauté va privilégier une branche et l’autre sera abandonnée.

On ne peut donc considérer qu’une transaction est définitivement adoptée par la blockchain qu’à partir du moment où elle est à une certaine profondeur (5 ou 6 blocs du sommet).

Pour la même raison, une fois un bloc ajouté à la chaîne, et puisque tous les blocs suivants dépendent de son contenu, il n’est plus possible de le modifier (il faudrait recréer toute la chaîne de blocs suivants, or elle grandit plus vite qu’on arrive à la modifier).

Ceci n’est plus vrai si une entité acquiert la majorité de la puissance de calcul (attaque des 51%), dans ce cas elle peut imposer l’adoption de ses blocs puisqu’elle travaille plus vite que le reste de la communauté, et peut même réécrire la chaîne.

Partage de secret

Le but est de distribuer une information entre plusieurs personnes, de manière à ce que ce soit uniquement en se réunissant qu’elles parviennent à reconstituer l’information.

Par exemple

  • l’emplacement du trésor des pirates, l’accès à un trésor

  • un testament, nécessitant la réunion des héritiers

  • un coffre à la banque, qui ne s’ouvre qu’en présence du banquier et du propriétaire. Plus généralement, les procédure d’authentification à \(k\) facteurs.

  • la clef d’activation du système DNSSEC, en cas d’attaque majeure des noeuds DNS principaux d’internet, est confiée à la réunion d’au moins 5 parmi 7 personnes.

On pourrait procéder par intersections d’hyperplans dans un espace affine. Une construction plus élégante est due à Shamir :

  • on se place dans un grand corps fini \(\F_p\)

  • le secret est un élément \(s=a_0\in\F_p\).

  • on tire au hasard \(a_1,\dots a_{p-1}\in\F_p\) et on construit le polynôme \(A(x)=\sum a_ix^i\).

  • on fournit à la \(i\)-ème personne l’évaluation \((i,A(i))\), \(A(i)\in\F_p\).

Pour reconstituer le secret, tout sous-ensemble de \(k\) personnes réunit \(k\) évaluations d’un polynôme de degré \(k-1\), ce qui permet de reconstruire \(A(x)\) par interpolation.

Ce système est satisfaisant car chaque participant reçoit une quantité d’information égale à celle du secret, et tant que l’on a réuni moins de \(k\) participants on n’a aucune information sur le secret.