Hash Length Extension Attacks

Cet article a pour but de résumer mes recherches web sur les attaques par extension des fonctions de hashage. Petit exemple d’attaque par extension sur du sha1.

Problématique

J’ai un message à transmettre et je souhaite garantir que ce message ne soit pas modifié entre son émission et sa réception. Je veux également être le seul à forger des messages à l’intention de mon destinataire. Dans les deux cas, la confidentialité du message n’est pas importante. Autrement dit : tout le monde peut voir le message que j’ai émis, mais personne ne doit pouvoir discuter de façon valide avec mon destinataire.

Prenons l’exemple d’une url. Nous sommes sur un site e-commerce et nous souhaitons rediriger l’internaute vers le site de la banque pour qu’il paie sa commande.

http://url_banque/paiement.cgi?commande=5580&montant=140€&texte-libre=Telephone

Aucune information de sensible ne transite, mais nous ne souhaitons pas que l’internaute puisse modifier le montant de la commande ou rajouter des paramètres à l’url.

MAC

Une solution consiste à signer les données transmises en utilisant un code d’authentification de message (MAC). Une version simple est de concaténer une clé secrète au message et de hasher le tout.

function createMac(key, msg) {
   return sha1(key + msg)
}

Nous allons générer une signature à partir d’une clé secrète et des données métier : la référence de la commande, le montant et un texte libre. Le « <*> » correspond au séparateur des données.

String mac = createMac("AABBCCDDEEFFGGHH", "<*>5580<*>349€<*>Telephone")
mac : af90d9acf27bb11cb7027920fe9b2f51a72ba754

L’url finale est la suivante : http://url_banque/paiement.cgi?commande=5580&montant=140€&texte-libre=Telephone&mac=af90d9acf27bb11cb7027920fe9b2f51a72ba754

API simplifié du site bancaire :

  • commande : référence de la commande
  • montant : montant que le client doit payer
  • texte-libre : chaine de caractère apparaissant sur la facture et renvoyée au site appelant lors de la confirmation.
  • nbre-paiement : nombres de débits à réaliser pour payer la commande.
  • mac : sceau certifiant les données émises par le commerçant. Le calcul du sceau est le suivant : cle secrete<*>commande<*>prix<*>texte-libre[<*>nb-paiement]

Attaque par extension

Les fonctions cryptographique comme MD5, SHA-1 ou SHA-256 qui sont construites selon le principe de Merkle-Damgård sont vulnérables aux attaques par extension. Ces attaques consistent à rajouter des données aux messages original puis à calculer un nouveau MAC sans connaitre la clé secrète. Les ingrédients suivants sont nécessaires à sa réalisation :

  • MAC construit de la sorte : H(cle + message)
  • taille de la clé connue (on peut néanmoins la deviner)
  • message transmis connu
  • algorithme vulnérable (md5, sha1, sha256, sha512)

Dans notre exemple, l’internaute veut rajouter un paramètre à l’url afin de déclencher une option sur le site bancaire : le paiement en 3 fois sans frais. Il lui faut ensuite calculer le MAC correspondant à son message.
L’url sera la suivante : http://url_banque/paiement.cgi?commande=5580&montant=140€&texte-libre=Telephone&nbre-paiement=3&mac=5db6f78e7a721f729147cd5166bb7541b1109ce6
En réalité, l’url n’est pas aussi jolie que cela car elle contient du padding. Pour comprendre pourquoi regardons comment fonctionne l’attaque par extension d’un point de vue technique.

Fonctionnement des algorithmes

Les fonctions de hash travaillent sur des blocs de données de taille fixes (512 bits pour md5, sha1 et sha256). Bien évidemment, la taille de la plupart des messages a hasher n’est pas divisible par 512. Il faut donc rajouter des données aux messages (padding) pour arriver à un multiple de la taille des blocs.
Dans notre exemple, le message que sha1 va hasher n’est pas « AABBCCDDEEFFGGHH5580<*>349€<*>Telephone » mais plutôt « AABBCCDDEEFFGGHH5580<*>349€<*>TelephonePADDING» afin d’obtenir un multiple de 512.

Données réellement hashé :
hash1
Une fois le remplissage du message réalisé, le premier bloc de l’algorithme est initialisé via un vecteur d’initialisation constant. Par la suite, le résultat du calcul du bloc courant sert d’initialisation pour le bloc suivant. Le résultat du dernier bloc correspond au hash.

Génération de l’extension

La première étape est de calculer le nouveau MAC. L’état final de hashage du message d’origine doit être notre état initial. Pour cela, le premier bloc de l’algorithme doit être initialisé avec la valeur du MAC original. Une fois cette étape de réalisée, il suffit de hasher normalement les données à rajouter. On obtient le hash du « message original + notre extension » qui devra être transmis dans l’url.

algo.initialiser(MAC_ORIGINALE) 
mac = algo.compute(extension)

Présenté différemment, voilà ce que nous avons fait :

  1. Initialisé l’algorithme à l’état final original (512) grâce au MAC
  2. Lancé SHA-1 avec notre extension
  3. SHA-1 a automatiquement paddé pour arriver à un multiple de 512.

hash2

Il ne reste plus qu’à reconstruire la totalité du message à envoyer à notre destinataire.
Nous connaissons :

  • le message original
  • l’extension (normal, c’est nos données)
  • le hash final (avec notre extension)

Il nous manque :

  • la taille du padding se situant après le message original

hash3
Si nous ne complétions pas le message original avec du padding le destinataire n’obtiendrait pas le même MAC que celui transmis dans l’url et refuserait de réaliser l’opération demandée.
Données envoyées (sans padding du message original) :hash5
Données hashées par notre interlocuteur (le padding de fin est automatiquement rajouté par SHA-1) :

hash4

Pour déterminer la taille du padding il n’existe pas 36 solutions.

  • Solution 1 : connaître la taille de la clé
  • Solution 2 : deviner la taille de la clé

Pour deviner la taille de la clé, il faut procéder de manière incrémentale jusqu’à obtenir un résultat positif. Pour obtenir une réponse, il faut soumettre le message au destinataire et analyser sa réaction. Dans la majorité des cas, l’application cible produit une sortie différente pour un message d’entrée valide et pour un message erroné.
Données envoyées (avec padding du message original) : hash6
Données hashées par notre interlocuteur (le padding de fin est automatiquement rajouté par SHA-1) :hash7

Dans l’exemple du service bancaire, pour activer l’option de paiement en 3 fois sans frais, l’attaquant doit forger l’url suivante :
http://url_banque/paiement.cgi?commande=5580&montant=140€&texte-libre=Telephone=80=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=01&nbre-paiement=3&mac=5db6f78e7a721f729147cd5166bb7541b1109ce6
Le padding est affiché en encodage Quoted-Printable.

En recevant cette url, le serveur bancaire extrait les paramètres et calcule le sceau :

Spécifications : 
sceau = sha1(cle secrete<*>commande<*>prix<*>texte-libre[<*>nb-paiement])

Mise en œuvre :
sceau = sha1("AABBCCDDEEFFGGHH<*>5580<*>349€<*>Telephone=80=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=01<*>3") ;
// sceau → 5db6f78e7a721f729147cd5166bb7541b1109ce6

sceau == mac => le serveur bancaire considère l'url comme valide.

POC

J’ai adapté et complété un POC en java que j’ai trouvé sur le site javacodegeeks. Les sources de l’algorithme SHA-1 ont été récupérées sur le site docjar.
Télécharger le POC

Sortie de l’exemple bancaire :

Données à certifier : <*>5580<*>349€<*>Telephone
Message avant MAC : AABBCCDDEEFFGGHH<*>5580<*>349€<*>Telephone
MAC original : af90d9acf27bb11cb7027920fe9b2f51a72ba754

Recover digest state...
Compute extension MAC...
Extended MAC  : 5db6f78e7a721f729147cd5166bb7541b1109ce6
Trying to find suitable input....
Message entendu
==> Hex    : 3c2a3e353538303c2a3e333439e282ac3c2a3e54656c6570686f6e6580000000000000000000000000000000000001603c2a3e33
==> Quoted Printable <*>5580<*>349=E2=82=AC<*>Telephone=80=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=00=01`<*>3
==> Padding Length: 12
==> Secret Length : 16

Algorithmes vulnérables

Sur son site, Ron Bowes indique avoir réalisé un outils implémentant l’attaque par extension pour les algorithmes suivants :

  • MD4
  • MD5
  • RIPEMD-160
  • SHA-0
  • SHA-1
  • SHA-256
  • SHA-512
  • WHIRLPOOL

HMAC

La solution au problème d’attaque par extension et HMAC (Keyed-Hash Message Authentication Code).
MAC = hash(key + hash(key + message))

Sources
http://benlog.com/articles/2008/06/19/dont-hash-secrets/
http://dev.ionous.net/2009/03/hmac-vs-raw-sha-1.html
http://www.skullsecurity.org/blog/2012/everything-you-need-to-know-about-hash-length-extension-attacks
http://www.javacodegeeks.com/2012/07/hash-length-extension-attacks.html
http://ballastsec.boards.net/index.cgi?board=hashing&action=display&thread=1
https://blog.whitehatsec.com/hash-length-extension-attacks/

 

  1. bien expliqué, ça m’a aidé pour bien comprendre. Merci infiniment.

Laisser un commentaire


huit + 4 =


NOTE - Vous pouvez utiliser les éléments et attributs HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>