SHA-1 aurait ete casse

Bonjour,

On Tue, 22 Feb 2005, Dominique Blas wrote:

Selon Bruce Schneier (que les cryptographes et le cryptanalystes
connaissent bien pour ses ouvrages) des chinois auraient trouvé une
méthode (forcément plus économique que la force brute, en l'occurrence
2048 fois plus économique) pour générer de manière certaine des conflits
dans SHA-1.

Faux. Pas de manière certaine, mais avec au moins 50% de chances d'obtenir
une collision. C'est le principe du paradoxe des anniversaires.

A quand le cassage de RIPE-160 ?

Pas tout de suite. RIPEMD-160 est différent de la suite MD/SHA. RIPEMD est
encore différent de RIPEMD-{128,160,...}.

--
Erwann ABALEA <erwann@abalea.com> - RSA PGP Key ID: 0x2D0EABD5
-----
JA> nous invitons chacun d'entre vous à découvrir notre site afin de
JA> vous faire une idée de notre raison d'être et de nos valeurs...
Et en plus, ils racolent! Allez donc attendre vos soucoupes ailleurs.
-+-GLM in:Guide du Neuneu d'Usenet- Neuneu bêlant bien identifié -+-

Dominique Blas wrote in message
<421b41c8$0$13406$626a14ce@news.free.fr>:

Bonjour,

Selon Bruce Schneier (que les cryptographes et le cryptanalystes
connaissent bien pour ses ouvrages) des chinois auraient trouvé une
méthode (forcément plus économique que la force brute, en l'occurrence
2048 fois plus économique) pour générer de manière certaine des conflits
dans SHA-1.

Comme indiqué par Erwann Abalea, ce n'est que probabiliste ; ceci dit, la
probabilité croît assez rapidement si on augmente un peu le temps de calcul.

Mais il n'y a pas que ça. D'une part, « SHA-1 cassé » veut dire qu'on sait
faire strictement mieux que la sécurité qu'on en attendait dans le cahier
des charges. Ici, si j'ai bien compris, on en attendait au début 160 bits de
sécurité (on me passera cet abus de langage), et on en est maintenant à 138.
Ça reste au delà de nos possibilités actuelles, même si l'échance s'est
rapprochée. D'ailleurs, on continue à faire assez souvent confiance à des
hash de 128 bits.

Enfin, il me semble, l'attaque est de peu de conséquence pour la plupart des
protocoles. En effet, il y a plusieurs choses exploits qu'on peut réaliser
sur un hash, que je classe grossièrement par ordre de gravité :

1. trouver une collision quelconque ;
2. trouver une collision avec une marge de manoeuvre sur le contenu ;
3. trouver un message de hash fixé à l'avance ;
4. trouver un message de hash fixé à l'avance avec un contenu utile.

L'attaque dont il est question, sauf erreur de ma part, ne fait que passer
dans la catégorie 1. Pour comparaison, MD5 est tombé il y a six mois dans la
catégorie 2. J'ai l'impression que dans la plupart des cas, il faut 4 pour
représenter un réel danger de sécurité, parfois 2 dans un scénario assez
tordu, et que 1 est presque anodin.

Pas de raison de paniquer donc, même s'il est bon de songer à utiliser autre
chose de plus solides pour les nouveaux développements.

[...]

Pas de raison de paniquer donc, même s'il est bon de songer à utiliser autre
chose de plus solides pour les nouveaux développements.

C'est bien là où je voulais en venir. La tentative chinoise, si elle est
reconnue vraiment différente, systématiquement, de la force brute, ne
fait que lancer un premier niveau d'alerte qui, à mon humble avis, nous
laisse encore 3 à 5 ans avant de connaître de vrais dangers.
On continue à utiliser MD5 de nos jours.

Plus généralement, si l'on conserve la méthodologie actuelle, basée sur
la décomposition en nombres premiers et si l'on suppose qu'il n'y aura
pas de révolution algorithmique permettant de factoriser bien plus
rapidement qu'aujourd'hui, alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

C'est à une fuite en avant perpétuelle que l'on se prépare ...
Pourquoi pas après tout.;-)

db

On 24 Feb 2005 10:27:00 GMT, Dominique Blas <db@internet.invalid>:

alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

Ne pourrait-on pas prévoir le coup un peu en avance et utiliser 4096
bits dans tous les nouveaux projets ?


--
;-)

Fabien LE LEZ wrote:

alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

Ne pourrait-on pas prévoir le coup un peu en avance et utiliser 4096
bits dans tous les nouveaux projets ?

Pour quoi faire?
Si maintenant le 128 bits[1] n'est pas envisgeable en temps raisonnable
et en supposant une augmentation de la puissance de calcul d'un facteur
2 par an passer à 256 te permet de tenir plus d'un siècle.

Maintenant je vois mal l'intérêt d'un wep 4096 bits si tu suis mon idée :)

Ensuite rien n'oblige à faire un md5 -par exemple- "simple" du document.
Faire un md5 du document en ajoutant ou on veut (pourvu que ça reste au
même endroit!) la longueur du document hashé par exemple doit, amha
(c'est une question que je compte poser un jour ou l'autre sur f.m.c)
compliquer très sérieusement la tache du gars qui doit trouver non
seulement un document "utile" mais qui en plus garde le même hash dans
lequel intervient un paramètre qui est fonction de la taille document.

Donc même si md5 semble quelque peu en fin de vie il ne faut pas jetter
le bébé avec l'eau du bain (en plus ça doit être interdit ça non? :) ).

Eric

[1] en supposant que seule l'attaque brute force par recherche
exhaustive soit possible.

--
L'invulnérable :
Je ne pense pas etre piratable, infectable par un trojen oui!
Vu sur fcs un jour de mars 2004.

OoO En cette soirée bien amorcée du jeudi 24 février 2005, vers 22:53,
Fabien LE LEZ <gramster@gramster.com> disait:

alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

Ne pourrait-on pas prévoir le coup un peu en avance et utiliser 4096
bits dans tous les nouveaux projets ?

A priori, on ne trouve jamais de méthode miracle. Que ce soit dans le
cas de MD5 ou de SHA1, on trouve simplement un affaiblissement,
suffisamment conséquent pour passer sous la barre des 80 bits.

Si on considère un hash sur 256 bits, il n'y a pas assez d'énergie
dans le système solaire pour effectuer tous les tests en prenant des
hypothèses extrêmement libérales. Prendre 4096 bits pour un algorithme
de hash n'apportera rien de plus, mais nécessitera beaucoup plus de
calculs. C'est la même raison de pourquoi on ne prend pas directement
un dérivé de AES à 4096 bits (en plus du fait qu'il faut l'adapter de
manière intelligente).

Si l'algo est tellement cassé qu'il nécessite une extension à 4096
bits, cette extension ne risque pas de faire long feu non plus et
mieux vaut en changer.
--
/*
* For moronic filesystems that do not allow holes in file.
* We may have to extend the file.
*/
2.4.0-test2 /usr/src/linux/fs/buffer.c

On Thu, 24 Feb 2005, Dominique Blas wrote:

[...]

Pas de raison de paniquer donc, même s'il est bon de songer à utiliser autre
chose de plus solides pour les nouveaux développements.

C'est bien là où je voulais en venir. La tentative chinoise, si elle est
reconnue vraiment différente, systématiquement, de la force brute, ne

Elle l'est, mais toujours probabiliste, et avec un coût non négligeable.

fait que lancer un premier niveau d'alerte qui, à mon humble avis, nous
laisse encore 3 à 5 ans avant de connaître de vrais dangers.

Oui. "il est temps de marcher vers la sortie, pas encore temps de courir".

On continue à utiliser MD5 de nos jours.

Alors que Dobbertin avait lancé la première alerte en 96. Mais MD5 utilisé
dans un HMAC reste sûr, tout comme il reste valable pour signer des
certificats (si certaines conditions sont remplies).

Plus généralement, si l'on conserve la méthodologie actuelle, basée sur
la décomposition en nombres premiers et si l'on suppose qu'il n'y aura

Oula.... Pas de nombres premiers ou de factorisation pour MD5/SHA1...
Qu'est-ce que ça vient faire là? DSA/DH n'utilisent pas non plus de
factorisation, les courbes elliptiques non plus, les algos symétriques non
plus.

--
Erwann ABALEA <erwann@abalea.com> - RSA PGP Key ID: 0x2D0EABD5
-----
Pour moi, que ce soit fr.rec.arts.musique.variete ou
fr.rect.arts.chansons, c négatif, parce que je considére pas
la musique comme un art,
-+- BenC in http://neuneu.mine.nu : Neuneu joue du pipo.

Si on considère un hash sur 256 bits, il n'y a pas assez d'énergie
dans le système solaire pour effectuer tous les tests en prenant des
hypothèses extrêmement libérales.

Est-ce que tu peux en dire un peu plus la dessus?

Je ne vois pas le lien entre traitement d'information et consommation
d'énergie.

--
Djoumé SALVETTI

On Fri, 25 Feb 2005, Eric Razny wrote:

Fabien LE LEZ wrote:

alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

Ne pourrait-on pas prévoir le coup un peu en avance et utiliser 4096
bits dans tous les nouveaux projets ?

Pour quoi faire?
Si maintenant le 128 bits[1] n'est pas envisgeable en temps raisonnable
et en supposant une augmentation de la puissance de calcul d'un facteur
2 par an passer à 256 te permet de tenir plus d'un siècle.

Maintenant je vois mal l'intérêt d'un wep 4096 bits si tu suis mon idée :)

Ensuite rien n'oblige à faire un md5 -par exemple- "simple" du document.
Faire un md5 du document en ajoutant ou on veut (pourvu que ça reste au
même endroit!) la longueur du document hashé par exemple doit, amha

Marche pas.

si md5(m1) = md5(m2), alors md5(m1 || data) = md5(m2 || data)

Si tu mets la taille de ton message au tout début (m1 et m2 font 1k
environ), ça va compliquer un peu, mais les chinois étant capable de
montrer des collisions en moins d'une heure en pratique, je pense que ça
ne leur prendra pas beaucoup plus de temps en ajoutant un truc au début
(qui ne fait que modifier l'état interne de la moulinette MD5). En gros, 1
heure + une édition de source + une recompilation. :)

--
Erwann ABALEA <erwann@abalea.com> - RSA PGP Key ID: 0x2D0EABD5
-----
(fufe) Ca deconne, domage... votre service est vraiment super! J'arrive
vraiment pas a envoyer ma candidature sur votre site: il me fait a
chaque fois error, pourquoi? Il y a t'il une limite de chrcter?
-+-JF - Guide du Neuneu d'Usenet - Souvent limité, jamais égalé -+-

On Thu, 24 Feb 2005, Fabien LE LEZ wrote:

On 24 Feb 2005 10:27:00 GMT, Dominique Blas <db@internet.invalid>:

alors, quel que soit le niveau un jour ou
l'autre il y aura danger. Après 128 bits ce sera 256, etc, etc.

Ne pourrait-on pas prévoir le coup un peu en avance et utiliser 4096
bits dans tous les nouveaux projets ?

Et utiliser des clés RSA de 8192 bits? Faut être fou. SHA-256, c'est déjà
prendre de l'avance.

Pour info, pour signer un document, on signe le hash de ce document. Si on
fait du RSA, il faut que la donnée signée soit plus petite que le module
de ta clé. Avec le padding PKCS#1, ce qui est réellement mouliné dans
l'opération m^d mod n de RSA, c'est:

00 || 01 || padding || 00 || data

* || désigne la concaténation
* le padding a une longueur égale à k-3-datalen, k étant la longueur du
module de la clé (1024 octets pour une clé RSA de 8192 bits), datalen
étant la longueur du bloc data, ce padding est constitué d'octets à
0xff
* data est une construction DER, de type DigestInfo, selon la définition
suivante:

DigestInfo ::= SEQUENCE {
digestAlgorithm DigestAlgorithmIdentifier,
digest Digest }

DigestAlgorithmIdentifier ::= AlgorithmIdentifier

Digest ::= OCTET STRING

la longueur de ce machin est de 35 octets environ pour du SHA1
(environ, parce que je ne me souviens plus exactement de la longueur de
l'OID sha1 exprimé en DER, j'ai pris 9 octets). Si on utilise un algo
de hash qui produit des empreintes de 4096 bits, cela fera une longueur
d'environ 531 octets, il faudra donc une clé RSA d'au moins 534 octets
de long, soient 4272 bits pour la signer.

Je ne parle pas ici du temps de génération d'une telle clé, du temps de
signature, etc...

openssl speed rsa4096 sur 4 machines différentes me donne comme résultat:
sign verify sign/s verify/s
UltraSparcII/300MHz:
rsa 4096 bits 2.4133s 0.0383s 0.4 26.1
PIII/450MHz:
rsa 4096 bits 0.6527s 0.0099s 1.5 101.2
PIII/800MHz:
rsa 4096 bits 0.3427s 0.0052s 2.9 191.5
Xeon/3GHz:
rsa 4096 bits 0.1683s 0.0026s 5.9 385.5

La génération prend au moins 15 secondes sur la machine la plus rapide, ma
Sun a mis un peu moins de 5 mn pour en générer une...

Inutile de tenter ça sur des cartes à puce.

Je viens de faire l'essai sur un token crypto (LunaSA de SafeNet, qui fait
du 1200 signatures/s en RSA1024), et il faut environ 6.5s par clé pour la
génération (mais c'est par définition aléatoire), et le machin peut signer
à environ 40 signatures par seconde, ce qui est très honorable.

--
Erwann ABALEA <erwann@abalea.com> - RSA PGP Key ID: 0x2D0EABD5
-----
Il y a un festnoz retransmis en realaudio. La transmission est, sauf erreur
assurée par oleane:impossible d'avoir image ou son...Que passa ????
Trop de bretons connectés en même temps ? Ou bien pb avec ci ???
-+-TS in : GNU - Ils ont plein de connexions, vive la bretagne -+-