Attaque par force brute

Deep Crack, circuit dédié à l'attaque par force brute de DES.

L'attaque par force brute est une méthode utilisée en cryptanalyse pour trouver un mot de passe ou une clé. Il s'agit de tester, une à une, toutes les combinaisons possibles.

Cette méthode est en général considérée comme la plus simple concevable. Elle permet de casser tout mot de passe en un temps fini indépendamment de la protection utilisée, mais le temps augmente avec la longueur du mot de passe. En théorie la complexité d'une attaque par force brute est une fonction exponentielle de la longueur du mot de passe, la rendant virtuellement impossible pour des mots de passe de longueur moyenne, mais en pratique des optimisations heuristiques peuvent donner des résultats dans des délais beaucoup plus courts.

Cette méthode est souvent combinée avec l'attaque par dictionnaire et par table arc-en-ciel pour trouver le secret plus rapidement.

Complexité théorique de l'attaque

Si le mot de passe contient N caractères, indépendants (la présence d'un caractère ne va pas influencer un autre) et uniformément distribués (aucun caractère n'est privilégié), le nombre maximum d'essais nécessaires se monte alors à :

26^N si le mot de passe ne contient que des lettres de l'alphabet totalement en minuscules ou en majuscules ;
52^N si le mot de passe ne contient que des lettres de l'alphabet, avec un mélange de minuscules et de majuscules ;
62^N si le mot de passe mélange les majuscules et les minuscules ainsi que les chiffres.

Il suffit en fait d'élever la taille de « l'alphabet » utilisé à la puissance N. Il s'agit ici d'une borne supérieure et en moyenne, il faut deux fois moins d'essais pour trouver le mot de passe (si celui-ci est aléatoire). En réalité, bien peu de mots de passe sont totalement aléatoires et le nombre d'essais est bien inférieur aux limites données ci-dessus (grâce à la possibilité d'une attaque par dictionnaire).

Le tableau ci-dessous donne le nombre maximum d'essais nécessaires pour trouver des mots de passe de longueurs variables.

Type	1 caractère	3 caractères	6 caractères	9 caractères
lettres minuscules	26	17 576	308 915 776	5,4 × 10¹²
lettres minuscules et chiffres	36	46 656	2 176 782 336	1,0 × 10¹⁴
minuscules, majuscules et chiffres	62	238 328	5,6 × 10¹⁰	1,3 × 10¹⁶

Un ordinateur personnel est capable de tester plusieurs centaines de milliers voire quelques millions de mots de passe par seconde. Cela dépend de l'algorithme utilisé pour la protection mais on voit qu'un mot de passe de seulement 6 caractères, eux-mêmes provenant d'un ensemble de 62 symboles (minuscules ou majuscules accompagnés de chiffres), ne tiendrait pas très longtemps face à une telle attaque.

Dans le cas des clés utilisées pour le chiffrement, la longueur est souvent donnée en bits. Dans ce cas, le nombre de possibilités (si la clé est aléatoire) à explorer est de l'ordre de 2^N où N est la longueur de la clé en bits. Une clé de 128 bits représente déjà une limite impossible à atteindre avec la technologie actuelle et l'attaquant doit envisager d'autres solutions cryptanalytiques si celles-ci existent. Il faut cependant prendre en compte que la puissance du matériel informatique évolue sans-cesse (voir Loi de Moore) et un message indéchiffrable à un moment donné peut l'être par le même type d'attaque une dizaine d'années plus tard.

Optimisation de l'attaque par force brute

Le principe général de l'attaque par force brute reste toujours de tester l'ensemble des mots de passe possible, cependant l'ordre de test peut être optimisé afin d'obtenir de meilleurs rendements qu'une attaque par ordre alphabétique.

ordre aléatoire : certains systèmes de mots de passe sont capables de reconnaître les tentatives d'attaque par force brute suivant les algorithmes les plus courants et de les bloquer, l'introduction d'éléments aléatoires peut masquer l'attaque.

Attaque par dictionnaire

Plutôt que d'utiliser des chaînes de caractère aléatoires comme mot de passe, les utilisateurs ont tendance à utiliser des mots courant plus faciles à retenir or, s'il existe un nombre important de combinaisons aléatoires pour une chaîne de longueur donnée, le nombre de mots présents dans un ou plusieurs langages est beaucoup plus faible (à titre d'exemple l'Académie française estime que les dictionnaires encyclopédiques comptent environ 200 000 mots^[1]). Connaissant ce phénomène culturel, il peut être judicieux de tester ces mots courants et leurs dérivés (y compris argot, dialectes, mots avec fautes d'orthographe courante…) en priorité.

Optimisation par observations statistiques

De manière générale, pour développer le principe de l'attaque par dictionnaire, l'attaquant peut tirer parti du fait qu'en l'état actuel des connaissance il n'existe pas de générateur aléatoire parfait et que de ce fait le générateur étant toujours pseudo-aléatoire (qu'il soit un processus informatique ou la saisie par une personne) il est toujours possible en observant de grands échantillons de mots de passe produits par un générateur donné d'identifier des tendances permettant un résultat généralement meilleur qu'une recherche alphabétique ou aléatoire^[2].

Optimisation par canal auxiliaire

Outre ces attaques théoriques, il existe des attaques tirant parti de l'implémentation des systèmes pour augmenter le rendement de l'attaque par force brute, notamment la transmission des mots de passe sous la forme de hash autorise l'usage de tables arc en ciel, du fait des collisions liées aux fonctions de hachage il est possible de casser une protection sans connaitre le mot de passe réel.

Accroissement de la puissance de calcul

Outre ces améliorations algorithmiques, l'attaque peut également être accélérée en augmentant la puissance de calcul matérielle consacrée à celle-ci par exemple en utilisant des superordinateurs ou de l'informatique distribuée (parfois sous la forme d'un botnet).

Défense contre l'attaque par force brute

Utilisation de mots de passe robustes

La première défense consiste à renforcer le mot de passe en évitant les écueils qu'exploitent les attaques par force brute optimisée. Renforcer la force brute du mot de passe consiste à :

allonger le mot de passe ou la clé si cela est possible ;
utiliser la plus grande gamme de symboles possibles (minuscules, majuscules, ponctuations, chiffres) ; l'introduction de caractères nationaux (Â, ÿ…) rend plus difficile le travail des pirates (mais parfois aussi l'entrée de son mot de passe quand on se trouve à l'étranger) ;

Randomisation des mots de passe

Éviter toutes les formes ou habitudes (patterns) identifiées ou identifiables par les attaquants

éviter l'emploi de mot du langage commun pour empêcher les attaques par dictionnaire
éviter les répétitions de formes de mot de passe (par exemple les mots de passe constitués de caractères en majuscules, caractères en minuscule puis terminés par des symboles sont une famille identifiée et testée en priorité par les logiciels d'attaque par force brute)
en poussant le raisonnement précédent jusqu'au bout il apparaît que la seule méthode de choix de mot de passe qui échappe à toute optimisation est la génération aléatoire (ou en pratique une génération pseudo-aléatoire de qualité suffisante);

Limitation temporelle des connexions

Les mots de passes sont censés rendre l'attaque virtuellement impossible par des temps de cassage extrêmement long, or les temps de cassage sont souvent une fonction linéaire de la capacité de la ou des machine(s) attaquante. Certains attaquants (services secrets, laboratoires…) peuvent disposer de machines très puissantes et les capacités des machines disponibles au grand public sont en constante progression que ce soit par leur puissance brute ou par l'introduction de nouveaux paradigmes (calcul parallèle par exemple). Il en résulte qu'une protection qui paraissait suffisante à un instant donné peut se trouver dépassée par les capacités disponibles à l'attaquant.
La principale méthode pour neutraliser la puissance de calcul d'un attaquant consiste à limiter les tentatives possibles dans le temps. La méthode la plus restrictive et la plus sûre (qu'on retrouve sur les cartes bancaires en France) consiste à n'autoriser qu'un nombre limité d'erreurs avant verrouillage du système. Des méthodes moins contraignantes peuvent être de limiter le nombre de tentatives par unité de temps. Ces méthodes présentent cependant des contraintes d'exploitation et peuvent être détournées par un attaquant pour créer des attaques par déni de service.

Deux brevets principaux existent à ce sujet :

Un des Laboratoires Bell consistant à doubler le temps d'attente après chaque essai infructueux, pour le faire redescendre ensuite en vol plané après un certain temps sans attaques ;
Un de la compagnie IBM consistant à répondre « Mot de passe invalide » après N essais infructueux en un temps T, y compris si le mot de passe est valide^[3] : le pirate a alors toutes les chances de rayer de façon erronée le mot de passe valide en le considérant invalide. De plus, cette méthode empêche toute attaque visant à un déni de service pour l'utilisateur.

Augmentation du coût par tentative

Une variante de l'attaque de la limitation temporelle du nombre de tentatives consiste à augmenter les ressources nécessaires pour réaliser chaque tentative.
Une première méthode consiste à utiliser une fonction de hachage cryptographique de complexité relativement élevée. Ainsi le coût de chaque tentative se trouve augmenté.
Comparé à la simple temporisation, l'intérêt de l'augmentation du coût du hachage est qu'il ne peut être contourné (l'opération de hachage est strictement nécessaire pour effectuer une tentative). Les inconvénients est que le temps de l'opération baisse avec la puissance de la machine attaquante, là où la temporisation reste constante et peut être choisie de façon arbitraire, et que l'augmentation de coût s'applique également aux opérations légitimes.

Un autre exemple de système de limitation des tentatives de connexion est l'utilisation de CAPTCHA. Ces dispositifs peuvent poser des difficultés significatives pour une machine tout en restant acceptables pour un utilisateur humain.

Mais la protection contre les attaques par force brute est souvent apportée par des solutions pragmatiques, en adéquation avec les besoins propres à l’utilisateur, comme la restriction d’accès à une, plusieurs, ou à une plage entière d’adresses IP^[4], ce qui correspond à la grande majorité des cas et se présente comme une alternative fiable à la limitation de durée de validité des mots de passe.

Renouvellement des mots de passe

Une solution peut constituer à limiter la durée de validité des mots de passe à une durée inférieure à celle estimée pour leur cassage en les renouvelant à intervalles réguliers. Ceci peut passer soit par une politique de sécurité informatique appliquée avec rigueur pour des périodes de renouvellement jusqu'à quelques jours ou par des dispositifs physiques token pour des fréquences de renouvellement très élevées.

Salage

Les systèmes de mots de passe comme celui d'Unix utilisent une version modifiée du chiffrement DES. Chaque mot de passe est accompagné d'une composante aléatoire appelée sel dont le but est de modifier la structure interne de DES et éviter ainsi une recherche exhaustive en utilisant du matériel spécialement conçu pour DES. Ce système peut cependant créer une faille de sécurité en facilitant les attaques par déni de service: le temps d'attente peut être utilisé pour gêner la connexion d'utilisateurs légitimes.

En théorie et avec suffisamment de temps, l'attaquant peut toujours trouver le mot de passe, mais lorsque ce temps dépasse la décennie, il ne pourra pas en escompter un grand profit, et le mot de passe aura de toute façon changé. Il change même à chaque fois si l'on emploie le principe du masque jetable.

Le problème est tout autre si l'attaquant récupère directement le fichier des hashs des mots de passe ; plus rien ne l'empêche alors de tester chez lui des mots de passe à la vitesse de son(es) ordinateur(s). C'est pourquoi dans tous les UNIX modernes ces hashs sont généralement situés dans le fichier /etc/shadow, lisible uniquement par l'utilisateur root. Une compromission de cet utilisateur permet par conséquent de récupérer ce fichier, et ainsi de lancer une attaque par force brute sur son contenu.

Notes et références

↑ Page internet de l'Académie française, Questions de langue, Nombre de mots de la langue française
↑ Dan Goodin, How crackers make minced meat out ofyour-passwords, ArsTechnica, 28 mai 2013
↑ System and method of preventing unauthorized access to computer resources - Patent EP1209551
↑ Stopper toutes les attaques en force brute, c’est possible, sur Parle-Net

Annexes

Liens externes

(fr) Programme qui génère des mots de passe, en évalue et en améliore la robustesse
(fr) Calculer une bonne taille de clef (www.keylength.com)

Portail de la cryptologie
Portail de la sécurité informatique

This article is issued from Wikipédia - version of the Friday, September 11, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.