Ah, MD5. Dans les années 90, c’était le chouchou de tout le monde. Rapide, compact, facile à implémenter, et surtout présenté comme « incassable ». Mais comme tout ado rebelle, il a vite montré ses failles. Aujourd’hui, l’utiliser pour la sécurité, c’est comme confier ton mot de passe Wi-Fi au premier stagiaire qui passe : une très mauvaise idée.
📜 Un peu d’histoire : la gloire passée de MD5
MD5 (Message Digest 5) a été conçu en 1992 par Ronald Rivest (le « R » de RSA).
L’idée : produire une empreinte 128 bits d’un message, suffisamment unique pour garantir :
- Intégrité : toute modification du message change le hash.
- Unicité : deux messages différents ne doivent pas donner la même empreinte.
Et à l’époque, 128 bits, ça semblait largement suffisant. Après tout, ça fait 2^{128} \approx 3,4 \times 10^{38} possibilités. Spoiler : ça n’a pas tenu bien longtemps.
🎁 Le paradoxe des anniversaires : quand 23 personnes suffisent
Le cœur du problème se cache dans un paradoxe mathématique aussi célèbre qu’élégant.
👉 Question : combien de personnes faut-il dans une salle pour qu’il y ait 50 % de chances que deux aient le même anniversaire ?
Réponse surprenante : 23 personnes.
🔬 Démonstration mathématique
On note :
- n : le nombre de jours possibles (365 pour un calendrier).
- k : le nombre de personnes.
La probabilité que tous les anniversaires soient distincts est :
P(\text{pas de collision}) = \prod_{i=0}^{k-1} \frac{n - i}{n}Donc la probabilité qu’il y ait au moins une collision est :
P(\text{collision}) = 1 - \prod_{i=0}^{k-1} \frac{n - i}{n}En posant n = 365, on trouve que :
P(\text{collision}) \approx 0,5 quand k \approx 23.
🔑 Application aux fonctions de hachage
Maintenant, appliquons ça aux empreintes MD5 :
- MD5 → 128 bits
- Nombre total de hashs possibles : 2^{128}
Le paradoxe des anniversaires nous dit que le nombre d’essais nécessaires pour obtenir une collision probable à 50 % est :
k \approx 1,177 \times \sqrt{2^{128}} = 1,177 \times 2^{64}Soit environ 2^{64} essais → totalement impossible dans les années 90… mais avec les clusters GPU d’aujourd’hui, c’est faisable.
🧩 Mais ce n’est pas tout : les attaques différentielles
Le vrai coup de grâce ne vient pas seulement du paradoxe. En 2004, la chercheuse chinoise Wang Xiaoyun a publié une méthode pour casser MD5 en moins d’une heure sur un PC classique. Pas besoin de faire 2^{64} essais, juste quelques millions suffisent.
Les chercheurs ont exploité la structure interne en rondes de MD5 (64 transformations Feistel-like).
En construisant des différentiels soigneusement choisis, ils ont pu générer deux messages différents avec le même hash :
🚨 Des collisions dans le monde réel
MD5 est mort théoriquement, mais il a continué à être utilisé (mauvaise habitude). Résultat :
- 2008 : une équipe génère un faux certificat SSL signé avec MD5. Résultat : un navigateur acceptait un certificat pirate comme légitime.
- 2012 : le malware Flame utilisait une attaque sur MD5 pour se faire passer pour une mise à jour Microsoft.
- 2017 : Google publie SHAttered, une collision sur SHA-1… mais le principe avait déjà été validé sur MD5 bien avant.
Bref : utiliser MD5, c’est comme laisser ta porte ouverte avec un panneau « ne pas entrer ».
📦 Résumé pédagogique
✅ Ce qu’il faut retenir
- MD5 produit des empreintes de 128 bits.
- Le paradoxe des anniversaires réduit la sécurité à 2^{64} opérations pour une collision.
- Les attaques différentielles rendent MD5 encore plus faible.
- Dans la vraie vie, MD5 a déjà été exploité dans des attaques critiques.
❌ Ce qu’il ne faut pas faire
- Ne jamais utiliser MD5 pour la sécurité (mots de passe, certificats, signatures).
- Ne pas se dire « c’est rapide, c’est pratique » → la sécurité, ce n’est pas un sprint.
⚰️ Conclusion sarcastique : MD5, le zombie de la crypto
MD5 est officiellement enterré depuis plus de 20 ans. Pourtant, on le croise encore dans certains logiciels, dans des bases de données poussiéreuses, ou pire, pour « sécuriser » des mots de passe. Autant dire que c’est comme utiliser un cadenas en plastique pour protéger une banque.
La leçon ? La cryptographie vieillit mal. Si tu veux faire du sérieux : SHA-256, SHA-3, BLAKE2, Argon2… mais surtout pas MD5.
🧪 Exercice — MD5 & paradoxe des anniversaires (démonstration chiffrée)
🎯 Objectif
Montrer mathématiquement que pour une empreinte de n bits (ex. MD5 : n=128), le nombre d’essais pour obtenir une collision avec probabilité p est de l’ordre de \Theta(2^{n/2}) et calculer précisément la constante.
✍️ Partie A — Démonstration générale (papier-crayon)
A1) Probabilité “zéro collision”
On hache k messages indépendants, uniformément sur N=2^n valeurs.
Montrer que la probabilité qu’il n’y ait aucune collision est :
Astuce : utiliser \ln(1-x)\approx -x-\frac{x^2}{2}-\dots et le fait que \sum_{i=0}^{k-1} i = \frac{k(k-1)}{2}.
En négligeant les termes d’ordre supérieur lorsque k \ll \sqrt{N}, on obtient l’approximation classique :
A2) Probabilité de collision
La probabilité d’avoir au moins une collision est :
P_{\text{coll}} ;=; 1 - P_0 ;\approx; 1 - \exp!\left(-\frac{k(k-1)}{2N}\right).A3) Inversion : nombre d’essais pour une cible p
Poser P_{\text{coll}} = p (ex. p=0{,}5) et résoudre pour k :
\exp!\left(-\frac{k(k-1)}{2N}\right) = 1-p \quad\Rightarrow\quad \frac{k(k-1)}{2N} = -\ln(1-p).Pour k grand, k(k-1)\approx k^2, donc :
k ;\approx; \sqrt{,2N,\ln!\frac{1}{1-p},},.A4) Cas “50 % de chances” (la formule culte)
Avec p = 1/2 : \ln!\frac{1}{1-p}=\ln 2, d’où :
k_{50} ;\approx; \sqrt{,2N\ln 2,} = \sqrt{,2\ln 2,};\sqrt{N} \approx 1{,}17741;\sqrt{N}.Comme N=2^n, on obtient :
k_{50} ;\approx; 1{,}17741 \times 2^{n/2}.👉 C’est LA constante qui justifie la règle empirique “sécurité collision ≈ n/2 bits”.
🔢 Partie B — Applications numériques
B1) MD5 (n=128)
N = 2^{128},\quad k_{50} \approx 1{,}17741 \times 2^{64}\approx 2{,}17 \times 10^{19}.Résultat : ≈ 2^{64} essais (à la constante près).
Historiquement “astronomique”, mais les attaques différentielles ont fait bien pire que ça (beaucoup moins d’essais en pratique).
B2) SHA-256 collision (repère)
n=256 \Rightarrow k_{50} \approx 1{,}17741 \times 2^{128},inatteignable dans tout horizon raisonnable.
B3) Variantes à calculer (exercice rapide)
Calcule k_{50} pour :
- n=64 : k_{50} \approx 1{,}17741 \times 2^{32}
- n=96 : k_{50} \approx 1{,}17741 \times 2^{48}
(Donne les valeurs décimales pour t’entraîner.)
🎯 Partie C — “Dans l’autre sens” : probabilité après un budget d’essais
On veut P_{\text{coll}} après k essais :
P_{\text{coll}}(k) \approx 1 - \exp!\left(-\frac{k(k-1)}{2\cdot 2^n}\right).C1) Exemple (à faire)
Pour n=64 et k=10^9 hachages, calcule :
\lambda = \frac{k(k-1)}{2\cdot 2^{64}}\approx \frac{(10^9)^2}{2\cdot 2^{64}}= \frac{10^{18}} {2\cdot1{,}8446744\times 10^{19}}\approx 0{,}0271,puis
P_{\text{coll}} \approx 1 - e^{-\lambda} \approx 1 - e^{-0{,}0271} \approx 2{,}67%.🧠 Partie D — “Pourquoi la constante 1,17741 ?”
Elle vient de \sqrt{2\ln 2} lorsque p=1/2.
Plus généralement, pour une cible p, la constante multiplicative est \sqrt{2\ln\frac{1}{1-p}}.
🧰 Partie E — Encadré “bonnes pratiques”
- Collision resistance d’une empreinte n bits ≈ n/2 bits effectifs (à cause du paradoxe).
- Pour signer/identifier : SHA-256 (ou plus), SHA-3, BLAKE2/3.
- MD5 : à bannir (attaques différentielles + collisions pratiques).
✅ Corrigé synthétique
- P_0 \approx \exp!\left(-\dfrac{k(k-1)}{2\cdot 2^n}\right)
- P_{\text{coll}} \approx 1 - \exp!\left(-\dfrac{k(k-1)}{2\cdot 2^n}\right)
- k_p \approx \sqrt{,2^{n+1},\ln!\dfrac{1}{1-p},}
- Cas 50 % : k_{50} \approx 1{,}17741 \times 2^{n/2}
- MD5 : k_{50} \approx 1{,}17741 \times 2^{64} \approx 2{,}17\times 10^{19}
💻 (Optionnel) Mini-simu à coder plus tard
- Tire des entiers uniformes dans [0,2^n), insère-les dans un set, et arrête quand tu vois la première collision.
- Répète l’expérience (ex. 1000 fois), moyenne le k observé → compare à 1{,}17741\times 2^{n/2}.
- Fais-le pour n=24 ou n=28 pour obtenir des résultats en quelques secondes.
