Brevet FR2796477A1 — publié le 20010119

PROCEDE D'AMELIORATION D'UN GENERATEUR ALEATOIRE EN VUE DE LE RENDRE RESISTANT CONTRE LES ATTAQUES PAR MESURE DE COURANT L'invention concerne une amélioration d'un procédé de génération de nombres aléatoires ou source aléatoire, en particulier des sources mises au point dans le cadre de systèmes cryptographiques tels que les générateurs de nombres aléatoires embarqués à bord de cartes à puce. Elle est particulièrement destinée à être mise en oeuvre dans le test et la validation de dispositifs électroniques du type carte à puce, PCMCIA, badges, cartes sans contact ou tout autre appareil portable. La plupart des systèmes de cryptographie à clé publique (dite aussi cryptographie asymétrique) et clé secrète (dite aussi cryptographie symétrique) nécessitent le tirage d'aléas secrets. Il est primordial que de tels aléas, ou nombres, destinés à servir comme clés ultérieurement soient à priori imprévisibles et ne présentent pas de régularités permettant de les retrouver par des stratégies de recherche exhaustive ou exhaustive améliorée pour laquelle les clés les plus probables sont cherchées en premier lieu. Il est possible de construire une source aléatoire à partir d'une fonction dont il est difficile de calculer l'inverse. Soit f une telle fonction. Il est possible de construire une source aléaoire en commençant par sélectionner une variable d'initialisation aléatoire s et en appliquant la fonction f à la suite de valeurs s, s+1, s+2,...La sortie de la source aléatoire est définie comme f (s) , f (s+1) , f (s+2) , ... En fonction des propriétés de la fonction f utilisée, il peut être préférable de ne garder que quelques bits de la sortie f (s) , f (s+1) , f (s+2) ... Une méthode de génération de nombre aléatoire à partir d'une fonction dont il est difficile de calculer l'inverse est spécifiée dans le standard ANSI X9.17. La méthode utilise l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, qui ne doit être utilisée que dans le cadre de cet algorithme. Le procédé de génération de nombre aléatoire prend en entrée un entier aléatoire et secret s de taille 64 bits et un entier m, et renvoie en sortie m entiers aléatoires de 64 bits x1, x2,..., xm. Le procédé est caractérisé par les 3 étapes suivantes . 1) Chiffrer avec l'algorithme DES utilisant la clef K une valeur D représentant une information de date et mettre le résultat dans la variable entière I. 2) Pour j allant de 1 à m exécuter les étapes suivantes . 2)a) Remplacer s par s xor I. 2)b) Mettre dans xj le résultat du chiffrement de s avec l'algorithme DES utilisant la clef secrète K. 2)c) Remplacer s par xj xor I. 2)d) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef secrète K. 3) Retourner en sortie la suite (x1, x2,..., xm). Il est possible d'utiliser ce générateur aléatoire dans une application pour laquelle un générateur aléatoire est déjà disponible, mais de qualité jugée insuffisante, par exemple un générateur aléatoire embarqué dans le microprocesseur d'une carte à puce. Dans ce cas, le procédé décrit précédemment est utilisé pour améliorer la qualité du générateur aléatoire. Ce procédé prend en entrée un entier aléatoire et secret s de taille 64 bits et un entier m, et renvoie en sortie m entiers aléatoires de 64 bits x1, x2, ... il xm. Le procédé utilise l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, qui ne doit être utilisée que dans le cadre de cet algorithme. Le procédé utilise une source S de qualité jugée insuffisante d'entiers aléatoires sur 64 bits. Le procédé est caractérisé par les 3 étapes suivantes . 1)Pour j allant de 1 à m faire 1)a) Générer un entier I à l'aide de la source S. 1)b) Remplacer s par s xor I. 1)c) Mettre dans xJ le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 1)d) Générer un entier I à l'aide de la source S. 1)e) Remplacer s par xj xor I. 1)f) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 2) Retourner en sortie la suite (x1, x2,..., xm). I1 est apparu que l'implémentation sur carte à puce d'un algorithme de chiffrement à clé secrète (par exemple l'algorithme DES) était vulnérable à des attaques consistant en une analyse différentielle de consommation de courant permettant de retrouver la clé secrète. Ces attaques sont appelées attaques DPA, acronyme pour Differential Power Analysis. Le principe de ces attaques DPA repose sur le fait que la consommation en courant du microprocesseur exécutant des instructions varie selon la donnée manipulée. Pour retrouver la clef secrète, il est nécessaire que le message d'entrée ou le message de sortie de l'algorithme de chiffrement soient connus. Les 2 procédés de génération de nombre aléatoire décrits précédemment sont donc vulnérables à des attaques de type attaques DPA. En effet, les nombres aléatoires renvoyés en sortie par ces 2 procédés sont les messages de sortie de l'algorithme de chiffrement. A partir de la consommation de courant de la carte à puce, il est donc possible de retrouver 1a clef K de chiffrement, et donc de prévoir ensuite la sortie du générateur aléatoire. Le procédé de l'invention consiste en une modification des procédés de générations de nombre aléatoire décrits précédemment de façon à les rendre résistant contre des attaques de type DPA. Le premier procédé modifié de générations de nombre aléatoire utilise l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, qui ne doit être utilisée que dans le cadre de cet algorithme. I1 prend en entrée un entier aléatoire et secret s de taille 64 bits et un entier m, et renvoie en sortie m entiers aléatoires de 64 bits x1, x2,..., xm. Le procédé utilise une variable entière intermédiaire y. Le procédé est caractérisé par les trois étapes suivantes . 1) Chiffrer avec l'algorithme DES utilisant la clef k une valeur D représentant une information de date et mettre le résultat dans la variable entière I. 2) Pour j allant de 1 à m exécuter les étapes suivantes . 2)a) Remplacer s par s xor I. 2)b) Mettre dans la variable entière y le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 2)c) Mettre dans xj le résultat de y xor s. 2)d) Remplacer s par y xor I. 2)e) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 3) Retourner en sortie la suite (x1, x2,..., xm). Dans ce procédé amélioré de génération de nombres aléatoires, une attaque par mesure de courant de type DPA est impossible car les messages d'entrée et de sortie de l'algorithme de chiffrement DES ne sont pas connus. Le second procédé amélioré de génération de nombre aléatoire est utilisé pour augmenter la qualité d'un générateur aléatoire dont la qualité est jugée insuffisante. Ce procédé prend en entrée un entier aléatoire et secret s de taille 64 bits et un entier m, et renvoie en sortie m entiers aléatoires de 64 bits x1, x2,..., xm. Le procédé utilise l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, qui ne doit être utilisée que dans le cadre de cet algorithme. Le procédé utilise une source S de qualité jugée insuffisante d'entiers aléatoires sur 64 bits. Le procédé est caractérisé par les deux étapes suivantes . 1)Pour j allant de 1 à m faire 1)a) Générer un entier I à l'aide de la source S. 1)b) Remplacer s par s xor I. 1)c) Mettre dans y 1e résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 1)d) Mettre dans xi le résultat de y xor s. 1)e) Remplacer s par y xor I. 1)f) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K. 3)Retourner en sortie la suite (x1, x2,..., xm). Dans ce procédé amélioré de génération de nombres aléatoires, une attaque par mesure de courant de type DPA est impossible car les messages d'entrée et de sortie de l'algorithme de chiffrement DES ne sont pas connus. Les deux procédés de génération de nombre aléatoires précédemment décrits permettent donc d'obtenir un générateur de nombre aléatoire résistant contre les attaques par mesure de courant de type DPA. REVENDICATIONS 1- Procédé de génération de nombre aléatoire utilisant l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, ladite clef K ne devant être utilisée que dans le cadre de cet algorithme, ledit procédé prenant en entrée un entier aléatoire et secret s de taille 64 bits et un paramètre entier m, ledit procédé renvoyant en sortie m entiers aléatoires de 64 bits x1, x2,..., xm, caractérisé en ce qu'il comprend trois étapes . 1) Chiffrer avec l'algorithme DES utilisant la clef K une valeur D représentant une information'de date et mettre le résultat dans une variable entière I; 2)Pour j allant de 1 à m faire: 2)a) Remplacer s par s xor I; 2)b) Mettre dans la variable entière y le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K; 2)c) Mettre dans xj le résultat de y xor s; 2)d) Remplacer s par y xor I; 2)e) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef k; 3) Retourner en sortie la suite (x1, x2,..., xm). 2- Procédé de génération de nombre aléatoire permettant d'améliorer la qualité d'un générateur aléatoire dont la qualité est jugée insuffisante, ledit procédé prenant en entrée un entier aléatoire et secret s de taille 64 bits et un entier m, ledit procédé renvoyant en sortie m entiers aléatoires de taille 64 bits x1, x2, ... , xm,, ledit procédé utilisant l'algorithme DES (pour Data Encryption Standard) avec une clé secrète K, qui ne doit être utilisée que dans le cadre de cet algorithme, ledit procédé utilisant une variable intermédiaire entière y, ledit procédé utilisant une source S de qualité jugée insuffisante d'entiers aléatoires sur 64 bits x1, x2, ..., xm" caractérisé en ce qu'il comprend les deux étapes suivantes . 1)Pour j allant de 1 à m faire 1)a) Générer un entier I à l'aide de la source S; 1)b) Remplacer s par s xor I; 1)c) Mettre dans y le résultat du chiffrement de s avec l'algorithme DES utilisant la clef k. 1)d) Mettre dans xi le résultat de y xor s; 1) e) Remplacer s par y xor I ; 1)f) Mettre dans s le résultat du chiffrement de s avec l'algorithme DES utilisant la clef K; 2)Retourner en sortie la suite (x1, x2,-., xm). 3. Dispositif électronique mettant en #uvre le procédé selon l'une quelconque des revendications 1 et 2 caractérisé en ce que le dispositif est un dispositif portable. 4. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte à puce. 5. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte sans contact. 6. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une carte PCMCIA. 7. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est un badge. 8. Dispositif électronique selon la revendication 3 caractérisé en ce que le dispositif est une montre intelligente.