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...
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.
voir par exemple http://fr.wikipedia.org/wiki/Nombre_RSA pour les records "homologués" actuels, quelques temps de calcul sont sur la page anglaise http://en.wikipedia.org/wiki/RSA_number
En gros :
330 bits ça se fait sur un PC de bureau en une dizaine d'heures.
463 ça a été fait en 2000 MIPS-year (c'est-à-dire 2000 ans de calcul à raison d'un million d'instruction par seconde, mais un peu comme les FLOPS ça dépend et des architectures et de la nature du code, c'est une estimation en vitesse de pointe. Doit-on considérer qu'un processeur à quelques GHz actuel fait 1000 MIPS ou pas, telle est la question).
512 en plus ou moins 8000 MIPS-year
le dernier record de type RSA fait 576 bits.
Pour des nombres moins difficiles que des nombres RSA, le dernier record est la factorisation de 2^1039 -1 (soit 1038 bits) par Aoki, Franke, Kleinjung, Lenstra et Osvik en (ordre de grandeur, différentes phases remises à l'échelle par les auteurs qui ont utilisé divers PC et clusters) :
95 années de Pentium-D à 3 GHz (plus ou moins équivalent à 100 années de Athlon64/opteron 2.2GHz)
plus 69 heures sur 113 Pentium-D
plus 59 jours sur 110 Pentium-D (ou de façon équivalente 162 jours sur 32 Core2Duo) (architecture : cluster de 110 Pentium-D et 36 Core2Duo, Ethernet Gbit)
voir http://www.loria.fr/~zimmerma/records/21039- pour les détails.
En gros, ça fait plus ou moins 110 ans de Pentium-D.
Pour un nombre sans structure (pour lequel des algorithmes spécifique, type pollard rho ne marchent pas), l'algorithme de factorisation le meilleur connu fonctionne avec une complexité heuristique sous-exponentielle (en gros une certaine puissance de la racine cubique du nombre à factoriser, multiplié par le nombre de chiffres binaires à la puissance 2/3). http://en.wikipedia.org/wiki/General_number_field_sieve
On comprend que leur capacité de calcul soit une donnée ultra-sensible pour eux : elle permet d'avoir une meilleure estimation de leur facilité à décrypter des messages. Ceci donne une meilleure idée des tailles de clefs à choisir pour s'assurer de la confidentialité des messages.
Pour la cryptanalyse à base de hardware dédié, il y a eu pas mal de projets de recherche, qui n'ont en majorité pas abouti à une réalisation pratique faute de crédits, nul doutes qu'il n'ont pas été perdus pour tout le monde :-)
voir par exemple http://people.csail.mit.edu/tromer/cryptodev/ pour une liste. Ils sont majoritairement destinés à être utilisés dans les algorithmes de factorisation (problème difficile, à la base de RSA).
Et quid des performances de ces petites bébêtes en calcul entier ?
Y a-t-il un simple coefficient pour passer de l'un à l'autre, peut-on supposer que c'est sensiblement la même chose, ou bien peut-on directement utiliser les indications de fréquences ?
est-ce totalement inintéressant ? (je pensais aux maths pures (théorie des groupes, algèbre polynômiale) et à l'informatique fondamentale).
Merci pour ce post très détaillé, notamment "considérer chaque classe dérivée comme une extension de la classe précédente". C'est la tendance à raisonner parfois comme "B est un A"... Notamment en mathématiques où les objets ayant plus de propriétés (corps par rapport à anneau) sont en fait ceux dont les possibilités sont les plus réduites.
(et juste au sujet des déclarations, c'était à titre d'exemple, j'ai appris à séparer les headers assez vite ;-) )
Les virtual sont en effet plus logiques comme ça. Mais malheureusement ça ne marche pas il ne réussit toujours pas à résoudre property1.
En fait c'est logique, même si cette méthode est déclarée virtuelle et donc redéfinissable dans B, cela n'implique pas qu'elle doive nécessairement être redéfinie vu qu'elle n'est pas virtuelle pure.
Je pense donc modifier le diagramme d'héritage pour éviter le diamant en question, auriez-vous des conseils pour l'exemple que je donnais à la fin ?
merci beaucoup pour la réponse, effectivement le dossier est très clair et précis, c'est idéal pour mettre en place gpg !!
J'aurais néanmoins voulu en savoir un peu plus sur les fonctions cryptographiques "de base" utilisées, et apparemment définies par défaut (je pense aux fonctions de hachage notamment)..
[^] # Re: Pas critique
Posté par apterium . En réponse à la dépêche Nouvelles attaques sur SHA-1 : Debian pourrait migrer vers SHA-2. Évalué à 10.
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...
[^] # Re: "Aisé"?
Posté par apterium . En réponse à la dépêche Nouvelles attaques sur SHA-1 : Debian pourrait migrer vers SHA-2. Évalué à 3.
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: FLOPS ?
Posté par apterium . En réponse à la dépêche Un top 500 sous le signe du pétaflops. Évalué à 7.
En gros :
330 bits ça se fait sur un PC de bureau en une dizaine d'heures.
463 ça a été fait en 2000 MIPS-year (c'est-à-dire 2000 ans de calcul à raison d'un million d'instruction par seconde, mais un peu comme les FLOPS ça dépend et des architectures et de la nature du code, c'est une estimation en vitesse de pointe. Doit-on considérer qu'un processeur à quelques GHz actuel fait 1000 MIPS ou pas, telle est la question).
512 en plus ou moins 8000 MIPS-year
le dernier record de type RSA fait 576 bits.
Pour des nombres moins difficiles que des nombres RSA, le dernier record est la factorisation de 2^1039 -1 (soit 1038 bits) par Aoki, Franke, Kleinjung, Lenstra et Osvik en (ordre de grandeur, différentes phases remises à l'échelle par les auteurs qui ont utilisé divers PC et clusters) :
95 années de Pentium-D à 3 GHz (plus ou moins équivalent à 100 années de Athlon64/opteron 2.2GHz)
plus 69 heures sur 113 Pentium-D
plus 59 jours sur 110 Pentium-D (ou de façon équivalente 162 jours sur 32 Core2Duo) (architecture : cluster de 110 Pentium-D et 36 Core2Duo, Ethernet Gbit)
voir http://www.loria.fr/~zimmerma/records/21039- pour les détails.
En gros, ça fait plus ou moins 110 ans de Pentium-D.
Pour un nombre sans structure (pour lequel des algorithmes spécifique, type pollard rho ne marchent pas), l'algorithme de factorisation le meilleur connu fonctionne avec une complexité heuristique sous-exponentielle (en gros une certaine puissance de la racine cubique du nombre à factoriser, multiplié par le nombre de chiffres binaires à la puissance 2/3). http://en.wikipedia.org/wiki/General_number_field_sieve
[^] # Re: Et la NSA ?
Posté par apterium . En réponse à la dépêche Un top 500 sous le signe du pétaflops. Évalué à 2.
Pour la cryptanalyse à base de hardware dédié, il y a eu pas mal de projets de recherche, qui n'ont en majorité pas abouti à une réalisation pratique faute de crédits, nul doutes qu'il n'ont pas été perdus pour tout le monde :-)
voir par exemple http://people.csail.mit.edu/tromer/cryptodev/ pour une liste. Ils sont majoritairement destinés à être utilisés dans les algorithmes de factorisation (problème difficile, à la base de RSA).
# FLOPS ?
Posté par apterium . En réponse à la dépêche Un top 500 sous le signe du pétaflops. Évalué à 2.
Y a-t-il un simple coefficient pour passer de l'un à l'autre, peut-on supposer que c'est sensiblement la même chose, ou bien peut-on directement utiliser les indications de fréquences ?
est-ce totalement inintéressant ? (je pensais aux maths pures (théorie des groupes, algèbre polynômiale) et à l'informatique fondamentale).
[^] # Re: Tes "virtual" sont mals placés
Posté par apterium . En réponse au message Autour de l'héritage multiple et des méthodes virtuelles.. Évalué à 2.
(et juste au sujet des déclarations, c'était à titre d'exemple, j'ai appris à séparer les headers assez vite ;-) )
[^] # Re: Tes "virtual" sont mals placés
Posté par apterium . En réponse au message Autour de l'héritage multiple et des méthodes virtuelles.. Évalué à 1.
Les virtual sont en effet plus logiques comme ça. Mais malheureusement ça ne marche pas il ne réussit toujours pas à résoudre property1.
En fait c'est logique, même si cette méthode est déclarée virtuelle et donc redéfinissable dans B, cela n'implique pas qu'elle doive nécessairement être redéfinie vu qu'elle n'est pas virtuelle pure.
Je pense donc modifier le diagramme d'héritage pour éviter le diamant en question, auriez-vous des conseils pour l'exemple que je donnais à la fin ?
[^] # Re: Sur Linuxfr
Posté par apterium . En réponse au message Aide configuration de gpg.... Évalué à 1.
merci beaucoup pour la réponse, effectivement le dossier est très clair et précis, c'est idéal pour mettre en place gpg !!
J'aurais néanmoins voulu en savoir un peu plus sur les fonctions cryptographiques "de base" utilisées, et apparemment définies par défaut (je pense aux fonctions de hachage notamment)..
Bref je vais me pencher dessus un peu plus ;-)