Les livraisons dangereuses

1. L’énigme du livreur glouton

Bob voudrait acheter un gâteau à une pâtisserie de renom tenue par Isabelle. La boutique étant trop éloignée pour y aller en personne, il demande une livraison à domicile. Malheureusement le livreur est connu pour sa gourmandise : il a tendance à manger compulsivement les gâteaux qu’il est censé livrer. C’est une situation complexe : Isabelle et Bob ont besoin du livreur mais savent aussi qu’ils ne peuvent pas lui faire confiance.

En discutant du problème par téléphone, ils se rendent compte qu’ils ont tous les deux des cadenas chez eux ; ainsi, quand ils utiliseront ce service postal peu fiable, ils pourraient mettre les livraisons dans des coffrets cadenassés pour limiter le risque de vol.

La difficulté est que, bien qu’Isabelle et Bob aient tous deux un cadenas, ils ne peuvent pas ouvrir celui de l’autre. Isabelle pourrait mettre le gâteau dans un coffret et envoyer la clé plus tard ; cependant le livreur pourrait alors obtenir à la fois le coffre verrouillé et sa clé.

Une première solution

Un moyen de s’en sortir est de combiner les deux cadenas comme suit. Dans un premier temps, Isabelle met le gâteau dans un coffre, le verrouille avec son cadenas, et demande au livreur d’apporter le tout à Bob :

Pour l’instant, le livreur ne peut pas manger le gâteau, mais Bob non plus. Ce dernier ajoute alors son propre cadenas au coffre de manière à ce qu’il soit verrouillé par les deux, puis retourne le colis à Isabelle :

À la réception du coffret, Isabelle y retire son propre cadenas et le renvoie :

Bob reçoit alors le gâteau dans un coffre scellé uniquement par son propre cadenas et peut donc le récupérer. Aucune clé n’a été envoyée durant le procédé et il y avait toujours au moins un cadenas sur les différents colis donnés au livreur. Nous obtenons donc :

… mais est-ce réellement le cas ? Il y a en fait de nombreuses façons pour le livreur de récupérer le gâteau, la plus directe étant de forcer les cadenas avec les outils appropriés.

La propriété ci-dessus repose en fait sur trois hypothèses implicites sur le livreur :

1. il ne peut pas forcer les cadenas,
2. ni voler les clés,
3. et est passif, c’est-à-dire, il suit les instructions qui lui sont données.

Sans ces hypothèses, le protocole n’offre a priori pas la sécurité attendue. Mais sont-elles réalistes ? Est-il possible de protéger le gâteau sans (certaines d’entre) elles ?

Contre un livreur actif

À partir de maintenant, nous nous concentrerons sur la structure logique du protocole plutôt que sur la solidité du matériel de sécurité. Mais même dans ce contexte, le protocole offre peu de garanties car il repose trop sur la passivité du livreur. En effet, une fois la livraison d’Isabelle prête, le livreur pourrait dévier de ses instructions : au lieu de livrer le colis à Bob, il ajoute son propre cadenas dessus et le retourne à Isabelle.

N’ayant pas conscience qu’il ne s’agit pas du cadenas de Bob, Isabelle pense que le protocole suit son cours normalement et retire son cadenas :

Le livreur peut alors déverrouiller le coffre avec sa propre clé. Cette attaque n’a nécessité de forcer aucun cadenas : elle exploite simplement une brèche dans la structure du protocole.

Corriger le protocole

Il est en fait presque impossible de concevoir un protocole résistant au vol contre un livreur actif avec ce système de cadenas. Isabelle et ses clients décident donc de souscrire à une organisation à grande échelle de cadenas publics :

1. tout membre de l’organisation se voit remettre une clé personnelle ;
2. toute personne peut obtenir auprès de l’organisation un cadenas ne pouvant être ouvert que par la clé d’un membre spécifique.

Un protocole de livraison de gâteaux (V2) consiste alors simplement à envoyer le colis à Bob verrouillé avec un cadenas de l’organisation que lui seul peut ouvrir.

2. Une énigme plus sombre

Mais l’histoire ne s’arrête pas là. Quelqu’un envoie à Bob un colis avec un gâteau empoisonné et un message prétendant qu’il s’agit d’un cadeau d’Isabelle. Heureux, Bob le mange, et c’est le drame : nous ne pouvons jamais être sûr que l’expéditeur d’une livraison est celui qu’il prétend être. Au retour de Bob de l’hôpital, Isabelle et lui décident de mettre à jour le protocole de livraison pour qu’il garantisse une forme d’authentification.

Nous supposons qu’Isabelle et son client (ici Bob) se sont procurés auprès de l’organisation des cadenas ne pouvant être ouverts que par l’autre. Cette fois, le client est celui qui initie le protocole, en écrivant sur un bout de papier un (long) mot de passe qui servira à identifier sa commande. Il l’envoie ensuite à Isabelle dans un coffre scellé avec le cadenas de cette dernière, et joint une note indiquant son propre nom pour qu’Isabelle sache à qui retourner la livraison :

À la réception du coffre, Isabelle lit le nom du client sur la note, ouvre le coffre avec sa clé, met le gâteau à l’intérieur à côté du papier où est écrit le mot de passe, puis scelle le tout avec le cadenas du client. Elle lui fait ensuite livrer le colis :

À la réception, le client vérifie que le gâteau est bien accompagné du même mot de passe qu’il a choisi initialement — sinon il le détruit. Si nous appelons V3 cette nouvelle version :

Intuitivement, le protocole est pensé pour qu’une personne voulant faire manger un gâteau piégé à Bob doive deviner son mot de passe — ce que l’on considère comme impossible s’il est assez long et imprévisible. Malheureusement la réalité est plus complexe que cela, comme illustré par l’attaque suivante. Le protocole commence comme d’habitude : Bob place un mot de passe dans un coffre verrouillé et indique son nom dessus. En parallèle le livreur commande aussi un gâteau, puis transmet la commande de Bob à Isabelle mais remplace le nom de Bob :

Isabelle suit les instructions du protocole et met le gâteau dans le coffre (pensant que le mot de passe qui s’y trouve est celui du livreur), puis le referme avec le cadenas du livreur. Ce dernier peut donc l’ouvrir, empoisonner le gâteau, et le refermer avec le cadenas de Bob.

Le livreur retourne ensuite voir Bob et lui donne la livraison piégée, et ce dernier la croit sûre à cause de la présence de son mot de passe et mange le gâteau empoisonné. Donc :

Une contre-mesure est que le client mette son nom à l’intérieur du coffre, à côté du mot de passe, pour empêcher le livreur de le modifier. En appelant V4 cette version finale du protocole, elle vérifie cette fois la propriété attendue :

Isabelle peut donc à présent offrir un gâteau à Bob en lui demandant d’initier une session du protocole avec elle.

3. Protocoles cryptographiques

Bien que la livraison de gâteaux ne soit pas un problème au cœur des préoccupations de la société, l’histoire d’Isabelle et Bob partage de nombreuses problématiques avec la sécurité des télécommunications. Cela inclut nos connexions quotidiennes au réseau 3/4/5G mais aussi le paiement en ligne, le vote électronique, ou même les puces RFID des passeports électroniques. Tous ces exemples partagent deux caractéristiques importantes :

1. Les données à envoyer (le gâteau dans l’énigme) sont sensibles, un manque de confidentialité ou d’intégrité peut avoir des conséquences économiques ou politiques (pensez au cas des paiements en ligne ou des élections électroniques).
2. Les échanges sont faits via des réseaux peu fiables comme Internet (le livreur dans l’énigme) pouvant être facilement espionnés par des antennes ou contrôlés.

On utilise ainsi des protocoles cryptographiques (les protocoles de livraison dans l’énigme) pour offrir de la sécurité dans ce contexte. On pourra citer, avec le vocabulaire de l’énigme :

1. La confidentialité : le livreur ne peut pas voler le gâteau ou, plus généralement, obtenir une quelconque information dessus.
2. L’authentification : le client peut toujours différencier les colis d’Isabelle des colis piégés.
3. L’anonymat : le livreur ne peut pas obtenir d’informations sur l’identité du client qu’il livre.
4. La non-traçabilité : le livreur ne peut pas savoir si deux commandes sont pour le même client ou des clients différents.

Pour offrir ces garanties, les protocoles ont recours à des primitives cryptographiques, comme le chiffrement rendant des messages inintelligibles à toute personne autre que le destinataire du message (représenté par les coffres et les cadenas dans l’énigme).

Analyse assistée par ordinateur

La solidité des primitives cryptographiques est cruciale : si, dans l’énigme, les cadenas étaient fragiles, il n’y aurait aucun moyen de garantir quoi que ce soit. Mais comme nous l’avons vu, cela ne fait pas tout : les versions V1-3 du protocole de livraison ont pu être attaquées sans forcer un seul cadenas. De telles attaques sont subtiles et difficiles à trouver manuellement ; peut-être aviez-vous vous-même l’intuition que les versions V1-3 offraient les garanties de sécurité attendues ? Des failles similaires sont même passées sous les radars des chercheurs et de l’industrie parfois pendant 30 ans…

Une difficulté majeure des analyses de sécurité est qu’elles sont fastidieuses : envisager tous les cas de figure — souvent des millions — sans en oublier aucun est tout sauf naturel pour un cerveau humain. Or s’il y a quelque chose que les ordinateurs font mieux que nous, c’est justement effectuer sans erreurs des tâches à la chaîne : automatiser une partie du processus d’analyse permet ainsi de mettre au jour plus facilement certaines brèches. Les failles du protocole de livraison de l’énigme sont des exemples typiques d’attaques aisément détectées par les outils développés par la recherche à ce jour. Malgré cela, la tâche reste complexe et une large marge de progression existe. Et pour cause, sous certaines hypothèses techniques non détaillées ici, la recherche d’attaque violant…

1. … l’authentification, ou certaines formes faibles de confidentialité, est un problème NP-complet. Pour simplifier à l’extrême, cela signifie qu’en pratique, la difficulté de l’analyse croît exponentiellement avec le nombre de participants du protocole.
2. … l’anonymat, la non-traçabilité, ou d’autres notions liées à la vie privée, est un problème NEXP-complet (c’est-à-dire, exponentiellement plus difficile qu’un problème NP-complet).

4. Morale(s) de l’histoire

En résumé, les protocoles sont complexes : autant pour un humain (au vu de notre difficulté à trouver des attaques sur les protocoles minimalistes de l’énigme) que pour une machine (au vu des résultats théoriques de NP/NEXP-complétude ci-dessus). Avoir une cryptographie solide ne fait donc pas tout et des efforts non négligeables sont nécessaires pour offrir les protections attendues. Des exemples récents incluent la dernière version de TLS (v1.3, 2018) permettant des connexions sécurisées à Internet, son alternative QUIC en phase finale de standardisation par l’IETF (2021), les protocoles du standard 5G… chacun ayant nécessité le travail de centaines de chercheurs et industriels pendant plusieurs années. L’expression « 100 % sécurisé » qu’on lit parfois est donc plus un message commercial qu’une réalité de terrain !