Cloud & Cryptanalyse : comment le cloud pourrait modifier les habitudes de piratage dans un avenir proche

L’un des objectifs d’une fonction de hachage est de stocker des données privées, comme les mots de passe, d’une manière floue. En effet, nous ne voulons pas d’un attaquant qui aurait accès à notre base de données pour obtenir les mots de passe simples des clients. Considérons une simple fonction de hachage convertissant un mot de passe en un résultat de hachage composé des deux derniers caractères de ce mot de passe :

L’attribut principal d’une fonction de hachage est sa caractéristique unidirectionnelle, en d’autres termes, il est simple de trouver le résultat du hachage à partir d’un mot de passe (ici il suffit de prendre les deux derniers caractères), mais il doit être très difficile de récupérer le mot de passe à partir d’un hachage donné (ici de « wd », on ne peut pas récupérer le mot de passe « mypasswd »).

Pour une fonction de hachage donnée, la taille du résultat est toujours fixe. Etant donné qu’il y a beaucoup plus de mots de passe possibles (parce que la taille peut varier) que de résultats de hachage possibles, une fonction de hachage admet toujours des collisions (plusieurs mots de passe donnant le même hachage), par exemple :

Cependant, on s’attend à ce qu’une fonction de hachage minimise le nombre de collisions et rende aussi difficile que possible la recherche d’une collision. En fait, une fonction de hachage est considérée comme bonne si un attaquant ne peut pas récupérer n’importe quelle entrée possible menant à un résultat de hachage donné. Pour notre exemple, un attaquant peut simplement choisir « passwd » s’il a le résultat de hachage « wd ». Par conséquent, notre fonction de hachage n’est pas vraiment bonne. Heureusement, il y en a beaucoup de bonnes qui respectent cette attente, parmi les plus célèbres : MD4, MD5, SHA1, SHA256, SHA3, SHA512.

Pensons-y du point de vue d’un agresseur. Nous voulons forcer un résultat de hachage brutal, en supposant que nous savons quelle fonction de hachage est utilisée. La façon la plus simple est de calculer le résultat de hachage correspondant à chaque mot de passe possible, jusqu’à trouver le bon mot de passe.

De cette façon nous devrions théoriquement récupérer le mot de passe simple (ou une collision de celui-ci). Cependant, s’il y a beaucoup de mots de passe possibles, le calcul pourrait durer trop longtemps. Par exemple, si nous supposons que le mot de passe est composé exactement de 9 caractères alphanumériques (inférieur ou supérieur), il augmente à 62 possibilités par caractère, soit 62⁹ possibilités, ce qui correspond à peu près à 2⁵⁴. En supposant que l’on peut calculer 32 millions de hashes par seconde (≈ 2⁵⁴hashes/s), cette attaque exhaustive durerait environ 500 millions de secondes (≈ 2²⁹ s), soit environ 17 ans (cet exemple utilise un processeur Intel i5-5300U, 2.3 GHz, avec 2 cœurs).

Une autre façon serait de faire une fois ce calcul avec une grosse calculatrice, et de stocker les paires dans un tableau. Ainsi, lorsque nous voulons récupérer un mot de passe simple, nous n’avons qu’à chercher le résultat du hash dans le tableau et prendre le mot de passe correspondant.

Avec cette méthode, le problème est de stocker la table, qui contient 2⁵⁴ paires de mots avec l’exemple précédent. Considérant qu’un mot de passe représente 9 caractères (donc 9 octets) et avec une taille de hachage de 16 octets (par exemple MD5), on obtient 2⁵⁴ fois 25 octets à stocker, soit plus de 2⁵⁸ octets, soit environ 250 000 TBytes !

Ces questions nous amènent à d’autres méthodes d’attaques par force brute. L’une d’entre elles consiste à créer des dictionnaires contenant les mots de passe les plus courants avec toutes les déclinaisons imaginables, en restant avec 9 caractères (Figure 3).

Avec cette méthode, nous réduisons définitivement le coût d’une attaque par force brute. Mais évidemment, cette méthode n’est pas exhaustive, si un client utilise un mot de passe peu commun (ex : ag14d23a4), il aura une petite probabilité d’être dans notre dictionnaire.

Il y a en fait une autre façon de faire, faire un compromis efficace entre le temps et la mémoire, mais en restant avec une recherche exhaustive. Imaginez un dictionnaire non exhaustif composé de 2 colonnes stockées (mots de passe dans la première et résultats de hachage dans l’autre), mais avec des colonnes intermédiaires cachées qui ne sont pas stockées mais qui peuvent être calculées en appliquant des fonctions intermédiaires. Enfin, toutes ces colonnes composeraient un tableau exhaustif, appelé Rainbow Table. D’une manière ingénieuse, les Rainbow Tables permettent aux attaquants de réduire significativement la complexité de la mémoire et du temps, pour notre exemple précédent, la quantité de données stockées passe de 250 000 TBytes à 690 GBytes, soit un facteur de gain d’environ 5 000.

Malgré que cette dernière méthode permette de faire un bon compromis entre le temps et la mémoire, la complexité de la force brute reste importante. Notamment si vous voulez pirater un mot de passe plus grand que 9 caractères.

Cela nous amène à nous demander quelles ont été les meilleures façons d’accélérer les calculs au cours des dernières années.

La loi de Moore, énoncée en 1975 par Gordon Moore (co-fondateur d’Intel), a annoncé que la capacité du CPU (Central Process Unit) doublerait tous les deux ans. Au cours des quarante dernières années, nous pouvons vérifier que cette loi a été plutôt vraie. Évidemment, cette évolution permet aux attaquants de doubler leur efficacité tous les deux ans. Cependant, de nouvelles méthodes utilisant des systèmes parallèles ont considérablement amélioré ces performances.

Les machines dédiées FPGA (Field-Programmable Get Array) ont été les premières à utiliser le calcul parallèle. En termes de performances, le FPGA permet d’être au plus près du langage machine, ignorant les outils inutiles sur votre ordinateur. Un exemple célèbre de ces machines est Copacobana, que nous pouvons observer ici (Figure 4).

Le FPGA a été utilisé jusqu’à la fin des années 2000, notamment pour faire des recherches exhaustives sur les clés. Capable de calculer jusqu’à 264 opérations en un temps raisonnable, il a pu trouver une clé DES (sécurité 56 bits) en moins d’une semaine. Par exemple, nous pouvons voir comment est montée la machine FPGA pour une recherche exhaustive sur une clé DES avec 4 unités de recherche, à partir de « Cryptanalyse avec Copacobana ». (Figure 5).

Les calculateurs parallèles GPU (Graphical Process Unit) permettent un grand gain de performance dans les grands calculs. Le GPU utilise la carte graphique d’un PC, il est donc accessible à tous ceux qui possèdent une carte graphique. Ici, la méthode consiste à attribuer les parties onéreuses d’un processus au GPU, qui exécutera cette charge de travail en parallèle en utilisant ses milliers de cœurs dédiés. Le reste du processus reste exécuté par le CPU, ce qui permet de concentrer toute la puissance du GPU sur la partie lourde. OpenCL et CUDA sont deux langages qui permettent de programmer de tels systèmes, le premier est open source tandis que le second est propriétaire de NVIDIA.

Sagitta est une société qui propose de puissantes machines multi-GPU programmées avec CUDA. Par exemple, il est possible d’acheter Brutalis (Figure 6), composé de huit GPU Nvidia GTX, deux processeurs Intel Xeon E5-2600V3 et 768 Go de mémoire ECC enregistrée, pour environ 18 000 $. Pour comparer avec notre ordinateur, qui calcule 32 millions de hashs MD5 par seconde, Brutalis peut calculer environ 130 milliards de hashs par seconde, soit 5 000 fois plus.

Aujourd’hui, nous pouvons choisir dans les instances Cloud des machines travaillant avec le GPU, donc les attaquants utilisent de plus en plus de GPU via le Cloud pour améliorer leurs performances en cryptanalyse et économiser de l’argent. Par exemple, afin d’exécuter l’attaque de noyade dans TLS en utilisant le protocole SSLv2, les chercheurs ont comparé les performances d’une exécution parallèle GPU optimisée avec leur propre matériel et via le Cloud.

Avec leur matériel (32 cartes Nvidia GTX 980 et 8 cartes AMD R9 290X), l’attaque a duré 18 heures et a coûté 18 000 $. Via le Cloud, en utilisant Amazon EC2, avec 200 instances : 150 instances de 150 g2.2xlarge, chacune contenant un GPU NVIDIA haute performance et 50 instances de 50 g2.8xlarge, chacune contenant quatre de ces GPU, l’attaque a duré 8 heures et a coûté 440 $.

Le principal défaut de l’utilisation du Cloud est que vous devez payer pour les instances chaque fois que vous exécutez une attaque, mais c’est presque 100 fois moins cher que d’acheter un cluster GPU approprié (pour la même efficacité). De plus, nous remarquons l’inutilité des locaux pour stocker une grande calculatrice ainsi que tous les coûts et contraintes techniques qu’elle génère (électricité, loyer, etc….).

Ces raisons amènent à considérer le Cloud comme le substitut d’une bonne grosse calculatrice à l’avenir. L’un des principaux défis serait dans ce cas de sécuriser au mieux les communications avec le serveur afin d’empêcher tout auditeur mal intentionné d’obtenir des informations.