Fonction de hashage

Une fonction de hashage H est une fonction permettant d'obtenir une "empreinte" de données informatiques : A tout bloc de données m, on fait correspondre une chaîne de taille fixe h :

h = H(m)

Intérêt

Ces fonctions permettent d'assurer l'intégrité des données. En effet, ces fonctions sont telles qu'une modification infime de la donnée entraîne un hash totalement différent :

berga@berga-laptop:~$ echo -N "ceci est une chaine de test" | sha1sum 
d69cd0e455d07d5aa288e94c581baa0f739c0e77  -
berga@berga-laptop:~$ echo -N "cela est une chaine de test" | sha1sum 
63b7dacf5b224dbfd8484119b85e59b973137117  -

Propriétés

Lorsqu'elle sont utilisées pour assurer l'intégrité d'une donnée, ces fonctions ont besoin de répondre à des contraintes fortes.

• Rapidité : Même si cette propriété peut paraître désuette, elle est primordiale. En effet, afin d'être utilisable, une fonction de hashage doit assurer le fait que, quelle que soit la donnée en entrée, la fonction fournira, en un temps fini et acceptable, une empreinte à taille fixe :

Pour tout m appartenant à l'ensemble des données possible (i.e. toute chaine binaire), H(m) existe et à une taille fixe

• Résistance au calcul d'une pré-image : Cette propriété assure le fait que, connaissant un hash h et l'algorithme de hashage utilisé pour obtenir h, retrouver la donné m telle que H(m) = h est suffisament difficile :

Connaissant un hash h, la seule façon de retrouver m tel que H(m) = h est d'effectuer une recherche exhausitve (brute-force)

• Résistance au calcul d'une seconde pré-image : Semblable à la propriété précédente, celle-ci stipule que, connaissant m et h tels que h = H(m), il doit être suffisament difficile de trouver m' tel que h(m') = h. La différence avec la résistance au calcul d'une pré-image vient du fait que dans le cas présent, m et h ne sont pas fixés. Le paradoxe des anniversaires fait ainsi passer la complexité de ce problème à 2 ^ (k/2) (au k est la taille du hash), alors qu'elle est de 2 ^ k dans le cas précédent.
• Résistance aux collisions. La nature même des fonctions de hashage fait qu'il existe des données différentes produisant le même hash. En effet, à un nombre infini de données on fait correspondre un nombre fini de hash (puisque de taille fixe). Une fonction de hashage effectue donc un passage d'un espace de cardinalité infinie à un espace de cardinalité 2^k (où k est la taille du hash). Ces fonctions sont donc par nature surjectives, et par conséquent, il existe plusieurs données différentes donnant le même hash. La résistance aux collisions réside donc à la complexité de trouver deux données donnant le même hash, qui augmente avec la taille du hash.

Utilisations

Contrôle d'intégrité

Comme expliqué précédemment, les fonctions de hashage sont utilisées pour assurer l'intégrité d'une donnée. En effet, supposons qu'une donnée m donne un hash h = H(m). Grâce à la propriété de résistance aux collisions, si la donnée m est modifiée ne serait-ce que d'un bit, alors le hash calculé sera différent. Ceci signifie qu'en calculant le hash d'une donnée, et connaissant le hash de la donnée originale, alors on peut vérifier que cette dernière est intègre :

Si H(m) = H(m') et que m et m' sont suffisament semblables, alors m = m'

A cause de l'existences de collisions, on sait que la propriété ci dessus n'est pas vraie pour toute donnée. Les fonctions de hashage utilises donc la théorie du chaos : un faible changement des données entraîne une grande différence des hashs. Cette propriété peut s'utiliser, car si on compare deux données totalement différentes (l'une 1000 fois plus grande que l'autre, par exemple), alors on sait déjà qu'elles ne sont pas les mêmes. Le calcul d'intégrité servant à comparer des données d'un seul espace (deux exécutables, deux corps de mail, deux packages, etc), alors on peut supposer que deux données différents dans cet espace ne pourront produire un hash semblable. D'où l'utilisation du suffisament semblable dans l'énonciation de la propriété précédente. Bref.

Une fonction de hashage est donc utilisée pour assurer qu'une donnée n'a as été modifiée illégitimement. Ceci s'applique par exemple à la distribution d'exécutables, de packages, comme à la transmission de données. Par exemple, dans le cas de la transmission d'un paquet contenant des données, on fait figurer dans l'entête du paquet le hash des données, calculé avant l'émission. Lorque le destinataire reçoit le paquet, il recalcule le hash et le compare à celui présent dans l'entête. Si les deux sont égaux, alors les données sont intègres (à moins qu'un intrus ait intercepté le paquet et modifié également le hash. Mais ceci est une autre histoire...)

Signature

Des mécanismes de chiffrement asymétrique utilise également les fonctions de hashage pour effectuer des signature. En effet, plutôt que de signer l'ensemble des données (ce qui peut devenir trop long lorsque la taille des données augmentent), on peut calculer le hash des données, et signer ce hash, et on transmet les deux. Par exemple, si Alice veut envoyer à Bob le message m et le signer avec sa clé privée PRIValice, elle devrait envoyer le message c tel que :

c = C{PRIValice}[m]

Bob reçoit alors le message, qu'il déchiffre avec la clé publique PUBalice d'Alice, et retrouve ainsi m :

m' = C{PUBalice}[c] = C{PUBalice}[C{PRIValice}[m]] = m 

Si m est suffisament grand, le temps de calcul peut être trop important. De plus, si Bob ne dispose pas de la clé publique d'Alice au moment où il reçoit le message, il ne pourra pas le lire. Pour éviter cela, Alice peut signer uniquement le hash de son message, et le transmettre en même temps. Elle envoit donc :

m, C{PRIValice}[H(m)]

Lorsque Bob reçoit ceci, il peut déjà lire m, même s'il ne dispose pas de la clé publique d'Alice. En revanche, s'il veut vérifier que les données n'ont pas été modifiées, il lui suffit de calculer le hash du message reçu h' :

h' = H[m]

Et de déchiffrer le message d'Alice avec sa clé publique :

C{PUBalice}[C{PRIValice}[H(m)]

Il recupère ainsi le hash qu'Alice a calculé, qu'il peut comparer avec celui qu'il vient de calculer. Si les deux sont égaux, alors il est assuré que le message n'a subit aucune modification.

On conserve ainsi la propriété d'intégrité, tout en facilitant les choses.

Stockage de mots de passe

Une autre utilisation courante des fonctions de hashage est le stockage de mots de passe. En effet, si les mots de passe (d'un site web, d'un forum, etc.), étaient stockés en clair, alors en y ayant accès, on pourrait récupérer les mots de passe de chaque utilisateur. En utilisant une fonction de hashage, on peut stocker les hashs des mots de passe, et non plus les mots de passe en clair. Lorsque l'utilisateur fournit son mot de passe, on calcule son hash et on le compare avec celui stocké. S'ils sont identiques, alors l'utilisateur a fourni le bon mot de passe. Et si le stockage des mots de passe venait à être corrompu, l'attaquent ne pourrait récupérer que les hash. Si les mots de passe utilisés sont suffisament robustes (afin de résister à une attaque par brute-force, alors il ne pourra pas les retrouver.

Principaux algorithmes de hashage

Il existe plusieurs algorithmes de hashagee utilisés aujourd'hui pour des applications diverses :

• MD5, crée en 1992. Des faiblesses ont été démontrées quant à sa résistance à la recherche de collisions. MD5 ne devrait donc plus être utilisé pour des applications de sécurité.
• SHA1, qui reste aujourd'hui l'algorihme de hashage le plus sûr (mais pour combien de temps ? :p).