Brevet FR3006789A1 — publié le 20141212

B12725 - 13-R0-0469 1 PROTECTION CONTRE DES INJECTIONS DE FAUTES DANS UN GÉNÉRATEUR DE NOMBRES ALÉATOIRES Domaine La présente demande concerne de façon générale des circuits électroniques et, plus particulièrement, les circuits exploitant des nombres aléatoires et incluant un ou plusieurs 5 circuits de génération de nombres aléatoires. Exposé de l'art antérieur Des nombres aléatoires ou pseudo-aléatoires sont couramment utilisés dans des applications cryptographiques ou de sécurité. L'utilisation de nombres aléatoires permet de masquer 10 des données à protéger (par exemple des clés secrètes) dans des traitements numériques, typiquement des algorithmes cryptographiques. Les nombres aléatoires sont également utilisés dans des systèmes de transmission chiffrés ou d'authentification. Pour que l'utilisation d'un nombre aléatoire produise 15 ses effets, il faut qu'il soit le moins déterministe possible. De plus, il faut qu'il ne soit pas susceptible d'être imposé par un attaquant, par exemple, dans le cadre d'une attaque par injection de fautes. En effet, si le nombre aléatoire peut être perturbé et perdre son caractère non déterministe, celà 20 introduit une faiblesse dans la sécurité de l'algorithme exploitant ce nombre aléatoire. B12725 - 13-R0-0469 2 On prévoit ainsi d'associer, aux générateurs de nombres aléatoires, des processus de vérification du caractère non déterministe des nombres générés, par exemple, en effectuant des tests statistiques sur une plus ou moins grande profondeur (en nombre de bits du nombre aléatoire). Ces techniques de vérification ont besoin d'être améliorées. Résumé Un mode de réalisation de la présente description vise 10 à pallier tout ou partie des inconvénients des mécanismes de génération de nombres aléatoires et, plus particulièrement, face à des attaques par injection de fautes. Selon un premier aspect, un mode de réalisation de la présente description vise à proposer une technique de détection 15 d'une attaque par injection de fautes visant la génération d'un nombre aléatoire. Selon un deuxième aspect, un mode de réalisation de la présente description vise à proposer une technique de protection d'une génération de nombres aléatoires contre une attaque par 20 injection de fautes. Un mode de réalisation de la présente description vise à proposer une technique de détection et/ou de protection résistant à différents types d'attaques par injection de fautes. Selon un mode de réalisation, on prévoit un procédé de 25 protection d'une génération d'un nombre aléatoire contre des attaques par injection de fautes, dans lequel un mot fourni par un algorithme cryptographique de traitement d'un train de bits fourni par une source de bruit est soumis à une fonction résiliente pour fournir le nombre aléatoire. 30 Selon un mode de réalisation, ladite fonction résiliente comporte un nombre de bits de sortie fonction de la taille du mot aléatoire souhaité. Selon un mode de réalisation, ladite fonction résiliente est une fonction cryptographique. B12725 - 13-R0-0469 3 Selon un mode de réalisation, le nombre de bits d'entrée de la fonction résiliente correspond au nombre de bits de sortie de l'algorithme cryptographique. Selon un mode de réalisation, on prévoit un circuit de 5 génération d'un nombre aléatoire. Brève description des dessins Ces caractéristiques et avantages, ainsi que d'autres, seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non limitatif en 10 relation avec les figures jointes parmi lesquelles : la figure 1 est un schéma bloc simplifié d'un exemple de circuit électronique du type auquel s'applique les modes de réalisation qui vont être décrits ; la figure 2 illustre, de façon très schématique et 15 sous forme de blocs, un exemple de générateur de nombres aléatoires ; la figure 3 illustre, de façon très schématique et sous forme de blocs, un autre exemple plus détaillé de générateur de nombres aléatoires ; 20 la figure 4 représente, de façon très schématique et sous forme de blocs, un mode de réalisation d'un procédé de détection d'une injection de fautes dans un générateur de nombres aléatoires selon le premier aspect ; la figure 5 illustre le fonctionnement du mécanisme de 25 détection de la figure 4 ; la figure 6 représente, de façon très schématique, une variante du procédé de détection ; la figure 7 représente, de façon très schématique et sous forme de blocs, un mode de réalisation d'un procédé de 30 protection d'un générateur de nombres aléatoires contre des injections de fautes ; et la figure 8 illustre le fonctionnement du mécanisme de protection de la figure 7. B12725 - 13-R0-0469 4 Description détaillée De mêmes éléments ont été désignés par de mêmes références aux différentes figures. Par souci de clarté, seuls les étapes et éléments utiles à la compréhension des modes de réalisation qui vont être décrits ont été représentés et seront détaillés. En particulier, l'exploitation faite des nombres aléatoires générés, que ce soit par un algorithme de chiffrement, par un mécanisme de transmission chiffrée ou plus généralement par tout circuit électronique n'a pas été détaillée, les modes de réalisation qui vont être décrits étant compatibles avec les utilisations habituelles de nombres aléatoires. De plus, les sources de bruit généralement utilisées pour la génération de nombres aléatoires n'ont pas non plus été détaillées, les modes de réalisation décrits étant là encore compatibles avec tout type de source de bruit habituellement utilisable pour la génération de nombres aléatoires. Dans la description qui suit, on fera référence à la terminologie "nombres aléatoires" mais on comprendra qu'il s'agit en fait de nombres pseudoaléatoires ou non déterministes, le caractère aléatoire du nombre n'étant en pratique que statistique. La figure 1 représente, de façon très schématique et sous forme de blocs, un exemple de circuit électronique 1 du type auquel sont susceptibles de s'appliquer les modes de 25 réalisation qui vont être décrits. Un tel circuit comporte généralement un processeur de traitement 12 (par exemple de type microcontrôleur) susceptible de communiquer, par un ou plusieurs bus 13 de données, d'adresses et de commandes, avec différents circuits 30 électroniques du système. Parmi ces circuits, on trouve habituellement des mémoires 14 (MEM) de type volatile ou non volatile, reprogrammable ou non ; un ou plusieurs circuits 15 d'entrée/sortie (I/O) pour communiquer avec les différents circuits internes et externes au système ; et différentes 35 fonctions électroniques (symbolisées en figure 1 par un bloc 16, B12725 - 13-R0-0469 FCT). Ces fonctions n'ont pas été détaillées et dépendent de l'application à laquelle est destiné le circuit 1. Dans les applications visées par la présente description, le circuit 1 inclut également un générateur 2 de 5 nombres aléatoires (RNG) dont des modes de réalisation seront décrits par la suite. Les nombres aléatoires générés par le circuit 2 sont exploités, par exemple, par un crypto-processeur 17 (CP) destiné à mettre en oeuvre des algorithmes de chiffrement ou d'authentification, etc. La représentation de la figure 1 est schématique et partielle. Le système incluant un générateur aléatoire 2 peut comprendre de multiples circuits de traitement analogiques et/ou numériques. La figure 2 est un schéma bloc d'un exemple de 15 générateur 2 de nombres aléatoires. Un tel générateur est basé sur l'utilisation d'une source de bruit 22 (NS). Cette source de bruit a pour rôle de générer un signal le plus aléatoire possible. La source de bruit 22 peut être basée sur un circuit analogique associé à une 20 conversion analogique-numérique pour fournir une succession d'états sur un signal numérique RB représentant des bits de valeur 0 ou 1. La source de bruit est, par exemple, un oscillateur en anneau, avec ou sans boucle à verrouillage de phase (PLL). 25 Le train de bits RB est soumis à un post-traitement 24 (PP) dont le rôle est de répartir équitablement, sur les bits de sortie, l'entropie du train de bits généré par la source de bruit. Le train de bits est ensuite mis en forme (bloc 26, 30 RP) en fonction de l'application pour répartir les bits par groupes de bits destinés à cette application. Enfin, les bits sont groupés en mots pour former des nombres aléatoires RN et sont placés dans un registre de sortie 28 (REG) susceptible d'être lus, par exemple, par le processeur 35 cryptographique 17 (figure 1). B12725 - 13-R0-0469 6 En général, un test statistique 30 est effectué sur les groupes de bits contenus dans le registre 28. La figure 3 représente, de façon très schématique et sous forme de blocs, un exemple plus détaillé d'une chaîne de 5 génération de nombres aléatoires illustrant, en particulier, un exemple de post-traitement. Dans l'exemple de la figure 3, la source de bruit 22 est divisée en une source de bruit analogique 221 (ANS), suivie d'un circuit d'extraction 223 (EXTRACT) dont le rôle est 10 d'extraire un train de bits du bruit analogique. Les bits fournis par la source de bruit 22 sont soumis à un post-traitement 24 constitué, dans cet exemple, d'un algorithme cryptographique (bloc 244, ALGO) exploitant une clé (bloc 242, K), de préférence secrète pour chiffrer le train de 15 bits. Le circuit 26 de mise en forme est alors une mémoire tampon (BUFF), exploitée par l'algorithme cryptographique par exemple pour stocker les résultats intermédiaires des différents tours de chiffrement. Le contenu de la mémoire 26 est transféré vers le registre 28 en fin de traitement. 20 Dans l'exemple de la figure 3, un test supplémentaire 32 (LR) est effectué en parallèle au traitement cryptographique. Ce test supplémentaire peut prendre diverses formes, par exemple, une vérification du fait que les états des bits du train RB fournis par la source ne restent pas à 1 ou à 0 pendant 25 trop longtemps. Les contre-mesures usuelles à des tentatives d'injection de fautes pour perturber le caractère aléatoire du train de bits généré exploitent soit le test statistique 30, soit le test 32. 30 Une première catégorie de fautes qu'est susceptible de subir un générateur aléatoire est une injection d'une fréquence particulière au niveau de la source de bruit, notamment si celle-ci est formée d'un oscillateur en anneau. L'objectif de l'attaquant est alors de stabiliser la fréquence de 35 l'oscillateur en anneau, ce qui lui permet d'imposer la valeur B12725 - 13-R0-0469 7 de sortie du flux de bits. Une telle attaque est typiquement détectée grâce au test 32 qui détecte alors que la sortie fournit des bits à l'état 1 ou à 0 pendant une durée déterminée. Cependant, cette attaque n'est pas détectable au 5 niveau du nombre généré lui-même, c'est-à-dire après le post-traitement algorithmique. On améliore généralement la résistance de la source de bruit en utilisant une boucle à verrouillage de phase qui évite une stabilisation de la fréquence de l'oscillateur en anneau. 10 Une autre catégorie d'attaques susceptibles d'être subies par un générateur de nombres aléatoires est une attaque par injection de fautes sous forme d'impulsions, dans laquelle l'attaquant injecte, en aval de la source de bruit, une impulsion perturbatrice de durée brève (type impulsion de 15 Dirac). Une telle perturbation n'est alors plus détectable par le test vérifiant les états successifs des bits (test 32) dans la mesure où elle n'impacte qu'une faible portion du train de bits. Une telle attaque peut également être mise en oeuvre au niveau de la sortie de l'algorithme de chiffrement (au niveau du 20 tampon 26) et n'est alors pas détectable par les tests usuels. Selon un premier aspect, on prévoit un mécanisme de détection d'une perturbation volontaire ou accidentelle sur un générateur de nombres aléatoires. La figure 4 illustre, sous forme de blocs, un mode de 25 réalisation d'un procédé de détection d'une attaque par injection de fautes. Selon ce mode de réalisation, on prévoit d'intercaler dans le train de bits, en aval de la source de bruit 22, par exemple juste après le circuit d'extraction 223 (figure 3), un 30 motif (bloc 42, DN), par exemple, une suite de bits déterminée. Ce motif est, en parallèle, fourni à une entité 44 de vérification (CHECK) qui reçoit également le signal sur lequel a été effectuée l'injection du motif DN. Le rôle de l'entité 44 est de vérifier que le motif DN se retrouve bien dans le signal 35 dans lequel ce motif a été injecté. Dans le cas d'une attaque B12725 - 13-R0-0469 8 par injection de fautes sous forme d'impulsions qui cible la logique combinatoire du circuit, le motif DN sera perturbé au même titre que le signal généré par la source de bruit. Par conséquent, si le circuit 44 ne retrouve pas le motif 42, cela signifie une faute. L'injection du motif 42 correspond à intercaler des bits entre les bits du train RB généré par la source 22. Le motif DN peut être fixe, variable, secret ou non. Il peut même lui-même être constitué d'un motif aléatoire dans la mesure où sa valeur est stockée dans le circuit 44 pour vérification. La taille du motif et sa répartition dans le train de bits sont choisies en fonction de la capacité attendue de l'attaquant. Par exemple, si l'on considère qu'une faute de l'attaquant va se répartir sur n bits, on s'assure qu'au plus n-1 bits du train RB se retrouvent entre deux motifs. Ainsi, une faute touchera au moins un bit du motif (au pire les n-1 bits d'alea et un bit du motif) et sera détectée. Si un attaquant est capable d'injecter une faute sur un seul bit, il sera cependant contraint de répéter cette injection de faute pour obtenir un résultat exploitable. Une répartition irrégulière du motif permet alors de détecter l'attaque car il faudrait que l'attaquant connaisse cette répartition. La façon d'intercaler les bits du motif dans les bits du flux aléatoire peut varier, de façon fixe ou de façon aléatoire. Selon divers exemples, on pourra prévoir d'intercaler un bit du motif DN tous les deux bits du train RB, d'alterner les bits du train RB et ceux du motif DN un par un, deux par deux, etc., d'insérer deux bits du motif DN pour un bit du train RB, inversement, etc. La figure 5 illustre, sous forme de chronogrammes représentant des séquences de bits, le fonctionnement du mécanisme de protection de la figure 4. On suppose que la source de bruit 22 génère nativement une série RB de bits 01101, etc. On suppose également que le motif DN est constitué par la suite de bits 11001. Le mécanisme de détection consiste, dans cet exemple, à intercaler un bit sur deux du motif avec un bit sur B12725 - 13-R0-0469 9 deux de la source de bruit. Par conséquent, le signal présent en aval de la source de bruit contient la suite 0111100011, etc. Connaissant le motif DN et sa règle de distribution dans le train de bits RB, le circuit 44 est capable de vérifier que le motif est toujours présent dans le train modifié résultant RBM et, ainsi, de détecter si une faute a été injectée dans le signal. De préférence, on adapte la période avec laquelle sont intercalés les bits du motif à ce que l'on attend comme attaque. Par exemple, si l'on considère qu'un attaquant à le pouvoir de changer n bits, les trains de bits sont interrompus au moins tous les n-1 bits par un ou plusieurs bits du motif DN. Si l'on considère que l'attaquant ne peut changer qu'un seul bit, on cherchera à conserver secret le schéma d'insertion du motif dans le train de bits RB. On aurait pu penser que l'introduction d'un motif, en particulier d'un motif déterminé répétitif, en aval de la source de bruit, nuirait au caractère aléatoire du nombre généré. Toutefois, en raison de son insertion dans le flux de bits aléatoires, et surtout en raison du post-traitement appliqué avant la fourniture du nombre aléatoire, l'introduction de ce motif n'est en pratique pas gênant. En variante, le motif est supprimé du train de bits juste avec le passage dans le post-traitement. La figure 6 représente, de façon très schématique et sous forme de blocs, un autre mode de réalisation selon lequel le motif DN est injecté non pas au niveau de la source de bruit 22 mais plus en aval, par exemple, avant le test 32. Dans ce cas, le circuit 44 prélève le signal également avant le test 32 pour vérifier la présence du motif. La fonction 223 peut en effet modifier le train de bits. On pourra prévoir d'intercaler des bits à plusieurs endroits du circuit. On prévoit alors soit plusieurs circuits de vérification 44, soit un seul circuit 44 qui prélève le signal 35 dans la position la plus aval dans le cheminement des bits, B12725 - 13-R0-0469 10 pourvu d'être capable, au niveau du circuit 44, de repérer le ou les motifs. Intercaler des bits entre d'autres bits sur un signal ne pose pas de problème particulier. En fait cela revient à prélever le signal sur le conducteur (entre les deux circuits) où l'on souhaite faire l'injection. Par exemple, on peut utiliser un registre à décalage contenant les bits du motif DN, asservi par un compteur. Tous les k (k supérieur ou égal à 1) bits du train RB, on ajoute une suite de t bits (t supérieur ou 10 égal à 1) du motif DN. Pour effectuer l'injection à une fréquence variable, on peut prévoir une matrice de plusieurs valeurs de k (différents pas) et de plusieurs motifs respectivement affectés aux différents pas, et de sélectionner les différents couples (k, t) séquentiellement ou aléatoirement. 15 Selon un deuxième aspect, on prévoit un mécanisme de protection d'une génération de nombres aléatoires contre des injections de fautes. La figure 7 représente, de façon très schématique et sous forme de blocs, un mode de réalisation d'un procédé de 20 détection d'une injection de fautes dans un générateur de nombres aléatoires. Ce mode de réalisation s'applique au générateur du type de celui de la figure 3, dans lequel le train de bits RB, extrait de la source de bruit, est traité par un algorithme de 25 cryptographie. On prévoit d'intercaler, entre la sortie de la mémoire tampon 26 et le registre 28 de nombres aléatoires générés, une fonction résiliente (bloc 40, RES FCT). Une fonction résiliente se caractérise par le fait qu'à partir d'un nombre de bits en 30 entrée, elle fournit un nombre égal ou différent de bits en sortie et assure la répartition uniforme de ces bits. De façon générique, une fonction résiliente se note f(n, m, t), où n désigne le nombre de bits en entrée, m le nombre de bits en sortie et t le nombre de bits dont la valeur est modifiée. Dans B12725 - 13-R0-0469 11 un système binaire, dire que les bits sont modifiés signifie que leur valeur est inversée. Par exemple, on pourra utiliser des fonctions telles que définies dans l'article "The bit extraction problem or t- resilient functions," de B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, et R. Smolensky, paru dans IEEE Symp. on Foundations of Computer Science, 1985, vol. 26, pp. 396-407, ou dans l'article "Privacy amplification by public discussion" de C. H. Bennett, G. Brassard, and J. M. Robert, paru dans SIAM J. Comput., vol. 17, pp. 210-229, 1988. La figure 8 illustre, de façon schématique, un mode de réalisation dans lequel on applique une fonction f(5, 4, 2). Dans cet exemple, on suppose un mot N26 de 5 bits 01101 en entrée (sortie du buffer 26), transformé en un mot N40 de 4 bits 0110 en sortie, avec inversion de la valeur de deux des bits. Des fonctions résilientes susceptibles d'être utilisées sont les fonctions cryptographiques. Toutefois, dans ce cas, à la différence d'un système usuel du type de celui illustré en figure 3, cela revient à appliquer successivement deux algorithmes de cryptographie respectivement entre l'extraction du train de bits aléatoires et la mémoire tampon, et entre cette mémoire tampon et le registre de sortie. En présence d'une injection de fautes par impulsion, il faudrait que l'attaquant change les états de suffisamment de bits pour que la fonction ne puisse plus être résiliente, faute de quoi, son attaque ne marchera pas. En pratique, on choisira le degré de résilience de la fonction en tenant compte des attaques que l'on souhaite bloquer. Les paramètres choisis pour la fonction résiliente (nombre de bits d'entrée, nombre de bits de sortie et nombre de bits modifiés) dépendent de l'application et de la robustesse souhaitée pour le mécanisme de protection. Par exemple, si t est le nombre de changements qu'autorise la fonction, c'est-à-dire le nombre en deçà duquel les sorties sont toujours équilibrées, on choisit une fonction dont le paramètre t est supérieur au B12725 - 13-R0-0469 12 nombre de changements que l'on estime possibles de la part de l'attaquant. Les mécanismes de détection et de protection sont combinables. Divers modes de réalisation ont été décrits, diverses variantes et modifications apparaîtront à l'homme de l'art. En particulier, le choix du motif selon le premier aspect et sa taille dépend de l'application et, notamment, de la capacité du circuit de génération du nombre aléatoire. De plus, l'exploitation de la détection effectuée peut prendre diverses formes usuelles (alerte, blocage du circuit, etc.). En outre, la réalisation pratique des modes de réalisation décrits est à la portée de l'homme du métier à partir des indications fonctionnelles en utilisant des outils matériels ou logiciels en eux-mêmes usuels. REVENDICATIONS1. Procédé de protection d'une génération d'un nombre aléatoire contre des attaques par injection de fautes, dans lequel un mot (N26) fourni par un algorithme cryptographique (244) de traitement d'un train de bits (RB) fourni par une source de bruit (221) est soumis à une fonction résiliente (40) pour fournir le nombre aléatoire (RN). 2. Procédé selon la revendication 1, dans lequel ladite fonction résiliente (40) comporte un nombre de bits de sortie fonction de la taille du mot aléatoire souhaité. 3. Procédé selon la revendication 1 ou 2, dans lequel ladite fonction résiliente (40) est une fonction cryptographique. 4. Procédé selon l'une quelconque des revendications 1 à 3, dans lequel le nombre (n) de bits d'entrée de la fonction 15 résiliente (40) correspond au nombre de bits de sortie de l'algorithme cryptographique. 5. Circuit de génération d'un nombre aléatoire (RN) adapté à la mise en oeuvre du procédé selon l'une quelconque des revendications précédentes.