Brevet FR2845843A1 — publié le 20040416

La présente invention concerne un procédé d'authentification d'un premier dispositif appelé " dispositif à authentifier " par un second dispositif appelé " dispositif d'authentification ". L'invention s'applique en particulier dans le cas ou le dispositif à authentifier est une carte à puce. Le procédé d'authentification couramment employé utilise des fonctions de chiffrement à clés asymétriques (clé publique/clé privée). On peut citer, par exemple, le RSA ou le 10 SSL. L'avantage de ce procédé est sa facilité d'utilisation. Le premier inconvénient de ce procédé est qu'il existe des attaques consistants en la décomposition de la clé publique en facteurs premiers. Le second inconvénient de ce procédé est qu'il nécessite une grande puissance de traitement. On peut donc 15 difficilement utiliser ce procédé au sein d'un dispositif tel que la carte à puce. Un des procédés alors couramment utilisé dans le domaine des cartes à puce, consiste à utiliser un algorithme de signature implémenté dans la carte à puce. Ce procédé comprend 20 classiquement les étapes suivantes: génération d'un nombre aléatoire par le dispositif d'authentification, envoi de ce nombre à la carte à puce, calcul par la carte à puce d'un premier résultat prenant en compte ledit nombre aléatoire et éventuellement d'autres valeurs contenues dans la carte à puce, 25 envoi de ce premier résultat et éventuellement d'autres valeurs contenues dans la carte à puce au dispositif d'authentification, calcul par le dispositif d'authentification d'un second résultat prenant en compte les mêmes données que pour le premier résultat, et vérification par le dispositif d'authentification 30 de la cohérence des deux résultats. L'inconvénient de cette signature algorithmique est que les données émises par la carte à puce sont liées aux données reçues, ce qui permet au fraudeur d'établir une correspondance entre données émises et données reçues, et le cas échéant, de trouver la relation qui lie ces 35 données. Le fraudeur peut également envoyer un certain nombre de combinaisons aléatoires à la carte à puce et lire les résultats -2 renvoyés et ainsi établir une correspondance exhaustive entre les données reçues et les données émises sans en connaître la relation. Le problème technique est donc de réaliser un procédé 5 rendant impossible la contre-façon du dispositif à authentifier tout en utilisant des ressources matérielles et logicielles faibles. Sous sa forme la plus générale, l'invention est un procédé 10 d'authentification d'un dispositif B (dispositif à authentifier) par un dispositif A (dispositif d'authentification). Par exemple, le dispositif A est un terminal informatique d'une banque et le dispositif B est la puce d'une carte bancaire. Cette authentification proprement dite est appelée " authentification primaire ". Cette authentification primaire est constituée de deux autres authentifications appelées " authentifications secondaires ". Le procédé d'authentification proprement dit (authentification primaire) comporte les étapes suivantes: - B effectue une authentification secondaire du dispositif A. Si cette authentification secondaire échoue alors B met en òuvre un moyen visant à faire échouer l'authentification primaire. Si cette authentification secondaire réussit alors B accepte de se faire authentifier par A. - A effectue une authentification secondaire sur B. Si cette authentification secondaire échoue alors l'authentification primaire échoue. Si cette authentification secondaire réussit alors l'authentification primaire réussit. L'invention va donc maintenant porter sur la manière 30 d'effectuer les authentifications secondaires. On peut implémenter chacune de ces authentifications secondaires avec des procédés d'authentification connus. On peut citer, par exemple, la transmission d'un mot de passe ou d'un nombre signé. Selon l'invention, pour réaliser chaque authentification 35 secondaire, on prévoit la transmission d'un nombre dont on verra -3 comment il est généré et comment l'on procède pour vérifier son authenticité. L'invention est donc un procédé d'authentification appelé " authentification primaire " consistant en ce que A génère un 5 nombre noté NA, en ce que B génère un nombre noté NB et en ce que le procédé comporte les étapes suivantes - A envoie NA à B. - B reçoit un nombre noté N. Le nombre N correspond théoriquement au nombre NA, cependant il peut également 10 correspondre à un nombre envoyé par un fraudeur. B évalue donc l'authenticité de N. Si cette authentification échoue alors B met en òuvre un moyen visant à faire échouer l'authentification primaire. Si cette authentification réussit alors B envoie NB à A. - A reçoit un nombre noté M. Le nombre M correspond théoriquement au nombre NB, cependant il peut également correspondre à un nombre envoyé par un fraudeur. A évalue donc l'authenticité de M. Si cette authentification échoue alors l'authentification primaire échoue, si cette authentification 20 réussit alors l'authentification primaire réussit. Selon l'invention, chacun des nombres NA et NB est généré par un générateur pseudo-aléatoire (GPA). Par exemple, un GPA peut être implémenté par une suite mathématique à modulo ou un registre à décalage alimenté par une fonction de rétroaction. 25 Cependant, ces dispositifs présentent l'inconvénient d'être connus et donc sont susceptibles d'être " cassés " par un fraudeur. L'invention prévoit donc l'utilisation d'un GPA amélioré. Selon l'invention, un GPA est constitué d'une mémoire contenant des nombres aléatoires. On utilise alors un algorithme 30 permettant de générer un nombre à partir de cette mémoire. Par exemple, on peut organiser la mémoire sous forme d'une liste de nombres aléatoires et utiliser une fonction qui génère un ou plusieurs nombres de ladite liste lors d'une authentification (pour des raisons de sécurité évidentes, chaque nombre de la 35 liste est généré qu'une seule fois). Le premier avantage de ce GPA est que les nombres générés sont totalement décorrélés entre -4 eux et sont donc imprévisibles pour un fraudeur. Le second avantage de ce GPA est sa facilité de réalisation et donc sa facilité d'application à l'échelle industrielle, car il est principalement constitué d'une mémoire. Ainsi, lors d'une 5 authentification, le nombre NA est généré par le dispositif d'authentification (A) en utilisant un GPA du type de l'invention que l'on note GPANA. De même, lors d'une authentification, le nombre NB est généré par le dispositif à authentifier (B) en utilisant un GPA du type de l'invention que 10 l'on note GPANB. Selon l'invention, pour déterminer l'authenticité du nombre N reçu, B génère un nombre NA' en utilisant un GPA appelé GPANA'. On construit GPANA et GPANA' de manière à ce que les nombres NA et NA' générés à chaque authentification soient liés 15 par une relation (notée Rl). Cette relation peut être extrêmement simple, comme une relation d'égalité. C'est à dire que les nombres NA et NA' générés à chaque authentification sont égaux. Cette relation peut être plus compliquée, comme une relation de type mathématique ou algorithmique. Par exemple, NA' 20 peut être l'image de NA par une fonction mathématique ou un algorithme. De même, selon l'invention, à chaque authentification, pour déterminer l'authenticité du nombre M reçu, A génère un nombre NB' en utilisant un GPA appelé GPANB'. On construit GPANB et GPANB' de manière à ce que les nombres NB 25 et NB' générés à chaque authentification soient liés par une relation (notée R2). Cette relation peut être extrêmement simple, comme une relation d'égalité. C'est à dire que les nombres NB et NB' générés à chaque authentification sont égaux. Cette relation peut être plus compliquée, comme une relation de 30 type mathématique ou algorithmique, par exemple, NB' peut être l'image de NB par une fonction mathématique ou un algorithme. L'invention est donc un procédé d'authentification appelé " authentification primaire " consistant en ce que A génère deux nombres notés NA et NB' et en ce que B génère 35 deux nombres notés NB et NA'. Ces nombres sont générés de manière à ce qu'il y ait une relation (notée Ri) entre les -5 nombres NA et NA' et en ce qu'il y ait une relation (notée R2) entre les nombres NB et NB'. Le procédé comporte les étapes suivantes: - A envoie NA à B. - B reçoit un nombre noté N. B évalue s'il existe la relation Ri entre les nombres N et NA'. S'il n'existe pas la relation Ri entre N et NA' alors B met en oeuvre un moyen visant à faire échouer l'authentification primaire. S'il existe la relation Rl entre N et NA' alors B envoie NB à A. - A reçoit un nombre noté M. A évalue s'il existe la relation R2 entre les nombres M et NB'. S'il existe la relation R2 entre M et NB' alors l'authentification primaire réussit. S'il n'existe pas la relation R2 entre M et NB' alors l'authentification primaire échoue. A fait également échouer l'authentification si B met en oeuvre au moins un des moyens suivants * B envoie un message d'erreur à A. * B n'envoie rien à A avant l'expiration d'un " timer ". * B envoie une donnée volontairement non valide à A. L'invention permet ainsi de réaliser une authentification présentant une sécurité maximale. En effet, au cours d'une authentification, les deux seuls nombres échangés par A et B (NA et NB) sont complètement indépendants, ce qui empêche un éventuel fraudeur de " casser " l'authentification en étudiant 25 une relation éventuelle entre NA et NB. Ensuite, tous les nombres NA générés au cours de plusieurs authentifications sont aléatoires et donc indépendants les uns des autres, ce qui empêche un éventuel fraudeur de " casser " l'authentification en étudiant une relation éventuelle entre les différents nombres NA 30 générés. Il en est bien sur de même pour les nombres NB. Dans ces conditions, un éventuel fraudeur est incapable de prévoir quels sont les nombres qui seront échangés lors des futures authentifications. De plus, l'utilisation de fonctions ou d'algorithmes complexes, intégrant des fonctions à sens unique, 35 comme relation entre les nombres permet de sécuriser le stockage de ces nombres. -6 Pour " casser " le procédé décrit par l'invention, le fraudeur peut uniquement tenter de transmettre à A ou B des nombres pris au hasard. Pour remédier à ce problème, il suffira alors d'utiliser des nombres de très grande taille (codés sur plusieurs centaines de bits). La figure 1 illustre l'invention sous sa forme la plus complète. Les traits pointillés verticaux délimitent trois zones le dispositif d'authentification (à gauche), le canal de 10 transmission (au milieu), le dispositif à authentifier (à droite). Le canal de transmission est la zone dans laquelle un éventuel fraudeur peut lire et modifier les nombres transmis. La référence 1 représente l'envoi de NA par A à B. La référence 2 représente la réception d'un nombre par B que 15 l'on note N. La référence 3 représente le test permettant à B de déterminer si N et NA' sont liés par la relation Ri. La référence 4 représente l'envoi de NB par B à A. La référence 5 représente la mise en oeuvre par B d'un moyen 20 visant à faire échouer l'authentification primaire. Ce moyen peut être l'envoi d'un message d'erreur, l'envoi d'aucun nombre avant l'expiration d'un " timer " ou l'envoi d'un nombre volontairement non valide. 1 La référence 6 représente la réception d'un nombre par A que 25 l'on note M. La référence 7 représente le test permettant à B de déterminer si M et NB' sont liés par la relation R2. La référence 8 représente la réussite de l'authentification primaire. La référence 9 représente l'échec de l'authentification primaire. Nous allons maintenant décrire un mode de réalisation de l'invention. Dans cet exemple, A est un terminal informatique et 35 B est la puce d'une carte bancaire. Le type de GPA utilisé est une mémoire contenant une liste de 1000 nombres aléatoires, -7 chacun de ces nombres est un mot binaire de 1 kilo-octets. Au sein de cette liste, les nombres sont numérotés de 1 à 1000. Pour la ième authentification, le nombre généré est le i'me nombre de la liste. Les relations Ri et R2 sont des relations 5 d'égalité. La carte à puce et le terminal possède donc chacun un exemplaire du couple de GPA: GPANA / GPANB. Chacun de ces deux GPA est du type précédemment décrit et possède sa propre liste de nombres. Le terminal utilise son GPANA pour générer NA. Le terminal envoie NA à la carte à puce. La carte à puce utilise 10 son GPANA pour générer NA. La carte à puce utilise son GPANB pour générer NB. La carte à puce compare son nombre reçu et son nombre NA généré, si ces deux nombres sont identiques alors la carte à puce envoie NB au terminal, si ces deux nombres sont différents, alors la carte à puce envoie un nombre différent de 15 NB au terminal. Le terminal utilise son GPANB pour générer NB. Le terminal compare son nombre reçu et son nombre NB généré, si ces deux nombres sont différents alors l'authentification primaire échoue, si ces deux nombres sont identiques alors l'authentification primaire réussit. Dans cet exemple, le procédé peut réaliser 1000 authentifications. La carte à puce et le terminal doivent stocker chacun 2 méga-octets. Pour un fraudeur, la seule façon de faire réussir l'authentification est de trouver le nombre NA ou le nombre NB en essayant des nombres au hasard, sa 25 probabilité de réussir l'authentification est donc de 1/21024 soit environ 5,6.10-309. L'invention est susceptible d'application dans le domaine des carte à puces telles que les cartes bancaires, le porte30 monnaie électroniques, les cartes téléphoniques. L'invention est applicable d'une manière générale à tout dispositif informatique ou électronique nécessitant d'être authentifié. -8 REVENDICATIONS 1) procédé d'authentification appelé " authentification primaire " d'un dispositif B (dispositif à authentifier) par un dispositif A (dispositif d'authentification), caractérisé en ce qu'il est constitué de deux " authentifications secondaires " et en ce qu'il comporte les étapes suivantes: - B effectue une authentification secondaire du dispositif A, si cette authentification secondaire échoue alors B met en òuvre un moyen visant à faire échouer l'authentification primaire, si cette authentification secondaire réussit alors B 10 accepte de se faire authentifier par A; - A effectue une authentification secondaire sur B, si cette authentification secondaire échoue alors l'authentification primaire échoue, si cette authentification secondaire réussit alors l'authentification primaire réussit. 2) procédé d'authentification appelé " authentification primaire " d'un dispositif B (dispositif à authentifier) par un dispositif A (dispositif d'authentification) caractérisé en ce que A génère un nombre noté NA, en ce que B génère un nombre 20 noté NB et en ce que le procédé comporte les étapes suivantes - A envoie NA à B; - B reçoit un nombre noté N, B évalue l'authenticité de N, si cette authentification réussit alors B envoie NB à A. Si cette authentification échoue alors B met en oeuvre un moyen 25 visant à faire échouer l'authentification primaire; - A reçoit un nombre noté M, A évalue l'authenticité de M, si cette authentification échoue alors l'authentification primaire échoue, si cette authentification réussit alors l'authentification primaire réussit. 3) procédé d'authentification appelé " authentification primaire " d'un dispositif B (dispositif à authentifier) par un dispositif A (dispositif d'authentification) caractérisé en ce REVENDICATIONS que A génère deux nombres notés NA et NB' en ce que le B génère deux nombres notés NB et NA', en ce que ces nombres sont générés de manière à ce qu'il y ait une relation (notée Rl) entre les nombres NA et NA' et une relation (notée R2) entre les nombres 5 NB et NB' et en ce que le procédé comporte les étapes suivantes: - A envoie NA à B; - B reçoit un nombre noté N, B évalue s'il existe la relation Rl entre les nombres N et NA', s'il n'existe pas la 10 relation Rl entre N et NA' alors B met en oeuvre un moyen visant à faire échouer l'authentification primaire, s'il existe la relation Rl entre N et NA' alors B envoie NB à A; - A reçoit un nombre noté M, A évalue s'il existe la relation R2 entre les nombres M et NB', s'il existe la relation 15 R2 entre M et NB' alors l'authentification primaire réussit, s'il n'existe pas la relation R2 entre M et NB' alors l'authentification primaire échoue. 4) procédé selon l'une des revendications 1, 2 ou 3, 20 caractérisé en ce que B est une carte à puce. ) procédé selon l'une des revendications 1, 2, 3 ou 4, caractérisé en ce que A fait échouer l'authentification primaire si B met en oeuvre au moins un des moyens suivants 25 * B envoie un message d'erreur à A * B n'envoie rien à A avant l'expiration d'un " timer " * B envoie une donnée volontairement non valide à A 6) procédé selon l'une des revendications 2, 3, 4 ou 5, 30 caractérisé en ce que chaque nombre est généré par un générateur pseudo-aléatoire. -10 REVENDICATIONS 7) procédé selon la revendication 6, caractérisé en ce que le type de générateur pseudo-aléatoire utilisé est une suite mathématique à modulo. 8) procédé selon la revendication 6, caractérisé le type de générateur pseudo-aléatoire utilisé est d'une mémoire contenant des nombres aléatoires algorithme permettant de générer un nombre à partir mémoire. en ce que constitué et d'un de ladite 9) procédé selon la revendication 8, caractérisé en ce que le type de générateur pseudo-aléatoire utilisé est constitué d'une liste de nombres aléatoires et d'une fonction qui génère un des nombres de ladite liste pour chaque authentification. ) procédé selon l'une des revendications 3 à 9, caractérisé en ce que chacune des relations Rl et R2 est une des relations suivantes: * une relation d'égalité * une relation fonctionnelle: l'un des nombres et l'image de l'autre par une fonction.