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 :

MD5(M_1) = MD5(M_2)

---

🚨 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 :

P_0= \prod_{i=0}^{k-1} \frac{N-i}{N}= \exp!\left( \sum_{i=0}^{k-1} \ln!\left(1-\frac{i}{N}\right) \right).

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 :

P_0 ;\approx; \exp!\left(-\frac{k(k-1)}{2N}\right).

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.