Brute-force

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.