vignette|droite|300px|Un tour de la fonction de compression de SHA-1 : A, B, C, D, E sont des mots de 32 bits ; <<<n désigne une rotation des bits par décalage de n bits vers la gauche ; F est une fonction (non linéaire sur le corps F2 des booléens) qui dépend du numéro de tour t ; ⊞ est l'addition modulo 232 (l'addition des entiers machines non signés de 32 bits), qui est non linéaire sur F2 ; Kt est une constante (32 bits) qui dépend du numéro de tour t ; Wt est un mot de 32 bits qui dépend du numéro de tour t ; il est obtenu par une procédure d'expansion à partir du bloc de donnée (512 bits) dont le traitement est en cours.
SHA-1 (, prononcé ) est une fonction de hachage cryptographique conçue par la des États-Unis (NSA), et publiée par le gouvernement des États-Unis comme un standard fédéral de traitement de l'information ( du (NIST)). Elle produit un résultat (appelé « » ou condensat) de (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 n'était pas suffisamment sûr pour continuer à l'utiliser. Depuis 2010, de nombreuses organisations ont recommandé son remplacement par SHA-2 ou SHA-3. Microsoft, Google et Mozilla ont annoncé que leurs navigateurs respectifs cesseraient d'accepter les certificats SHA-1 au plus tard en 2017.
Origine La fonction de hachage SHA-1 succède à SHA-0 qui a été rapidement mise de côté par le NIST pour des raisons de sécurité insuffisante. 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 de SHA-0 et certains constats que l'on attribue à la NSA, SHA-0 a été modifiée peu après sa sortie (1993) pour devenir SHA-1 (1995). Une collision complète sur SHA-0 a été effectivement découverte par Antoine Joux en .
Abandon de SHA-1 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 nettement plus efficace que l'attaque des anniversaires (l'attaque générique de référence). L'attaque complète sera publiée à Crypto 2015. Le NIST pour sa part recommande de passer à SHA-2 ou SHA-3 quand c'est possible. Depuis 2013, Microsoft a déclaré l’obsolescence de SHA-1 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) d'application au . Enfin, Google annonce que ses versions de Chrome n'accepteront plus, de façon graduelle, SHA-1 jusqu'à refuser les certificats l'utilisant qui expirent après le .
En Google et le Centrum voor Wiskunde en Informatica annoncent une attaque effective et la première collision pour SHA-1..
Exemples Voici la signature obtenue sur une phrase (codée en utf8) :
En modifiant un caractère, la signature change radicalement :
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.
Caractéristiques En résumé les caractéristiques de SHA-1 sont les suivantes : taille du message : 264 bits maximum taille des blocs : 512 bits (le message en entrée est découpé en blocs de 512 bits) taille des mots : 32 bits (SHA-1 est construite à partir d'opérations sur des mots de 32 bits) taille du condensé : 160 bits niveau de sécurité : collision en 263 opérations. L’attaque des anniversaires, qui est l'attaque générique sur les fonctions de hachage cryptographique pour trouver une collision, permet de trouver (théoriquement) celle-ci 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 opérations connue depuis 2005. C'est attaque a été améliorée en une attaque en 263 opérations, et une collision a effectivement été découverte en 2017.
Attaques Une attaque brute basée sur le paradoxe des anniversaires permet de trouver une collision complète sur une clé SHA-1 complète (sur 160 bits) avec un nombre d'opérations de l'ordre de .
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 opérations.
En , 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. Leur méthode permet de trouver :
une collision dans le SHA-1 complet de avec opérations au lieu de par l’attaque des anniversaires une collision dans le SHA-0 complet avec seulement opérations une collision dans une version simplifiée du SHA-1 (58 tours) avec opérations
La description de l'attaque a été publiée en .
Le , une amélioration de l'attaque a été annoncée par Wang à la conférence CRYPTO 2005, la complexité passe ainsi de 2 à 2, soit une division par 64 de la complexité originale.
Lors de l'Eurocrypt 2009 (avril), une améliorationhttp://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf de l'attaque aurait permis de réduire à nouveau sa complexité jusqu'à atteindre . Toutefois, ces résultats furent démentis et l'articlehttp://www.ictlex.net/wp-content/iacrhash.pdf fut retiré. à la suite de la découverte d'une erreur dans l'évaluation de cette complexité.
Une équipe composée de chercheurs de chez Google et du CWI (Centrum Wiskunde et Informatica) ont annoncé le qu'ils avaient réussi à obtenir une collision entre deux documents..
Une équipe composée de chercheurs universitaires (Gaëtan Leurent de l'Inria en France et son collègue Thomas Peyrin de l'Université de Nanyang à Singapour) a annoncé en début avoir mis au point une attaque sur la version complète de SHA-1 (80 tours) permettant d'obtenir pour n'importe quelle valeur de hachage une collision sur des préfixes choisis en un nombre d'opérations situé entre et , ce qui réduit le coût d'obtention de collisions à moins de , à la portée d'une organisation de moyenne taille (ou de bandes organisées) et plus seulement de grandes organisations ou de gouvernements, basée sur une analyse différentielle multi-bloc (et non un bloc unique avec les tentatives précédentes), ce qui permet d'en améliorer l'efficacité en réduisant l'espace de recherche de façon incrémentielle. En , ces mêmes chercheurs ont annoncé avoir amélioré leur attaque et pouvoir obtenir une collision en opérations, pour un coût de 45k$. Les investigations continuent pour déterminer le coût minimum de ce type d'attaque qui pourrait en pratique s'avérer même inférieur (des attaques similaires sont démontrées également sur d'autres algorithmes de hachage similaires, y compris MD5 qui était déjà connu pour être cassé mais qui le devient encore plus facilement). Toutefois l'attaque annoncée ne concerne pas encore les empreintes de messages (ou signatures) HMAC basées sur SHA-1., pour EUROCRYPT 2019, paru dans Advances in Cryptology, pp. 5247-555 ()..
Description La fonction de hachage SHA-1 est une fonction de hachage itérative, c'est-à-dire qu'elle itère sur le message en entrée découpé en blocs successifs de même taille une fonction, dite fonction de compression pour produire un condensé, ou haché, ou empreinte de taille fixe. Plus précisément elle repose sur la construction de Merkle-Damgård, c'est-à-dire que l'entrée est complétée par un procédé dur de bourrage pour que sa longueur soit un multiple de la taille du bloc, le dernier bloc contenant une représentation binaire de la taille de l'entrée initiale, ce qui permet de réduire la résistance aux collisions de la fonction de hachage à celle de la fonction de compression. Son fonctionnement est similaire à celui des fonctions MD4 et MD5 de Ronald Rivest.
Dans le cas de SHA-1 on a : taille de bloc : 512 bits ; taille du haché : 160 bits ; fonction de compression :{0,1}160+512 → {0,1}160 ; taille maximale de l'entrée : 264 bits. Cette dernière limitation (théorique) vient du fait que la longueur de l'entrée, ajoutée dans le dernier bloc, est stockée sur 64 bits.
La fonction de compression est construite à partir d'opérations sur des mots de 32 bits, qui représentent des entiers non-signés inférieurs à 232. Ces opérations sont : les opérations bit à bit usuelles : le ET bit à bit ; le OU bit à bit ; le OU exclusif bit à bit ; le NON bit à bit ; l'addition entière modulo 232, c'est-à-dire l'addition informatique usuelle sur des entiers non-signés de 32 bits ; un décalage circulaire de bits vers la gauche (0 ≤ s < 32).
Ces opérations s'implémentent de façon extrêmement efficace, mais combinées de façon adéquate, elles permettent d'obtenir une sortie qui parait avoir les qualités recherchées pour une fonction de hachage (en particulier résistance à la collision, résistance à la préimage).
Détails Les spécifications de SHA-1 sont décrites pour la première fois en dans le document officiel du NIST FIPS 180-1 pour un standard de fonction de hachage cryptographique, puis reprises dans les versions successives de ce document jusqu'à la version de 2015 du FIPS-180-4. Elles ne seront pas reprises dans la version suivante.. Elles sont largement accessibles sur InternetStinson et Paterson utilisent cet argument pour ne pas détailler l'algorithme. Outre les FIPS PUB 180-1 à 180-4 du NIST, les spécifications sont données dans la RFC 3174, qui les accompagne d'un programme C..
Bourrage Le bourrage consiste à compléter le message initial de longueur en bits < 264, pour obtenir un message dont la longueur est un multiple de 512 bits (la taille de bloc). L'injectivité du procédé est une condition nécessaire : on aurait une collision évidente si ≠ mais que, après bourrage = .
Le message complété est obtenu en concaténant à la fin du message un bit à 1 suivi d'une suite de bits à 0 dont la longueur dépend de , suivie de la représentation binaire de , codée sur 64 bits, c'est-à-dre que les 64 derniers bits de sont réservés à cet usage. La longueur de la suite de bits à 0 est la plus petite pour laquelle la longueur du message complété est un multiple de 512.
Fonction de hachage itérative Le message complété est découpé en blocs de 512 bits consécutifs, soient . La concaténation est notée , on a : = .
L'algorithme itère une fonction de compression, soit : {0,1}160+512 → {0,1}160, et utilise un vecteur d'initialisation de 160 bits. Il produit une suite de valeurs de chaînage de 160 bits, la dernière valeur étant le haché.
:= , pour = particularisé au cas de SHA-1..
Fonction de compression
Pour chaque bloc l'algorithme calcule 80 tours ( » en anglais) successifs et applique une série de transformations sur l'entrée. La première étape consiste à calculer 80 valeurs sur . 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 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.