Amélioration de la résistance aux attaques cryptanalytiques d'une fonction de hachage .

La présente invention se rapporte au domaine de l'informatique et notamment à l'amélioration de la résistance aux attaques cryptanalytiques d'une fonction de condensation (dite aussi de "compression", ou encore de "hachage") . Plus particulièrement, l'invention permet d'améliorer la sécurité dans la signature des messages électroniques .

Les fonctions de hachage sont actuellement très utilisées en cryptographie. En effet, elles génèrent, à partir d'un message de longueur arbitraire en entrée, un message de longueur déterminée en sortie. Elles facilitent, ainsi, la création de signatures électroniques qui permettent de garantir 1 ' intégrité et l'authenticité des informations. Elles servent, par exemple, à produire des certificats électroniques, et interviennent dans de nombreux protocoles d' authentification .

Pour garantir un haut niveau de sécurité, les fonctions de hachage doivent pouvoir résister à différentes attaques. Elles doivent pouvoir résister, par exemple, aux collisions. Les collisions consistent à obtenir, à partir de messages différents, le même résultat à la sortie de la fonction. Or pour une fonction de hachage garantissant un bon niveau de sécurité, il est très difficile de trouver de tels messages en un temps raisonnable .

Cependant X. Wang et H. Yu ont démontré dans leurs articles "How to Break MD5 and Other Hash Functions" en mai 2005 et "Finding Collisions in the FuIl SHA-I" en août 2005, qu'en choisissant des messages avec une structure particulière, il est possible de construire des collisions en un temps raisonnable. Ceci fragilise la confiance que placent les utilisateurs dans ces fonctions. En effet, si une fonction de hachage ne résiste pas aux collisions, il y a des doutes sur sa capacité à garantir d'autres propriétés. Ces autres propriétés sont, par exemple, celle d'être à sens unique ou celle d'être résistante à un deuxième antécédent.

Szydlo et Yin ont alors proposé dans le document "Collision résistant Usage of SHA-I via Message Pre- Processing", une étape de pré-traitement. Cette étape modifie la structure des messages avant leur entrée dans la fonction de hachage. L'étape de prétraitement consiste, notamment, en une simple duplication de tout ou partie du message. Cette opération pourrait être facilement contournable par des cryptoanalystes, afin de créer de nouveau des collisions .

La présente invention permet de palier ou pour le moins de réduire tout ou partie des inconvénients précités en ce qu'au cours d'un procédé de transformation d'un premier message de données de longueur quelconque en un troisième message de données de longueur déterminée, une étape génère pseudo-aléatoirement un deuxième message de données à partir du premier message, ledit deuxième message étant comprimé en un troisième message. L'étape de

génération pseudo-aléatoire est implémentée dans un dispositif de hachage .

Ainsi, l'étape de génération pseudo-aléatoire modifie de manière non prévisible la structure du premier message. Il sera donc plus difficile, pour un attaquant, d'imposer une structure particulière au deuxième message. Ceci améliore la résistance, aux attaques cryptanalytiques, de la fonction de hachage utilisée lors de l'étape de compression.

Selon des modes de réalisation préférentiels non limitatifs, le procédé objet de l'invention présente les caractéristiques supplémentaires prises isolément ou en combinaison, énoncées ci-après:

L'étape de génération pseudo-aléatoire permet de générer un deuxième message de données de longueur plus grande que le premier message.

Ainsi, l'obtention d'une structure voulue par l'attaquant pour le deuxième message, est plus difficile à obtenir.

L'étape de génération pseudo-aléatoire utilise un algorithme de chiffrement par flot. Cet algorithme permet de générer des messages. Ces messages, pour un attaquant, sont indistinguables de messages aléatoires. Il est donc très difficile, pour cet attaquant, de déterminer un premier message de telle sorte que le second message possède la structure voulue. De plus, il est très difficile de remonter au premier message en partant du second. Enfin, l'utilisation d'un tel algorithme permet d'adapter la longueur des messages à la fonction de hachage utilisée.

L'étape de génération pseudo-aléatoire du deuxième message de données se fait à partir d'une variable de chaîne.

L'utilisation de la variable de chaîne permet ainsi d'améliorer le caractère aléatoire du deuxième message généré.

Selon un deuxième objet de l'invention, un dispositif de transformation d'un premier message comprend:

- un dispositif de génération pseudo-aléatoire d'un deuxième message de données à partir du premier message; un dispositif de hachage du deuxième message destiné à générer un troisième message de données de longueur déterminée, le dispositif de génération pseudo-aléatoire étant implémenté dans le dispositif de hachage.

Selon des modes de réalisation préférentiels non limitatifs, le dispositif objet de l'invention présente les caractéristiques supplémentaires prises isolément ou en combinaison, énoncées ci-après:

Le dispositif de génération pseudo-aléatoire permet de générer un deuxième message de longueur plus grande que le premier message.

Le dispositif de génération pseudo-aléatoire utilise un algorithme de chiffrement par flot.

La génération pseudo-aléatoire du deuxième message se fait à partir d'une variable de chaîne.

Selon un troisième objet de l'invention, un procédé de signature d'un premier message de données comprend:

- une étape de génération pseudo-aléatoire d'un deuxième message de données à partir du premier message de données; une étape de compression dudit deuxième message en un troisième message de données; une étape de cryptographie dudit troisième message pour générer un quatrième message;

- une étape d'assemblage dudit quatrième message avec le premier message de données.

Un quatrième objet de l'invention concerne un dispositif de signature d'un premier message de données pour la mise en œuvre du procédé selon le troisième objet de l'invention.

Selon un cinquième objet de l'invention, un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur, comprend des instructions pour l'exécution des étapes du procédé selon le premier objet de l'invention.

L'invention sera mieux comprise et d'autres particularités et avantages apparaîtront à la lecture de la description, faite à titre d'exemple, cette description faisant références aux dessins annexés représentant :

- A la Fig.l, un dispositif de traitement d'un message de données selon un premier mode de réalisation l'invention;

- A la Fig.2, un dispositif de traitement d'un message de données selon un second mode de réalisation de l'invention;

- A la Fig.3, un dispositif de traitement d'un message de données selon un troisième mode de réalisation de l'invention;

- A la Fig.4, un procédé de traitement d'un message de données ainsi qu'un procédé de signature d'un message de données selon l'invention.

L'invention est décrite ci-après dans une application particulière à la signature des messages électroniques. Cependant, cette invention s'applique également à tout système utilisant une fonction de hachage .

La Fig.l présente un dispositif de transformation 1 d'un premier message M selon un premier mode de réalisation de l'invention.

Ce dispositif de transformation 1 permet à partir d'un premier message M de données, de longueur quelconque, de générer un troisième message H de longueur déterminée h. Le message M est ici un message de données numériques, en variante les données peuvent être de tout type.

Le dispositif de transformation 1 comprend un dispositif de génération pseudo-aléatoire 5 d'un second message N et un dispositif de hachage 4 pour la génération d'un troisième message H de longueur déterminée. On notera que N peut également s'écrire W(M) où W est la fonction transformant le message M en un message N.

Le dispositif de génération 5 est destiné à former un message N de données pseudo-aléatoire à

partir d'un message M de longueur quelconque. Ce dispositif constitue un pré-traitement ou "pre- whitening" pour le dispositif de hachage 4. Le pre- whitening est une opération permettant de rendre la structure d'un message non prévisible.

Par structure, il faut comprendre l'ensemble des propriétés qui régissent la valeur des bits de données entre eux.

Le dispositif de génération 5 comprend ainsi des moyens de formation 2, des moyens de calcul 13 et des moyens de concaténation 14.

Les moyens de formation 2 sont destinés à former une séquence Ml,..., Mi,..., Mt de t blocs de données à partir d'un message M. Chaque bloc est d'une longueur de K bits, K étant, par exemple, de l'ordre de 256 bits. Ceci peut être typiquement réalisé, en ajoutant des éléments supplémentaires δM au message M pour former un message complété M+δM. La longueur du message complété est alors un multiple de celle d'un bloc Mi. Avantageusement, les éléments supplémentaires δM peuvent comporter des informations relatives au message M d'origine, comme la longueur initiale de ce message M. Ces moyens 2 de formation comportent ainsi des moyens de bourrage 11 ou "padding means" et des moyens de subdivision 12. Les moyens de bourrage 11 sont destinés à bourrer le message M par les éléments supplémentaires δM. Ceci permet de compléter la longueur du message pour pouvoir le subdiviser en blocs Mi de longueur voulue. Les moyens de subdivision 12 sont destinés à subdiviser le message complété M+δM pour former la séquence Ml, ...Mi, ...Mt de t blocs de longueur K bits.

Des moyens de calcul 13 définissent une séquence pseudo-aléatoire une séquence Nl,..., Ni,..., Nt de t blocs de données de longueur b bits à partir de

la séquence Ml,..., Mi,..., Mt du premier message. Ces moyens de calcul 13 sont, par exemple, des algorithmes assurant à partir d'un bloc Mi la génération d'un bloc Ni. Cette génération se fait de manière à ce qu'il soit très difficile pour un attaquant de distinguer la séquence Nl, ...Ni, ...Nt d'une séquence pseudo-aléatoire. En outre, les moyens 13 sont non inversibles, c'est-à-dire que la connaissance de la séquence Nl,..., Ni,..., Nt ne permet pas aisément de retrouver, par ces moyens, une séquence Ml,..., Mi,..., Mt lui correspondant. Ces caractéristiques permettent, ainsi, d'éviter qu'un attaquant ne puisse imposer une structure choisie sur le second message N de données entrant dans le dispositif de compression 4. On notera que les algorithmes permettent également une expansion de la longueur de chaque bloc. La longueur b d'un bloc Ni est ainsi supérieure à la longueur K d'un bloc Mi. La longueur b est, par exemple, de 512 bits. Les moyens de calcul 13 sont, par exemple, des algorithmes de chiffrement par flot ou "stream cipher" comme l'algorithme RC4. Ces algorithmes permettent de générer une séquence pseudo-aléatoire de blocs à partir d'une clé CL de longueur K bits. Cette clé permet de définir l'état interne des moyens 13. La longueur de la clé est inférieure à la taille de l'état interne de ces moyens. En variante, la longueur de la clé équivaut à la taille de l'état interne. Les moyens 13 constituent alors un simple générateur pseudo-aléatoire de blocs de données.

Grâce à la clé CL, les moyens 13 de calcul génèrent b bits de données tel que :

SC(K)=Sl S2 S3 S4 S5 ... Sj avec SC correspondant à la séquence Sl, .. , Sj de bits obtenue avec les moyens 13 par l'utilisation de la clé CL de longueur K bits.

La variable j correspond au nombre de coups d'horloge nécessaires pour obtenir une suite SC de longueur b bits. Les moyens 13 de calcul utilisent, ici, la séquence Ml,..., Mi,..., Mt comme t clés de longueur K bits. Ainsi, il est possible de générer la séquence Nl,..., Ni,..., Nt tel que: SC(Ml)=Sl, 1 Sl, 2 Sl, 3 ... Sl, j = Nl SC(M2)=S2,1 S2,2 S2,3 ... S2,j = N2

SC(Mt)=St, 1 St, 2 St, 3 ... St, j = Nt

On notera qu'à chaque coup d'horloge, le nombre de bits générés par les moyens 13 est de e. Lorsque e=l, on a donc j=b. En variante, à chaque coup d'horloge le nombre de bits générés par les moyens 13 est par exemple e=8, e=32 ou e=64, ce qui correspond ainsi respectivement à j=b/8, j=b/32 ou j=b/64.

L'utilisation de la séquence Ml,..., Mi,..., Mt comme t clés n'est pas la seule possibilité. Les algorithmes de chiffrement par flot ont souvent une deuxième entrée appelée vecteur d'initialisation. Ce vecteur est un nombre fixé. En variante, ce vecteur varie. Il correspond, par exemple, à la séquence Ml,..., Mi,..., Mt de t blocs. Ainsi la clé CL utilisée dans les moyens 13 de calcul est une combinaison du vecteur d'initialisation et de la séquence Ml,..., Mi,..., Mt des t blocs.

L'utilisation d'algorithmes de chiffrement par flot permet de faire varier aisément la longueur des blocs en sortie des moyens 13 de calcul. Pour cela, il suffit d'attendre autant de coups d'horloges que nécessaire. En effet, la longueur de la clé CL est variable. Ceci permet d'adapter le dispositif 5 de génération au dispositif 4 de hachage utilisé.

En variante, il est possible d'utiliser des algorithmes de chiffrement par blocs ou "bloc

cipher" . Ces algorithmes ne permettent, normalement, pas de faire varier facilement la longueur des blocs en sortie des moyens 13 de calcul. Cependant en utilisant de tels algorithmes dans des modes de fonctionnement particuliers, tels que 1 ' OFB ou "Output-feedback mode" ou le mode "counter", il est possible d'arriver au même résultat qu'un "stream cipher" .

Les t*b bits générés par les moyens 13 de calcul sont ensuite assemblés par les moyens 14 de concaténation pour former le message N de données pseudo-aléatoire .

Le message N est ensuite traité par le dispositif 4 de hachage . Pour cela un second dispositif 15 de "padding" bourre le message N par des éléments supplémentaires δN afin de compléter la longueur de message pour pouvoir la subdiviser en blocs de longueur voulue. Des moyens 16 de subdivision sont ainsi destinés à subdiviser le message complété N+δN. Les moyens 16 forment alors la séquence N'1,..., N'i,..., N'c de c blocs de longueur d bits.

Dans certains cas, c et t sont égaux ainsi que les longueurs b et d. Il n'est pas alors nécessaire de compléter la longueur du message pour son traitement par les moyens de compression 17. C'est le cas par exemple lorsqu'on combine un algorithme RC4, générant un message N multiple de 512 bits, avec une fonction de hachage SHA-I utilisant en entrée des séquences de blocs de 512 bits. Cependant, pour des raisons de coût et de simplicité, il est parfois opportun d'utiliser des dispositifs de compression 4 existants. Dans ce cas, les moyens 15 et 16 sont maintenus.

Les moyens de compression 17 sont ici formés selon la structure de Merkle-Damgard. Cette structure réalise la compression sous la forme d'une chaîne d'opérations réalisées successivement par une fonction de compression f . En variante, il est possible de réaliser la compression sous la forme d'opérations réalisées en arbre.

Dans la structure de Merkle-Damgard, la fonction de compression est répétée de manière itérative. L'étape i utilise deux éléments à savoir un bloc N'i de longueur d bits et une variable de chaîne, Vi-I de longueur h fixée. La sortie de la fonction de compression est la valeur suivante de la variable de chaîne, Vi de longueur h bits, tel que Vi=f (Vi-I , N ' i) . Ainsi la fonction de compression transforme une entrée de h+d bits en une sortie de longueur h bits. A la dernière étape, i=c et la dernière variable de chaîne sortant est Vc, avec Vc = f(...f(V0,N'l),N'2),...N'c) . On notera que la variable de chaîne initiale VO est dépendante de la fonction de compression f utilisée.

Finalement, des moyens 18 de détermination permettent de déterminer le troisième message H, noté également H(W(M)), en fonction de la dernière sortie Vc. Ainsi, H=φ (Vc) où φ est une fonction quelconque qui peut tout simplement être la fonction identité de sorte que H=Vc.

Ainsi, le "pre-whitening" réalisé par le dispositif 5, permet de substituer le message M par un message N. Pour que le message N soit généré pseudo-aléatoirement, il faut que le "stream cipher" soit fort au niveau cryptographique. Le "stream cipher" doit donc respecter différentes conditions. Une de ces conditions, est que l'échantillon de

sortie SC(CL) doit rester indiscernable, pour un attaquant, d'un échantillon dérivé d'une vraie source aléatoire. Une autre condition est qu'un attaquant ne doit avoir aucune chance de déterminer, en un temps raisonnable, un couple de clés CLl et CL2, tel que SC (CLl)=SC (CL2) . Une autre condition est que les moyens 13 ne doivent pas être inversibles. Ainsi, la connaissance de la séquence Nl,..., Ni,..., Nt ne permet pas aisément de retrouver une séquence Ml,..., Mi,..., Mt correspondante.

Ainsi, avec un "stream cipher" respectant ces conditions, les attaques sur les fonctions de compression f, sont contrées. En effet, l'attaquant ne peut manipuler aisément la structure du message N car le pré-traitement l'en empêche. Le "pre- whitening" améliore ainsi la résistance du dispositif 4 de hachage .

Le dispositif 5 de pré-traitement permet, en outre, de renforcer la sécurité du dispositif 4 de hachage. Même si la fonction de hachage est fragile à certaines attaques, les moyens de calcul 13 évitent qu'un attaquant impose uns structure particulière de messages à l'entrée du dispositif 4. Le dispositif 1 de transformation est alors globalement résistant à la pré-image, à la seconde pré-image ou aux collisions alors que la fonction de hachage peut ne pas l'être. Le pré-traitement permet donc de rendre la fonction de hachage cryptographiquement plus sûre.

On notera que le mode de réalisation présenté ici permet d'utiliser, sans modifications, un dispositif de hachage utilisant une fonction de hachage existante. Il laisse, en effet, les opérations internes à la fonction de hachage inchangées. La mise en œuvre du dispositif de

transformation, avec les dispositifs de hachage existants, est donc très simple.

On notera enfin que les fonctions de compression les plus utilisées sont par exemple SHA-I ou MD5.

La Fig.2 présente un dispositif 20 de transformation d'un premier message de données selon un second mode de réalisation de l'invention.

Ce mode de réalisation se distingue du précédent en ce que le dispositif de transformation 20 comprend un dispositif de hachage 24 dans lequel sont implémentés des moyens de calcul 23 pour la génération pseudo-aléatoire d'un second message N.

En effet, le dispositif de hachage 24 se compose, ici, de moyens de formation 22, de moyens de compression 27, des moyens de détermination 28.

Des moyens 23 de calcul sont insérés entre les moyens 22 de formation et les moyens 27 de compression. Ces moyens constituent un pré-traitement ou "pre-whitening" pour les moyens 27 de compression. Le dispositif de génération pseudo-aléatoire 21, se réduit donc ici aux moyens de calcul 23.

Un premier message M de données de longueur quelconque, est d'abord bourré par les moyens 25 puis subdivisé en une séquence Ml, ..., Mi..., Mc de c blocs de données de longueur k. Un deuxième message N, représenté par une séquence Nl, ...Ni, ..., Nc de c blocs de données de longueur b, est généré pseudo- aléatoirement par les moyens 23 de calcul. On notera que b est généralement supérieur à c.

La séquence est utilisée, ensuite, par les moyens 27 de compression, pour constituer en sortie la variable de chaîne Vc. Les moyens 28 de détermination permettent, au final, de déterminer le troisième message H.

La Fig.3 présente un dispositif 30 de transformation d'un premier message de données selon un troisième mode de réalisation de l'invention. Ce dispositif comprend un dispositif de hachage 34 dans lequel sont implémentés des moyens de calcul 33 pour la génération d'un second message N séquence en blocs Nl,..., Ni,..., Nc. Le dispositif de génération pseudoaléatoire 31 se réduit, ici, aux moyens 33 de calcul. Dans ce mode de réalisation, les moyens 33 reçoivent en entrée la séquence Nl,..., Ni, ...Nc. Cette séquence provient d'un premier message M bourré et subdivisé par les moyens 35 et 36 constituant des moyens de formation 32. Les moyens 33 reçoivent également à chaque itération de la fonction de compression une variable de chaîne.

Le bloc Ni constituant la séquence pseudoaléatoire Nl,..., Ni,..., Nc provient alors d'une opération, associant en entrée le bloc Mi avec la variable Vi-I.

L'utilisation de la variable de chaîne permet ainsi d'améliorer le caractère aléatoire de la séquence Nl,..., Ni,..., Nc générée.

On notera que, le "stream cipher" adapte également la taille de chaque bloc Ni à la fonction de hachage utilisée dans les moyens 37 de compression.

La fig.4 présente un procédé de signature d'un premier message. Ce procédé utilise les étapes d'un procédé de transformation dudit premier message M afin de générer un message H de longueur déterminée.

Le procédé de transformation comporte ainsi une étape A de génération pseudo-aléatoire d'un deuxième message N de données à partir du premier message M. Cette étape modifie de manière non prévisible pour un

attaquant la structure du message M. Il sera donc plus difficile, pour un attaquant, d'imposer une structure particulière au deuxième message N. Ceci améliore la résistance du dispositif de hachage . En variante, l'étape A permet de générer un deuxième message N de données de longueur plus grande que le premier message. Ceci augmente la complexité pour un attaquant d'imposer une structure particulière au deuxième message. On notera que l'étape de génération pseudoaléatoire utilise un algorithme de chiffrement par flot. Cet algorithme permet de générer des messages de données pseudo-aléatoires qui sont difficilement distinguables pour un attaquant. En outre, avec un tel algorithme un attaquant ne peut pas retrouver le premier message M à partir de la connaissance du second message N.

Dans un mode de réalisation, l'étape A de génération pseudo-aléatoire est implémentée dans un dispositif de hachage.

Le procédé de transformation comporte également une étape B de compression du deuxième message N en un troisième message H constituant l'empreinte du message M. Le procédé de signature comprend outre les étapes A et B, une étape de cryptographie C pour générer un quatrième message S ou signature. Cette étape est réalisée, par exemple, à l'aide d'une clé privée. Elle permet de garantir l'authenticité et l'intégrité du troisième message M.

Le quatrième message S est ensuite assemblée avec le premier message M pour former le message signé M+S .

Le procédé de transformation d'un premier message de données ainsi que le procédé de signature d'un premier message de données sont mises en œuvre par un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur. Ce programme d'ordinateur comprend ainsi des instructions pour l'exécution des étapes desdits procédés. En variante, les différents procédés sont mises en œuvre de manière logique.