Attaque par extension de longueur

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La mise en forme de cet article est à améliorer (février 2022).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

En cryptographie et sécurité des systèmes d'information, une attaque par extension de longueur est un type d'attaque où l'attaquant utilise le hash Hash(message₁) et la longueur de message₁ pour calculer Hash(message₁ ‖ message₂) avec un message₂ contrôlé par l'attaquant, sans avoir à connaître le contenu de message₁. Les algorithmes tels que MD5, SHA-1 et la plupart des versions de SHA-2 qui sont basés sur la construction de Merkle-Damgård sont vulnérables à ce type d'attaque^[1]^,^[2]^,^[3]. Les versions tronquées de SHA-2, comprenant SHA-384 et SHA-512/256 n'y sont pas vulnérables^[4], tout comme l'algorithme SHA-3^[5].

Lorsqu'une fonction de hachage basée sur la Construction de Merkle-Damgård est utilisée en tant que code d'authentification de message avec la construction H(secret ‖ message)^[1], et que le message et la longueur du secret sont connus, une attaque par extension de longueur permet à un attaquant d'inclure des informations supplémentaires à la fin du message et produire un hash valide sans connaître le secret. Comme HMAC n'est pas conçu selon la construction de Merkle-Damgård, les hashs produits avec HMAC ne sont pas vulnérables à l'attaque par extension de longueur^[6].

Explication

Les fonctions de hachage vulnérables à cette attaque prennent un message comme valeur d'entrée et l'utilisent pour transformer leur état interne. Après le traitement du message, le condensé du message (hash) est généré en renvoyant l'état interne de la fonction. Il est possible de reconstruire l'état interne à partir du hash, qui peut alors être utilisé pour traiter d'autres données. De cette façon, quelqu'un peut agrandir le message et calculer le hash qui est une signature valide pour le nouveau message.

Exemple

Un serveur qui gère un service de livraison de gaufres proposant plusieurs saveurs à un utilisateur géolocalisé pourrait être implémenté pour gérer des requêtes d'après le format suivant :

Donnée originale: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Signature originale: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

Le serveur prendrait la requête en compte (livrer dix gaufres "eggo" à l'adresse donnée pour l'utilisateur "1") seulement si la signature est valide pour l'utilisateur. La signature utilisée ici est un code d'authentification de message, signé avec une clé inconnue de l'attaquant. (Cet exemple est aussi vulnérable à une attaque par rejeu, en envoyant la même requête et la même signature une nouvelle fois.)

Il est possible pour l'attaquant de modifier la requête, dans cet exemple la gaufre demandée passe de "eggo" à "liege." C'est faisable en abusant de la flexibilité du format du message car un contenu dupliqué dans la requête HTTP prendra seulement en compte la dernière valeur.

Nouvelle donnée: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

Afin de signer ce nouveau message, l'attaquant aurait besoin de connaître la clé qui a été utilisée pour signer le message original, et générer une nouvelle signature en générant un nouveau code d'authentification de message. Mais avec une attaque par extension de longueur, il est possible d'entrer le hash (la signature originale) dans l'état de la fonction de hachage, et reprendre où la requête originale s'était terminée, tant que la longueur de la requête originale est connue. Dans cette requête, la longueur de la clé d'origine était 14 octets, ce qui aurait pu être trouvé en essayant plusieurs requêtes frauduleuses supposant différentes longueurs de clé, et constater quelle longueur constitue une requête que le serveur accepte comme étant valide.

Le message donné à la fonction de hachage est souvent remplis, car de nombreux algorithmes travaillent avec des données d'entrée dont les longueurs sont des multiples de longueurs prédéfinies. Le contenu de ce remplissage est toujours spécifié par la fonction de hachage utilisée. L'attaquant doit inclure tous ces bits de remplissage dans ses messages frauduleux avant de les aligner avec l'état interne de la fonction de hachage du message original. Ainsi, l'attaquant construit un message différent en suivant les règles de remplissage:

Nouvelle donnée: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x02\x28&waffle=liege

Ce message inclut le remplissage qui a été ajouté au message original dans la fonction de hachage avant la donnée frauduleuse (ici, un 0x80 suivi par des 0x00s et la longueur du message, 0x228 = 552 = (14+55)*8, qui est la longueur de la clé plus la longueur du message original). L'attaquant sait que l'état correspondant au hash de la paire clé/message pour le message original est identique à celui du nouveau message jusqu'au dernier "&". L'attaquant connaît le hash à ce moment-là, c'est-à-dire l'état interne de la fonction de hachage. Il est alors trivial de lancer l'algorithme de hachage, ajouter les derniers caractères, et générer un nouveau hash pour signer son nouveau message sans la clé originale.

Nouvelle signature: 0e41270260895979317fff3898ab85668953aaa2

En combinant la nouvelle signature et la nouvelle donnée dans une nouvelle requête, le serveur va considérer la requête frauduleuse comme une requête valide car sa signature est la même que si elle avait été générée avec le mot de passe de l'utilisateur.

Références

↑ ^{a et b} Hoàng Vũ, « MD5 Length Extension Attack Revisited - Vũ's Inner Peace » [archive du 29 octobre 2014], 30 mars 2012 (consulté le 27 octobre 2017)
↑ Thai Duong et Juliano Rizzo, « Flickr's API Signature Forgery Vulnerability », 28 septembre 2009 (consulté le 27 octobre 2017)
↑ Christopher Meyer, « Hash Length Extension Attacks », 30 juillet 2012 (consulté le 27 octobre 2017)
↑ Michael Bostrom, « size_t Does Matter: Hash Length Extension Attacks Explained », 29 octobre 2015 (consulté le 23 novembre 2020)
↑ Keccak Team, « Strengths of Keccak - Design and security » (consulté le 27 octobre 2017) : « Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key. »
↑ Nate Lawson, « Stop using unsafe keyed hashes, use HMAC », 29 octobre 2009 (consulté le 27 octobre 2017)