URL: https://linuxfr.org/news/sha-mbles-une-collision-a-prefixes-choisis-sur-sha-1 Title: SHA-mbles : une collision à préfixes choisis sur SHA-1 Authors: gouttegd Benoît Sibaud, Xavier Claude et theojouedubanjo Date: 2020-04-19T22:25:15+02:00 License: CC by-sa Tags: sécurité, collision, sha-1 et cve-2019-14855 Score: 4 Au début de l’année 2020, alors que l’on commençait à entendre parler de quelques cas de pneumonie atypique dans la ville chinoise de Wuhan, deux chercheurs français, Gaëtan Leurent (Inria) et Thomas Peyrin (Nanyang Technological University, Singapour), publiaient la première collision à préfixes choisis sur l’algorithme de condensation cryptographique SHA-1, et démontraient la faisabilité d’une attaque contre la toile de confiance OpenPGP. L’attaque, dénommée _SHA-mbles_ (« chaos », « désordre »), est de toute beauté et son étude fournit une excellente occasion, en cette période de confinement, de se pencher sur diverses notions comme le format des certifications OpenPGP ou le fonctionnement des algorithmes de condensation. ---- [Le papier de Leurent et Peyrin décrivant l’attaque](https://eprint.iacr.org/2020/014.pdf) ---- # Description sommaire de l’attaque Avant d’entrer dans les détails sur le fonctionnement de l’attaque, voyons au préalable ce qu’elle permet de faire exactement. Mallory, l’attaquant, cherche à usurper l’identité d’Alice, en fabriquant une clef OpenPGP à son nom qu’il pourra utiliser par exemple pour signer des documents et convaincre une tierce personne que ces documents proviennent d’Alice. Pour réaliser cette attaque, Mallory génère _deux_ clefs : une clef A portant le nom d’Alice, et une clef B portant un autre nom. Il fait certifier la clef B par Charlie, puis _copie la certification de Charlie_ sur la clef A au nom d’Alice. Le but de l’attaque est que quiconque faisant confiance à Charlie accepte la clef A comme étant réellement la clef d’Alice, alors qu’Alice est totalement étrangère à cette clef. Normalement, la manipulation de Mallory, qui consiste à copier une certification d’une clef vers une autre, ne devrait pas être possible. Ou plutôt, elle est complètement possible (une certification n’est jamais qu’une suite d’octets après tout) mais le résultat ne devrait pas pouvoir être considéré comme légitime, de par le principe même de ce qu’est une certification. Quiconque vérifie les certifications portées par la fausse clef A devrait se rendre compte que la certification émise par Charlie n’est pas valable (puisque c’est la clef B que Charlie a certifiée). L’exploit de Leurent et Peyrin est de générer les clefs A et B de telle sorte qu’une certification sur la seconde est _aussi_ une certification valable sur la première. L’attaque vise l’algorithme de condensation SHA-1 et le format des clefs publiques OpenPGP. À ce titre, elle ne dépend pas d’une implémentation particulière du standard OpenPGP (GnuPG par exemple), c’est le standard lui-même qui est vulnérable. # Anatomie d’un certificat OpenPGP Les briques de base du format OpenPGP, tel que défini dans le [RFC 4880](https://tools.ietf.org/html/rfc4880), sont les _paquets_. Chaque paquet a une structure de type TLV (_Tag, Length, Value_), composée d’un octet indiquant le type de paquet (le _tag_), un ou plusieurs octets indiquant la taille (en octets) du contenu du paquet, et le contenu (ou valeur) du paquet proprement dit. Une suite de plusieurs paquets constitue un _message OpenPGP_. Un exemple de message OpenPGP est une _clef publique transférable_ (_Transferable Public Key_ ou TPK), parfois aussi appelé _certificat OpenPGP_, qui contient toutes les informations publiques nécessaires pour communiquer avec le détenteur d’une paire de clefs (c’est par exemple ce que produit la commande `--export` de GnuPG). Une clef publique transférable est composée des paquets suivants : * un paquet de clef publique (_Public-Key Packet_) contenant la partie publique de la clef maîtresse ; * pour chaque _identité_ associée à la clef : * soit un paquet d’identifiant utilisateur (_User ID Packet_, contenant une chaîne au format `Nom (Commentaire) `), soit un paquet d’attribut utilisateur (_User Attribute Packet_, contenant une photo au format JPEG); * un paquet de signature (_Signature Packet_) contenant une auto-certification émise par la clef maîtresse ; * éventuellement, des paquets de signature contenant des certifications émises par des clefs tierces ; * pour chaque sous-clef associée à la clef maîtresse : * un paquet de sous-clef publique (_Public-Subkey Packet_) contenant la partie publique de la sous-clef ; * un paquet contenant une signature d’attachement (_Binding Signature_), émise par la clef maîtresse. Les _certifications_ mentionnées servent à attester (« certifier ») qu’une identité donnée est associée à la clef maîtresse située dans le premier paquet, c’est-à-dire que la clef appartient à l’utilisateur identifié. Une certification est une signature calculée comme suit : * on concatène le paquet de clef publique, le paquet contenant l’identité (_User ID Packet_ ou _User Attribute Packet_), plus quelques métadonnées (par exemple la date de signature) ; * on condense le tout à travers une fonction de condensation choisie parmi celles supportées par le standard (typiquement de nos jours, SHA2-256 — mais SHA-1 peut aussi être utilisée) ; * on exécute l’algorithme de signature sur le condensat ainsi généré, avec sa clef maîtresse privée (dans le cas d’une auto-certification, il s’agit de la clef privée correspondant à la clef publique située dans le premier paquet du certificat) ; * on empaquette le résultat de la signature dans un _Signature Packet_. Si une clef est associée à plusieurs identités (par exemples plusieurs adresses de courriel, ou une adresse de courriel et une photo), chaque identité est certifiée indépendamment, en répétant la procédure ci-dessus pour chaque _User ID Packet_ et chaque _User Attribute Packet_. # De SHA-1 et des collisions Brièvement, une fonction de condensation (_hash function_) cryptographique comme SHA-1 a pour objectif de produire une valeur unique de taille fixe (le condensat, ou l’image) à partir d’une entrée arbitraire (la pré-image), et doit avoir les propriétés suivantes : il doit être pratiquement infaisable de trouver deux pré-images produisant le même condensat (résistance aux collisions), et il doit être pratiquement infaisable de trouver une pré-image correspondant à un condensat donné (_preimage resistance_, qui n’a pas vraiment de traduction élégante à mon goût en français)[^1]. Dans le standard OpenPGP, la fonction SHA-1 a deux rôles distincts. Le premier est le calcul des empreintes des clefs au format v4 (le seul format courant aujourd’hui, le format v3 étant obsolète depuis des années), qui permettent d’identifier une clef de manière unique. L’utilisation de SHA-1 est ici _obligatoire_, le standard n’autorise pas l’emploi d’une autre fonction pour cet usage[^2], du moins pas sans changer le format des clefs (la prochaine version du standard OpenPGP introduira un format v5 où les empreintes seront calculées avec SHA2-256). Le deuxième rôle de SHA-1 est de participer aux opérations de signature, pour calculer le condensat des données à signer qui est ensuite passé à l’algorithme de signature. Pour cet usage, SHA-1 n’est qu’une des fonctions possibles, le standard autorise aussi toute la famille SHA2 (SHA2-224, -256, -384, et -512). Toutes les implémentations modernes utilisent SHA2-256 par défaut, mais il est toujours possible de choisir d’utiliser SHA-1. Dans les (très) grandes lignes, SHA-1 fonctionne en découpant les données à condenser en blocs de 64 octets et en traitant chaque bloc les uns après les autres ; chaque nouveau bloc traité met à jour un état interne sur 160 bits, et le condensat final renvoyé par la fonction est cet état interne tel qu’il est une fois le dernier bloc traité. Une collision est la production de deux documents (« documents » au sens large : dans ce contexte, toute suite d’octets est un document) au contenu différent mais pour lequel la fonction SHA-1 donne un condensat identique. Trouver une collision devrait normalement demander 2^80 opérations, ce qui en pratique est infaisable à l’heure actuelle. Néanmoins, des faiblesses de la fonction permettent de réduire ce nombre d’un facteur ~100 000 (à ~2^(63)), ce qui rend la recherche de collisions réalisable en pratique — comme démontré par l’attaque `shattered` de [Marc Stevens et col. (2017)](https://eprint.iacr.org/2017/190.pdf). Une conséquence du fonctionnement par bloc de la fonction SHA-1, importante pour l’attaque qui nous intéresse ici, est qu’une fois que vous avez trouvé deux documents produisant une collision, vous pouvez étendre ces documents avec des données arbitraires tout en préservant la collision, dès lors que vous ajoutez les _mêmes_ données arbitraires à la fin de chaque document. Par exemple, si les chaînes `ALICE` et `BOBBY` sont une collision et ont le même condensat `X`, alors les chaînes `ALICEAIMELESFRAISES` et `BOBBYAIMELESFRAISES` sont _aussi_ une collision et auront un même condensat `Y`. Un type particulier de collision est la collision _à préfixes choisis_ (_chosen-prefix collision_). Cela consiste à partir de deux documents (les préfixes) distincts — qui donnent donc chacun un condensat différent — et à ajouter des blocs à chacun d’eux de telle sorte que les condensats des documents résultant soient identiques, permettant ainsi « d’annuler » la différence de départ. C’est une collision de ce type que décrivent Leurent et Peyrin dans leur attaque. Je ne m’attarderai pas sur les détails mathématiques qui sous-tendent la recherche de la collision — j’en serais bien incapable —, mais soulignerai seulement qu’ils démontrent qu’il est possible de trouver une collision après avoir ajouté dix blocs (640 octets ou 5120 bits) à chaque préfixe, au prix de ~2^63.4 opérations nécessitant deux mois de calcul sur 900 processeurs graphiques Nvidia (pour un coût de $75 000). # L’attaque sur les certifications OpenPGP Pouvoir générer une collision à préfixes choisis, c’est bien, mais encore faut-il exploiter cette possibilité pour monter une attaque crédible et pratique contre OpenPGP. Là, Leurent et Peyrin quittent le domaine de la cryptographie pour entrer dans celui du _hack_, et c’est un hack de toute beauté qu’ils proposent. Rappelons leur objectif : il s’agit de générer deux clefs OpenPGP A et B de telle sorte qu’une signature de certification sur la clef B soit aussi valable sur la clef A. La clef A sera une clef RSA de 8192 bits, et sera associée à l’identifiant utilisateur `Alice `. La clef B sera une clef RSA de 6144 bits (on reviendra dans un instant sur le choix de ces tailles), et sera associée à deux identités : un identifiant utilisateur `Bob ` et un attribut utilisateur (une image JPEG). Quand Charlie signera la clef B que lui présentera Mallory, et conformément à la procédure de certification décrite plus haut, il générera deux certifications distinctes : une calculée sur la concaténation de la clef B et de l’identifiant `Bob ` (cette certification ne jouera aucun rôle dans le reste de l’attaque ; en fait cet identifiant est seulement là pour rendre la clef conforme — le standard OpenPGP impose qu’une clef publique soit associée à au moins un identifiant utilisateur), et une calculée sur la concaténation de la clef B et de l’image JPEG — c’est cette certification que Mallory va ré-utiliser. Le principe de l’attaque est de faire en sorte que la concaténation de la clef A et de l’identifiant `Alice ` produise un condensat SHA-1 identique à celui produit par la concaténation de la clef B et de la photo. Comment ? D’une part en cachant une copie de l’identifiant `Alice ` dans la photo de Bob (en exploitant le fait que les parseurs JPEG ignorent généralement tous les octets situés après le marqueur de fin d’image, 0xFFD9), et d’autre part en cachant le début de cette même photo à la fin de la clef A. Voilà pourquoi les deux clefs sont de tailles différentes (8192 bits pour la clef A contre 6144 bits pour la clef B) : il faut que la clef B et le début de le la photo de Bob (jusqu’à l’identifiant caché à la fin de celle-ci) fassent au total la même taille que la clef A. Cette différence de taille pose un problème, toutefois : la taille de chaque clef figure au début de son paquet (on a vu plus haut qu’un paquet OpenPGP avait une structure de type _étiquette, taille, valeur_) ; puisque les deux clefs A et B ont des tailles différentes, leurs paquets respectifs commencent différemment et produisent donc un condensat SHA-1 différent. Il faut donc pouvoir réussir à « annuler » cette différence… c’est-à-dire générer une collision à partir de deux préfixes choisis — exactement ce que Leurent et Peyrin sont capables de faire ! ![Fig1](https://incenp.org/files/misc/2020/shambles-concept.png) La figure ci-dessus illustre le fonctionnement de l’attaque en résumant la composition des deux clefs A et B. Chaque clef commence par un préfixe différent (à cause de la différence de taille) ; puis viennent les blocs permettant d’établir la collision, c’est-à-dire de neutraliser la différence des préfixes. La collision est établie juste avant la fin du paquet contenant la clef publique B. Au-delà de la collision, le contenu des deux clefs est _identique_, ce qui permet de préserver la collision et de garantir que les deux clefs produiront toujours un même condensat. La présence de la photo de Bob « cachée » dans le paquet de clef publique de la clef A est ignorée, car les octets correspondants sont simplement considérés comme faisant partie du module RSA ; dans la clef B, la présence de l’identifiant d’Alice « caché » dans la photo de Bob est ignorée, car il est situé après le marqueur de fin d’image JPEG. # Quel impact ? Est-ce qu’on va tous mourir ? Non. Enfin si, mais pas à cause d’une collision à préfixes choisis sur SHA-1. Si l’attaque est sérieuse et prouve encore, si besoin en était, que SHA-1 ne devrait plus être utilisé, l’impact sur OpenPGP devrait rester assez limité, en raison de plusieurs contraintes : * Charlie, le signataire à qui Mallory demande de certifier la clef B, doit certifier avec l’algorithme de condensation SHA-1 obligatoirement. S’il certifie avec un quelconque autre algorithme (comme SHA2-256 qui est l’algorithme utilisé par défaut par les versions modernes de GnuPG), l’attaque est inopérante. Ce paramètre est _a priori_ hors du contrôle de Mallory. * Les victimes de Mallory (celles à qui il présentera la fausse clef d’Alice) doivent accepter les certifications utilisant SHA-1. La version 2.2.18 de GnuPG [refuse](https://lists.gnupg.org/pipermail/gnupg-announce/2019q4/000442.html) de telles certifications, précisément suite à la révélation de cette attaque (référence [CVE-2019-14855](http://cve.circl.lu/cve/CVE-2019-14855)) ; toutefois les versions plus anciennes les acceptent sans sourciller (message pas subliminal : mettez à jour). * Le plus important à mon sens : l’attaque suppose que les victimes se reposent exclusivement sur la toile de confiance, _i.e._ sur la certification de Charlie, pour valider la clef que Mallory leur présente comme la clef d’Alice. En pratique, la toile de confiance OpenPGP est rarement utilisée, même par les « vétérans » d’OpenPGP ; la plupart des utilisateurs ont recours à d’autres canaux pour s’assurer de la validité d’une clef. * L’attaque est par ailleurs assez facile à détecter pour qui sait à quoi s’attendre. Les clefs de taille inhabituelle (6144 et 8192 bits) et la présence d’un attribut utilisateur contenant une photo minuscule (262 octets) peuvent suffire à éveiller des soupçons, et dès lors un examen attentif révélera facilement la présence de la photo cachée dans le module RSA de la clef A. La prochaine version du standard OpenPGP déconseillera formellement toute utilisation de SHA-1 dans les nouveaux messages, ce que toutes les implémentations modernes respectent déjà de toute façon. [^1]: Formellement on distingue la _preimage resistance_ de la _second preimage resistance_, mais cette distinction est inutile pour ce qui nous intéresse ici. [^2]: C’est le seul aspect du standard OpenPGP à ne pas offrir d’_agilité cryptographique_.