Brevet FR3127056A1 — publié le 20230317

Une liste de révocation (LR) comporte au moins une paire (h i , k i ) extraite d’une signature générée par une entité révoquée, où h i est un élément d’un groupe mathématique (G1) et k i = h i xi , où xi est un secret de ladite entité révoquée. Une première entité (100) envoie (E60), à une deuxième entité (200), pour s’authentifier auprès d’elle : - une signature (SIG) générée par ladite première entité (100) pour cette authentification ; - une chaîne de caractères (STR) ; - un élément (C i ) du groupe (G1) pour chaque paire (h i , k i ) de la liste de révocation (LR) ; - et une preuve (P) à divulgation nulle de connaissance que ladite première entité (100) a utilisé un secret (X100) de cette première entité (100) et la chaîne de caractères pour obtenir ledit élément de groupe (C i ) pour chacune des paires de ladite liste de révocation (LR). La deuxième entité rejette (F70) ladite première entité (100) si ladite preuve a divulgation nulle de connaissance (P) n’est pas valide ou si pour au moins une dite paire (h i , k i ), l’élément de groupe (C i ) est tel que C i = h i A , où A est une valeur connue. Fig. 2 Procédés et dispositifs d’authentification et de vérification de non-révocation Arrière-plan de l’invention L’invention se rapporte au domaine général de la protection des données numériques et de la cryptographie. Elle se situe plus particulièrement dans le contexte des mécanismes d’authentification. Ces mécanismes d’authentification sont aujourd’hui très largement répandus, notamment ceux à base de signature numérique ou de certificat. L’utilisation de signatures numériques pose un certain nombre de problèmes, notamment en ce qu’elle permet de tracer le signataire et en ce qu’elle révèle potentiellement trop d’informations sur le signataire. En effet, lorsqu’une signature numérique porte sur un ensemble de données certifiées, l’ensemble des données certifiées doit être révélé pour pouvoir en vérifier l’authenticité. Ceci a conduit au développement de techniques d’authentification qui visent à révéler le moins d’éléments possibles au moment d’une authentification. Ces techniques sont largement déployées et connues sous le nom de signatures numériques anonymes. Ces systèmes d’authentification anonymes posent cependant des difficultés lorsqu’il s’agit de révoquer les droits d’une entité. Pour répondre à ce problème, un mécanisme d’authentification connu sous le nom de EPID (Enhanced Privacy ID) a été défini (voir par exemple la publication « Enhanced privacy id: a direct anonymous attestation scheme with enhanced revocation capabilities » de Brickell et Li, publié à la conférence WPS2007). Dans ce mécanisme : - une entité est dite révoquée lorsqu’une de ses clés de signature est révoquée, ce qui est fait en plaçant une des signatures générées avec cette clé sur une liste de révocation ; - toute entité qui produit une signature doit apporter la preuve que cette signature n’a pas été produite avec la clé révoquée, c’est-à-dire avec la clé d’une signature enregistrée dans la liste de révocation, prouvant ainsi que l’entité qui s’authentifie n’est pas celle qui a été révoquée. L’invention se situe plus spécifiquement dans le contexte dans lequel les signatures comportent une paire (h, h x ), où h est un élément d’un groupe mathématique et x est le secret de l’entité signataire et dans lequel cette paire est inscrite dans la liste de révocation. Cette paire est notée (h i , k i = h i xi ) par la suite. La technique la plus efficace connue à ce jour pour rapporter la preuve qu’un secret x utilisé pour produire une signature diffère d’un secret xi utilisé pour produire une signature (h i , k i =h i xi ) de la liste de révocation nécessite d’envoyer trois éléments du groupe mathématique à l’entité qui vérifie la preuve, soit environ 894 bits. En pratique les listes de révocation peuvent contenir un nombre N très important de paires (h i , k i = h i xi ) typiquement plusieurs dizaines de milliers. Le fait de devoir communiquer 3.N éléments de groupe (ou 894.N bits) pour prouver qu’une entité signataire n’est pas révoquée peut constituer un inconvénient important lorsque N augmente. L’invention vise notamment une méthode d’authentification qui ne présente pas cet inconvénient. Objet et résumé de l’invention Selon un premier aspect, l’invention concerne un procédé d’authentification mis en œuvre par un dispositif d’authentification d’une première entité pour effectuer une authentification de cette première entité auprès d’une deuxième entité. Ce procédé comporte : - une étape de génération d’une signature pour authentifier la première entité auprès de la deuxième entité, ladite signature comportant une paire (h, h X100 ), où X100 est un secret propre à la première entité et h est un élément d’un groupe mathématique ; - pour chaque indice i d’une paire (h i , k i ) comprise dans une liste de révocation (LR), ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe, avec k i = h i xi , xi étant un secret propre à ladite entité révoquée : (i) une étape d’obtention, de façon déterministe, d’une valeur a i à partir dudit indice i et d’une chaîne de caractères propre à ladite authentification ; (ii) une étape d’obtention d’un élément du groupe mathématique selon la formule où : - h i et k i sont les éléments de la paire d’indice i dans la liste de révocation ; - A est une valeur connue ; - a i est ladite valeur obtenue de façon déterministe; et - X100 est le secret de la première entité ; - une étape de génération d’une preuve à divulgation nulle de connaissance que ledit dispositif d’authentification a utilisé le secret X100 et ladite chaîne de caractères pour obtenir ledit élément de groupe C i pour chacune des paires de la liste de révocation ; et - une étape d’envoi, à la deuxième entité : - de ladite signature; - de ladite chaîne de caractères ; - de ladite preuve à divulgation nulle de connaissance ; et - dudit élément C i pour chaque paire (h i , k i ) de la liste de révocation. Corrélativement, l’invention concerne un dispositif d’authentification d’une première entité, ledit dispositif étant configuré pour effectuer une authentification de cette première entité auprès d’une deuxième entité, ce dispositif comportant : - un module de génération d’une signature pour authentifier la première entité auprès de la deuxième entité, ladite signature comportant une paire (h, h X100 ), où X100 est un secret propre à la première entité et h est un élément d’un groupe mathématique ; - un module cryptographique configuré pour chaque indice i d’une paire (h i , k i ) comprise dans une liste de révocation, ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe, avec k i = h i xi , xi étant un secret propre à une entité ayant généré ladite signature : (i) obtenir, de façon déterministe, une valeur a i à partir dudit indice i et de ladite chaîne de caractères ; (ii) obtenir un élément C i dudit groupe mathématique (G1) selon la formule où : - h i et k i sont les éléments de la paire d’indice i dans la liste de révocation ; - A est une valeur connue ; - a i est ladite valeur obtenue de façon déterministe; et - X100 est le secret de l’entité 100 ; - un module de génération d’une preuve à divulgation nulle de connaissance que ledit dispositif d’authentification a utilisé le secret et la chaîne de caractères pour obtenir l’élément de groupe C i pour chacune des paires de ladite liste de révocation ; et - un module d’envoi, à la deuxième entité : - de ladite signature ; - de ladite chaîne de caractères ; - de ladite preuve à divulgation nulle de connaissance ; et - dudit élément C i pour chaque paire (h i , k i ) de la liste de révocation. Selon un deuxième aspect, l’invention concerne un procédé de vérification de non-révocation mis en œuvre par un dispositif de vérification de non-révocation d’une deuxième entité lors de l’authentification d’une première entité, ledit procédé comportant : - une étape de réception : - d’une signature générée par la première entité pour cette authentification ; - d’une chaîne de caractères ; - d’un élément C i d’un même groupe mathématique pour chaque paire (h i , k i ) comprise dans une liste de révocation, ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe, avec k i = h i xi , xi étant un secret propre à ladite entité révoquée ; et - d’une preuve à divulgation nulle de connaissance que ladite première entité a utilisé un secret de cette première entité et ladite chaîne de caractères pour obtenir ledit élément de groupe pour chacune des paires de la liste de révocation ; et - une étape de rejet pour cause de révocation de ladite première entité si ladite preuve a divulgation nulle de connaissance n’est pas valide ou si pour au moins une dite paire (h i , k i ), l’élément de groupe C i est tel que C i = h i A , où A est une valeur connue. Corrélativement, l’invention concerne un dispositif de vérification de non-révocation, ce dispositif étant configuré pour vérifier lors de l’authentification d’une première entité auprès d’une deuxième entité, si cette première entité doit être rejetée pour cause de révocation, ce dispositif comportant : - un module de réception : - d’une signature générée par la première entité pour cette authentification ; - d’une chaîne de caractères ; - d’un élément C i d’un même groupe mathématique pour chaque paire (h i , k i ) d’une liste de révocation, ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe, avec k i = h i xi , xi étant un secret propre à ladite entité révoquée ; et - d’une preuve à divulgation nulle de connaissance que ladite première entité a utilisé un secret de cette première entité et ladite chaîne de caractères pour obtenir ledit élément de groupe C i pour chacune des paires de ladite liste de révocation ; et - un module de rejet pour cause de révocation de ladite première entité si ladite preuve a divulgation nulle de connaissance n’est pas valide ou si pour au moins une dite paire (h i , k i ), l’élément de groupe C i est tel que C i = h i A , où A est une valeur connue. D’une façon générale, l’invention se situe dans le contexte de l’authentification d’une première entité auprès d’une deuxième entité, aucune limitation n’étant attachée à la nature des première et deuxième entités. Par exemple : - la première entité est un processeur et la deuxième entité est un serveur du fabricant de ce processeur ; - la première entité est un dispositif client et la deuxième entité est un dispositif serveur ; - la première entité est une carte à microcircuit et la deuxième entité est un lecteur d’une telle carte ; - etc. Comme mentionné en introduction, l’invention propose un mécanisme dans lequel une première entité qui cherche à s’authentifier auprès d’une deuxième entité, produit pour cette nouvelle authentification une signature avec un secret qui lui est propre, et apporte la preuve à cette deuxième entité que ce secret est différent de tous les secrets utilisés pour produire des signatures desquelles ont été extraites des paires enregistrées dans la liste de révocation. Dans un mode particulier de réalisation, la liste de révocation est créée et mise à jour par la deuxième entité. Par exemple, lorsque la deuxième entité considère qu’une entité qui s’est authentifiée auprès d’elle avec une signature a un comportement suspect, elle enregistre la paire (h i , k i ) de cette signature dans la liste de révocation. Mais ce mode de réalisation n’est pas limitatif, la liste de révocation pouvant être créée ou maintenue par un tiers, voire par une pluralité de tiers. De façon remarquable, si on appelle N le nombre de paires dans la liste de révocation, on note que la preuve de non-révocation en tant que telle comporte : - d’une part une chaîne de caractères et une preuve à divulgation nulle de connaissance, quel que soit le nombre de paires dans la liste de révocation ; et - d’autre part, un unique élément du groupe mathématique, Ci, par paire dans la liste de révocation. Ce résultat est particulièrement intéressant, car comme mentionné auparavant, dans les meilleures techniques connues, la preuve de non révocation comporte trois éléments du groupe mathématique par paire dans la liste de révocation. L’unique élément de groupe Ci envoyé dans la technique proposée a une taille maximum de 380 bits alors que dans l’art antérieur connu, les trois éléments cycliques présentent, cumulés, une taille de 894 bits. Pour plus de renseignements, l’homme du métier peut se reporter aux documents https://electriccoin.co/blog/new-snark-curve/ et https://link.springer.com/chapter/10.1007%2F978-3-540-45146-4_8 , Section 5. Le gain apporté par l’invention est très important, surtout quand le nombre de signatures révoquées augmente. Dans un mode particulier de réalisation de l’invention, la preuve à divulgation nulle de connaissance est produite en utilisant le protocole de Schnorr décrit dans la publication « Efficient Identification and Signatures for Smart Cards » de Claus-Peter Schnorr, CRYPTO 1989 ». Lorsque le protocole de Schnorr est utilisé, la preuve à divulgation nulle de connaissance ne contient que 2 scalaires (entier modulo p), de 256 bits chacun. Elle a donc une taille de 512 bits quel que soit le nombre N de paires dans la liste de révocation. Par ailleurs, le calcul de C i est particulièrement avantageux. En effet conformément à l’invention (1) où : - h i et k i sont les éléments de la paire d’indice i dans la liste de révocation ; - A est une valeur connue, par exemple 1 ; - a i est la valeur obtenue de façon déterministe; et - X100 est le secret de la première entité. Grâce à cette formule, la vérification de la non-révocation est extrêmement simple. En effet, si la première entité a déjà été révoquée, la liste de révocation comporte une paire (h i , k i ) avec k i =h i X100 . Et dans ce cas, C i = h i A (par exemple C i = h i si A = 1). Le dispositif de vérification de non-révocation peut donc détecter très facilement, sur la base du seul élément de groupe C i reçu, que la première entité doit être rejetée pour cette nouvelle authentification. Il lui suffit, après avoir vérifié la validité de la preuve à divulgation nulle de connaissance pour s’assurer que les éléments C i ont bien été formés, de comparer la valeur C i reçue avec h i A . Au contraire, si le secret X100 de la première entité n’a été utilisé dans aucune des signatures dont les paires sont mémorisées dans la liste de révocation, alors l’élément C i apparaît au dispositif de vérification de non-révocation comme une valeur pseudo-aléatoire. Cette caractéristique est très intéressante d’un point de vue de préservation de l’anonymat car l’élément C i ne révèle aucune information sur le secret X100. La chaîne de caractères précitée peut être quelconque. La seule contrainte est qu’elle soit propre à cette nouvelle authentification, autrement dit qu’elle soit différente des autres chaînes de caractères utilisées pour constituer des preuves de non-révocation pour des authentifications précédentes de la première entité. En pratique, le dispositif d’authentification ne vérifie pas explicitement que la chaîne de caractères n’a pas été utilisée pour prouver une non-révocation pour une authentification précédente de l’entité. Mais le mécanisme d’obtention de la chaîne de caractères est tel qu’une telle collision est statistiquement improbable ; la chaîne de caractères est par exemple un aléa de 256 bits. Dans un mode de réalisation, la chaîne de caractères est au moins une partie de la signature. Ce mode de réalisation est particulièrement avantageux car il évite de devoir envoyer la chaîne de caractères en tant que telle, celle-ci pouvant être déduite directement par le dispositif de vérification de non-révocation à partir de la signature. Dans un mode de réalisation, la valeur a i est obtenue par ai = H(STR ‖ i) où H est une fonction de hachage publique. Dans un mode de réalisation, le groupe mathématique est un groupe cyclique d’un ordre p, p étant un nombre premier. L’invention s’applique en particulier mais de façon non limitative lorsque les signatures sont produites pour des groupes bilinéaires. Dans un mode particulier de réalisation, les différentes étapes du procédé d'authentification et les différentes étapes du procédé de vérification de non-révocation sont déterminées par des instructions de programmes d'ordinateurs ou sont implémentées par une puce en silicium qui comprend des transistors adaptés pour constituer des portes logiques d'une logique câblée non programmable. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un dispositif ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé d'authentification ou d’un procédé de vérification de non-révocation tel que décrit ci-dessus. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, une mémoire non volatile de type flash ou encore un moyen d'enregistrement magnétique, par exemple un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. D’autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent des exemples de réalisation dépourvus de tout caractère limitatif. Sur les figures : La représente un dispositif d’authentification et un dispositif de vérification de non-révocation conformes à un mode particulier de réalisation de l’invention ; La représente, sous forme d’organigramme, les principales étapes d’un procédé d’authentification et les principales étapes d’un procédé de vérification de non-révocation conformes à un mode particulier de réalisation de l’invention ; La représente l’architecture fonctionnelle d’un dispositif d’authentification conforme à un mode particulier de mise en œuvre de l’invention ; et La représente l’architecture fonctionnelle d’un dispositif de vérification de non-révocation conforme à un mode particulier de mise en œuvre de l’invention. Procédé d’authentification mis en œuvre par un dispositif d’authentification (10) d’une première entité (100) pour effectuer une authentification de ladite première entité (100) auprès d’une deuxième entité (200), ledit procédé comportant : - une étape (E10) de génération d’une signature (SIG) pour authentifier la première entité (100) auprès de la deuxième entité (200), ladite signature (SIG) comportant une paire (h, h X100 ), où X100 est un secret propre à ladite première entité (100) et h est un élément d’un groupe mathématique (G1) ; - pour chaque indice i d’une paire (h i , k i ) comprise dans une liste de révocation (LR), ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe (G1), avec k i = h i xi , xi étant un secret propre à ladite entité révoquée : (i) une étape (E30) d’obtention, de façon déterministe, d’une valeur a i à partir dudit indice i et d’une chaîne de caractères (STR) propre à ladite authentification ; (ii) une étape (E40) d’obtention d’un élément C i dudit groupe mathématique (G1) selon la formule où : - h i et k i sont les éléments de la paire d’indice i dans la liste de révocation (LR) ; - A est une valeur connue ; - a i est ladite valeur obtenue de façon déterministe; et - X100 est le secret de la première entité (100) - une étape (E50) de génération d’une preuve (P) à divulgation nulle de connaissance que ledit dispositif (10) a utilisé le secret X100 et ladite chaîne de caractères (STR) pour obtenir ledit élément de groupe C i pour chacune des paires de ladite liste de révocation (LR) ; et - une étape (E60) d’envoi, à la deuxième entité (200) : - de ladite signature (SIG); - de ladite chaîne de caractères (STR) ; - de ladite preuve (P) à divulgation nulle de connaissance ; et - dudit élément C i pour chaque paire de la liste de révocation (LR). Procédé d’authentification selon la revendication 1 dans lequel ledit groupe mathématique est un groupe cyclique d’un ordre p, p étant un nombre premier. Procédé d’authentification selon la revendication 1 ou 2, dans lequel ladite chaîne de caractères (STR) est au moins une partie de ladite signature (SIG). Procédé d’authentification selon l’une quelconque des revendications 1 à 3, dans lequel ladite valeur a i est obtenue par a i = H(STR ‖ i) où H est une fonction de hachage publique. Procédé de vérification de non-révocation mis en œuvre par un dispositif (20) de vérification de non-révocation d’une deuxième entité (200) lors de l’authentification d’une première entité (100), ledit procédé comportant : - une étape (F60) de réception : - d’une signature (SIG) générée par ladite première entité (100) pour cette authentification ; - d’une chaîne de caractères (STR) ; - d’un élément C i d’un même groupe mathématique (G1) pour chaque paire (h i , k i ) comprise dans une liste de révocation (LR), ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe (G1), avec k i = h i xi , xi étant un secret propre à ladite entité révoquée ; - et d’une preuve (P) à divulgation nulle de connaissance que ladite première entité (100) a utilisé un secret (X100) de cette première entité (100) et ladite chaîne de caractères (STR) pour obtenir ledit élément de groupe (C i ) pour chacune des paires comprise dans la liste de révocation (LR) ; et - une étape (F70) de rejet pour cause de révocation de ladite première entité (100) si ladite preuve a divulgation nulle de connaissance (P) n’est pas valide ou si pour au moins une dite paire (h i , k i ), l’élément de groupe (C i ) est tel que C i = h i A , où A est une valeur connue. Programme d’ordinateur (PGA) comportant des instructions pour l’exécution des étapes du procédé d’authentification selon l’une quelconque des revendications 1 à 4 lorsque ledit programme est exécuté par un ordinateur. Programme d’ordinateur (PGV) comportant des instructions pour l’exécution des étapes du procédé de vérification de non-révocation selon la revendication 5 lorsque ledit programme est exécuté par un ordinateur. Dispositif d’authentification (10) d’une première entité (100), ledit dispositif étant configuré pour effectuer une authentification de ladite première entité (100) auprès d’une deuxième entité (200), ledit dispositif (10) comportant : - un module (MGS) de génération d’une signature (SIG) pour authentifier la première entité (100) auprès de la deuxième entité (200), ladite signature (SIG) comportant une paire (h, h X100 ), où X100 est un secret propre à ladite première entité (100) et h est un élément d’un groupe mathématique (G1) ; - un module cryptographique (CRY) configuré pour chaque indice i d’une paire (h i , k i ) comprise dans une liste de révocation (LR), ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe (G1), avec k i = h i xi , xi étant un secret propre à ladite entité révoquée: (i) obtenir, de façon déterministe, une valeur a i à partir dudit indice i et d’une chaîne de caractères (STR) propre à ladite authentification ; (ii) obtenir un élément C i dudit groupe mathématique (G1) selon la formule où : - h i et k i sont les éléments de la paire d’indice i dans la liste de révocation (LR) ; - A est une valeur connue ; - a i est ladite valeur obtenue de façon déterministe; et - X100 est le secret de l’entité 100 ; - un module (MGP) de génération d’une preuve (P) à divulgation nulle de connaissance que ledit dispositif d’authentification (10) a utilisé le secret X100 et ladite chaîne de caractères (STR) pour obtenir ledit élément de groupe (C i ) pour chacune des paires de ladite liste de révocation (LR) ; et - un module (COM1) d’envoi, à la deuxième entité (200) : - de ladite signature (SIG); - de ladite chaîne de caractères (STR) ; - de ladite preuve (P) à divulgation nulle de connaissance ; et - dudit élément C i du pour chaque paire de la liste de révocation (LR). Dispositif (20) de vérification de non-révocation, ledit dispositif étant configuré pour vérifier lors de l’authentification d’une première entité (100) auprès d’une deuxième entité (200), si cette première entité doit être rejetée, ledit dispositif comportant : - un module (COM2) de réception : - d’une signature (SIG) générée par ladite première entité (100) pour cette authentification ; - d’une chaîne de caractères (STR) ; - d’un élément C i d’un même groupe mathématique (G1) pour chaque paire (h i , k i ) d’une liste de révocation (LR), ladite paire (h i , k i ) ayant été extraite d’une signature générée par une entité révoquée, h i étant un élément dudit groupe (G1), avec k i = h i xi , xi étant un secret propre à ladite entité révoquée ; - et d’une preuve (P) à divulgation nulle de connaissance que ladite première entité (100) a utilisé un secret (X100) de cette première entité (100) et ladite chaîne de caractères (STR) pour obtenir ledit élément de groupe C i pour chacune des paires de ladite liste de révocation (LR) ; et - un module (MR) de rejet pour cause de révocation de ladite première entité (100) si ladite preuve a divulgation nulle de connaissance (P) n’est pas valide ou si pour au moins une dite paire (h i , k i ), l’élément de groupe C i est tel que C i = h i A , où A est une valeur connue. Procédés et dispositifs d’authentification et de vérification de non-révocation