SHA-1

SHA-1 (Secure Hash Algorithm) est une fonction de hachage cryptographique conçue par la National Security Agency des États-Unis (NSA), et publiée par le gouvernement des États-Unis comme un standard fédéral de traitement de l'information (Federal Information Processing Standard du NIST). Elle produit un résultat (appelé « hash » ou condensat) de 160 bits.

Sommaire

1 Origine : SHA-0 et SHA-1 2 Attaques 2.1 Conséquences 3 Fonctionnement du SHA-1 4 Exemples 5 Le SHA-1 en mode chiffrement 6 La famille SHA

Origine : SHA-0 et SHA-1

Le SHA-1 est le successeur du SHA-0 qui a été rapidement mis de côté par le NIST pour des raisons de sécurité insuffisante. Le SHA-0 était légitimement soupçonné de contenir des failles qui permettraient d'aboutir rapidement à des collisions (deux documents différents qui génèrent le même condensat). Face à la controverse soulevée par le fonctionnement du SHA-0 et certains constats que l'on attribue au NSA, le SHA-0 s'est vu modifié peu après sa sortie (1993) et complexifié pour obtenir le SHA-1 (1995). Une collision complète sur le SHA-0 a été récemment découverte par Antoine Joux et al. (août 2004) et laisse penser que le SHA-1 pourrait lui aussi subir une attaque.

Attaques

Une attaque basée sur le paradoxe des anniversaires permet de trouver une collision complète sur le SHA-1 avec un nombre d'opérations de l'ordre de 2⁸⁰.

En 2005, Rijmen et Oswald ont publié une attaque sur une version simplifiée du SHA-1 (53 tours), leur attaque permet de trouver une collision avec moins de 2⁸⁰ opérations.

En février 2005, Bruce Schneier a fait état d'une attaque sur la version complète du SHA-1 par l'équipe chinoise de Wang, Yin et Yu. Le papier détaillant l'attaque n'ayant pas encore été publié à l'heure où ces lignes sont écrites, il est difficile d'en estimer la portée. Toutefois, les chercheurs affirment que leur méthode pourrait permettre de trouver :

• une collision dans le SHA-1 complet de 128 bits avec 2⁶⁹ opérations au lieu de 2⁸⁰
• une collision dans le SHA-0 complet avec seulement 2³⁹ opérations
• une collision dans une version simplifiée du SHA-1 (58 tours) avec 2³³ opérations

Cette découverte, si elle se confirme, est remarquable du point de vue théorique mais n'est pas encore envisageable en pratique. Des détails commencent à être diffusés. Il semblerait que l'attaque ne fonctionne que sur un SHA-1 sans padding, c’est-à-dire que des données ne sont pas ajoutées à la fin d'un message dont la taille ne serait pas adéquate (multiple de 512 bits). En outre, l'attaque serait similaire à ce qui a déjà été fait sur SHA-0. C’est-à-dire une attaque différentielle combinée à des méthodes qui ont fait leurs preuves sur MD5. On sait également que l'attaque se base sur des observations faites dans les 20 premiers tours de l'algorithme et que des faiblesses auraient été décelées.

Un résumé de l'attaque, sans détails techniques, est disponible sur le site d'un des chercheurs :

Collision Search Attacks on SHA-1

Conséquences

Même si un gain de 2¹¹ opérations permet de diviser le temps de recherche par un facteur 2048, l'attaque avec ses 2⁶⁹ opérations reste encore inaccessible en pratique. Toutefois, la règle veut qu'une attaque plus rapide que la recherche exhaustive rende l'algorithme non sûr du point de vue cryptographique. De plus, avec 2⁶⁹ opérations, nous ne sommes pas loin des 2⁶⁴ nécessaires pour une recherche exhaustive sur un MD5 (qui n'est plus conseillé pour les nouvelles applications). Ayant perdu une longueur d'avance, le SHA-1 pourrait donc être retiré des applications cryptographiques au profit du SHA-256 ou des autres fonctions de hachage comme le Whirlpool ou le Tiger. Les voix s'élèvent déjà pour réclamer un nouveau standard de hachage, comme cela a été le cas il y a quelques années pour la cryptographie symétrique avec AES.

L'attaque produite par Wang et al. ne concerne que des collisions quelconques (tout comme leur fameuse collision complète sur le MD5). C’est-à-dire que l'on peut trouver deux messages au contenu aléatoire qui produisent la même signature. Par contre, à partir d'une signature donnée, il est impossible de forger un second message qui génère la même valeur. Or, c'est ce type d'attaque qui pourrait mettre en péril les applications comme PGP et l'authenticité des données.

Fonctionnement du SHA-1

Le SHA-1 prend un message d'un maximum de 2⁶⁴ bits en entrée. Son fonctionnement est similaire à celui du MD4 ou MD5 de Ronald Rivest. Si le message n'a pas une longueur qui est un multiple de 512 alors l'algorithme rajoute un bit à 1 suivi d'une série de bits à 0. Finalement, la longueur du message (en bits) codée sur 64 bits est ajoutée à la fin de cette séquence. Quatre fonctions booléennes sont définies, elles prennent 3 mots de 32 bits en entrée et calculent un mot de 32 bits. Une fonction spécifique de rotation est également disponible, elle permet de déplacer les bits vers la gauche (le mouvement est circulaire et les bits reviennent à droite). Une de ces rotations n'était pas présente dans le SHA-0, elle permet de casser certaines caractéristiques linéaires dans la structure. Cela permet d'éviter une attaque sur les bits neutres par Eli Biham, technique reprise pour calculer la collision complète sur SHA-0 (Antoine Joux et al.).

Le SHA-1 travaille ensuite individuellement sur des blocs de 512 bits. L'algorithme calcule 80 rondes ("rounds") successives et applique une série de transformations sur l'entrée. La première étape consiste à calculer 80 valeurs sur 32 bits. Les 16 premières valeurs sont obtenues directement à partir du bloc « message » en entrée. Les 64 autres sont calculées successivement. Le SHA-1 les obtient grâce à une rotation (absente dans SHA-0) qui est appliquée sur le résultat d'un XOR, il utilise pour cela 4 mots obtenus dans les itérations précédentes. On définit ensuite 5 variables qui sont initialisées avec des constantes (spécifiées par le standard), le SHA-1 utilise encore 4 autres constantes dans ses calculs. Si un bloc de 512 bits a déjà été calculé auparavant, les variables sont initialisées avec les valeurs obtenues à la fin du calcul sur le bloc précédent.

Il s'ensuit 80 tours qui alternent des rotations, des additions entre les variables et les constantes. Selon le numéro du tour, le SHA-1 utilise une des quatre fonctions booléennes. L'une de ces fonctions est appliquée sur 3 des 5 variables disponibles. Les variables sont mises à jour pour le tour suivant grâce à des permutations et une rotation. En résumé, le SHA-1 change sa méthode de calcul tous les 20 tours et utilise les sorties des tours précédents.

A la fin des 80 rondes, on additionne le résultat avec le vecteur initial et les cinq variables concaténées (5 · 32 = 160 bits) représentent la signature.

Exemples

Voici la signature obtenue sur une phrase :

SHA1("Wikipedia, l'encyclopedie libre et gratuite") = c18cc65028bbdc147288a2d136313287782b9c73

En modifiant un caractère, la signature change radicalement :

SHA1("Wikipedia, l'encyclopedie libre et gratuitE") = 3981d4f03f2732e582f629ba27af75a213cfc7f3

Le SHA-1 est un excellent générateur de nombres pseudo-aléatoires (comme beaucoup de fonctions de hachage) et il passe avec succès tous les tests statistiques. Le seul biais qui a été repéré est la présence d'un plus grand nombre de 0 que de 1 sur de très longues séquences, chose somme toute normale pour un générateur pseudo-aléatoire.

Le SHA-1 en mode chiffrement

Contrairement à ce que l'on peut penser, une fonction de hachage peut être utilisée pour chiffrer mais elle nécessite quelques petites modifications. Dans le cas du SHA-1, il existe un algorithme de chiffrement symétrique, le SHACAL* que l'on doit à Helena Handschuh et David Naccache. Cette possibilité d'encryption est offerte par la réversibilité des variables A,B,C,D et E définies par le standard. Contrairement au hachage, le chiffrement n'additionne pas les variables obtenues à la fin des 80 tours avec des valeurs de départ (présentes au début des 80 tours). La valeur initiale de l'algorithme correspond au texte en clair et la clé secrète est utilisée comme message. En résumé, SHACAL travaille avec une clé d'un maximum de 512 bits (minimum 128 bits) et un message de 160 bits en entrée. Comme tout algorithme de chiffrement par blocs, il est possible de traiter des messages plus longs en chaînant les blocs grâce à des modes de chiffrement comme le CBC, CTR ou encore OFB. Cet algorithme semble résister à la plupart des attaques connues employées avec succès sur le DES (cryptanalyse linéaire, cryptanalyse différentielle) mais les récentes failles trouvées sur le SHA-1 lui promettent un sombre avenir.

La famille SHA

Des versions offrant plus de sécurité sont également disponible : SHA-256, SHA-384 et SHA-512. Comme leur nom l'indique, ces versions fournissent des signatures de 256, 384 et 512 bits. Une variante a été récemment ajoutée, le SHA-224 assure une compatibilité avec la longueur de deux clés qui seraient utilisées pour du Triple DES (4 clés de 56 bits, le 3DES utilise 3 clés de 56 bits).

See also: SHA-1, Aléatoire, Biais, Bit, CBC, Chiffrement, Cryptanalyse différentielle, Cryptanalyse linéaire