Brevet FR3063857A1 — publié le 20180914

PROCEDE DE SIGNATURE ELECTRONIQUE D'UN DOCUMENT AVEC UNE CLE SECRETE PREDETERMINEE DOMAINE TECHNIQUE GENERAL La présente invention concerne le domaine de la cryptographie, et en particulier un procédé de signature de type - boite blanche ». ETAT DE L'ART Une fonction est considérée comme une - boîte noire » lorsqu'on ne peut pas accéder à son fonctionnement interne, i.e. qu'on peut connaître ses entrées et ses sorties mais pas ses paramètres secrets ou ses états intermédiaire. 15 Les algorithmes cryptographiques (par exemple pour du chiffrement ou de la signature) sont ainsi classiquement supposés des boites noires lorsqu'on évalue leur fiabilité (résistance aux attaques). L'hypothèse de boite noire impose une contrainte forte sur le stockage et la 20 manipulation de ces paramètres. Cependant des outils ont été récemment publiés pour permettre l'automatisation d'attaques sur implémentation matérielle, attaques dites par canaux auxiliaires ou par fautes. Aujourd'hui, pour de nombreux cas d'usages incluant le paiement sur mobile, 25 il est nécessaire de déployer des algorithmes cryptographiques en faisant le moins d'hypothèses possibles sur la sécurité du matériel cible. Le stockage et la manipulation sécurisés des paramètres secrets doivent alors être assurés au niveau applicatif. 30 La cryptographie dite boite blanche vise à répondre à ce défi en proposant des implémentations des algorithmes cryptographiques qui sont sensés rendre l'extraction des secrets impossible, même en cas d'attaque permettant à l'attaquant un accès complet à l'implémentation logicielle de l'algorithme. Plus précisément, une fonction est considérée comme une - boîte blanche » lorsque ses mécanismes 35 sont visibles et permettent d'en comprendre le fonctionnement. En d'autres termes, 10 3063857 2 on fait directement l'hypothèse que l'attaquant a accès à tout ce qu'il souhaite (le binaire est complètement visible et modifiable par l'attaquant et celui-ci a le plein contrôle de la plateforrne d'exécution). Par conséquent, l'implémentation elle-même est la seule ligne de défense. On parle alors - d'implémentation blanchie » d'un 5 calcul élémentaire de l'algorithme lorsqu'on arrive à représenter ce calcul sous une forme sécurisée évitant d'avoir les clés utilisées en clair, par exemple en représentant le calcul par une table stockée en mémoire. Il a par exemple été proposé dans la demande US2016/328543 une méthode visant à cacher les entrées et les sorties d'une fonction d'exponentiation modulaire, ce qui permet d'améliorer la sécurité d'algorithmes cryptographiques tels que RSA (- Rivest, Shamir, Adlernan »). Toutefois, il a été montré que cette méthode n'était pas suffisante pour assurer une protection satisfaisante de l'algorithme de signature DSA (- Digital Signature Algorithrn »). Le calcul d'une signature DSA présuppose qu'une clef publique (p,q, g ,y) et une clef privée x ont été associées à l'utilisateur. Le procédé de génération de ces clefs se compose des différentes étapes suivantes : - Choisir un nombre premier p de longueur L telle que 512 L 1024, et L est divisible par 64 - Choisir un nombre premier q de 160 bits, de telle façon que p - 1 = qc, avec c un entier - Choisir h, avec 1 1 - Générer aléatoirement un x, avec 0 (z + slx)ki-1 mod q, où sl est 10 le premier état interne, ki le nonce, x la clé secrète et q une constante ; - s = (gki mod p) mod q, où g et p sont des constantes ; - la signature est le couple (sl,$) des premier et deuxième états internes ; - le procédé comprend une étape préalable (a0) de génération dudit ensemble de couples par des moyens de traitement de données d'un serveur, et sa transmission à 15 l'équipement ; - l'étape (a0) comprend la génération d'une pluralité de nonces, puis la génération du couple pour chaque nonce ; - l'étape (a0) comprend la génération préalable des constantes p, q, g conformément à l'algorithme DSA ; 20 - l'étape (a0) comprend également la génération préalable de la clé secrète et d'une clé publique associée en fonction des constantes p, q, g; - lesdites implémentations blanchies utilisent un Système de Représentation Modulaire, RNS, pour effectuer ladite opération d'arithmétique modulaire ; - le procédé comprend une étape subséquente (d) d'association par les moyens de 25 traitement de données de l'équipement de la signature électronique générée au document de sorte à former le document signé Selon un deuxième et un troisième aspect, l'invention propose un produit programme d'ordinateur comprenant des instructions de code pour l'exécution d'un 30 procédé selon le premier aspect de signature électronique d'un document avec une clé secrète prédéterminée ; et un moyen de stockage lisible par un équipement informatique sur lequel un produit programme d'ordinateur comprend des instructions de code pour l'exécution d'un procédé selon le premier aspect de signature électronique d'un document avec une clé secrète prédéterminée. 3063857 5 PRESENTATION DES FIGURES D'autres caractéristiques et avantages de la présente invention apparaîtront à 5 la lecture de la description qui va suivre d'un mode de réalisation préférentiel. Cette description sera donnée en référence aux dessins annexés dans lesquels : - la figure 1 est un schéma d'une architecture pour la mise en oeuvre du procédé selon l'invention. 10 DESCRIPTION DETAILLEE Architecture En référence à la figure 1, est proposé un procédé de signature - boite 15 blanche » d'un document mis en oeuvre au sein d'un équipement 10a tel qu'un terminal mobile (snnartphone, tablette tactile, etc.), i.e. un équipement ne disposant pas particulièrement d'un matériel sécurisé et qui peut faire l'objet d'attaques sur implémentation matérielle, et pour lequel l'approche boite blanche prend tout son intérêt. 20 L'équipement 10a comprend des moyens de traitement de données 11a (un processeur) et des moyens de stockage de données 12a (une mémoire, par exemple flash). 25 L'équipement 10a est par exemple relié à un serveur 10b par exemple via le réseau internet 20. Il peut être amené à recevoir depuis ce serveur 10b (par exemple celui d'un fournisseur de solutions de sécurité) des objets cryptographiques (qu'on décrira plus loin) contenant des secrets qui vont être stockées dans la mémoire 12a et utilisées pour la mise en oeuvre du présent procédé 30 L'équipement 10a peut lui-même être connecté à d'autres serveurs 10c de tiers auxquels il pourra transmettre le document signé une fois qu'il aura généré la signature électronique. Procédé de signature 3063857 6 Le présent procédé est bien un procédé de - génération de signature électronique de document », et non - de signature d'un document ». Cela signifie qu'il permet seulement d'obtenir la signature électronique du document et pas encore le - document signé », i.e. l'association du document original et de la 5 signature, généralement dans un conteneur quelconque. Par - signature électronique » d'un document, on entend la définition classique de ce terme, à savoir une primitive cryptographique permettant d'identifier le signataire et garantissant que le document n'a pas été altéré depuis l'instant où la 10 signature a été produite et est bien le document original (dans la suite de la présente description, on désignera comme - original » le document dont est réellement issu le condensat). Cet objet cryptographique consiste généralement en un chiffré du condensat du document grâce à une fonction de chiffrement asymétrique : le signataire utilise une clé privé, et tout le monde peut vérifier la signature grâce à 15 une clé publique (en comparant le condensat contenu dans la signature et un condensat recalculé). On comprendra que le présent procédé est une nouvelle implémentation d'algorithmes connus utilisant des opérations d'arithmétique modulaire (i.e. des 20 opérations comprenant des calculs de modulo, notamment des exponentiations modulaires), en particulier DSA qui est un standard actuel et dont on prendra l'exemple dans la suite de la description. Plus précisément, il ne propose pas une nouvelle stratégie de signature, mais seulement une nouvelle façon de manipuler les données au sein de l'algorithme qui soit résistante à toutes les attaques matérielles 25 en - boite blanche ». Le document est associé à un condensat obtenu par une fonction de hachage donnée. Comme expliqué, une fonction de hachage prend en entrée un message de 30 taille arbitraire (le document original) et produit un condensat de taille fixe associé à ce message. Ici, ladite fonction de hachage donnée est avantageusement une fonction dite cryptographique, c'est-à-dire avec des propriétés supplémentaires : le condensat est statistiquement bien réparti dans l'ensemble des valeurs d'arrivées, il est impossible en temps raisonnable de trouver deux messages qui ont le même 35 condensat (résistance aux collisions) et on ne peut pas à partir du condensat 3063857 7 retrouver un message qui a permis d'obtenir cette valeur (résistance au calcul de pré-image). On prendra l'exemple des fonctions de la famille SHA (- Secure Nash 5 Algorithrn »), standardisées par le NIST (- National Institute of Standards and Technology »), en particulier les sous-familles SHA-1 ou SHA-2 (notamment SHA-256). Principe 10 La présente invention propose, pour une même paire de clés publique/privée, de faire précalculer plusieurs valeurs d'un premier état interne sl chacune pour un nonce ki, puis une implémentation blanchie WBi d'une opération d'arithmétique modulaire utilisée par l'algorithme de signature pour chacun des nonces ki, ladite opération d'arithmétique modulaire étant en effet fonction du premier état interne 15 s, du nonce ki et de la clé secrète x. On rappelle que par implémentation blanchie, ou white box irnplennentation », d'une opération, on entend une représentation de l'opération qui ne permette pas de remonter aux états internes ou aux paramètres lorsque l'opération est exécutée (par application de l'implémentation blanchie aux données d'entrée). 20 Ainsi, un ensemble de couples [(si, WBDIiE[[0 du premier état interne sl et de l'implémentation l'implémentation blanchie WBi de l'opération d'arithmétique modulaire sont prédéfinis et stockés sur les stocké sur les moyens de stockage de données 12a de l'équipement 10a. 25 En d'autres termes, à clés publique/privée fixée, chaque couple (s1,WBi) est entièrement déterminé par le nonce ki: tirer un nonce équivaut à tirer un couple. Le nonce ki n'est donc pas une donnée d'entrée de l'implémentation blanchie WBi mais bien un paramètre encapsulé » auquel un attaquant ne peut pas remonter. 30 De façon préférée, ledit ensemble de couples [(si, WBDIiE[[0 ,n-11 est générée par les moyens de traitement de données 1 1 b du serveur lb et sa transmis pour stockage à l'équipement 10a dans une étape préalable (a0). 3063857 8 Cette génération peut comprendre la génération de la pluralité de nonces puis la génération du couple (sl, W Bi) pour chaque nonce ki de sorte à définir l'ensemble [(si, WBDI iE[[0,n-11- 5 Les propriétés attendues du blanchiment d'application font que l'observation de l'exécution de l'implémentation blanchie WB, ne doit pas permettre de retrouver les valeurs de la clef secrète x et du nonce k, enfouies dans le calcul. Il suffit donc de n'autoriser l'utilisation de chaque WB, qu'une seule fois pour empêcher de remonter à k, et ainsi éviter les restart attack. Le procédé de signature proposé 10 permet donc de résister à un attaquant qui observerait les états intermédiaires (par exemple à l'aide d'une application malveillante tournant sur le mobile). Les implémentations blanchies WB, (et donc les couples d'un premier état et d'une implémentation blanchie) sont ainsi supprimés après utilisation pour éviter 15 toute attaque possible. Mode de réalisation préféré Dans l'exemple où l'algorithme de signature est conforme à DSA, alors sl peut 20 être égal à (gki mod p) mod q, où g,p et q sont des constantes (en particulier des nombres premiers pour p et q). Sinnilairennent, ladite opération d'arithmétique modulaire représentée par l'implémentation blanchie WB, peut être z 1-> (z + mod q. On peut 25 facilement vérifier que ce calcul correspond à celui du s associé au sl généré précédemment, pour une valeur de condensat z du message. Les valeurs p, q, g sont préférentiellement prédéterminés conformément à l'algorithme DSA, en particulier par les moyens de traitement de données 11b du 30 serveur 10b lors de l'étape préalable (a0). On rappelle que dans DSA, (p, q, g, y) forme une clé publique générée avec une clef privée x de la façon suivante : 3063857 9 - Choisir un nombre premier p de longueur L telle que 512 L 1024, et L est divisible par 64 - Choisir un nombre premier q de 160 bits, de telle façon que p - 1 = qc, avec c un entier 5 - Choisir h, avec 1 1 - Générer aléatoirement un x, avec 0 REVENDICATIONS1. Procédé de signature électronique d'un document avec une clé secrète (x) prédéterminée, le procédé étant caractérisé en ce qu'il comprend la mise en oeuvre par des moyens de traitement de données (11a) d'un équipement (10a) d'étapes de : (a) Tirage d'un couple d'un premier état interne (5'1) et d'une implémentation blanchie (WBi) d'une opération d'arithmétique modulaire parmi un ensemble de couples (1(sl, WBDIiE[[0 11) prédéterminés chacun pour un ,n- nonce (ki), ledit ensemble de couples ([(si, WBDIiE[[0 ) étant stocké sur ,n-11 des moyens de stockage de données (12a) de l'équipement (10a), ledit premier état interne (5'1) étant fonction du nonce (ki) et ladite opération d'arithmétique modulaire étant fonction du premier état interne (5'1), du nonce (ki) et de la clé secrète (x) ; (b) Détermination d'un deuxième état interne (.9) par application à un condensat du document obtenu par une fonction de hachage donnée, de ladite implémentation blanchie (W Bi) tirée ; (c) génération d'une signature électronique du document à partir du premier état interne (s1) du couple tiré et du deuxième état interne (.9) déterminé, et suppression du couple tiré dudit ensemble de couples (PL WB1)liEfto,n- 2. Procédé selon la revendication 1, dans lequel ladite opération d'arithmétique modulaire est z 1-> (z + mod q, où sl est le premier état interne, ki le nonce, x la clé secrète et q une constante. 3. Procédé selon la revendication 2, dans lequel = (gki modp)mod q, où g et p sont des constantes. 4. Procédé selon l'une des revendications 1 à 3, dans lequel la signature est le couple (sl,$) des premier et deuxième états internes. 3063857 13 5. Procédé selon l'une des revendications 1 à 4, comprenant une étape préalable (a0) de génération dudit ensemble de couples G(51, JI WB.- iiello,n-11) par des moyens de traitement de données (11 b) d'un serveur (1 b), et sa transmission à l'équipement (10a). 5 6. Procédé selon la revendication 5, dans lequel l'étape (a0) comprend la génération d'une pluralité de nonces (fkil,,M,n-111), puis la génération du couple (s1_,W Bi) pour chaque nonce (ki). 10 7. Procédé selon les revendications 3 et 6 en combinaison, dans lequel l'étape (a0) comprend la génération préalable des constantes p, q, g conformément à l'algorithme DSA. 8. Procédé selon la revendication 7, dans lequel l'étape (a0) 15 comprend également la génération préalable de la clé secrète (x) et d'une clé publique associée en fonction des constantes p, q, g. 9. Procédé selon l'une des revendications 1 à 8, dans lequel lesdites implémentations blanchies (WBi) utilisent un Système de Représentation 20 Modulaire, RNS, pour effectuer ladite opération d'arithmétique modulaire. 10. Procédé selon l'une des revendications 1 à 9, comprenant une étape subséquente (d) d'association par les moyens de traitement de données (11a) de l'équipement (10a) de la signature électronique générée au document de sorte à 25 former le document signé 11. Produit programme d'ordinateur comprenant des instructions de code pour l'exécution d'un procédé selon l'une des revendications 1 à 10 de signature électronique d'un document avec une clé secrète (x) prédéterminée, 30 lorsque ledit programme est exécuté par un ordinateur. 12. Moyen de stockage lisible par un équipement informatique sur lequel un produit programme d'ordinateur comprend des instructions de code pour l'exécution d'un procédé selon l'une des revendications 1 à 10 de de signature électronique d'un document avec une clé secrète (x) prédéterminée.