Fonctions de hachage : ce que le NIST prépare

Point névralgique des infrastructures de sécurité et de la signature électronique, les fonctions de hachage doivent être sûres. Or, depuis quelques années, des failles ont été mises en évidence sur plusieurs standards dont SHA-1. D'où la préparation par le NIST d'un nouvel algorithme : SHA-3. Le point sur l'avancée de la compétition.

Les fonctions de hachage constituent un élément essentiel des infrastructures de sécurité. Une fonction de hachage calcule une chaîne de bits de longueur fixe à partir d’une chaîne de bits de longueur arbitraire. Une bonne fonction de hachage (au sens cryptographique) possède un certain nombre de propriétés et peut-être utilisée dans des contextes très variés. Les fonctions de hachage interviennent en effet fréquemment dans les mécanismes de sécurité, ce qui implique que ces mécanismes reposent directement sur la sécurité d’une primitive unique. Pire : seul un très petit nombre de fonctions de hachage se trouve actuellement déployé dans l’industrie. Pour simplifier, les trois propriétés fondamentales qu’une fonction de hachage doit vérifier sont :

Sens-unique. Etant donnée la sortie d’une fonction de hachage, trouver une entrée qui donne cette sortie doit être difficile.

Résistance à la deuxième pré-image. Etant donnée une entrée, trouver une autre entrée qui donne la même sortie doit être difficile.

Résistance aux collisions. Trouver deux entrées distinctes qui donnent la même sortie doit être difficile.

Une quatrième propriété qui pourrait être ajoutée à cette liste est que la sortie d’une fonction de hachage doit » avoir l’air aléatoire « . Ces notions ont bien sûr été formalisées de façon plus rigoureuse par les cryptologues (voir le livre Handbook of Applied Cryptographie).Une des applications classiques des fonctions de hachage est la signature électronique où il est souhaitable de pouvoir signer le haché d’un document plutôt que le document lui-même. La vérification de la signature s’effectue en appliquant la même fonction de hachage au document afin de vérifier la signature du haché. Cette approche n’est bien entendu valable que si les deux primitives cryptographiques (fonction de hachage et signature) sont sûres.La résistance aux collisions est, par exemple, nécessaire pour garantir la non-répudiation, un attaquant étant en effet capable de produire de multiples variations (même infîmes comme faire varier imperceptiblement les espaces entre caractères) de deux documents donnés et à l’aide du paradoxe des anniversaires de trouver une collision beaucoup plus rapidement qu’une pré-image. En obtenant la signature d’un des deux documents, l’attaquant dispose simultanément d’une signature du second document à l’insu du signataire. Une fonction de hachage utilisée lors de l’authentification d’un utilisateur d’un système d’exploitation doit en revanche être résistante aux secondes pré-images. Il est donc important de garder à l’esprit qu’utilisée dans des contextes différents, une fonction de hachage fait souvent appel à des propriétés différentes.

NIST et SHA-3

Le National Institute of Standards and Technology (NIST) est en charge de l’édition et de la mise à jour des standards pour la sécurité des systèmes d’information. La fonction de hachage originalement proposée par le NIST, SHA, a été remplacée par SHA-1 en 1995. Très proche des constructions MD4 et MD5 de Rivest, SHA-1 a depuis lors été rejointe par deux autres standards de hachage, les fonctions de la famille SHA-2 (voir le site du NIST). De récentes avancées en cryptanalyse ont démontré que trouver des collisions pour SHA-1 est beaucoup plus facile qu’espéré. Bien que personne n’ait encore réussi à produire une telle collision, le très large déploiement dont SHA-1 a fait l’objet montre qu’il est nécessaire de migrer rapidement pour une alternative plus robuste. Bien qu’il existe de telles alternatives au sein de la famille SHA-2, le NIST prépare un algorithme alternatif entièrement nouveau : SHA-3.La quête de SHA-3 a débuté le 23 janvier 2007. Après un an de design et d’implémentation, 64 soumissions ont été reçues par le NIST le 31 octobre 2008. Sur ces soumissions, 51 ont été retenues pour le premier tour d’évaluations. A partir de ces évaluations, et afin de concentrer ses efforts sur un nombre de candidats plus restreint, le NIST a sélectionné ce 24 juillet 14 soumissions pour évaluation lors du second tour ; trois des soumissions en lice sont françaises, deux américaines, les autres provenant de divers pays.Ceux qui ont assisté au processus de sélection de l’AES se souviennent peut-être la diversité des soumissions. Dans le cas de la compétition SHA-3, la situation est encore plus marquée. BLAKE, BMW, CUBEHASH, KECCAK, LUFFA, SHABAL, SIMD et SKEIN n’utilisent que des opérations telles que les additions, les » ou exclusifs » et les rotations de bits. Les candidats HAMSI et JH utilisent des briques un peu plus complexes, et les autres sont basés sur l’AES. Les candidats reposant sur des techniques utilisées pour le design de l’AES peuvent être divisés en deux groupes : FUGUE et GRØSTL d’une part et ECHO et SHAvite-3 d’autre part qui peuvent utiliser les nouvelles instructions AES disponibles dès la prochaine génération de processeurs d’Intel. Il est probable que le second tour dure plus d’un an. Cette année fournira certainement son lot d’avancées en cryptanalyse et d’intéressantes discussions sur les compromis adéquats entre sécurité et performance. Les finalistes seront probablement annoncés au troisième trimestre 2010 et au second trimestre 2012, le NIST aura certainement sélectionné le(s) gagnant(s) de la compétition SHA-3. Compte tenu de la chute de plusieurs favoris durant le premier tour, il nous semble beaucoup trop tôt pour faire des pronostics. Ceux qui souhaitent suivre le processus de sélection de SHA-3 trouveront un certain nombre d’informations sur cette page du NIST. L’outil eBASH fournit quant à lui des informations très détaillées sur les performances des candidats (ainsi que de nombreuses autres fonctions de hachage) sur un très grand nombre de plate-formes, et le SHA-3 Zoo maintient un ensemble de pages avec des liens sur les dernières cryptanalyses ainsi que sur les diverses implémentations hardware disponibles. Par O. Billet et M. Robshaw