Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
cryptologie

cryptographie & cryptanalyse

Les fonctions de hachage 1

Publié le 30 Mars 2014 par Levy

Une fonction de hachage est une fonction prenant en entrée un élément de taille variable et renvoyant en sortie un élément de taille fixe et prédéterminée. Ces fonctions sont très utiles notamment dans le domaine des bases de données. Elles permettent de manipuler de très grandes structures tout en gardant une vitesse acceptable en ce qui concerne la recherche d’éléments.Il existe donc deux types de fonctions de hachage:

  • Les fonctions de hachage classiques
  • Les fonctions de hachage cryptographiques

La principale différence entre les fonctions de hachage classiques et les fonctions de hachage cryptographiques est que ces dernières ne doivent pas pouvoir être inversées facilement. Une fonction de hachage classique a très peu de chances de vérifier cette propriété de sécurité. Il en est de même en ce qui concerne les collisions : pour une fonction de hachage classique, on souhaite uniquement que des messages choisis au hasard n’aboutissent à une collision qu’avec une probabilité relativement faible en moyenne.

Pour une fonction de hachage cryptographique, on souhaite qu’il soit difficile pour un adversaire de trouver une collision, cet adversaire pouvant choisir à loisir les messages et donc essayer de se placer dans un cas qui lui est favorable.

 

Une bonne fonction de hachage vérifie (approximativement) l’hypothèse du hachage uniforme simple : chaque clé a autant de chances d’être hachée vers l’une quelconque des m alvéoles, indépendamment des endroits où sont allées les autres clés. Malheureusement, il est impossible en général de vérifier cette condition ; en effet, il est rare que l’on connaisse la distribution de probabilité selon laquelle les clés sont tirées, et les clés peuvent ne pas être tirées de façon indépendante.

Il peut advenir, à l’occasion, que l’on connaisse la distribution. Par exemple, supposons que les clés soient k nombres réels aléatoires, distribués indépendamment et uniformément dans l’intervalle 0<= k < 1.

Dans ce cas, la fonction de hachage h(k) = km  satisfait à la condition du hachage uniforme simple.

En pratique, on peut souvent faire appel à des techniques heuristiques pour créer une fonction de hachage efficace. On a parfois besoin, pour ce processus de conception, de connaître des informations qualitatives sur la distribution des clés. Considérons, par exemple, la table des symboles d’un compilateur, dans laquelle les clés sont des chaînes de caractères arbitraires représentant les identificateurs d’un programme.Il arrive souvent que des symboles proches, comme pt et pts, soient employés dans le même programme. Une bonne fonction de hachage minimise le risque que ces variantes se retrouvent dans la même alvéole.

Une approche courante est de former la valeur de hachage de manière à la rendre indépendante des motifs (patterns) susceptibles d’exister dans les données. Par exemple, la « méthode de la division » (étudiée plus loin) calcule la valeur de hachage comme reste de la division de la clé par un nombre premier particulier. A moins qu’il n’existe des relations entre ce nombre premier et des motifs figurant dans la distribution des clés, cette méthode donne de bons résultats.

 

Propriété des fonctions de hachage

Les fonctions de hachage doivent posséder plusieurs propriétés utiles en cryptographie. Les principales sont la résistance aux attaques recherchant des collisions, des préimages ou des secondes préimages.

  • collision : trouver deux messages distincts M1 et M2 , tels que H (M1) = H (M2).
  • seconde préimage : étant donné un message M1 choisi aléatoirement, trouver un message distinct M2 tel que H (M1) = H (M2).
  • préimage  : étant donné un haché H 1 choisi aléatoirement, trouver un message M 1 tel que H (M1) = H1.

Il doit être impossible pour un attaquant de trouver une collision, une préimage ou une
seconde préimage. On remarque que puisque la taille d’entrée de la fonction de hachage est arbitrairement grande, des collisions existent nécessairement (si l’on choisit 2n+1 messages distincts, il existera obligatoirement une paire de messages aboutissant au même haché).On définit donc l’impossibilité d’un attaquant relativement à une certaine quantité d’opérations,déterminée par la meilleure attaque générique contre une fonction de hachage idéale. Ainsi,un attaquant ne doit pas être en mesure de trouver une préimage en moins de O(2n) opérations, puisque la meilleure attaque générique consiste à essayer O(2n) messages distincts pour avoir une bonne probabilité de succès d’obtenir une solution. Le raisonnement est identique pour la seconde préimage, O(2n) opérations sont nécessaires dans le cas d’une fonction de hachage idéale.

 

Commenter cet article