PICSI

Ce paragraphe pose les premières définitions et propriétés liées aux fonctions de hachage. Ces propriétés sont conçues pour que ces fonctions assurent un maximum de sécurité dans les protocoles où elles sont utilisées : signature, authentification ... Son aspect est donc assez formel mais indispensable pour une bonne compréhension de ces fonctions. Dans la suite, h désignera une fonction de hachage. Définition 1 On dit qu'une fonction de hachage h est résistante aux collisions faibles si, étant donné un message x, il est difficile de trouver un message x′, x′ ≠ x, tel que :

h(x′)=h(x)

Autrement dit,une fonction de hachage est résistante aux collisions faibles s'il est difficile de construire des messages différents possédant la même empreinte. On entend par difficile calculatoirement difficile voir impossible en un temps raisonnable même avec l'aide d'ordinateurs très puissants. Cette définition empêche un éventuel attaquant de modifier le message signé d'une personne et ainsi imiter sa signature. La définition suivante permet de renforcer la sécurité d'un protocole de signature : Définition 2 On dit qu'une fonction de hachage h est résistante aux collisions fortes s'il est difficile de créer deux messages x et x′ différents tels que :

h(x)=h(x′)

Cette mesure a la même finalité que celle de la première définition. Enfin, explicitons ce que nous avons sous entendu en disant que les fonctions de hachage étaient des fonctions à sens unique : Définition 3 On dit qu'une fonction de hachage h est à sens unique si, étant donné une empreinte y, il est difficile de trouver un message x tel que :

h(x)=y

En d'autres termes, on ne peut pas trouver une fonction qui permet d'inverser le processus de hachage. Les fonctions de hachage que nous venons de définir ci-dessus correspondent à la catégorie des fonctions MDC que nous avons signalés dans l'introduction. Pour définir l'autre type de fonction de hachage, c'est à dire les MAC, nous avons besoin de la définition suivante : Définition 4 Une fonction de hachage h_k de type Message Authentification Code (MAC) est une fonction de hachage paramétrée par une clé secrète k telle que :

• Étant donnée une valeur k et un message x, la valeur h_k(x) est facile à calculer. Ce résultat est souvent appelé valeur MAC
• h_k(x) a une valeur fixe de n bits, pour toute valeur de k et toute entrée x
• Étant donné un ensemble de couples (x_i,h_k(x_i)), il est impossible de créer un nouveau message x différent de tous les messages x_i et telle que pour un certain i :
  

  hk(x)=hk(xi)

Retenez principalement qu'une fonction de hachage MAC est une fonction de hachage paramétrée par une clé secrète k et que le calcul du haché, plus précisément de la valeur MAC dans ce cas, nécessite la connaissance de la clé secrète k.