Ours & Hippy — le blog

Cette année, j’ai eu l’occasion de faire un peu de cryptologie.

Alors moi, dans l’idée, calculer n^(pq) dans un groupe cyclique d’ordre d, ou décaler-xorer les bits 17 fois pour calculer un hash cryptographique, ça ne me tente pas du tout.

J’ai cependant découvert qu’il y a d’autres aspects de la crypto qui ne concernent pas l’analyse technique des algorithmes, mais plutôt une analyse « sémantique » de leur utilisation. Par exemple, on a beau avoir un super algorithme de chiffrement, si on envoie la clé en clair avec le message chiffré, ce n’est pas sécurisé. Il y a des façons moins évidentes de se tromper et des gens qui cherchent comment éviter ces pièges.

Dans ce billet, je présenterai juste un exemple assez simple. Ne vous attendez pas à des merveilles tout de suite, mais elles viendront peut-être plus tard.

Étude formelle des protocoles cryptographiques

On fait une différence entre l’étude « formelle » et l’étude « calculatoire » des systèmes utilisant la cryptographie. Dans le modèle formel, on considère les algorithmes cryptographiques comme des boîtes noires, qui marchent toujours et sont incassables, et on étudie l’utilisation qui est faite de ces boîtes noires : sous des conditions données, est-ce que telle utilisation est sûre ?

Dans le modèle calculatoire, on met les mains dans le cambouis en regardant dans les boîtes, dans le but d’avoir des estimations quantitatives de la difficulté calculatoire pour casser une utilisation aux paramètres de sécurité (taille des clés, etc.) donnés. Par exemple, si vous utilisez tel algorithme de telle façon et espérez garantir telle propriété de sécurité, il faudra au moins 2⁸⁰ calculs à un attaquant pour la casser.

Je me limiterai au modèle formel, en utilisant certaines des boîtes noires et notations suivantes :

chiffrement symétrique

On peut encoder ou décoder un message M avec la clé K. Sans la clé, il n’y aucun moyen de décoder le message. Je note senc(M,K) le message chiffré.

chiffrement asymétrique

Un utilisateur U possède une clé publique pk(U) et une clé secrète sk(U). Il diffuse la clé publique, et garde la clé secrète… secrète. On peut chiffrer un message avec une clé publique pk(X), et alors pour le déchiffrer il faut avoir sk(X). Cela permet de faire des échanges sans partager un secret commun, comme dans le cas symétrique. Je note aenc(M,pk(X)) le message chiffré.

signature

Toujours dans un cadre asymétrique, U peut « signer » un message M dans le but de garantir qu’il vient bien de lui. Il utilise pour cela sa clé secrète, et obtient une signature qui peut être vérifiée par tout possesseur de la clé publique pk(U). On note sign(M, sk(X)) la signature, et il y a une opération check(M, S, pk(X)) qui renvoie vrai si et seulement si S est bien la signature du message M avec la clé privée correspondant à pk(X). Bien sûr, on ne peut pas récupérer sk(X) à partir de sign(M, sk(X))…

Ça c’est ce que peut faire tout le monde, en particulier les « gentils », pour utiliser la crypto en espérant arriver à leurs fins. Mais que peuvent faire les méchants ? On fait en général des hypothèses paranoïaques : on considère que tout message envoyé sur le réseau peut être lu et même stoppé (avant qu’il arrive à son destinataire) par un méchant attaquant.

Un cas d’école : le protocole d’authentification de Needham-Schroeder

Le cas d’école d’étude des protocoles cryptographiques est le protocole d’authentification de Needham-Schroeder. C’est un protocole destiné à « authentifier » des agents qui communiquent entre eux, c’est-à-dire à garantir qu’ils sont bien en train de parler à la personne à laquelle ils pensent parler.

L’idée générale est d’envoyer un « défi » (challenge) à la personne avec laquelle on parle : un nombre aléatoire qu’on vient de générer, donc introuvable (on appelle un tel nombre un nonce, affreux anglicisme proche du mot « hapax »), chiffré avec la clé de la personne avec laquelle on pense parler. Si elle arrive à déchiffrer ce nonce et à nous le renvoyer, elle est authentifiée.

Pour toute paire d’agents A et B, le protocole procède comme suit :

A → B : aenc((N_A, A), pk(B))
B → A : aenc((N_A, N_B), pk(A))
A → B : aenc(N_B, pk(B))

A génère un nonce N_A et envoie la paire (N_A, A) (ici A représente une donnée qui l’identifie : son nom, son adresse mail…) à B. Il génère à son tour un nonce N_B et renvoie les deux à A, qui répond en renvoyant N_B. Si tout se passe bien, les deux ont bien répondu à leurs défis respectifs et se sont mutuellement authentifiés.

Il est crucial que les défis soient générés aléatoirement, à chaque session d’authentification. Sinon un attaquant pourrait écouter les messages et les « rejouer » ensuite dans le futur, en se faisant passer pour l’un des participants. Par exemple si N_B était une constante choisie une fois pour toute par B, un attaquant C ayant observé cet échange pourrait entamer la session en prétendant être A, et à la troisième étape renvoyer le message aenc(N_B, pk(B)), faisant ainsi croire à B qu’il est à nouveau en train de parler avec A.

La notation que j’ai utilisée pour le protocole est relativement informelle. On peut la formaliser un peu mieux, ou encore passer à des descriptions plus fines, qui décrivent par exemple précisément le moment de génération d’un nonce. Les cryptographes utilisent pour cela des variantes du π-calcul, un calcul de processus développé au départ comme base théorique de la programmation distribuée.

Il y a aussi de l’implicite au niveau du lien entre une identité A, et ses clés pk(A) et sk(A). En particulier, sk n’est pas une simple fonction, car on veut que seul A puisse calculer sk(A). La façon dont on associe pk(A) à A peut aussi être modélisée. Ici j’ai considéré que les participants « connaissent » les clés publiques, mais on peut aussi supposer un (ou plusieurs) serveurs de certifications, supposés de confiance, et qui indiquent la clé publique associée à une identité. Cela complique un peu le protocole, de façon inessentielle ici.

Enfin, il convient de faire une dernière remarque sur ce protocole : après l’authentification, N_A et N_B sont des secrets partagés entre A et B. Il a donc été suggéré d’utiliser ces secrets partagés pour une communication entre A et B, par exemple comme clé d’un chiffrage symétrique. En plus d’authentifier A et B, on souhaiterait donc garantir le secret de ces nonces.

… pas si sûr qu’il n’y paraît

Le protocole que j’ai décrit plus haut est en fait non sûr : il ne garantit pas l’authenticité des participants. Imaginons un ensemble d’agents qui s’authentifient mutuellement en utilisant ce protocole. Certains, comme A et B, sont honnêtes, mais d’autres, comme I, sont mauvais et cherchent à subvertir le protocole à leurs fins propres.

Si A entame une communication avec I en essayant de s’authentifier, I peut en profiter pour se faire passer pour A auprès de B. Je noterai Î pour l’agent I se faisant passer pour A ; c’est toujours I, mais l’intention est différente :

A → I : aenc((N_A, A), pk(I))
Î → B : aenc((N_A, A), pk(B))
B → Î : aenc((N_A, N_B), pk(A))
I → A : aenc((N_A, N_B), pk(A))
A → I : aenc(N_B, pk(I))
Î → B : aenc(N_B, pk(B))

L’idée de I est proche des man in the middle attacks : transférer les paquets sans trop y toucher, dans le but que les personnes aux deux bouts ne se rendent pas compte du problème et fassent tout le travail pour lui. Il envoie la demande de connexion de A à B, et attend la réponse de B. Il ne peut pas la lire puisqu’elle est chiffrée avec la clé de A (B pense parler à A). Mais il peut se servir de A pour la déchiffrer à sa place ! Il envoie ainsi la réponse de B, qui contient le défi N_B, à A, comme si c’était son propre défi. A le déchiffre et renvoie N_B à I, qui peut alors répondre triomphalement à B.

L’authentification est brisée, puisque B pense avoir conclu une session avec A alors que ce dernier n’a jamais parlé à B. De plus, si les nonce étaient ensuite utilisés comme clé de chiffrement de messages post-authentification, cela pourrait avoir des conséquences graves. Par exemple si B est une banque et A un de ses clients :

Î → B : senc("I'm A, please transfer all my money to I", (N_A, N_B))

Quand on parle de « cas d’école », on veut dire qu’il a été très étudié, pas que c’est un exemple fait sur mesure pour les étudiants. Le protocole de Needham-Schroeder a été publié en 1978, et la faille n’a été découverte par Gavin Lowe qu’en 1995. Inutile de dire que les personnes ayant utilisé le protocole entre temps ont dû être très, très stressées…

Gavin Lowe, simultanément à son attaque, a proposé de corriger le protocole de la façon suivante :

A → B : aenc((N_A, A), pk(B))
B → A : aenc((N_A, B, N_B), pk(A))
A → B : aenc(N_B, pk(B))

Dans la deuxième étape, B envoie son identité en plus du défi. Ainsi, A peut bien vérifier qu’il provient bien de la personne auprès de laquelle elle essaie de s’authentifier. Dans le cas de l’attaque, où A pense parler à I qui s’en sert pour le mettre en communication avec B, la réponse de I à A, issue de B, deviendrait alors :

I → A : aenc((N_A, B, N_B), pk(A))

et A, voyant que le message ne provient pas de I, interromprait immédiatement la tentative d’authentification.

Gavin Lowe conclut ainsi son article (PS, 5 pages) :

We conjecture that the revised protocol is safe against all attacks — at least, those attacks not dependent upon properties of the encryption method used. Proving this formally is the topic of current research.

C’était current research en 1995, maintenant on sait faire… tant qu’on sait ce qu’on doit prouver. Ce sera peut-être le sujet d’un prochain billet.