SHA-1 & MD5 cassés Jan 2007?

According to Roland Le Franc <x-kane@hotmail.com>:

Suite à cet article http://en.epochtimes.com/news/7-1-11/50336.html, qui
annonce qu'une équipe chinoise a maintenant cassé SHA1

Ce n'est pas une nouveauté ; c'est un résultat d'il y a environ deux
ans. En l'occurrence, il s'agit d'une attaque qui devrait pouvoir
calculer une collision sur SHA-1 en 2^63 opérations, c'est-à-dire
moins que le minimum théorique pour une "bonne" fonction de hachage (à
savoir 2^80 opérations pour une fonction qui a une sortie sur 160 bits,
comme SHA-1). Académiquement parlant, SHA-1 est "cassée" puisqu'elle
est d'une sécurité sous-optimale. Notons bien que 2^63, ça reste
beaucoup : c'est atteignable en quelques années de calculs sur quelques
dizaines de milliers de machines (l'ordre de grandeur est environ 100000
machines-années, en comptant des PC modernes, qui offrent le meilleur
rapport puissance-prix dans leur domaine), mais l'attaque sur SHA-1 n'a
pas été, à ma connaissance, implémentée. Autrement dit, on a une attaque
pour pourrait produire une collision, mais aucune collision n'a été
actuellement exhibée.

Par comparaison, l'attaque de 2004 sur MD5 produisait une collision en
quelques heures sur une unique machine.

je me demande dans quelle mesure ces hash sont "cassés"
- facilité de construire des collisions quelconques?
- ou possibilité de construire une collision sur un hash donné?

Ce deuxième cas ne s'appelle pas "collision" mais "attaque en seconde
préimage". Soyons précis dans la terminologie.

Si h() est une fonction de hachage, alors il y a trois "niveaux"
d'attaque :
-- attaque en collision : produire deux messages m et m', distincts,
tels que h(m) = h(m')
-- attaque en seconde pré-image : étant donné un message m, produire
un message m' distinct de m tel que h(m) = h(m')
-- attaque en pré-image : étant donné une sortie x, produire un
message m tel que h(m) = x

En d'autres mots, l'attaque en pré-image est une inversion de la
fonction, où on impose la cible ; l'attaque en seconde pré-image est
une variation de cette attaque où on donne à l'attaquant un "bonus",
c'est-à-dire une première solution, et où on lui demande d'en produire
une seconde.


Pour autant qu'on sache, SHA-1, mais aussi MD5 et même MD4 sont
résistants aux secondes pré-images. Ça ne veut pas dire qu'on ait
confiance, mais que pour le moment aucune attaque, même théorique, n'a
pu faire mieux que la bête recherche exhaustive, d'un coût en 2^159
pour SHA-1, 2^127 pour MD5 et MD4.

La bonne nouvelle de l'affaire, c'est que l'immense majorité des usages
courants de fonctions de hachage repose sur la résistance aux secondes
pré-images, et se moque complètement de la facilité de produire des
collisions. Par exemple, quand on fait des requêtes en HTTPS, il y
a du SSL (ou TLS) qui se met en route, et les données échangées ont
un contrôle d'intégrité (pour détecter les altérations) fondé sur,
classiquement, MD5 ou SHA-1. Ces usages ne nécessitent que la résistance
aux secondes pré-images, et aucune des attaques en collision publiées ne
permet d'entamer la sécurité de SSL.

Il y a quelques usages (liés aux fonctions de signature dans des
contextes bien précis) où les collisions peuvent être pénible. Par
ailleurs, l'existence de producteurs de collisions efficaces montre
que ces fonctions de hachage ne sont pas aussi bien calibrées qu'elles
devraient être. Pour "restaurer la confiance", comme on dit, il faut
donc faire de la recherche sur le sujet et trouver de nouvelles
fonctions plus solides. Cette recherche est en cours actuellement ; les
fonctions de hachage sont très à la mode.


--Thomas Pornin

Dans l'article <45b85e06$0$27492$426a34cc@news.free.fr>
Thomas Pornin <pornin@nerim.net> fait un excellent exposé.

J'y ajoute mes grains de sel:

Soulignons qu'à ce jour on ne connais pas concrètement deux
messages qui ont le même SHA-1; c'est un challenge à relever.

Quand on fait des requêtes en HTTPS, il y a du SSL (ou TLS)
qui se met en route, et les données échangées ont un contrôle
d'intégrité (pour détecter les altérations) fondé sur,
classiquement, MD5 ou SHA-1. Ces usages ne nécessitent que la
résistance aux secondes pré-images, et aucune des attaques en
collision publiées ne permet d'entamer la sécurité de SSL.

Pas entièrement d'accord, et je vais donner un contre-exemple.


Quand on fait des requêtes en HTTPS, un des éléments de la chaîne
de confiance est le certificat du serveur, qui est signé par une
autorité de confiance, dont le certificat maître est dans liste
de confiance du poste client.
Mon attaque porte sur le certificat du serveur et son precessus
d'obtention auprès de l'autorité de confiance, et vise à obtenir
un certificat valide et la clé privée correspondant à la clé publique
indiquée dans le certificat, apparaissant appartenir à la Banque X
titulaire du domaine banquex.com, alors qu'aucune autorité de
confiance n'estsensée émettre un certificat faisant référence
à la Banque X et à son domaine banquex.com sans s'être assurée
que la Banque X est titulaire du domaine banquex.com, et peut
faire usage de la clé privée dont la clé publique est dans le
certificat.

L'attaque suppose qu'une autorité de confiance émet des certificats
utilisant MD5 et RSA, et le fait au moyen d'un logiciel qui n'insère
rien d'imprévisible en tête de la requête de certificat que l'on lui
demande de signer. A ma dernière relecture, OpenSSL répond à ces
conditions.
On peut alors construire une requête de certificat telle qu'elle
apparaisse être pour la SARL Y titulaire de sarly.com, société et
domaine que contrôle l'attquant, et donc requête que l'autorité
honorera (moyennant finance probablement); mais telle que le
certificat obtenu sera transformable en un certificat utilisable
pour la banque X titulaire de banquex.com.
Pour ce faire, on utilise le champ module public pour rétablir
des hashs identiques malgré des contenus distincts dans les
champs désignant le titulaire et son doamin, et avoir deux modules
publics dont la factorisation est possible, de sorte que les deux
clés secrètes correspondantes peuvent être trouvées, avant de
soumettre celle des deux requêtes de certificat qui est acceptable
par l'autorité.

L'attaque demande environ 2^65 rounds MD5 et des ressources mémoire
très modestes, elle est concevable avec un PC **et** une batterie
d'accélérateurs de MD5 avec hardware dédié. Mais:
- l'attaque de MD5 par Xiaoyun Wang, Dengguo Feng, Xuejia Lai
et Hongbo Yu ne s'applique pas, car elle ne permet pas assez
de liberté dans les messages en collision; que je sache, il
faut utiliser la force brute et des techniques (classiques)
de recherche de cycle pour limiter la mémoire
- l'attaque ne permet en aucun cas de transformer un certificat
déjà émis; il faut demander à l'autorité un nouveau certificat,
et être capable de prévoir à l'avance quel numéro de série
l'autorité lui attribuera
- il semble que les autorités commerciales qui émettent encore des
certificats avec hash MD5 (prisés car extrêmement compatibles)
prennent maintenant la précaution de "randomiser" le numéro de
série, qui est en tête, ce qui bloque l'attaque; les mauvaises
anciennes pratiques (facilement vérifiables sur les certificats
déjà en circulation) ne sont donc plus un danger, et ces anciens
certificats utilisables sans grande crainte.

Bref c'est à un cheveu d'être une attaque dangereuse, mais ce n'est
en fait pas praticable que je sache.


Quoi qu'il en soit, cela montre que dans le cas des certificats SSL,
il faut une fonction de hashage résistant aux collisions, ou/et
modifier la spécification pour prescire la randomization par
l'autorité de certification d'un champ en tête du certificat,
tel que le numéro de série.


Francois Grieu

According to Francois Grieu <fgrieu@gmail.com>:

Pas entièrement d'accord, et je vais donner un contre-exemple.

Certes, certes. Je parlais du contrôle d'intégrité sur les données
une fois le handshake effectué ; c'est du HMAC en TLS, et quelque
chose de quasiment identique en SSL. Les certificats sont une
autre affaire.

Ceci étant :

L'attaque demande environ 2^65 rounds MD5

Beaucoup moins que ça, en fait. Ce 2^65 est le coût qu'on aurait si
MD5 était résistante aux collisions ; c'est le coût théorique pour une
fonction de hachage "parfaite" offrant 128 bits en sortie. Mais MD5
n'est pas une telle fonction, et les attaques de Wang sont détournables
pour faire deux certificats distincts ayant la même signature en RSA +
MD5.

Et ça a été fait. Cf :
http://www.win.tue.nl/~bdeweger/CollidingCertificates/

(et aussi le papier 2005/067 sur ePrint)

- il semble que les autorités commerciales qui émettent encore des
certificats avec hash MD5 (prisés car extrêmement compatibles)
prennent maintenant la précaution de "randomiser" le numéro de
série, qui est en tête, ce qui bloque l'attaque; les mauvaises
anciennes pratiques (facilement vérifiables sur les certificats
déjà en circulation) ne sont donc plus un danger, et ces anciens
certificats utilisables sans grande crainte.

L'attaque fonctionne si l'attaquant peut induire une variation sur
son nom et rattraper le coup plus loin, par exemple sur la clé
publique RSA. Un certificat X.509 contient les champs suivants,
dans cet ordre :

version
Version du certificat, normalement 0 (version 1) ou 2 (version 3),
prédictible par l'attaquant.

serialNumber
Numéro de série, choisi par la CA. Pour une même CA, les numéros de
série ne doivent pas se répéter. OpenSSL garde un compteur dans un
fichier, augmenté de 1 à chaque émission. Comme le fait remarquer
Peter Guttman, une telle stratégie permet à un concurrent d'acheter
un certificat et de savoir ainsi précisément combien de certificats
ont été émis, et, partant, quelle est la santé financière de la CA.
De plus, des numéros de série "courts" ne font pas "sérieux". Pour
ces raisons, les CA commerciales choisissent des numéros de série
longs ; une possibilité est de les calibrer sur l'heure courante,
mais ce n'est pas robuste face aux errances de l'horloge interne.
Aussi, la plupart des CA choisissent un numéro aléatoire.

signature
Type d'algorithme de signature utilisé. Hautement prédictible par
l'attaquant.

issuer
Nom de la CA. Prédictible.

validity
Période de validité du certificat ; prédictible avec une certaine
précision par l'attaquant. Certaines CA font débuter la validité
à la seconde près de traitement, ce qui suppose alors que
l'attaquant envoie sa requête dans la seconde précise où la date
est celle sur laquelle il a travaillé. D'autres CA émettent le
certificat à une date ronde conventionnelle, genre minuit. En
bref, c'est prédictible.

subject
Le(s) nom(s) de l'attaquant. L'attaquant peut les choisir, dans une
certaine limite, mais les CA contraignent les champs possibles. Du
coup, l'attaquant a ici deux noms, prédictibles mais peu maniables ;
la différence entre les deux noms induit une variabilité qui doit
être compensée plus loin.

subjectPublicKeyInfo
La clé publique de l'attaquant. Dans le cas cité plus haut,
les attaquants (Lenstra et de Weger) ont travaillé là dessus
pour obtenir leur collision. Le plus difficile était d'obtenir
la collision sur MD5 tout en connaissant les deux clés privées
associées aux deux clés publiques : la clé "honnête" (celle
associée à la vraie identité de l'attaquant) sert à signer la
requête de certificat, et la CA vérifie cette signature ; la clé
"malhonnête" (celle associée à la fausse identité) doit être connue
de l'attaquant pour qu'il puisse faire quoi que ce soit de son
attaque.

issuerUniqueID
Identifiant unique pour la CA. C'est optionnel et usuellement absent ;
la RFC 3280 (profil PKIX pour X.509, le plus utilisé) recommande de ne
pas en utiliser. Donc prédictible.

subjectUniqueID
Identifiant unique pour le propriétaire du certificat. Même statut
que l'issuerUniqueID.

extensions
Des extensions diverses, dont le contenu est en général prédictible
par l'attaquant. Certaines extensions peuvent être sous son
contrôle, par exemple la subjectAltName.


Tout ce verbiage est là pour insister sur les points suivants :

-- L'attaque est une "correction" des modifications induites par les
différences sur les noms (le vrai et l'usurpé). Ces modifications
peuvent être prises en compte dans le choix de la clé publique ; c'est
comme ça que l'attaque a été montée dans la pratique. Mais on pourrait
aussi envisager de faire les modifications dans les extensions du
certificat, par exemple la subjectAltName.

-- L'attaque ne fonctionne que si l'ensemble des différences est dans un
environnement contrôlé par l'attaquant. Ça veut dire que si on considère
la zone de différences entre les deux certificats, alors le contenu de
cette zone et tout ce qui la précède doit être prédit par l'attaquant.
C'est cela qui rend le numéro de série "spécial" : il est placé avant
la fin de la zone (de fait, le "subject" est situé après), donc il doit
être prédit par l'attaquant. C'est également le seul champ qui peut être
utilisé comme contre-attaque dans le cas général.

-- Le numéro de série est imprédictible dans les CA comerciales pour
des raisons qui ne sont pas liées à la sécurité. Dans le cas présent,
c'est juste un "heureux hasard".

Quoi qu'il en soit, cela montre que dans le cas des certificats SSL,
il faut une fonction de hashage résistant aux collisions

En fait c'est dans le cas des certificats tout court. Ça n'a rien de
spécifique à SSL. Ça marcherait aussi pour, par exemple, des certificats
de chiffrement de mail en S/MIME.


--Thomas Pornin

Dans l'article <45b89967$0$30497$426a74cc@news.free.fr>,
Thomas Pornin <pornin@nerim.net> écrit:

Ceci étant :

L'attaque demande environ 2^65 rounds MD5

Beaucoup moins que ça, en fait. Ce 2^65 est le coût qu'on aurait si
MD5 était résistante aux collisions ; c'est le coût théorique pour une
fonction de hachage "parfaite" offrant 128 bits en sortie. Mais MD5
n'est pas une telle fonction, et les attaques de Wang sont détournables
pour faire deux certificats distincts ayant la même signature en RSA +
MD5.

Et ça a été fait. Cf :
http://www.win.tue.nl/~bdeweger/CollidingCertificates/

Ce papier (que j'avais lu) présente deux certificats en collision,
mais ces deux certificats font référence au même titulaire.
Il me semble donc impossible d'en tirer parti pour tromper un
utilisateur final. Je range cela au rayon attaque sans grand
danger pratique.

Au contraire, l'attaque que je décris produit deux certificats en
collision avec des valeurs distinctes choisies arbitrairement
dans le champ subject; avec cette contrainte, l'attaque de
Xiaoyun Wang et al ne fonctionne plus, et je ne crois pas que l'on
puisse l'étendre; mais la force brute fonctionne encore, avec un
coût seulement doublé.

C'est une attaque tout ce qu'il y a de plus concrète et dévastatrice.
Noter que la Banque X a beau choisir une excellente autorité qui
n'émet que des certicicats en béton, ça ne gène en rien l'attaquant:
il a besoin d'une seule (autre) autorité de confiance qui utilise
OpenSSL, ou plus généralement qui n'est PAS plus prudente que ne
l'exige la spécification X.509 en "randomizant" le serialNumber.

Mais je ne vois PAS de risque d'apocalypse internet imminente:
- une recherche rapide faite il y a un an n'a pas détecté
d'autorité vulnérable dans la liste de celles dans le client
web typique
- 2^65 blocks MD5, ce n'est pas rien, et pour un moment
- il me semble en fait plus facile d'obtenir un "vrai faux"
certificat auprès d'une autorité, complice ou abusée
- un faux certificat, ce n'est ni suffisant, ni nécessaire
pour monter une attaque réelle; je ne dit pas que ça ne sert
à rien, mais ce n'est AMHA pas le maillon faible, qui est plutôt
l'intégrité du poste utilisateur.


François Grieu

According to Francois Grieu <fgrieu@gmail.com>:

Ce papier (que j'avais lu) présente deux certificats en collision,
mais ces deux certificats font référence au même titulaire.

Ah oui, en effet. J'étais persuadé d'avoir vu deux certificats en
collision avec des noms de sujet distincts (car nous sommes d'accord,
c'est bien ça qui est utile). Ça n'a rien d'invraisemblable, puisque
le nom du sujet est, dans un certificat classique, immédiatement suivi
de la clé publique (il y a juste l'OID rsaEncryption entre les deux).
L'attaque de Wang laisse de la liberté dans le choix des bits variants,
et c'est un sujet de recherche active, donc je ne trouve pas évident
a priori que le principe ne puisse pas marcher.


--Thomas Pornin

Thomas Pornin <pornin@nerim.net> écrit:

According to Francois Grieu <fgrieu@gmail.com>:

Ce papier (que j'avais lu) présente deux certificats en collision,
mais ces deux certificats font référence au même titulaire.

Ah oui, en effet. J'étais persuadé d'avoir vu deux certificats en
collision avec des noms de sujet distincts (car nous sommes d'accord,
c'est bien ça qui est utile). Ça n'a rien d'invraisemblable, puisque
le nom du sujet est, dans un certificat classique, immédiatement suivi
de la clé publique (il y a juste l'OID rsaEncryption entre les deux).
L'attaque de Wang laisse de la liberté dans le choix des bits variants,
et c'est un sujet de recherche active, donc je ne trouve pas évident
a priori que le principe ne puisse pas marcher.

Je n'ai je crois pas dit que l'attaque Wang et al ne peut absolument
pas s'étendre à des certificats SSL avec "subject" distincts; j'ai dit
que contrairement à la force brute, elle ne permet pas de choisir
le champ "subject" en toute liberté dans les deux certificats, ce
qui rend une attaque réelle très difficile: il ne suffit pas que
les certificats diffèrent dans leurs champs "subject" respectifs;
il faut en outre que l'un soit admissible par le CA, et l'autre par
le récipiendaire abusé, qui tout de même doit bien le vérifier,
ce champ "subject", sinon par besoin de collision du tout.

J'avais un peu regardé le risque d'une attaque réelle au moment de
la sortie de l'attaque de Wang et al, puis de l'article de
Lenstra/Wang/Weger.
Il y a des tas de détails pénibles: alignement défavorable pour
l'attque de la frontière de bloc avec le champ "subject" dans
les certificats X509 réels, et attaque Wang qui a la fâcheuse
tendance à concerner l'altération de bits de poids fort, qu'il
est difficile de transformer en des noms de société/domaine un
tant soit peu crédibles.

Méta argument: les termes de l'article de Lenstra/Wang/Weger sont
si finement dosés quand ils exposent la portée de leur attaque,
qu'il est évident qu'ils savent qu'elle a le défaut de ne pas
concerner une modification du champ "subject", dont la portée
serait bien plus grande; comme ils n'évoquent même pas cette
perspective, je me dit qu'il n'ont pas plus de piste que moi.


Francois Grieu

"Thomas Pornin" <pornin@nerim.net> a écrit dans le message de news:
45b89967$0$30497$426a74cc@news.free.fr...

-- Le numéro de série est imprédictible dans les CA comerciales pour
des raisons qui ne sont pas liées à la sécurité. Dans le cas présent,
c'est juste un "heureux hasard".

Mais est-il vraiment imprédictible ? Une complicité interne ne pourrait-elle
pas aider à le prévoir ?

Parce que dans ce cas c'est quand même une faiblesse de sécurité : on ne
pourra prouver aucune faute de la part du CA, puisque le CA pourra exhiber
le vrai certificat accordé, et prouver que la procédure normale de
vérification a été respectée. Et pourtant il existera un faux certificat.

JL.