Une attaque en 2^69 opérations aurait été trouvée, c'est à dire plus rapide d'un facteur 2000 par rapport à l'attaque par force brute en 2^80 (Cependant, 2^69 opérations reste à l'heure actuelle hors de portée du commun des ordinateurs). Cette attaque, basée sur l'attaque de SHA-0, est un résultat très important dans le domaine de la cryptanalyse. Il faut maintenant attendre que l'équipe publie son papier pour avoir les détails de l'attaque.
Le nombre de fonctions de hachage cryptographique sûres commence à se réduire et, comme le disait d'ailleurs Bruce Schneier quand les collisions sur MD5 et SHA-0 avaient été publiées, il est peut-être temps de réfléchir à un nouveau standard. NdM : un algorithme de hashage est "cassé" quand il existe une méthode de coût bien moindre que la recherche brute pour générer de façon déterministe des collisions, c'est à dire deux fichiers ayant la même empreinte. C'est le cas ici puisque la méthode annoncée est 2^11 fois moins coûteuse que la méthode brute.
Ce qui n'est pas encore clair cependant, c'est le type de collisions que cette méthode permet de produire. Est-ce qu'elle génère une collision quelconque (c'est le cas de l'attaque existante pour MD5) ou bien est-il possible de viser une empreinte particulière ? Et dans la seconde hypothèse, le fichier généré sera-t-il quelconque ou bien peut-il être contraint à une forme particulière (par exemple, à être un code source proche de l'original mais avec une backdoor et une chaîne en commentaire servant à corriger l'empreinte) ?
Aller plus loin
- Schneier on Security, le blog de Bruce Schneier (23 clics)
- MD5 et SHA-0 cassés (68 clics)
- Cryptanalysis of MD5 and SHA: Time for a New Standard (8 clics)
- SHA-1 sur Wikipedia (51 clics)
# alternatives
Posté par Antoine . Évalué à 4.
Ont-elles été éprouvées ?
[^] # Re: alternatives
Posté par Beretta_Vexee . Évalué à 2.
Il y a aussi le RIPEMD-160 mais je ne sais absolument pas ce qu’il vaut, mais c’est un Hash a vocation cryptographique.
[^] # Re: alternatives
Posté par udok . Évalué à 2.
ça tombe bien, c'est de vérification d'intégrité qu'il est question ici ;)
[^] # Re: alternatives
Posté par Vivi (site web personnel) . Évalué à 2.
non, SHA-1 est un hash crypto.
[^] # Re: alternatives
Posté par Beretta_Vexee . Évalué à 3.
Tiger hash a pour principalement fonction de faire des Hash tree a la volé, par d'étre très résistant aux attaques, il est d'aillieur presque exclusivement utilisé dans des soft de peer to peer ( qui sont très demandeur de fonction de hash rapide et de hash tree pour faire du contrôle d'intégrité par fragment ).
SHA-1 a pour vocation d'être un Hash crypto, après tous pour faire de la vérification d'intégrité CRC suffirait dans pas mal de cas.
[^] # Re: alternatives
Posté par tgl . Évalué à 5.
> to peer ( qui sont très demandeur de fonction de hash rapide et de
> hash tree pour faire du contrôle d'intégrité par fragment ).
En même temps, le p2p a quand même intérêt à s'assurer un peu de la sécurité au niveau des fonctions de hash qu'il utilise, sinon il peut se faire polluer très facilement.
Par exemple, je pense que si les protocoles les plus populaires reposaient sur des fonctions de hash trop faibles, les majors prendraient la peine de forger les empreintes de leurs fakes de mp3 pour imiter celles des vrais fichiers déjà en circulation. Ou encore, l'industrie du cinéma pourrait diffuser des chunks de pur bruit avec de très bonnes chance de corrompre au moins partiellement la plupart les téléchargements des divx visés. Enfin, les utilisateurs les moins scrupuleux des systèmes qui favorisent le donnant-donnant de façon active (à la emule, "tu m'as envoyé tel chunk, et il a la bonne empreinte, donc je te mets preums dans ma file d'attente") pourraient chercher à gagner des places en diffusant des fakes de tout et n'importe quoi pourvu que ce soit ce dont leur cible est demandeuse.
Enfin bref, c'était juste pour préciser que le p2p a vraiment besoin de plus que d'un bête CRC, pour la bonne raison que tous les participants ne sont pas de bonne volonté.
[^] # Re: alternatives
Posté par Beretta_Vexee . Évalué à 3.
Dans ces conditions le spoofing est supra simple puisque qu'il suffit des conserver les 512 premier Ko du fichier et de foutre n'importe quoi apres pour poluer un fichier.
A ma connaissance les autres protocoles n'ont pas trop de problème, ( et aussi surment parce que le protocol qui utilise Tiger Hash n'est franchement pas populaire ...).
[^] # Re: alternatives
Posté par Benoît Sibaud (site web personnel) . Évalué à 4.
[^] # Re: alternatives
Posté par Beretta_Vexee . Évalué à 2.
Ce sont des milices pas des bénevoles.
[^] # Re: alternatives
Posté par Christophe Renard . Évalué à 3.
Même méthode mais en plus long ... l'attaque marchera sans doute, mais le gain est normalement moins significatif.
http://freshmeat.net/projects/sha2/
Reste à attendre la publi effective du papier des chercheurs chinois pour connaitre les détails.
[^] # Re: alternatives
Posté par Christophe Renard . Évalué à 1.
zewoo plus bas a mieux répondu que moi à la question.
En revanche, les interessés pourront tirer profit d'une visite à la Hashing Function Lounge : http://planeta.terra.com.br/informatica/paulobarreto/hflounge.html
# Temps de réfléchir à un nouveau standard ?
Posté par bmc . Évalué à 5.
Y'aurait-il une personne bien informée dans la salle pour nous expliquer les différents axes de recherche actuels ? Le troisième lien de la news parle de SHA-256, SHA-384 et SHA-512, mais ils sont a priori sur la même base que SHA-1, non ? Ils ont par contre l'air de limiter les collisions...
[^] # Re: Temps de réfléchir à un nouveau standard ?
Posté par zewoo . Évalué à 10.
Niveau recommandation, dans le même esprit, cela fait un moment que DES n'est plus recommandé (et triple-DES guère plus), mais que seul AES l'est.
Il faut voire que l'appellation casser un algorithme de cryptage dépent énormément de ce que l'on veut faire: est-ce qu'être capable d'extraire des collisions est suffisant? Pour autant, cela n'est pas utilisable pour casser une utilisation: ce qui est intéressant, c'est être capable de créer des collisions à partir de n'importe quelle données en entrée; ou de retrouver les sources des collisions, en ayant une empreinte à disposition... Ainsi pour le commerce électronique ou tout autre application nécessitant de la sécurité, ce résultat nouveau n'apporte rien d'utilisable en pratique (encore plus s'il est relativement semblables à leur travaux de l'été dernier: ils pouvaient trouver des collisions, mais pas en trouver qui correspondaient à une empreinte donnée)
Enfin, juste comme ça; Citer Bruce Schneier n'est pas vraiment gage de valeur: il n'est pas vraiment consideré comme un spécialiste dans le milieu de la crypto: son bouquin est une bonne introduction (la meilleur disponible certainement) mais cela s'arrete là. Il y a des erreurs dans les algorithmes de son bouqin.
[^] # Re: Temps de réfléchir à un nouveau standard ?
Posté par densmore . Évalué à 2.
Donc non, ce n'est vraiment pas un amateur en la matière.
Le SHA-256 partage le même type de structure que le SHA-1 (blocs de 512 bits) alors que le SHA-384 et SHA-512 travaillent sur 1024 bits. Le SHA-256 utilise d'autres fonctions par rapport au SHA-1. Comme tu le soulignes, l'adaptation de l'attaque sur le SHA-1 sera sûrement compliquée mais les Chinois sont très forts dans ce domaine :)
http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchang(...)
[^] # l'algo de hachage du futur : Whirlpool
Posté par patrick_g (site web personnel) . Évalué à 6.
http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.(...)
# Ou bien est-il possible de viser une empreinte particulière
Posté par Beretta_Vexee . Évalué à 3.
Quelqu’un a connaissance d’un précèdent de ce type, avec une taille comparable au fichier original ? Parce que j’avais bien vue un exploit de ce genre pour le CRC ( qui n’est pas une fonction de hash destiné a la crypto je suis d’accord ), mais celle-ci générée des fichiers avec une surpoids au alentour des 100 voir 200%.
Personnellement cela m’étonnerais que la faille soit de ce type, pourvoir générer des collision a la demande permet déjà de casser pas mal de mot de passe.
De plus même si la puissance peut paraître énorme il ne faut pas oublier qu’elle peut déboucher sur des attaques a de type compromit temps/mémoire, a la manière des rainbow crackers pour le MD5. Donc avec un bonne bande d’amis un système de calcul distribué casser des pass SHA-1 pourrait devenir accessible a tous groupe un peut organisé.
[^] # Re: Ou bien est-il possible de viser une empreinte particulière
Posté par dvrasp . Évalué à 2.
Pour SHA-1, je ne sais pas si toutes les combinaisons de 80 bits donnent toutes des hash différents. Si c'est le cas, on peut théoriquement forger la signature d'un document en n'en modifiant au maximum que 80 bits. Dans le cas contraire, le nombre de bits à modifier doit tout de même rester dans le même ordre de grandeur.
Ce qu'apporterait cette découverte dans ce contexte (en attendant la publication du papier), c'est que pour trouver la combinaison de bits qui permet de forger une signature quelconque, il n'est pas nécessaire de tester toutes les possibilité de manière exaustive (2000 fois moins de tests). C'est dans ce sens qu'on dite que SHA-1 aurait été cassé, même si le temps de calculs nécessaire reste encore astronomique (de l'ordre de l'année, à vue de nez, avec des moyens sérieux).
# et les distribs?
Posté par Thomas Maurin (site web personnel) . Évalué à 1.
Est-ce que c'est prévu ?
Est-ce que l'utilisation du PGP dans portage est une réponse à ce problème ?
[^] # Re: et les distribs?
Posté par mdlh . Évalué à 3.
[^] # Re: et les distribs?
Posté par udok . Évalué à -1.
[^] # Re: et les distribs?
Posté par Beretta_Vexee . Évalué à 7.
Donc pour l'identification le MD5 n'est plus sur, mais pour la vérification d'intégrité les risques sont assez faible.
[^] # Re: et les distribs?
Posté par tgl . Évalué à 9.
> n'ont pas changé de système de hachage ?
Le MD5 est "cassé", mais pas n'importe comment non plus. En particulier, on ne sait pas forger un fichier donné pour lui donner une empreinte particulière. Donc les failles de MD5 sont à ce jour inexploitable pour ce qui est de distribuer incognito (càd sans modification de leur MD5) des programmes backdoorés ou ce genre de choses. Bref, ça n'est pas franchement un risque de sécurité pour les distribs, et comme ça fait bien son boulot pour ce qui est de vérifier qu'il n'y a pas eu d'erreur de téléchargement, y'a pas vraiment d'urgence à changer.
> Est-ce que l'utilisation du PGP dans portage est une réponse à ce problème ?
Non, justement.
Le problème que ça règle (règlera), c'est le cas où un mirroir serait compromis. Actuellement, si un méchant bidouille des ebuilds et regénère le bon digest pour aller avec, il passera inaperçu. Pas besoin de casser du MD5 pour ça... Le but d'une utilisation de GPG là dedans, c'est justement de signer ces digests, pour que leur remplacement par le méchant ne passe plus inaperçue, et que donc du coup il ne puisse plus dissimuler ses modifications sur les ebuilds.
Quand ça sera fait, la seule solution qui restera à notre méchant sera justement de faire ses trucs dans les fichiers sans pour autant en modifier les empreintes, pour que le digest signé reste valide. Mais là, même avec de simples MD5, il faudra qu'il s'accroche, pour les raisons exposées plus haut.
[^] # Re: et les distribs?
Posté par Thomas Maurin (site web personnel) . Évalué à 1.
Merci beaucoup pour toutes ses précisions, j'y vois plus clair. :)
[^] # Re: et les distribs?
Posté par zewoo . Évalué à 1.
[^] # Re: et les distribs?
Posté par PierreF . Évalué à 1.
Pour les mots de passe du systeme, il est probablement plus rapide de tester toutes les possibilité (les mots de passe sont pas très long,seulement des lettres, sauf si on est attentif à la sécurité). De plus il faut avoir acces au fichier /etc/shadow, sinon il faut donnée les mots de passe à un programme du genre login, or login attend un certain temps avant de dire que le mot de passe n'est pas valable. Donc pour les mot de passe des utilisateurs, c'est pas le MD5 qui posse de problème de sécurité.
Sinon pour signer des données (les fichiers sources), il est assez difficile de falsifier les fichiers (mais pas impossible):
- il faut crée un fichiers valable avec le même hash (on sais faire en qq heures un fichier avec le même hash MD5, mais il n'aura pas de sens [1])
- il faut le remplacer sur le mirroir utilisé (donc le piraté)
- faire tout ca assez vite (il faut pas qu'il y ai déjà une nouvelle version)
[1] http://fr.wikipedia.org/wiki/MD5
[^] # Re: et les distribs?
Posté par Jaimz . Évalué à 2.
Par contre certains ont évoquer des scénarios où cette faiblesse pourrait être exploitée. Par exemple à une époque, je ne sais pas si c'est toujours vrai, Verisign permettait de générer des certificats MD5 choisi par l'utilisateur. Un Escroc pourrait donc générer une collision, se créer un certificat avec un des éléments. Et utiliser ensuite l'autre élément pour utiliser le certificat de manière malhonnête et se dédouaner en montrant que le "malfaiteur" n'a pas utilisé la même "clef" que lui.
[^] # Re: et les distribs?
Posté par Éric (site web personnel) . Évalué à 9.
Quatre raisons :
- Le problème récent du md5 concerne si j'ai bien compris la possibilité théorique de trouver deux nombres ayant le même hash par une méthode meilleure que l'itération de toutes les possibilités.
Il s'agit d'une faille théorique, je ne crois pas avoir vu passer d'annonces pour quelque chose de pratique/utilisable.
- Le problème du sha1 est un problème à long terme, même avec la faille casser du sha1 n'est pas à la portée de tout un chacun. (c'es dit aussi dans la news). Outre la faille, il faut aussi mesurer son importance face aux systèmes de calculs actuels. Si tu prend 60.000 ans au lieu de 5 millions d'années ça ne va pas t'avancer beaucoup.
- Il s'agit d'une faille pour générer deux sources qui ont le même hash, *pas* pour générer une source à partir d'un hash. Les authentifications basées sur md5 ne risquent donc rien de ce coté là.
Bref, pas de quoi s'affoler pour l'instant pour l'alerte collision md5.
Et même pour les algos de signature signatures (qui sont effectivement concernées par la possibilité d'avoir deux sources d'un même hash), la possibilité d'avoir deux sources n'implique pas forcément un problème concrêt :
- rien n'indique qu'on peut trouver une seconde source avec une première source "réelle" qui veut dire quelque chose (si c'est juste deux flots de bits qu'on ne peut pas contrôler ça ne servira à personne)
- rien n'indique que même si on pouvait choisir une des sources, l'autre aurait une consistance réelle (que ça ressemble à un mail, un tar, un fichier gzip ... si c'est là aussi un flot binaire aléatoire sans aucun contrôle ça ne servira à personne).
- et même si on choisissait la première source, si on avait une seconde réelle, rien n'indique qu'on pourrait suffisament contrôler cette seconde source pour y insérer des choses utiles comme changer le sens d'un texte ou mettre une backdoor.
Bref, pas de quoi s'affoler non plus à la première alerte collision
Est-ce plus clair que dans la news ?
[^] # Re: et les distribs?
Posté par XHTML/CSS inside (site web personnel) . Évalué à 2.
[^] # Re: et les distribs?
Posté par Beretta_Vexee . Évalué à 3.
Ce qui est gênant c'est que visiblement la il a été prouvé qu'il existé une méthode plus rapide que la force brute pour trouver une collision sur une clé, bon après comme le rappel l'article il y a encore beaucoup d'incertitude sur la méthode ( est ce la clé ou le fichier source qui est utilisé pour calculer la collision ).
Conclusion le SHA-1 est un peut moins sur que ce a quoi l'on pourrait s'attendre, mais surment encore assez sur pour la plus part d'entre nous, et plus sur que le MD5.
[^] # Re: et les distribs?
Posté par Larry Cow . Évalué à 10.
Mensonge! La meilleure compression au monde est celle offerte par /dev/null (pour compresser) et /dev/random (pour décompresser). Bon, c'est vrai que c'est un peu une compression à perte, mais le ratio est quand même super intéressant :)
(je suis déjà dehors, je cours monter une startup)
[^] # Re: et les distribs?
Posté par Christophe Renard . Évalué à 1.
Quand un algo de hash produit des digest de 128bits, ca veut dire qu'il n'y a que 2^128 hashs possibles(meme si 2^128 est un grand nombre ) pour un nombre infini d'intrants possibles.
Du coup, on sait de façon certaine qu'il existe des collisions, mais les trouver est difficile avec une fonction raisonnablement efficace.
Pour la vérification de la non corruption d'un fichier c'est relativement anodin (car il y'a peut de chance qu'on ne puisse faire grand chose de fichier faisant collision avec mon tarball du kernel par exemple).
En revanche, si MD5 est serieusement attaquable (apparemment c'est le cas aussi), et qu'un tiers recupere mon /etc/shadow, il pourra trouver des mots de passe acceptables au login (pas forcement les originaux), reste a voir si leur taille/contenu seront acceptables comme mots de passe...
[^] # Re: et les distribs?
Posté par Bruno Bord . Évalué à 2.
Je me permettrais même d'employer une métaphore pour expliquer en quoi c'est évident, c'est d'ailleurs cette métaphore qui m'a fait comprendre. (merci les cours de soutien de math)
[jargon=off]
Prenons une population, par exemple celle d'une ville. Imaginons qu'elle ait une dizaine de milliers d'habitants.
Il est facilement démontrable que sur cette population, il y a au moins deux personnes qui ont le même jour anniversaire. Si l'habitant 1 est né le 1° janvier, l'habitant 2 le 2 janvier, etc. jusqu'au 365 qui est né le 31 décembre, le 366... peut-être qu'il est né un 29 février, mais le 367, c'est sûr qu'il est né le même jour qu'un des 366 précédents.
[jargon=On]
Comme le disait Christophe Renard ci-dessus, le nombre de possibilités offertes par l'algo de hachage est limité, alors que le nombre de "textes" entrants est potentiellement infini.
[^] # Re: et les distribs?
Posté par densmore . Évalué à 1.
[^] # Re: et les distribs?
Posté par jcs (site web personnel) . Évalué à 2.
Non, pas uniquement théorique : elle a été implémentée avec succès et des collisions ont été publiées à CRYPTO2004 (http://eprint.iacr.org/2004/199(...)). En revanche l'attaque contre SHA-1 est elle pour le moment complètement théorique.
[^] # Re: et les distribs?
Posté par Moule Atarte (site web personnel) . Évalué à 0.
oui et non.
exemple 1 : j'heberge un service nécessitant une identifiaction; à la création d'un compte j'écris en gros et en gras que voici le mot de passe généré automatiquement pour le nouveau compte, il est complexe, fort et mon client est le seul à le connaître; bref je fait tout pour l'encourager à conserver son mdp initial.
Cependant j'ai généré son mot de passe, à son insu, avec une moulinette qui sait faire deux sources qui entrent en collision lors du hash du mdp. Du coup je n'ai pas menti : je ne connais pas son mot de passe, cependant je peux me connecter au compte de mon client sans qu'il le sache. (bon si je suis root sur la machine en question, c'est vraiment se donner de la peine pour le plaisir, j'en conviens)
exemple 2 : j'héberge un site web anonyme de génération de mots de passe. je vise quelqu'un et j'ai les moyens humains et financiers pour atteindre ma cible, alors je monte une attaque MITM, je le pousse à générer un nouveau mot de passe avec ma moulinette (donc je dispose d'un deuxième mot de passe générant le même hash) et, puisque je suis l'homme du milieu, je sais sur quel service il a implanté son nouveau mot de passe ... (oui c'est tiré par les cheveux, mais si j'ai les moyens de casser du SHA-1 en 2^69 opérations, je peux aussi jouer à l'homme du milieu ;) )
[^] # Re: et les distribs?
Posté par Éric (site web personnel) . Évalué à 5.
De plus tu te bases sur le postulat que la collision est de taille courte (si elle est de 40 char elle ne te servira à rien pour une authentification par mot de passe.) et que le postulat qu'elle contient uniquement des caractères valides pour un mot de passe. Ces deux postulats ne sont pas anodins et sont certainement exagérés.
Exemple 2 : Même chose, si ta moulinette a les moyens de générer un second mot de passe en collision et de le stocker, elle avait déjà moyen de stocker le mot de passe réell sans collision. Tu ne gagnes donc rien là non plus. Et ... tu fais toujours les mêmes postulats qui sont probablement faux.
# Un peu de précision....
Posté par Olivier Faurax (site web personnel) . Évalué à -2.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.