Brevet FR2920618A1 — publié le 20090306

PROCEDE DE DISTRIBUTION DE CLES CRYPTOGRAPHIQUES DANS UN RESEAU DE COMMUNICATION La présente invention concerne un protocole de négociation distribué de clés 5 cryptographiques. Elle s'applique, notamment, dans la sécurité des échanges entre les entités d'un réseau de communication. Ce réseau peut être un réseau fixe fortement redondant, c'est-à-dire qu'il comporte plusieurs chemins de routage ou encore un réseau ad hoc. Les réseaux ad hoc sont formés via l'auto 10 configuration des tables de routage de chacun des noeuds communicants faisant partie intégrante du réseau. Dans un réseau fixe, le problème de la sécurité est généralement résolu via des systèmes d'infrastructures de gestion des clés désignées sous 15 l'abréviation IGC, permettant le partage d'une clé ou d'un certificat entre les entités du réseau communicant. Cette généralisation n'est pas toujours souhaitable vu la complexité de mise en oeuvre d'une telle infrastructure. Dans ce contexte, la sécurisation d'un canal entre deux utilisateurs doit pouvoir faire face à un nombre important d'attaque sans l'aide externe d'une 20 ICG. Dans un réseau Ad hoc, le problème est d'autant plus important que la notion d'infrastructures de clés est pratiquement inexistante du fait même de la mobilité et de la volatilité de la topologie ad hoc. En effet, un réseau ad hoc est un réseau dans lequel le routage des informations est effectué par les 25 noeuds composant le réseau. Il n'existe pas d'infrastructures fixes de routage permettant la connaissance de la topologie globale du réseau. Chacun des noeuds du réseau se comporte comme un routeur avec ses voisins. Dans ce cadre, les problèmes techniques à résoudre sont de plusieurs ordres : chacun des noeuds doit pouvoir à un instant donné connaître une partie de la 30 topologie du réseau afin de pouvoir communiquer avec un noeud destinataire. Ce problème est résolu en partie, par des protocoles dit 2 proactifs qui établissent les routes à l'avance grâce à une gestion périodique des tables de routage et les protocoles réactifs qui recherchent les routes à la demande, dans ce dernier cas, le noeud source et/ou les noeuds destinataires sont équipés de tables et de protocole de routage permettant de déterminer les chemins à emprunter par un message. La confiance dans le réseau est un des problèmes majeurs dans le cadre des réseaux ad hoc. En effet, les informations de routage et les informations utilisateurs circulent via des noeuds de communications privés, donc avec un niveau de confiance nul. Le réseau Ad hoc étant par nature mobile, aucun système de confiance, infrastructure de clés publiques, ne peut être réalisé dans ce contexte. En effet, la validation doit être effectuée par le système de confiance. L'art antérieur, connu du Demandeur, concerne le protocole d'échange de clés via Internet plus connu sous l'abréviation anglo-saxonne IKE pour Internet Exchange Key, qui permet le calcul d'un secret commun afin de sécuriser l'échange entre deux entités. Ce protocole est décrit dans le document RCF 2409 de l'IETF disponible à l'adresse internet suivante http://www.ietf.ora/rfc/rfc2409.txt. Bien qu'il soit efficace, ce protocole présente les inconvénients suivants : • La longueur des échanges entre les deux partenaires occasionne une surchage dans la bande passante du réseau, • II ne permet la vérification du secret qu'à partir d'une clé ou d'un certificat pré partagé via un moyen organisationnel hors communication, • Ce protocole n'est pas adapté à une gestion du réseau ad hoc et il est donc vulnérable à une attaque qui consiste à ce qu'une personne malveillante se fasse passer pour le pair de chacun des deux utilisateurs de la communication, en générant un secret en lieu et place des utilisateurs finaux, plus connue sous l'abréviation MIM (en 3o anglo-saxon Men ln the Middle) 3 Dans le cadre d'un réseau ad hoc, il est aussi connu de mettre en oeuvre des protocoles basés sur la certification d'anneau de noeuds communicants, ainsi que la décomposition de la clé privée par une opération mathématique polynomiale. De même, l'un des inconvénients des certifications de groupe par anneau est la capacité MIM précitée au niveau de l'anneau. De manière plus générale, l'état de l'art précité permet de partager un secret commun entre deux entités d'un réseau fixe, via une simple liaison de routage. Par contre, ce secret est validé par le chiffrement et la vérification du dit secret par une clé pré partagée ou par un certificat fourni par une infrastructure de gestion de clés (IGC ou infrastructure de clé publique PKI). Dans le contexte des réseaux centralisés, la confiance entre les acteurs est mise en oeuvre via des certificats ou des signatures, déployés à partir d'infrastructures de gestion à clés publiques (IGC). Ce mécanisme permet à une autorité dite de certification, de valider la confiance des informations entre les divers utilisateurs certifiés. La confiance est donc localisée au niveau d'une seule entité, regroupant les fonctionnalités de certification, de validation et de révocation des utilisateurs ou d'équipements regroupés au sein d'un groupe déterminé détenant les certificats valides. Cette stratégie de sécurité dans un réseau fonctionnant avec le protocole Internet ou IP est donc basée sur la centralisation de la confiance en un noeud unique du réseau, et d'une diffusion de cette confiance sous la forme de certificats par des méthodes administratives (cartes à puce, clé USB,...). En dehors de ce cadre, il existe plusieurs mécanismes cryptographiques permettant de partager un secret commun, via un procédé à divulgation nulle. Un de ces principes ou mécanismes est le protocole Diffie-Hellman, noté DH dans la description, mis en oeuvre dans le protocole IKE précité. Ce principe, qui sera rappelé dans le paragraphe suivant, présente comme principal défaut MIM. Le protocole Diffie Hellman est rappelé à la figure 1. Les concepts théoriques de la cryptographie à clé publique remontent à l'article publié par Diffie et Hellman en 1976 (W.Diffie-M.E.Hellman : New Directions in cryptography. IEEE Trans. on Information Theory, VoI.IT-22-6, November 1976). Le principal résultat de cet article fondateur est la possibilité pour deux utilisateurs communiquant via un réseau peu sûr, de se mettre d'accord sur une clé de session, destinée à chiffrer leurs communications ultérieurs. Soit G= un groupe cyclique. Les deux participants Ut U2 choisissent chacun au hasard x1,x2 appartenant au groupe cyclique G respectivement et échangent les valeurs gxl gx2 sur le réseau. L'utilisateur Ut (respectivement U2) calcule alors le secret Diffie-Hellman gXlX2 en recevant le message de U2 (respectivement U1). Cette hypothèse stipule qu'étant donnée trois valeurs gxl gX2 gr, un adversaire polynomial ne peut décider avec un avantage significatif si gr = gx'X2 ou non. L'attaque connue du MIM est présenté sur la figure 2. Un ou plusieurs utilisateurs malveillants H s'interposent entre les deux participants Ul, U2, et va se charger de relayer les informations de l'un vers l'autre. La figure 2 représente le cas où il n'y a qu'un tiers malveillant. Lorsque Ul échange sa valeur g''sur le réseau en destination de U2, l'attaquant H va se faire passer pour U2 et répondre à sa place via un secret gh. Il fera de même pour le participant U2. Dans ce cadre, les deux participants communiqueront par un canal pseudo confidentiel via l'attaquant H avec les secrets communs, entre Ul et H : gX''h et entre U2 et H : gx2.h Un des buts de l'invention est d'offrir une solution aux problèmes de confiance entre au moins deux entités d'un réseau. L'objet de l'invention concerne, notamment, un protocole de négociation distribuée de clés via un mécanisme de répartition redondant et non sensible unitairement d'une valeur publique sensible à l'attaque précitée, cette valeur permettant à chacun des participants à générer un secret commun, sur un ensemble dynamique de chemins de routage dans un réseau cible. Le réseau peut être un réseau ad hoc ou encore un réseau fixe. L'ensemble de chemins de routage peut être fixé au démarrage ou encore évoluer au cours du temps. L'objet de l'invention concerne un procédé permettant de distribuer des éléments pour générer une ou plusieurs clés cryptographique ou de chiffrement entre au moins deux utilisateurs A et B dans un réseau comprenant plusieurs noeuds Ni reliés entre eux au moyen d'artères de communication, le réseau mettant en oeuvre un protocole de routage, caractérisé en ce qu'il comporte au moins les étapes suivantes : • pour communiquer avec B, A génère une valeur publique sensible à une attaque malveillante où un tiers cherche à se faire passer pour un participant au réseau ou �MIM � et la décompose utilisant une transformation mathématique en m segments de redondance o, c'est-à-dire qu'une information est recomposable à partir de o segments, et transmet ces informations concaténées avec un message référence Na sur le réseau par k chemins de routage, • pour communiquer avec A, B génère une valeur publique sensible à une attaque MIM et le décompose en utilisant une transformation mathématique en m segments de redondance o, c'est-à-dire qu'une information est recomposable à partir de o segments, et transmet ces informations concaténées avec un message référence Nb sur le réseau par k chemins de routage, • les deux participants A et B régénèrent le secret commun en recalculant la transformée inverse de toutes les combinaisons de o segments et en choisissant la valeur statistiquement la plus représentée : gab- et g-ab • une fois calculés les deux secrets supposés communs, ga' pour A, et et g-ab pour B, le participant A envoie un message de vérification correspondant au message référence Nb de B chiffré avec le secret commun : gab' et l'envoie vers le participant B : { Nb } gab-, B déchiffre alors le message de A avec sa clé g-ab et vérifie la cohérence avec son message référence Nb, puis renvoie vers le message d'acquittement de la même manière : { Na } g-ab pour validation du secret commun entre les deux entités, et utilisation du secret commun pour coder un message. Le message référence Na, Nb pour les participants A et B est, par exemple, 5 un aléa. D'autres caractéristiques apparaîtront à la lecture de la description détaillée donnée à titre d'exemple non limitatif qui suit faite en regard de dessins annexés qui représentent : la figure 1, un schéma relatif au protocole de Diffie-Hellman, 10 la figure 2, un exemple d'attaque de type MIM du protocole Diffie- Hellman, la figure 3, un routage Multi-chemin dans le réseau Ad hoc, la figure 4, la structure du protocole DHD selon l'invention natif dans un réseau Ad Hoc, et 15 - la figure 5 la structure du protocole DHD intégré dans la version 6 du protocole ou IP.v6 en option. Afin de mieux faire comprendre le principe du procédé et du système selon l'invention, l'exemple donné ci-après de manière non limitative est basé sur 20 le mécanisme de décomposition et de recomposition de l'information Diffie-Hellman, et sa répartition sur un réseau ad hoc comprenant plusieurs noeuds Ni reliés entre eux au moyen d'artères de communication, une source A et un destinataire B. Le mécanisme de distribution et de diffusion de la valeur publique de Diffie-Hellman via plusieurs chemins de routage permet de 25 disperser la possibilité d'une attaque sur la communication entre les deux entités au moment de la négociation de la clé qui servira au chiffrement du canal de communication. Tout autre mécanisme de cryptographie, en dehors du mécanisme de Diffie-Hellman peut être utilisé. 30 La figure 4 illustre le principe mis en oeuvre par le procédé selon l'invention. L'exemple est donné à titre non limitatif pour le cas d'un réseau ad hoc de forte densité. Cet exemple peut correspondre aux réseaux qu'il existera dans les métropoles dans quelques années. Le réseau pourrait aussi être un réseau fixe comportant un nombre de chemins suffisant pour exécuter les étapes du procédé selon l'invention. Les chemins de routage empruntés par les parties de la valeur publique calculée sont, de préférence, des chemins disjoints, c'est-à-dire qu'ils ne comportent pas de noeuds Ni en commun. Dans le cas où le réseau comprend des chemins pseudo-disjoints, le procédé autorise un pourcentage de noeuds à se croiser. Dans cet exemple, le procédé comporte plusieurs étapes détaillées ci-après : a) le procédé calcule une valeur publique sensible au MIM prédéfinie de type Diffie-Hellman, par exemple, puis morcelle cette valeur calculée par une exponentiation Diffie-Hellman, par exemple, par une transformée mathématique Mojette dont une description peut être trouvée dans l'article de Jean-Pierre Guédon, séminaire IRCCyN juin 2001 disponible sur le site Internet Jean-Pierre.Guédon@irccyn.ec-nantes.fr, par les deux entités qui échangent de l'information (entité qui émet l'information et entité qui va la recevoir). En lieu et place de la transformée Mojette, il est possible d'utiliser un code Reed Solomon ou toute type de traitement présentant des fonctions similaires à celles de la fonction Mojette. La valeur publique sert à fabriquer la valeur secrète ou secret partagé par les utilisateurs. b) l'étape suivante consiste à communiquer sur plusieurs chemins de routage entre les deux entités, une ou plusieurs parties de la valeur publique sensible au MIM sur un chemin donné, et, par exemple, un aléa unique à tous les chemins associés à chacune des entités ; la voie de routage comprenant les chemins et les noeuds empruntés par les différentes portions de la valeur publique est choisie en fonction du type de réseau. Dans le cas d'un réseau proactif, c'est l'émetteur ou source qui choisit le chemin, ce dernier ayant été mémorisé à l'initialisation ou démarrage du système. Dans le cas d'un réseau filaire, les modifications permettant de choisir une route au niveau d'un noeud sont choisies via une étiquette ou label, par exemple MPLS. c) la troisième étape comporte la synchronisation du secret commun par le calcul inverse Mojette du secret commun via les parties récupérées sur les divers chemins, en utilisant le calcul inverse de la transformation mathématique utilisée lors de la première étape, puis la vérification de ce secret via le chiffrement par le secret commun d'un aléa respectif de chacune des entités, et de la communication de cette donnée chiffrée entre les partenaires. Par exemple, l'émetteur A génère une valeur publique qu'il transmet à une deuxième entité B, afin que ce dernier puisse calculer la valeur du secret commun. La valeur du secret commun est obtenu en mettant en oeuvre la transformée inverse de Mojette, par exemple, de toutes les combinaisons de o segments, o correspondant à la redondance utilisée, et en choisissant pour chacun, A et B, la valeur statistiquement la plus représentée. Cette opération est effectuée pour A et pour B de façon individuelle. Ensuite, A et B vérifient que les deux valeurs trouvées sont identiques. Dans le cas où il y a identité, A et B, utilisent alors cette valeur comme clé de chiffrement. Dans le cas contraire, il peut y avoir soupçon d'une intrusion malveillante dans les communications entre A et B. La transformée Mojette est une transformée mathématique de Radon discrète qui permet de projeter un ensemble de données d'un espace de dimension N sur un espace de dimension N-1. Cette transformée possède les propriétés nécessaires de � morcellement � et de � sécurité � dans le cadre du protocole. Il est aussi possible d'utiliser la transformée Reed Solomon en lieu et place de la transformée Mojette. La transformation utilisée dans le procédé selon l'invention présente comme particularité de générer de la redondance. Cette redondance est distribuée sur les segments résultant de la décomposition de la valeur publique sensible en plusieurs parties ou portions. Le choix de la valeur de redondance à utiliser est définie, par exemple, en fonction du nombre de chemins qui peut être attaqué. De manière détaillée, le procédé distribué de négociation de clés selon l'invention comporte au moins les étapes suivantes : En considérant, pour mieux fixer les idées, un réseau ad hoc, de taille N, avec deux participants A et B communiquant via k chemins disjoints ou partiellement disjoints (cf. Figure 3). Ces chemins seront choisis dans la base topologique de chacun des deux noeuds communicants A et B, via la mise en oeuvre d'un protocole de découverte de chemin basé sur un mode pro-actif selon des principes connus de l'Homme du métier et qui ne seront donc pas précisés. Les noeuds intermédiaires jouent le rôle de routeur et transmettent un paquet vers le prochain noeud, ceci en suivant les voies de routage prédéfinies ou définies en temps réel, comme il a été mentionné ci-dessus. Le protocole distribué de négociation de clés sera alors décrit par les phases suivantes : • Pour communiquer avec B, A génère une valeur publique sensible au MIM selon le protocole DH, par exemple ga, et la décompose en m 15 segments de redondance o (c-a-d que l'information est recomposable à partir de o segments), avec o Données chemin k : gamll Na Dans le cas où k sensible au MIM selon le protocole de Diffie-Hellman DH gb, et la décompose en m segments de redondance o (c-a-d que l'information 10 est recomposable à partir de o segments), avec o attaquant, soit par une erreur réseau : g" gf2 gfi , avec j+l statistiquement la plus représentée : gai).- et g-ab (dans le cas pratique, un trigger devra être positionné afin de raccourcir le temps de calcul). Dans le cas du participant A, le calcul mis en oeuvre est le suivant : 30 gab_ .9 max(M-1 (gY' gyi+f gvi+2 gY+0) avec g" appartenant à [gb' gf] Dans le cas du participant B, le calcul mis en oeuvre est le suivant : g-ab -> max(M 1 (gY gY'+' gY'+2 gY+°) avec gY' appartenant à [gai ghi]• Une fois calculé les deux secrets supposés communs, ga' pour A, et et g-ab pour B, le participant A envoie un message de vérification correspondant au Nonce Nb de B chiffré avec la clé générée via le secret commun : gab' et l'envoie vers le participant B : { Nb } gab~ B déchiffre alors le message de A avec sa clé g"ab et vérifie la cohérence avec son Nonce Nb, puis renvoie vers le message d'acquittement de la même manière : { Na } g`ab.pour validation de la négociation de la clé commune entre les deux entités. Ce principe permet de résister à plusieurs attaques de type MIM � Men in The Middle �, avec mise en oeuvre d'une décision (représentativité d'une donnée vis à vis du nombre total de combinaisons) afin de retenir la valeur la plus cohérente gX. De même, ce principe permet de valider l'intégrité des données gX de la communication. En effet, si toutes les combinaisons possibles de o segments donnent le même résultat, nous pouvons conclure qu'il n'y a pas eu modification intentionnelle ou non de la communication. Format du protocole Diffie-Hellman Distribué Dans le cadre de l'exemple donné pour un réseau ad hoc, le protocole distribué de négociation de clés est, par exemple, mis en oeuvre en l'intégrant de manière représentative (Identifiant DHD) tel qu'il est schématisé à la figure 4, dans la donnée du format du protocole Ad hoc. Identifiant Trame : IDO, Référence ou Nonce de la source : Ns, Un segment ou une partie concaténée des segments : S., Chacun des segments sera représenté par : Identification de la Politique DH (elliptique, polynomiale,...) Identifiant de la projection : IDP, Numéro de segments : NS, Données du segment : DS, suivant le procédé DH. Dans le cadre d'une application à un réseau IPv6, où le protocole distribué de négociation de clés est vue en tant que option IPv6, tel qu'il est représenté à la figure 5, le procédé inclut les champs suivants : Identifiant Option : IDO, Référence ou Nonce de la source : Ns, Un segment ou une partie concaténée des segments : Ss, Chacun des segments sera représenté par : Identification de la Politique DH (elliptique, polynomiale,...) : PDH Identifiant de la projection : IDP, Nombre de segments : NTS, Numéro de segments : NS, Données du segment : DS sur x octets, suivant le procédé DH. Le procédé et le système selon l'invention offrent notamment les avantages 15 suivants : Le procédé utilise plusieurs chemins de distribution en décomposant l'information entre les deux participants afin de ne communiquer qu'une aprtie de la valeur publique à chacun de ses voisins ; si un ou plusieurs attaquants tentent de modifier la valeur DH de chacun des participants 20 finaux, il ne pourra qu'en modifier un certain pourcentage, qui est d'autant plus faible que le nombre de décomposition est important. Il n'est pas nécessaire que les utilisateurs disposent de clés pré partagées ou de certificats via un moyen organisationnel hors communication, Le système composé par les deux entités se suffit à lui-même, et permet de 25 créer un canal sécurisé en utilisant la distribution d'éléments redondants et non sensibles unitairement, Le système est autonome et ne dispose, en fonctionnement normal, de centre de gestion de clés, avantage dans un réseau ad hoc où la gestion des clés est un problème non résolu actuellement par l'art antérieur. 30 Le protocole selon l'invention ne nécessite pas de clés ou de certificats prépartagés entre les deux entités. Chaque entité doit pouvoir recalculer le secret commun à partir d'un ensemble redondant de parties du secret original et vérifie la cohérence de ce secret entre les deux entités. Sans sortir du cadre de l'invention, le procédé et le système selon l'invention peut être mise en oeuvre sur des équipements ou des solutions de sécurité permettant un minimum de configuration pour l'utilisateur, et notamment, dans le calcul et le partage du secret pré partagé. Dans ce cadre, il est possible de l'utiliser dans les systèmes du marché civil, tels que les téléphones VoIP, les terminaux mobiles, mais aussi les équipements radio tactiques qui doivent utiliser un réseau ad hoc dans le cadre de déploiement localisé et qui ont un besoin de sécurisation d'une communication sur une période temporelle courte donnée. 20 25 REVENDICATIONS 1 û Procédé permettant de distribuer des éléments pour générer une ou plusieurs clés cryptographiques entre au moins deux utilisateurs A et B dans un réseau comprenant plusieurs noeuds Ni reliés entre eux au moyen d'artères de communication, le réseau mettant en oeuvre un protocole de routage, caractérisé en ce qu'il comporte au moins les étapes suivantes : • pour communiquer avec B, A génère une valeur publique sensible à une attaque malveillante où un tiers cherche à se faire passer pour un participant au réseau ou � MIM � et la décompose utilisant une transformation mathématique en m segments de redondance o, c'est-à-dire qu'une information est recomposable à partir de o segments, et transmet ces informations concaténées avec un message référence Na sur le réseau par k chemins de routage, • pour communiquer avec A, B génère une valeur publique sensible à une attaque MIM et le décompose en utilisant une transformation mathématique en m segments de redondance o, c'est-à-dire qu'une information est recomposable à partir de o segments, et transmet ces informations concaténées avec un message référence Nb sur le réseau par k chemins de routage, • les deux participants A et B régénèrent le secret commun en recalculant la transformée inverse de toutes les combinaisons de o segments et en choisissant la valeur statistiquement la plus représentée : ga' et gùab • une fois calculés les deux secrets supposés communs, gab" pour A, et et g_ab pour B, le participant A envoie un message de vérification correspondant au message référence Nb de B chiffré avec le secret commun : ga' et l'envoie vers le participant B : { Nb } gab-, B déchiffre alors le message de A avec sa clé g"ab et vérifie la 30 cohérence avec son message référence Nb, puis renvoie vers le message d'acquittement de la même manière : { Na } g-ab pourvalidation du secret commun entre les deux entités, et utilisation du secret commun pour coder un message. 2 û Procédé selon la revendication 1 caractérisé en ce que le message 5 référence Na, Nb pour les participants A et B est un aléa. 3 û Procédé selon la revendication 1 caractérisé en ce que la transformée mathématique est la transformée de Mojette. 10 4 û Procédé selon la revendication 1 caractérisé en ce que l'on utilise le protocole Diffie-Hellman pour générer la valeur publique sensible au MIM. û Procédé selon la revendication 1 caractérisé en ce que l'on utilise le protocole Reed-Solomon pour générer la valeur publique sensible au MIM. 15 7 û Procédé selon la revendication 1 caractérisé en ce que l'étape de régénération du secret commun comporte les étapes suivantes : Dans le cas du participant A, on a le calcul suivant : gab- -) max(M 1 (gyi gyi+1 gyi+2 gY+O)' avec g" appartenant à [gbi ,gfi] 20 Dans le cas du participant B, on a le calcul suivant : g-ab .3 max(M 1 (gyi gyi+1 gyi+2 . gY+O), avec gYi appartenant à [gai ,gni]. 8 û Procédé selon la revendication 1 caractérisé en ce que le réseau est un réseau ad hoc. 9 û Procédé selon l'une des revendications 1 ou 8 caractérisé en ce que le protocole de routage est un protocole pro actif. 25 30..DA1: 20090306