Brevet FR2829334A1 — publié le 20030307

Procédé d'indentification sans secret à l'intérieur La présente invention concerne un procédé d'identification électronique contenant un dispositif d'identification qui n'a pas besoin de posséder un secret physiquement alors que pour s'identifier il lui est nécessaire de révéler la connaissance d'un secret. Bien que paradoxale a priori, la description qui suit éclairera le lecteur. Dans les années 70 la carte à puce a été inventée. Elle est née de l'idée selon laquelle on peut protéger dans une puce électronique des secrets soit par des mécanismes hardware soit par une dissémination de l'information soit les deux à la fois. Cependant, aucune technique aujourd'hui n'est complètement hermétique à l'intrusion et en fait si la fraude ne se fait pas davantage sur les cartes à puce c'est parce que les fraudeurs ont semble-t-il, pour l'instant, différé les investissements nécessaires à la scrutation interne des puces des cartes. On peut ainsi dire sans ambiguïté qu'aujourd'hui il est possible, avec les moyens adéquats, de forcer n'importe quelle carte à puce et, pire, d'en faire un clone. Parallèlement, des attaques grossières mais qui marchent, comme le collet marseillais, ont été mises au point et expérimentées avec succès. D'autre part, l'avènement de la téléphonie mobile et de l'Internet ont à la fois multiplié la nécessité d'identification électronique auprès de systèmes informatiques mais ont aussi créé des concurrents à la carte à puce. En effet, pourquoi payer nécessairement à l'aide d'une carte à puce alors que la fonction de sécurisation pourrait très bien s'intégrer dans le téléphone mobile lui-même par exemple. On va même jusqu'à la contradiction où le téléphone nécessite une sorte de carte à puce, la fameuse carte SIM pour fonctionner. Le marché de l'identification dans les années qui viennent devrait donc évoluer et se diversifier, la carte à puce ne devenant qu'un moyen parmi d'autres de s'identifier. Or, nous l'avons dit, l'identification à un ordinateur distant par exemple, nécessite non seulement de prouver qu'on connaît un secret, typiquement le mot de passe, mais encore faut-il que ce secret soit stocké quelque part dans la machine qui veut se connecter et c'est là que le bât blesse car il faut alors protéger ce secret physiquement. D'où la question suivante : Peut-on concevoir une architecture d'un dispositif d'identification à un ordinateur qui, tout en prouvant la cowKH. & Kmce t/'MK a 1. Algorithmique Il ne s'agit pas seulement ici de trouver une astuce hardware qui ferait fi des progrès de la cryptographie moderne. Au contraire, le procédé proposé ici doit être vu comme un tout, assurant la meilleure sécurité possible. Ainsi, nous allons proposer un algorithme d'identification qui est une preuve zero-knowledge au sens de Fiat-Shamir pour une personne extérieure à l'échange et qui n'a pas accès aux données qui sont à la fois dans le dispositif qui s'identifie et le dispositif qui identifie. C'est le plus haut standard de sécurité imaginable pour un protocole. Nous verrons dans le paragraphe suivant l'architecture hardware que cela implique pour la réalisation du dispositif d'identification. Commençons donc par décrire comment, pour notre cas, générer un protocole de preuve interactive zero-knowledge au sens de Fiat-Shamir qui convienne à une architecture d'un dispositif d'identification sans secret stocké à l'intérieur du dispositif en question. Appelons (E, A, Y, A...) une structure. Une telle structure peut-être par exemple (R, +,.) ou bien (Z/nZ,.) etc.. Etant donné un ensemble de propriétés que doivent vérifier les operations A cela caractérise un modèle de structure. Ainsi si l'opération A est associative, commutative, interne, possède un élément neutre et si tout élément possède un inverse pour Á, la structure (E, A) sera du modèle groupe commutatif. D'autres exemples de modèles de structure sont les corps, les anneaux (commutatifs ou non), les algèbres, les espaces vectoriels, les modules etc.. Considérons alors une structure (E, Á,.,. 6....) et supposons qu'il existe sur El xE2 x... xEn, où les Ei sont des sous-ensembles de E, une relation d'équivalence-compatible avec la structure de E ; c'est à dire que F = El XE2 x... xEn/-, l'ensemble quotient, muni des lois #, #, #... comme E, a le même modèle de structure que E. Supposons qu'il existe sur E un algorithme de chiffrement à clé publique f qui soit résistant à une attaque à chiffré choisi. Alors on peut facilement transposer à F un algorithme similaire à f sur E, mais où les opérations sont cette fois faites dans F. Appelons-le encore f par commodité et remarquons que d'un point de vue informatique, si une machine manipule les données de E pour effectuer les opérations A, V, A... lorsqu'on passe aux éléments de F qui sont des classes d'équivalence des éléments de El xE2 x... x En, la machine ne peut travailler qu'avec des représentants de ces éléments et non directement sur les classes d'équivalence. Ainsi, si x = (xi, 2,... Xn) E Ei xE2 x... xE, x n'est qu'un représentant de la classe d'équivalence x E F. Considérons alors l'algorithme f sur F qui chiffre x en calculant j-'= f (i). Considérons maintenant l'algorithme réciproque de f, soit/*'. Lorsqu'on va calculer (y), bien entendu, on va obtenir comme résultat Je. Cependant, rien ne dit qu'on va obtenir le représentant x de la classe d'équivalence x. En fait, dans le cas général, on obtiendra un représentant x'tel que x'= je. On peut même faire mieux. En faisant les"réglages"adéquats dans le calcul de j-1 on peut s'assurer que le représentant x'obtenu sera choisi avec la probabilité uniforme parmi les représentants possibles de je. Dans ce cadre, si Alice veut motrer à Bob son identité, le protocole suivant constitue un protocole de preuve interactive zero-knowledge en 1 tour au sens de Fiat-Shamir. Bob tire au hasard x E El xE2 x... xEn et envoie à Alice y = f (i). Alice renvoie alors, selon ce qui a été dit plus haut x'tel que x'= x. Si tel est le cas Bob accepte, sinon Bob refuse l'identification. N 2. Description du dispositif Décrivons d'abord les protagonistes d'une identification. Le modèle retenu est celui qui se produit par exemple lors de l'achat dans un magasin et paiement par carte bancaire. Beaucoup d'autres transactions peuvent se faire sur le même modèle, mais pour simplifier, nous décrirons ce cas. Nous supposerons qu'Alice veut donc payer un objet à Bob qui tient un magasin et que le compte d'Alice est géré par la banque de Claire. Le procédé d'identification s'effectue comme suit et le dispositif d'identification est la propriété d'Alice. Ce dernier contient, conformément à la figure 1, un système de fourniture de puissance électrique, qui peut être, dans le cas d'une carte à puce, une micro-pile interne comme dans la carte"VOCALID" (marque déposée) faite par la société"ELVA" (marque déposée). Si le dispositif d'identification est inclus dans un téléphone, la batterie convient. Reprenons maintenant les résultats du paragraphe précédent et supposons que nous ayons à notre disposition un protocol interactif de preuve zero-knowledge caractérisé par l'algorithme f Cet algorithme, pour être implanté dans du hardware, va avoir une représentation binaire. Appelons Mi, Mz,..., Un cette représentation. Tirons au hasard m valeurs parmi les u, et forçons les par exemple à zero. On obtient ainsi un algorithme f. C'est un peu comme si on avait percé des trous dans f C'est f'qui est stocké sur le dispositif d'identification. Avec lui, il nous faut un générateur pseudo-aléatoire PRGI. Une horloge interne, donnant la date et l'heure courante doit être incluse dans le dispositif Elle est alimenté par le système qui délivre la puissance électrique. Le dispositif doit aussi disposer soit d'un clavier (par exemple les 10 chiffres) soit d'un système biométrique de reconnaissance d'empreintes digitales ou autres. Lorsque le clavier ou le système biométrique sont activés correctement, c'est à dire soit avec la bonne séquence sur le clavier soit avec la bonne empreinte sur le système biométrique, une suite pseudo-aléatoire binaire est généré par le générateur PRO 1 considérant les données générées comme une graine, qui correspond exactement au complément des trous de f'pour former f Le câblage est donc réalisé en conséquence de façon à ce qu'une fois le code confidentiel tapé, l'algorithme f soit chargé dans le dispositif Qui plus est, le dispositif dispose d'un deuxième générateur aléatoire RG2. A l'inverse de PRG1, RG2 peut générer éventuellement un véritable aléa et pas seulement un pseudo-aléa. RG2 peut être initié par les données internes du dispositif qui peuvent être la date, l'état de certaines bascules etc.. La fonction de RG2 est de générer aléatoirement un élément A de F en choisissant au hasard un représentant x. Une fois cela fait, le dispositif calcule y = f (gd ( x)) où gd est une fonction quelconque d'une variable, inversible sur F et où d est une chaîne binaire contenant la date et l'heure. Une fonction monostable maintient la valeur y pendant une durée limitée, par exemple 1 minute. Au-delà, cette valeur est effacée. De plus, dès que y est calculé, l'algorithme f est effacé (il ne reste que f'). Alice transfère alors à Bob le quadruplet suivant (Alice y, x, d) Bob, lui, transfère à Claire le triplet (Alice, y, d). Claire est supposée connaître l'algorithme/-1 correspondant à Alice. A la réception du message de Bob, elle calculez = ga (x) et obtient x = gdl (gd ( x)). En fait, comme vu dans le paragraphe 1, Claire obtient en réalité x'tel que x'== i. Dans ces conditions et seulement si d correspond de façon"crédible"avec la date interne de Claire, cette dernière retourne x'à Bob qui vérifie si = t ou non. Si oui, Bob accepte de vendre, sinon il refuse. Pour qu'ensuite Claire, en tant que banque, paie Bob, il suffit que Bob exhibe les quadruplets qu'il lui a envoyés. On remarquera que si le dispositif d'identification est une carte à puce, alors il est nécessaire d'effacer f avant d'insérer la carte dans le lecteur. D'une façon générale, le dispositif ne doit pouvoir fournir comme information à Bob, que ce qui est spécifié dans la procédure ci-dessus ou bien ce qui est dans le dispositif de manière permanente et publique (i. e. f', PRG1, RG2, etc.). Le reste ayant servi au calcul doit être effacé. Nous constatons ainsi que le seul élément qui est et doit rester secret est l'algorithme/-1 et en particulier que le dispositif d'identification ne comporte aucun secret. Son contenu peut donc être publique et il peut même être cloné. La seule façon de s'identifier est alors soit de taper le code confidentiel sur son clavier soit d'avoir la bonne empreinte pour que le lecteur bio métrique fournisse la bonne graine à PRO 1. . 3. Utilité des fonctions secondaires Dans ce qui précède un certain nombre de fonctions a une utilité concernant la sécurité mais pas directement en ce qui concerne le protocole. En particulier, le caractère zero-knowledge est uniquement dû à l'algorithme alors que certains aspects d'attaques sont régulés par les fonctions secondaires. - La présence de la date permet en particulier d'éviter 1e "replay" c'est-à-dire la tentation pour Bob, ou une personne malveillante qui aurait enregistré les transactions, de rejouer le même message en envoi. De même en est-il pour la comparaison que fait Claire entre sa date courante et celle envoyée par Bob et issue d'Alice. - La fonction monostable qui efface les données après un certain temps évite que des données valides aient été chargées à un moment et que, le dispositifs ayant été subtilisé, le voleur puisse faire une transaction acceptée, fusse une seule d'ailleurs dans ce cas. - La source de puissance interne au dispositif, n'est nécessaire qu'à la determination de la date en permanence ou, dans le cas d'une carte à puce, à la détermination des éléments à transmettre tout en assurant l'effacement des éléments intermédiaires avant l'insertion dans un dispositif étranger et donc potentiellement dangereux pour le dispositif Ainsi, dans un processus d'identification où il ne serait pas nécessaire de se protéger contre ces attaques, le procédé d'identifications est caractérisé par les dialogues suivants entre Alice, Bob et Claire. Alice envoie à Bob le triplet (Alice, y, x), Bob transfère à Claire le couple (Alice, y), Claire calcule x'= f-l (y) et l'envoie à Bob. Bob vérifie si x'= x et en fonction de la réponse, accepte ou non l'identification. a 4. Cas d'une banque malhonnête Les cas étudiés ci-dessus ne répondent pas au critère où la banque, Claire, est malhonnête. Notamment, Alice doit se protéger contre une éventuelle banque qui pourraient sortir, ex-nihilo, de vraies-fausses transactions devant un tribunal. Pour ce faire, supposons qu'Alice possède une fonction de signature h. Le protocole fonctionne alors comme suit. Alice forme le quintuplet (Alice, h (Alice, d), y = f (gd (i)), x, d) qu'elle transfère à Bob. Ce dernier filtre et envoie à Claire le quadruplet (Alice, h (Alice, d), y, d). Comme précédemment, Claire envoie à Bob = gjl (f-' (Y et selon sa conformité avec x Bob accepte ou non la transaction. Le système diffère ici dans le sens où, devant un tribunal, Claire doit prouver qu'Alice a bien demandé la transaction effectuée. Or seule Alice est censée être capable de signer h (Alice, d), c'est une des propriétés fondamentales des algorithmes de signature. Dans notre cas, donc, la fonction de signature doit être incluse dans le dispositif d'identification. . REVENDICATIONS 1- Procédé d'identification caractérisé par l'interaction de 3 interlocuteurs, Alice, Bob et Claire, Alice transmettant à Bob le triplet (Alice, , x) où x est un élément tiré avec la probabilité uniforme sur la structure de travail (F, A, v. A...), y = f (x) où f est un algorithme cryptographique à clé publique sur la structure (F, A) transposé du même algorithme cryptographique à clé publique sur (E, A, y, et aussi noté f, où F = eX # E2 #...# En/#, chacun des Ei étant un sous-ensemble de E, - étant une relation d'équivalence sur le produit cartésien El xE x... xE, compatible avec la structure de (E, A, T, A...), Bob transmettant à Claire le couple (Alice, y), Claire calculant x'=/ (- l) (y) et renvoyantx1 à Bob, lequel vérifie si x'= x et acceptant l'identification ou non selon que cette égalité est ou non vérifiée. 2-Procédé d'identification selon la revendication 1 caractérisé par le fait que l'algorithme f sur la structure (E, #, #, #...) est un algorithme cryptographique à clé publique résistant à une attaque à chiffré choisi. 3-Dispositif d'identification pour la mise en oeuvre du procédé selon la revendication 1 caractérisé par la présence d'un clavier ou d'un dispositif bio métrique, un générateur pseudo-aléatoire prenant pour graine les données fournies par le clavier ou le dispositif bio métrique, un générateur aléatoire qui permet de tirer avec la probabilité uniforme #, une unité de stockage contenant une partie de l'algorithme f, notée f', laquelle partie f', est complétée par la sortie du générateur pseudo-aléatoire, cette complétion donnant f lorsque le bon code a été tapé sur le clavier ou la bonne empreinte fournie au dispositif bio métrique et une unité de calcul et d'envoi permettant de former et envoyer le message (Alice, y, #) décrit dans la revendication 1. 4-Dispositif d'identification selon la revendication 3 caractérisé par la présence d'une fonction d'effaçage qui élimine toute trace de f (seule reste la trace de f') dans le dispositif une fois le calcul du message à envoyer effectué. 5-Procédé d'identification selon la revendication 1 caractérisé, dans un mode de réalisation particulier, par le fait qu'Alice envoie à Bob le quadruplet (Alice, y, f, d) où d est une chaîne binaire contenant la date et l'heure courantes connues par Alice au moment de la transaction, y = f (d (x)), X et f étant choisi comme dans la revendication 1, où gd est une fonction inversible quelconque d'une variable sur F, Bob transmettant le triplet (Alice, y, d) à Claire, cette dernière calculant # = gd-1(f^(-1)(#)), vérifiant la corrélation entre la date et l'heure fournies par Alice via Bob et sa date et son heure propres, et en fonction de ce résultat acceptant ou non la poursuite de la transaction, fournissant dans le cas positif à Bob, ce dernier acceptant si et seulement si x'= i. 6-Dispositif d'identification selon la revendication 3 caractérisé, dans un mode de réalisation particulier, par la présence d'une source de puissance électrique interne au dispositif, cette source alimentant une horloge fournissant la date et l'heure en permanence, d'une fonction monostable permettant la survie des informations à envoyer pour une durée limitée, d'une unité de calcul ainsi que les interfaces nécessaires à la fourniture des données sous la forme décrite dans la revendication 5. 7- Procédé d'identification selon la revendication 1, caractérisé par le fait que le calcul de l'algorithme f A (~ 1) doit assurer de trouver un représentant x'de 1a classe x avec une distribution uniforme parmi les représentants possibles de la classe A. 8- Procédé d'identification, selon la revendication 1, caractérisé, dans un mode de réalisation particulier, par le fait qu'Alice dispose d'un algorithme de signature h et par le fait qu'elle fournit à Bob le quintuplet (Alice, h (Alice, d), y = f (gd (c)), i, d) où les éléments sont déterminés comme dans les revendications précédentes, Bob transmet ensuite le quadruplet (Alice, h (Alice, d), , d) à Claire, cette dernière renvoyant à Bob x'comme dans les revendications précédentes, mais archivant aussi les traces de la transaction comme preuve de la demande d'Alice. 9-Dispositif d'identification, selon la revendication 3, caractérisé, dans un mode de réalisation particulier, par le fait qu'il comporte une unité de signature électronique permettant la signature de l'identité du porteur et de la date de la transaction.