SHA-1
De Wikipedia, l'encyclopédie encyclopedia
SHA-1 (Secure Hash Algorithm, prononcé /ʃa.œ̃/[1]) 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 National Institute of Standards and Technology (NIST)). Elle produit un résultat (appelé « hash » ou condensat) de 160 bits (20 octets), habituellement représenté par un nombre hexadécimal de 40 caractères.
SHA-1 n'est plus considéré comme sûr contre des adversaires disposant de moyens importants. En 2005, des cryptanalystes ont découvert des attaques sur SHA-1, suggérant que l'algorithme pourrait ne plus être suffisamment sûr pour continuer à l'utiliser dans le futur[2]. Depuis 2010, de nombreuses organisations ont recommandé son remplacement par SHA-2 ou SHA-3[3],[4],[5]. Microsoft[6], Google[7] et Mozilla[8],[9],[10] ont annoncé que leurs navigateurs respectifs cesseraient d'accepter les certificats SHA-1 au plus tard en 2017.
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 à la NSA, le SHA-0 s'est vu modifié peu après sa sortie (1993) et complexifié pour devenir le SHA-1 (1995). Une collision complète sur le SHA-0 a été découverte par Antoine Joux et al. en . En 2005, la cryptanalyste Xiaoyun Wang et ses co-auteurs Yiqun Lisa Yin et Hongbo Yu annoncent une attaque théorique pour la recherche de collisions pour SHA-1 qui est plus efficace que l'attaque des anniversaires (l'attaque générique de référence)[11]. L'attaque complète sera publiée à Crypto 2015[12]. Le NIST pour sa part recommande de passer sur un algorithme SHA-2 ou SHA-3 quand c'est possible. Depuis 2013, Microsoft a déclaré l’obsolescence du SHA-1[13] et en 2014. L'ANSSI déconseille son utilisation dans la seconde version de son Référentiel Général de Sécurité (RGS)[14] d'application au . Enfin, Google annonce que ses versions de Chrome n'accepteront plus, de façon graduelle, le SHA-1 jusqu'à le refuser pour les certificats expirant après le [15].
En Google et le Centrum voor Wiskunde en Informatica annoncent une attaque effective et la première collision sur SHA-1[16].
Voici la signature obtenue sur une phrase (codée en utf8) : SHA1("Wikipédia, l'encyclopédie libre et gratuite") = 6153A6FA0E4880D9B8D0BE4720F78E895265D0A9.
En modifiant un caractère, la signature change radicalement : SHA1("Wikipédia, l'encyclopédie libre et gratuitE") = 11F453355B28E1158D4E516A2D3EDF96B3450406.
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 SHA-1 prend un message d'un maximum de 264 bits en entrée. Son fonctionnement est similaire à celui du MD4 ou MD5 de Ronald Rivest. 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 décrite par Eli Biham, technique reprise pour calculer la collision complète sur SHA-0 (Antoine Joux et al.).
Le SHA-1 commence par ajouter à la fin du message un bit à 1 suivi d'une série de bits à 0, puis la longueur du message initial (en bits) codée sur 64 bits. La série de 0 a une longueur telle que la séquence ainsi prolongée a une longueur multiple de 512 bits. L'algorithme travaille ensuite successivement sur des blocs de 512 bits.
Pour chaque bloc l'algorithme calcule 80 tours (ou rondes, « rounds » en anglais) successifs 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 cinq 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.
À la fin des 80 tours, on additionne le résultat avec le vecteur initial. Lorsque tous les blocs ont été traités, les cinq variables concaténées (5 × 32 = 160 bits) représentent la signature.
Les caractéristiques de SHA-1 sont les suivantes :
- taille du message : 264 bits maximum
- taille des blocs : 512 bits
- taille des mots : 32 bits
- taille du condensé : 160 bits
- niveau de sécurité : collision en 263 opérations.
L’attaque générique des anniversaires permet de trouver une collision en 280 opérations, ce qui est donc la sécurité attendue pour une telle fonction de hachage. Mais dans le cas de SHA-1, il existe une attaque théorique en 269 connue depuis 2005[17], qui a été améliorée en une attaque en 263 opérations. Ces attaques, bien que théoriques, ouvrent la possibilité que de réelles collisions soient découvertes (ce qui est également une question de temps et de moyens).