Schéma aléatoire de pré-distribution de clés de L.ESCHENAUER et D.GLIGOR
Eschenauer et Gligor ont proposé un schéma de gestion de clé basé sur la probabilité de partager une clé entre les nœuds d'un graphe aléatoire. Il fournit des techniques pour la pré- distribution de clé, la découverte de la clé partagée, l'établissement de chemin de clé, et la révocation de clé.
L'idée maîtresse de ce schéma, est de distribuer aléatoirement un certain nombre de clés, issues d'un ensemble fini à chaque nœud du réseau avant son déploiement. Deux nœuds quelconques seront en mesure de s'échanger des messages sécurisés s'ils possèdent une clé commune.
Un grand ensemble S de clés est générée (217-220 Clés). Pour chaque nœud, m clés sont choisies au hasard de l'ensemble S (S= {(kid1, key1), (kid2, key2),....}). Ces m clés sont stockées dans la mémoire du nœud et forment le trousseau de clés du nœud. Le nombre de clés |S| de l'ensemble est choisi de telle manière que deux sous-ensembles aléatoires de S de taille m auront une certaine probabilité p d'avoir au moins une clé en commun, par exemple pour une probabilité p=0.5 on a besoin d'un sous ensemble de taille m=75 clés de l'ensemble S de taille |S|=10,000 clés.
Les nœuds découvrent leurs voisins et plus particulièrement ceux avec qui ils sont en mesure de communiquer de façon sécurisée car ils possèdent une clé identique dans leur trousseau de clés respectif. Le protocole peut être de diffuser la liste des identités kidi des clés possédées. La clé partagée devient la clé de session du lien entre les deux nœuds. La figure suivante illustre cette phase :
Après la phase de découverte de clés partagées, le réseau devient un graphe connecté formé de quelques liens sécurisés. Les nœuds peuvent alors utiliser les liens existants pour mettre en place des clés partagées avec leurs voisins qui ne partageaient pas de clé en commun avec eux. La figure suivante illustre cette phase :
La révocation d'un nœud compromis se fait par l'élimination de leur trousseau de clés. Pour cela, un nœud contrôleur (qui a une grande connectivité et peut être mobile) annonce un message simple de révocation contenant une liste signée de k identificateurs des clés (kidi) pour que ces clés soient retirées des trousseaux de clés des autres noeuds. La liste des identités est signée par une clé de signature Ke générée par le nœud contrôleur et envoyée en unicast à chaque nœud i en la chiffrant avec la clé Kci (la clé Kci est partagée entre le contrôleur et le ième nœud pendant la phase de pré- distribution de clés). Quelques liens seront disparus à cause de la suppression de clés du noeud compromis ce qui nécessite une reconfiguration de ces liens (par la découverte de clés partagées ou l'établissement de chemin de clé). La figure suivante illustre cette phase :
Ce schéma est identique à celui de Eschenaur et Gligor sauf qu'au lieu d'exiger le partage d'une clé commune pour sécuriser un lien, une paire de nœud doit partager q clés avec q > 1 pour établir un lien sécurisé. La nouvelle clé utilisée pour la communication entre ces deux nœuds est le hash de toutes les clés partagées, par exemple pour deux nœuds quelconque qui partage q' clés (q'≥q) la clé utilisée pour la communication est K = hash (k1 || k2 || ... || kq'). Plus le nombre de clé partagées augmente plus la résilience contre la capture du nœud augmente. Autrement, lorsque le nombre, exigé, de clés partagées augmente, il devient plus difficile à un attaquant avec un ensemble donné de clés de casser un lien. Cependant, pour préserver une probabilité donnée p que deux nœuds partageant des clés suffisantes pour établir un lien sécurisé, il est nécessaire de réduire la taille de l'ensemble de clés S. Ceci permet à un attaquant de gagner un plus grand échantillon de S en cassant peu de nœuds.
La figure suivante illustre un exemple de partage de clés avec q=2.
