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
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
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))\) où \(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.