Brute-force
Aussi appelé : Attaque par force brute · Recherche exhaustive
L’attaque par brute-force (force brute) consiste à énumérer toutes les clés possibles d’un chiffre et à tester chacune d’elles jusqu’à obtenir un déchiffrement plausible. C’est conceptuellement la plus simple des attaques : aucune idée fine n’est requise, juste de la patience et du temps machine. Et c’est aussi conceptuellement la plus puissante : si la clé existe, on finira par tomber dessus. Pas d’angle mort, pas d’hypothèse à valider.
Le tout est de savoir combien de temps cela prend.
Échelle des chiffres face à la brute-force
| Chiffre | Espace de clés | Temps de brute-force |
|---|---|---|
| César | 25 décalages | Humain : 5 min |
| ROT | 25 décalages | Humain : 5 min (identique au César) |
| Affine | 12 × 26 = 312 paires (a, b) | Humain : 30 min |
| Substitution monoalphabétique | 26! ≈ 4 × 10²⁶ | Brute-force pure infaisable, mais analyse de fréquence en quelques minutes |
| Vigenère, clé 5 lettres | 26⁵ ≈ 12 millions | Ordinateur : trivial |
| Vigenère, clé 12 lettres | 26¹² ≈ 9 × 10¹⁶ | Idem DES |
| DES (1977) | 2⁵⁶ ≈ 7 × 10¹⁶ | EFF Deep Crack 1998 : 56 heures |
| AES-128 | 2¹²⁸ | Tous les ordinateurs de la Terre : milliards d’années |
| AES-256 | 2²⁵⁶ | Plus d’atomes que l’univers visible |
| Masque jetable (clé aussi longue que le message) | Aussi grand que le message | Même la bonne clé est indistinguable d’une fausse |
Le tableau illustre une règle d’or : c’est le logarithme de l’espace de clés (en bits) qui détermine la résistance à la brute-force. À chaque bit ajouté à la clé, on double le coût de l’attaque. Passer de 56 bits (DES) à 64 bits (DES double, naïf) ne suffit plus aujourd’hui ; passer à 128 (AES-128) sort du domaine du faisable.
L’astuce du masque jetable
Le masque jetable mérite une mention spéciale. Sa résistance à la brute-force est infinie — non pas parce que l’espace de clés est plus grand qu’AES, mais parce que toutes les clés produisent des déchiffrements plausibles. Avec une clé K1, votre chiffré XY9R donne HELLO ; avec une autre clé K2, le même chiffré donne WORLD ; avec une autre encore, ATTACK ; avec encore une autre, RETREAT. Aucun moyen de distinguer la « vraie » clé d’une clé bidon. C’est ce que Shannon a prouvé en 1949 sous le nom de secret parfait.
Optimisations classiques
La brute-force pure est rarement faite telle quelle. On l’accélère :
- Tri par plausibilité : on essaie d’abord les clés statistiquement probables (mots du dictionnaire pour Vigenère, dates de naissance pour les codes 4 chiffres, mots de passe les plus courants —
123456,password,qwerty). - Parallélisation : un GPU exécute des milliards de tests par seconde. Une ferme de GPU loués (cloud) divise encore le temps.
- Tables précalculées (rainbow tables) : on stocke à l’avance les hashes de millions de mots de passe, l’attaque devient une simple recherche.
- Élagage : sur Vigenère, on essaie d’abord les clés courtes (3-7 lettres) qui couvrent l’écrasante majorité des cas réels.
Parades : KDF, sel, rate limiting
Pour les systèmes vivants (mots de passe, authentification), on ralentit volontairement la brute-force :
- KDF (Key Derivation Function) : on hashe le mot de passe avec Argon2, bcrypt ou scrypt — fonctions conçues pour être lentes et coûteuses en mémoire. Une vérification légitime prend 100 ms ; un attaquant qui veut tester un milliard de candidats prend des années.
- Sel : on ajoute des octets aléatoires uniques au mot de passe avant hashing. Un attaquant ne peut plus précalculer une rainbow table universelle ; il doit refaire le travail pour chaque utilisateur.
- Rate limiting : 5 essais ratés et le compte se bloque temporairement. Le brute-force en ligne devient impossible. (Hors ligne sur une fuite de base, le sel + KDF restent la dernière barrière.)
Brute-force comme borne supérieure
À noter : la brute-force est toujours en arrière-plan comme borne supérieure de cassabilité. Une attaque cryptanalytique « réelle » (analyse différentielle, attaque par canal auxiliaire) ne vaut la peine que si elle est plus rapide que la brute-force. Quand on annonce qu’AES-256 a une attaque théorique en 2²⁵⁴ opérations, c’est plus rapide que 2²⁵⁶ — donc une attaque valide — même si en pratique elle reste totalement infaisable.
À retenir :
- Brute-force = essayer toutes les clés. Toujours possible, mais pas toujours raisonnable.
- C’est le logarithme de l’espace de clés qui compte. Chaque bit double le coût.
- Pour les systèmes vivants, ralentir la brute-force est une parade aussi importante que choisir un bon algorithme : KDF (Argon2, bcrypt) + sel + rate limiting.
- Brute-force est la borne supérieure : toute « vraie » attaque cryptanalytique se mesure à elle.