Nouvelles attaques sur SHA-1 : Debian pourrait migrer vers SHA-2

Posté par  . Modéré par Florent Zara.
Étiquettes :
25
9
mai
2009
Sécurité
La conférence Eurocrypt 2009 qui s'est achevé le 20 avril dernier nous a donné de nouvelles attaques sur la fonction de hachage SHA-1. Trouver une collision ne nécessite maintenant plus que 2^52 opérations, soit quelques semaines de calcul sur un PC standard (voir ce document pdf d'annonce de la nouvelle attaque).

Un plan de migration pour la bien connue distribution GNU/Linux Debian a été proposé, soit une migration de l'ensemble des clefs PGP et GPG de son infrastructure (développeurs compris) vers des clefs plus robustes. Beaucoup de ses clefs font en effet appel aux mécanismes RSA ou DSA, avec des clefs de 1024 bits, ainsi qu'à la fonction de hachage SHA-1, à l'exception notable de la clef primaire de la distribution stable actuelle, Lenny, qui fait 4096 bits (RSA).

Les clefs migreraient donc toutes vers l'algorithme RSA, taille 2048 bits, ainsi que vers les fonctions de hachage de la famille SHA-2 (SHA-224, SHA-256, SHA-384 et SHA-512). Tout l'enjeu de cette migration est de ne pas casser le Web of Trust (chaîne de confiance) déjà existant mais de le faire migrer en douceur.

Plus de détails dans la suite de la dépêche. Concernant la migration
Il s'agit de signer les nouvelles clefs, fortes, avec les anciennes. Ainsi, la confiance déjà existante dans l'infrastructure actuelle se transposera naturellement vers les nouvelles clefs, plus robustes. Une fois que la nouvelle clef est prise en compte partout où nécessaire, on peut alors publier un certificat de révocation de l'ancienne.

À propos des fonctions de hachage et de cryptographie
Une fonction de hachage est une des primitives de base de la cryptographie. Elles servent notamment à tout ce qui est signature et authentification. Pour schématiser, une fonction de hachage prend un gros fichier (typiquement, un paquet logiciel dont on veut certifier la provenance, ou bien une clef GPG d'une personne à qui on donne confiance), et fournit ce qu'on appelle un hash ou condensat de quelques centaines de bits. On signe alors uniquement le hash avec sa clef publique (RSA ou DSA) et non pas le fichier total initial. Comme la signature est une opération longue, on évite ainsi de signer un fichier qui peut être très gros.

La sécurité de la fonction de hachage repose alors sur l'impossibilité pratique de calculer une « collision » - c'est-à-dire de trouver deux fichiers qui ont le même hash - ou pire, une « deuxième pré-image » - c'est-à-dire trouver un deuxième fichier de même hash qu'un fichier donné. Dans l'exemple d'un paquet logiciel, trouver un autre fichier possédant le même hash qu'un paquet signé signifie que ce deuxième fichier sera reconnu comme paquet certifié par le gestionnaire de paquets. Ajoutons qu'une fois trouvé un deuxième fichier de même hash que le paquet initial, il est souvent « aisé » (au moins pour un spécialiste, aidé de quelques machines de calcul :) de le triturer jusqu'à en faire à peu près n'importe quoi (un programme malveillant par exemple). Ce genre d'attaque ouvre alors la voie à l'émission de paquets avec signatures valables sans aucune compromission de l'infrastructure existante : il suffit de créer un faux paquet de même hash qu'un paquet déjà existant (ou ancien) et on peut récupérer la signature de cet ancien paquet pour faire passer le nouveau comme valide.

Un successeur pour la famille SHA-2
Notons par ailleurs que la famille SHA-2 a été construite sur le même principe que la fonction SHA-1. Si aucune attaque n'a encore été trouvée (au moins officiellement :), il n'en demeure pas moins que leur sécurité n'est plus aussi estimée qu'avant. C'est pour cela que le NIST (l'Institut national des standards et de la technologie aux USA) a proposé une compétition internationale pour trouver un successeur à la famille SHA, sur le même modèle que celle qui avait eu lieu pour l'AES. Il est prévu que cette compétition débouche en 2012 sur la nouvelle fonction de hachage SHA-3.

Aller plus loin

  • # Annonce un peu hâtive ?

    Posté par  (site web personnel) . Évalué à 10.

    Je pense que la nouvelle va un peu fort avec un titre comme « Debian migre vers SHA-2 ». Une personne qui n'est pas (encore) Developeur Debian propose un mécanisme de migration, et on en conclu que Debian migre vers SHA-2. Oui, c'est quelque chose qui va se faire tôt ou tard, mais pour le moment rien n'a encore été décidé.
    • [^] # Re: Annonce un peu hâtive ?

      Posté par  (site web personnel) . Évalué à 10.

      A mon sens, un des soucis de ce genre de réseau (PGP/GPG ou SSH) est qu'il est basé sur des clefs ayant la plupart du temps une durée de vie infini. Donc on monte son réseau et puis un jour ... patatras, il y a un article qui dis que les clefs ne sont pas si géniale que cela à terme.

      Au final, cela me donne comme pour SSH le sentiment d'un défaut de conception. Les clefs de chiffrement à usage pour le réseau devrait toujours avoir une durée de vie limitée (c'est souvent le cas des certificat X509 que le trouve pour les sites HTTPS, mais pas toujours). La durée de vie limité résout à terme le problème des failles inévitable (cf carte bleu).

      La solution de la révocation n'est pas bonne car elle demande au client d'aller voir des listes centralisées, de se mettre à jour et que celui-ci ai effectivement implémenté ce mécanisme de révocation. Bref, c'est bien mais pas assez fiable pour se baser la dessus sur du long terme.

      A partir du moment ou les clefs ont une durée de vie limité, il faut dès la conception penser à la mise à jour de ces clefs et assurer la période transitoire à deux clefs. C'est souvent mal fait, même sur les certificats X509. Le CNRS a d'ailleurs été confronté au passage aux certificats CNRS2 il n'y a pas longtemps et nous avons deux ans pour mettre à jour tous nos certificats dans les laboratoires. Malgré cela, pas mal d'applications n'aiment pas le changement de certificat. Par exemple, comment mettre à jour le certificat de mon serveur OCS qui me déploie mes logiciels sachant que celui-ci a soit le nouveau, soit l'ancien certificat mais ne peut pas avoir les deux ! Cela se mors la queue et je n'ai pas trouvé de bonne solution intégrée dans OCS...

      Au final, je dirais qu'il y a du travail sur la planche pour que les développeurs de ces applications modifient leurs protocoles pour tenir compte de cet aspect temporel et que le protocole lui-même gère la phase de transition avec une mise à jour automatique des clients vers les nouvelles clefs et que les deux clefs soient équivalentes pour les clients. Pour le moment, un serveur web ou ssh ne peut avoir deux clefs !

      Debian l'a bien compris puisque chaque distribution est lié a une et une seule clef. Lorsqu'elle sors une distribution, la clef de la future stable est déjà dans le paquetage keyring pour que la mise à jour de la stable vers la future stable (testing) puisse se faire sans hurlement de la part d'APT. C'est ce genre de mécanisme qui doit être pensé et généralisé, bien sur en s'adaptant à la problémtique !
  • # Pas une migration officielle

    Posté par  (site web personnel) . Évalué à 10.

    Il ne s'agit pas d'une annonce officielle du projet Debian, simplement une (excellente) méthode de migration proposée par un utilisateur du site debian-administration.org

    De nombreux développeurs ont déjà annoncé la migration de leur clé personnelle (utilisée notamment pour signer les paquets qui vont atterrir dans l'archive officielle), mais je n'ai vu aucune annonce du projet pour le moment.

    @++
    Julien
  • # Pas critique

    Posté par  (site web personnel) . Évalué à 10.

    Attention à ne pas sombrer dans l'hystérie : cette faille est loin d'être critique. Elle permet de fabriquer une paire X et X' qui ont la propriété SHA1(X) = SHA1(X'), mais ne permet pas de choisir X ou X', ce qui fait qu'il serait très difficile d'imiter une signature numérique.

    D'ailleurs, cette attaque est connue pour MD5 depuis un bout de temps, et n'a pu être exploitée en situation réelle qu'une seule fois (voir l'attaque sur les certifs SSL).

    Bref, il vaut mieux rester avec du SHA-1 que se ruer sur un successeur qui n'a pas encore fait ses preuves. Debian agit prudemment en voulant passer en douceur à une solution plus sécurisée.

    J'attendrais aussi d'avoir des preuves un peu plus sérieuses que ce pdf avant de crier au loup (par ex la publication d'une collision)
    • [^] # Re: Pas critique

      Posté par  (site web personnel) . Évalué à 5.

      et si on trie les fonctions de hashage par ordre de "sécurité" supposée , est-ce que
      md5 est toujours moins secure que sha-1 ou bien est-ce que l'annonce de cette attaque a remis les deux à égalité ?
      • [^] # Re: Pas critique

        Posté par  . Évalué à 9.

        MD5 est moins secure que SHA-1.
        Il est possible de calculer très rapidement des collisions sur MD5.
        L'attaque sur SHA-1 indique qu'il est devenu théoriquement plus rapide de trouver des collisions que tout ce qui était connu jusqu'à présent.

        Des applications cassant SHA-1 aussi bien qu'a pu le faire HashClash pour MD5, on a pas encore vu, mais ça ne saurait tarder.

        Moralite:
        N'utilisez plus MD5. Faute de mieux, utilisez SHA-1, mais prévoyez _très_ rapidement de migrer vers plus solide.
    • [^] # Re: Pas critique

      Posté par  . Évalué à 10.

      Elle permet de fabriquer une paire X et X' qui ont la propriété SHA1(X) = SHA1(X'), mais ne permet pas de choisir X ou X

      Certes. Autrement dit, elle permet de trouver une collision, mais pas une seconde préimage. D'un autre côté, cela ne présage rien de bon pour les attaques en seconde préimage comme l'a montré l'histoire des attaques sur MD5. D'une manière générale, s'il est impossible de trouver des collisions alors il est impossible de trouver une seconde préimage (l'inverse n'étant pas vrai). Mais ici, il est possible de trouver des collisions... Les secondes préimages ne sont donc sans doutes plus très loin.

      Au sujet du papier :
      L'attaque dont parle la dépêche est une application des attaques boomerang d'Antoine Joux et de Thomas Peyrin.
      Ceux-ci ont montré qu'on pouvait appliquer les attaques boomerang (voir wikipedia, http://fr.wikipedia.org/wiki/Attaque_boomerang ) aux attaques connues sur SHA-1. Une fois trouvé des caractéristiques différentielles sur SHA-1, on peut réduire la complexité de l'attaque déjà connue en 2^57.
      Une caractéristique différentielle est en gros un couple de messages différents, dont la différence a une forte probabilité (plus forte que si la fonction de hachage était parfaite) de rester identique au cours de chaque tour de la fonction. C'est une des briques de bases qui permettent de construire deux messages ayant le même hash.

      Tout ce que fait le papier est d'exhiber 5 caractéristiques différentielles, il est peu probable qu'ils se soient lourdement trompés en les trouvant :) L'intérêt est de gagner 2^5 sur le temps de la meilleure attaque connue, soit un facteur 32.
      Les auteurs disent d'ailleurs qu'ils publieront leur travail bientôt, il ne reste plus qu'à surveiller http://eprint.iacr.org :)

      Sinon les successeurs de SHA (SHA-256 & Co), quoique construits sur le même principe de base que SHA-1, ont été étudiées pour justement en améliorer la sécurité. D'ailleurs le fait que les attaques sur SHA-1 ne s'y appliquent pas bien montre bien qu'elles lui sont préférables :) D'une manière générale en cryptographie, un système n'est de toutes façons considéré sûr que parce que la communauté des cryptanalystes a passé beaucoup de temps à l'étudier mais n'a pas trouvé de faille...
  • # "Aisé"?

    Posté par  . Évalué à 9.

    <<il est souvent « aisé » (au moins pour un spécialiste, aidé de quelques machines de calcul :) de le triturer jusqu'à en faire à peu près n'importe quoi (un programme malveillant par exemple).>>

    Là, je tique un peu: un paquet étant donné, il est si "facile" de créer un deuxième paquet avec la même signature, les mêmes fonctions "apparentes" et du code malveillant en plus? ça fait beaucoup de contraintes!

    Car même l'utilisateur le plus basique va se rendre compte que quelque chose cloche, s'il installe le paquet "iceweasel" et que le navigateur n'est toujours pas apparu dans ses menus et son PATH.
    Reprendre une application existante, et insérer du code malveillant, en gardant la même signature, ça me parait un peu "mission impossible."

    THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

    • [^] # Re: "Aisé"?

      Posté par  . Évalué à 3.

      Pour reprendre ce qui avait été fait sur MD5 (certificats ou autres), les attaques intéressantes en deuxième préimage sur les fonctions de hachage utilisent le fait que dans un fichier à corrompre il y a souvent énormément de place pour ajouter des informations inutiles pour le fonctionnement normal du fichier mais utiles pour que le hash soit le bon.
      Typiquement, des méta-données d'un document PDF ou PS remplies de garbage sont peu visibles pour l'utilisateur quelconque, mais le contenu "réel" (intéresssant) du document sera complètement modifié (il y a un certain nombre d'exemples qui traînent sur le web dans le cas de MD5)

      Dans le cas d'un paquet logiciel, on peut modifier des parties sensibles du code, et pour que le hash soit le bon ajouter avec un peu de travail du code mort totalement invalide (de toutes façons il ne sera jamais exécuté) ailleurs dans les fichiers, garbage qui servira seulement au hash.

      Sinon en règle générale il ne vaut mieux pas attendre les attaques pour commencer à s'y préparer :) Il n'y a qu'à voir le GIE cartes bancaires qui en avait bien fait les frais avec [[Serge Humpich]] . Dans le cas des fonctions de hachage, c'est d'autant plus critique de s'y prendre à l'avance que sitôt une collision trouvée, l'émission de paquets falsifiés mais reconnus certifiés sera possible sans compromission aucune de l'infrastructure existante, en reprenant la signature d'un ancien paquet.
      • [^] # Re: "Aisé"?

        Posté par  (site web personnel) . Évalué à 3.

        Pour que cette attaque fonctionne, il faut que l'attaquant soit l'auteur du premier message signé (dans lequel il insère la chaine à collision), qu'il remplace ensuite par la collision.

        En pratique, dans un paquet de distribution, ça n'a pas d'intéret, parce qu'on ne peut pas faire signer n'importe quoi en premier lieu (il suffirait de mettre directement la backdoor dedans dans ce cas, pas besoin d'attaque cryptographique de sioux)
      • [^] # Re: "Aisé"?

        Posté par  . Évalué à 4.

        Pour un exemple pratique, voir l'"attaque Nostradamus" où des chercheurs néerlandais on pu "prédire" qui sera le futur président américain aux dernières élections :
        http://www.win.tue.nl/hashclash/Nostradamus/
    • [^] # Re: Aisé?

      Posté par  . Évalué à 3.

      Car même l'utilisateur le plus basique va se rendre compte que quelque chose cloche, s'il installe le paquet "iceweasel" et que le navigateur n'est toujours pas apparu dans ses menus et son PATH.

      Hum, c'est justement un peu trop tard...

      Disons qu'il est plus intéressant de faire cela dans le cadre d'une mise à jour...

      Et puis j'installe iceweasel et je suis un débutant, je vais simplement penser que :

      Debian c'est pas si super que ça, ça n'installe pas le programme que je demande...

      Le tout étant de trouver un clone parfait du hash, ensuite la comparaison des deux programmes va permettre de faire ce qu'on veux avec un troisième programme mutant dans lequel on aura enlevé quelques bytes et ajouté quelques autres, le tout étant de garder un hash identique. Je ne dit pas que c'est simple, je dit que c'est concevable.

      "Gentoo" is an ancient african word, meaning "Read the F*ckin' Manual". "Gentoo" also means "I am what I am because you all are freaky n3rdz"

    • [^] # Re: "Aisé"?

      Posté par  . Évalué à 5.

      Non, pas aisé. C'est difficile.

      Aujourd'hui, (et c'est aussi le cas pour MD5), on ne sait pas produire un message dont son hash aurait une valeur fixé.
      Donc si Iceweasel est signé, alors je ne peux pas trouver un autre programme dont le hash correspondrait au hash de iceweasel.

      Néanmoins, il est possible de produire des collisions assez facilement (pour MD5 c'est le cas, pour SHA-1) ça ne saurait tarder.
      Donc je peux écrire un programme iceweasel qui possède le même hash qu'un programme iseweasel-evil.

      Je demande à faire signer iceweasel. J'utilise la signature donnée pour mon programme iceweasel-evil.

      L'utilisateur installe le evil, et la signature est bone.

      La limite de cette attaque, c'est que tu dois fournir les deux programmes. C'est toujours le même principe. Autant il est simple d'obtenir deux programmes dont le hash concorde, autant tu ne peux pas, à posteriori, retomber sur un hash existant.

      Il me semble que justement on en parle dans un magazine en ce moment.
      • [^] # Re: "Aisé"?

        Posté par  . Évalué à 1.

        Merci, je comprends mieux maintenant.

        Ceci dit, vu que Debian patche à tout va ce qui lui tombe sous la main avant de le packager, c'est inapplicable à cette distribution :+p

        D'ailleurs, OpenSSL avait été patché afin de se prémunir contre une attaque sur la signature du paquet, même si le remède était pire que le mal. ^^'

        (Pas de troll, je suis sous Debian).

        THIS IS JUST A PLACEHOLDER. YOU SHOULD NEVER SEE THIS STRING.

        • [^] # Re: "Aisé"?

          Posté par  . Évalué à 6.

          Ceci dit, vu que Debian patche à tout va ce qui lui tombe sous la main avant de le packager, c'est inapplicable à cette distribution :+p

          Je dirais que justement, c'est d'autant plus facile à attaquer!

          On a vu qu'il n'est pas possible de trouver le même hash que le iceweasel d'origine.

          Mais Debian passe son temps à ajouter des patches.

          Donc, je suis dans la situation parfaite:
          Je fournis un patch qui ajoute un petit truc, mais qui surtout rend la signature d'iceweasel (ou d'un autre prog) égale à un autre programme!

          Donc pour l'attaquant, c'est du pain béni. A partir du moment ou tu as réussi à devenir developpeur debian, tu peux intégrer un patch soit disant 'inoffensif' dont le seul but est de faire concorder le paquet initial avec ton paquet 'evil'.

          Exemple: tu reprends en main un vieux paquet tout pourri dont personne ne se sert (parceque iceweasel, ça va être dur à noyauter :) ). Tu fais deux trois màj, tu deviens dev debian. Tu ajoutes un patch de plus, ton paquet est signé automatiquement. Ce patch te donne le même hash que le hash d'un paquet 'login' amélioré :-) par tes soins.
          Tu demandes la signature de ton paquet. Tu t'en sers pour le paquet 'login' qui te permet de passer root.

          Arrive la seconde partie de ton attaque. Admettons que tu sois dans une université. Tu rebalances un bon vieux coup de DNS spoof pour faire pointer les serveurs de maj chez toi. Tu forces la maj du paquet 'login'. Petit à petit, toutes les debian de ton université se mettent à jour. La signature est validée, donc il n'y a pas la moindre protestation de la part d'apt etc...

          ---) tu es root sur toutes les debian.

          Pour revenir au sujet initial, le problème des collisions de fonctions de hachage est un vrai problème, comme on peut le voir.
          • [^] # Re: "Aisé"?

            Posté par  (site web personnel) . Évalué à 3.

            > Mais Debian passe son temps à ajouter des patches.

            Je ne suis pas sur que Red-Hat (et Fedora) et Novell patchent moins... J'aimerais avoir des vrais statistiques que ce genre de phrase gratuite.
            • [^] # Re: "Aisé"?

              Posté par  . Évalué à 4.

              Debian passe son temps à ajouter des patches != Debian est la seule distribution à ajouter beaucoup de patches
          • [^] # Re: "Aisé"?

            Posté par  . Évalué à 5.

            Euh, tu sais comment fonctionne un repository Debian (a fortiori officiel) ? Parce qu'il y a des expressions que je vois pour le premiere fois, genre "ton paquet est signé automatiquement" ou "Tu demandes la signature de ton paquet", bien qu'étant DD et ayant maintenu un repo pendant 3 ans.

            Tu as aussi l'air de considérer que les packages sont signés individuellement dans l'archive, ce qui n'est pas le cas, ce sont les fichiers Release et Packages qui le sont, le second contenant les hash (MD5, SHA1 et SHA256) de chaque package.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.