Rapide, facteur 1081.

Ou si vous préférez, répondez à ceci: combien de 23 fois 47?

Lequel est le plus facile? Il est plus facile d'effectuer une multiplication (il suffit de suivre les règles mécaniquement) que de récupérer les opérandes ne donnant que le produit. Multiplication. (Ceci, en passant, est la base de certains algorithmes cryptographiques tels que RSA.)

Fonctions de hachage cryptographique ont des fondements mathématiques différents, mais ils ont la même propriété: ils sont faciles à calculer à l'avenir (calculer H (x) étant donné x), mais pratiquement impossible à calculer en arrière (étant donné y, calculer x tel que H (x) = y). En fait, l'un des signes d'une bonne fonction de hachage cryptographique est qu'il n'y a pas de meilleur moyen de trouver x que de les essayer tous et de calculer H (x) jusqu'à ce que vous trouviez une correspondance.

Une autre propriété importante de fonctions de hachage est que deux entrées différentes ont des hachages différents. Donc si H (x ₁ ) = H (x ₂ ), nous pouvons conclure que x ₁ = x _{2 sub >. Mathématiquement parlant, c'est impossible - si les entrées sont plus longues que la longueur du hachage, il doit y avoir des collisions. Mais avec une bonne fonction de hachage cryptographique, il n'existe aucun moyen connu de trouver une collision avec toutes les ressources informatiques du monde.}

Si vous voulez en savoir plus sur les fonctions de hachage cryptographique , lisez cette réponse de Thomas Pornin. Continuez, j'attendrai.

Notez qu'une fonction de hachage n'est pas une fonction de cryptage. Le chiffrement implique que vous pouvez déchiffrer (si vous connaissez la clé). Avec un hachage, il n'y a pas de nombre magique qui vous permet de revenir en arrière.

Les principales fonctions de hachage cryptographiques recommandées sont SHA-1 et la famille SHA-2 (qui existe en plusieurs tailles de sortie, principalement SHA-256 et SHA-512) . MD5 est plus ancien, désormais obsolète car il a connu des collisions. En fin de compte, il n'y a aucune preuve mathématique qu'il s'agit en effet de bonnes fonctions de hachage cryptographique, seulement une croyance largement répandue car de nombreux cryptographes professionnels ont passé des années de leur vie à essayer, et à échouer, de les casser.

Ok, c'est un une partie de l'histoire. Désormais, un hachage de mot de passe n'est pas directement une fonction de hachage cryptographique. Une fonction de hachage de mot de passe (PHF) prend deux entrées: le mot de passe et un sel. Le sel est généré aléatoirement lorsque l'utilisateur choisit son mot de passe, et il est stocké avec le mot de passe haché PHF (mot de passe, sel). (Ce qui compte, c'est que deux comptes différents ont toujours des sels différents, et générer de manière aléatoire un sel suffisamment gros est un bon moyen d'avoir cette propriété avec une probabilité écrasante.) Lorsque l'utilisateur se connecte à nouveau, le système de vérification lit le sel dans la base de données de mots de passe. , calcule PHF (mot de passe, salt), et vérifie que le résultat est ce qui est stocké dans la base de données.

Le point du sel est que si quelqu'un veut déchiffrer un mot de passe, il va doivent connaître le hachage avant de pouvoir commencer, et ils doivent attaquer chaque compte séparément. Le sel rend impossible d'effectuer de nombreux travaux de craquage à l'avance, par ex. en générant une table arc-en-ciel.

Cela répond (2) et (3) - le vérificateur légitime et l'attaquant découvrent de la même manière si le mot de passe (saisi par l'utilisateur ou deviné par l'attaquant) est correct. Un dernier point dans l'histoire: une bonne fonction de hachage de mot de passe a une propriété supplémentaire, elle doit être lente. Le serveur légitime n'a besoin de le calculer qu'une fois par tentative de connexion, alors qu'un attaquant doit le calculer une fois par estimation, donc la lenteur nuit davantage à l'attaquant (ce qui est nécessaire, car l'attaquant a généralement plus de matériel spécialisé).

Si jamais vous avez besoin de hacher des mots de passe, n’inventez pas votre propre méthode. Utilisez l'une des méthodes standard: scrypt, bcrypt ou PBKDF2.

Les fonctions de hachage cryptographique sont des objets mathématiques qui peuvent être décrits comme "un grand mélange et brouillage de certains bits". Ils prennent en entrée une séquence de bits (éventuellement très longue) et offrent une sortie de taille fixe. En gros, ils sont tellement enchevêtrés que bien qu'il n'y ait rien de secret à leur sujet (c'est juste du code déterministe), personne ne peut trouver comment les "inverser" (trouver une entrée correspondante pour une sortie donnée) sauf par la méthode de base appelée "chance ": essayez des entrées aléatoires jusqu'à ce qu'une correspondance soit trouvée.

Comment il peut arriver, scientifiquement, que des fonctions de hachage puissent exister du tout est une bonne question.

Le hachage n'est pas un chiffrement . Il n'y a pas de secret, pas de clé dans le hachage.

Les fonctions de hachage ont de nombreuses utilisations; l'un d'eux est le "stockage des mots de passe". Une fonction de hachage semble être une bonne chose pour le stockage des mots de passe. Nous ne voulons pas stocker les mots de passe directement (sinon un coup d'œil occasionnel à nos bases de données par l'attaquant lui donnerait trop d'informations; voir ce article de blog pour une discussion); nous voulons stocker des jetons de vérification de mot de passe : quelque chose qui permet la vérification d'un mot de passe (que l'utilisateur présente) mais ne révèle pas le mot de passe lui-même. L'idée est donc la suivante: stockons le hachage du mot de passe. Lorsqu'un mot de passe doit être vérifié, nous calculons simplement son hachage et voyons s'il correspond à la valeur stockée. Mais deviner le mot de passe uniquement à partir de la valeur de hachage est difficile, car la fonction de hachage est résistante à "l'inversion" (voir ci-dessus).

Puisque les mots de passe sont un type particulier de données (ce sont des données dont les humains peuvent se souvenir) , pour une bonne sécurité, nous avons besoin d'une fonction de hachage "renforcée":

• Nous voulons une fonction de hachage très lente .
• Nous ne voulons pas une fonction de hachage, mais plusieurs fonctions de hachage distinctes, afin que chaque mot de passe soit haché avec sa propre fonction de hachage; il s'agit de dissuader les attaques parallèles. Ce processus de transformation d'une fonction de hachage unique en plusieurs variantes est appelé salting .

Voir cette réponse pour un traitement approfondi du sujet des mots de passe de hachage.

Le hachage est une fonction d'une chaîne de bits (généralement de longueur variable) à une autre chaîne de bits (généralement plus petite et de longueur fixe).

Le hachage est utilisé dans les bases de données pour la récupération de données, et dans structures de données de mémoire appelées tables de hachage. Cela nous permet de réduire des données arbitraires, telles qu'une chaîne de caractères ou un objet compliqué avec de nombreux champs, à un nombre binaire qui peut ensuite être utilisé directement comme index dans un tableau clairsemé pour récupérer les données associées (avec quelques détails pour gérer le hachage collisions).

Les fonctions de hachage utilisées de la manière ci-dessus sont des "cousins" des fonctions de hachage cryptographiques. Ils sont conçus pour répondre à différentes exigences. Ils doivent être rapides à calculer et obtenir une bonne distribution.

Dans l'informatique sécurisée, les hachages cryptographiques sont utilisés pour digérer les données en une petite chaîne binaire représentative. Les fonctions cryptographiques ont des exigences différentes. Ils sont conçus pour être difficiles à inverser (pour être des fonctions "trappe" ou "unidirectionnelle"). Non seulement cela, mais une exigence importante est qu'il doit être difficile de trouver, pour un texte en clair et une valeur de hachage donnés, un autre texte en clair qui produit le même hachage.

Le hachage peut être utilisé non seulement pour les mots de passe, mais comme somme de contrôle pour vérifier l'intégrité des données et dans le cadre de la mise en œuvre de signatures numériques. Pour signer numériquement un grand document, nous devons simplement hacher le document pour produire un "digest" (un nom utilisé pour la sortie d'une fonction de hachage, lorsque quelque chose de très long est haché). Ensuite, juste ce condensé est transmis au système de cryptage à clé publique pour produire une signature. Vous pouvez y voir la faiblesse: que se passe-t-il si un attaquant réussit à produire un document qui a le même condensé? Ensuite, il semble que la signature originale produite sur le document authentique est en fait la signature d'un document contrefait: une falsification de transplantation de signature a été effectivement perpétrée.

Le hachage de mot de passe permet aux systèmes de ne pas stocker la version en texte brut d'un mot de passe, mais leur permet de vérifier si l'utilisateur essayant d'obtenir une entrée connaît ce mot de passe. Non seulement le hachage permet aux systèmes de ne pas stocker les mots de passe en texte brut (ce qui devrait être très soigneusement gardé), mais il permet également la possibilité que même si les hachages sont exposés publiquement, les mots de passe soient toujours sécurisés (de la même manière que la crypto clé publique systèmes peuvent révéler des clés publiques). Bien qu'en pratique, les hachages soient néanmoins protégés de l'accès public: par exemple les fichiers / etc / shadow sur des systèmes de type Unix, complétant les fichiers / etc / passwd lisibles par le monde.

La fonction de hachage est tout sauf aléatoire. Cependant, la randomisation est utilisée pour contrecarrer les attaquants qui construisent de gros dictionnaires de mots de passe et de hachages, qui leur permettent de rechercher un code de hachage et de récupérer le mot de passe correspondant.

Pour hacher un mot de passe de manière plus sécurisée, nous pouvons simplement ajouter quelques bits aléatoires appelés un "sel". Différents sels ajoutés au même mot de passe, bien sûr, conduisent à des hachages différents (avec un peu de chance ou pas de collisions).

Si le sel aléatoire est, disons, 32 bits de large, cela signifie qu'en théorie, un mot de passe peut hacher de plus de quatre milliards de façons différentes, ce qui rend très peu pratique d'avoir un dictionnaire précalculé de tous les hachages possibles d'un grand nombre de mots de passe.

Bien sûr, lorsque l'utilisateur est authentifié, il ne sait rien de ce sel. Ce n'est pas grave car le sel est stocké avec le hachage dans le profil de l'utilisateur (souvent, combiné avec le hachage dans une seule chaîne de bits compacte). Lorsque l'entrée du mot de passe de l'utilisateur est en cours de validation, le sel est ajouté au mot de passe saisi, de sorte que le hachage est effectué avec le sel correct. Si le mot de passe est correct, le hachage correspondra, puisque le sel utilisé est également le bon, ayant été extrait du profil de l'utilisateur.

C'est ainsi que le caractère aléatoire est incorporé dans le hachage des mots de passe, tout en lui permettant de fonctionner.

Ce qui rend les hachages difficiles à déchiffrer, c'est qu'ils sont construits à partir de fonctions «trappe» ou «à sens unique» . En mathématiques, il existe de nombreux exemples de telles choses. Par exemple, un simple ajout est une trappe. Si nous ajoutons des nombres entiers pour produire une somme, il est impossible de récupérer les nombres originaux, ne connaissant que la somme.

Les hachages de mot de passe ne sont pas des mots de passe chiffrés. Si un attaquant a le hachage et le sel d'un mot de passe, et parvient à deviner le mot de passe, alors il peut facilement le confirmer, exactement de la même manière que le logiciel d'authentification de connexion le fait: il exécute le mot de passe plus le sel via la fonction de hachage et voit que le hachage correct émerge.

L'une des clés du hachage est qu'il jette des informations. Vous ne pouvez pas inverser un hachage car les connaissances nécessaires ont disparu. Voici quelques exemples de fonctions de hachage exploitables (mais sans valeur). Si vous me donnez un mot de passe, je pourrais faire quelque chose comme l'un des suivants:

• Comptez le nombre de voyelles
• Prenez le code ASCII pour chaque lettre et XOR-les toutes ensemble
• Prenez la somme de contrôle CRC32 de la représentation binaire du mot de passe (celui-ci est en fait un véritable hachage, mais pas un hachage cryptographique)

Dans chacun de ces cas, je ne peux pas inverser le processus. Au lieu de cela, je dois relancer le processus lorsque vous me donnez à nouveau le mot de passe plus tard pour voir si le calcul que j'ai effectué correspond.

Par exemple: Si vous me donnez initialement le mot de passe "singe", je pourrais stocker le numéro 3 (3 voyelles). Puis, plus tard, lorsque j'essaye d'authentifier le mot de passe «dragon», je lance à nouveau la même vérification et j'en trouve 2, ce qui ne correspond pas à 3. Donc je sais que vous m'avez donné le mauvais mot de passe. Mais si vous me donnez le mot de passe "melissa", je supposerais à tort que vous avez tapé le bon mot de passe. Ceci est un hachage collision

L'ensemble de règles que vous appliquez pour trouver le nombre qui représente un mot de passe donné est votre fonction de hachage . Celles-ci sont considérées comme des fonctions «unidirectionnelles» car vous ne devriez pas pouvoir les inverser. Les fonctions de hachage de haute qualité sont conçues pour limiter le nombre de collisions potentielles, afin que vous n'ayez pas à vous soucier de ce problème. Un peu plus loin, les fonctions de hachage cryptographique sont conçues pour rendre difficile la création d'une chaîne qui pourrait correspondre à une sortie donnée (et peut-être créer intentionnellement des collisions). Ils sont également conçus pour limiter la quantité d'informations que vous pouvez glaner sur une entrée donnée uniquement à partir de la sortie de hachage.

1. Détermine la valeur constante de z satisfaisant cette équation: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Besoin d'aide? OK, x = 32. Vous n'arrivez toujours pas à le résoudre? Alors vous ne devriez pas connaître la réponse en premier lieu.

   La valeur de y, qui réduira cela à une seule équation variable, ce qui rend la résolution de cette variable simple triviale pour n'importe quel élève de 6e (ayant éventuellement besoin d'une calculatrice), est un secret que je n'ai partagé que avec des gens en qui j'ai confiance. Sans lui, z pourrait être n'importe quoi; sa valeur dépend de y et il ne peut donc pas être résolu de manière satisfaisante sans une constante, connue y. Si vous ne connaissez pas la valeur de y, c'est que je ne vous ai pas assez fait confiance pour vous la donner en privé.

   C'est le principe de base de la cryptographie; la formule mathématique ou un autre processus déterministe est bien documenté, et une ou plusieurs des variables possibles de la formule sont également autorisées à être publiquement connues, permettant aux deux parties de s'entendre sur un moyen de configurer leurs chiffrements afin que chacune puisse déchiffrer ce que l'autre chiffre. Cependant, deux variables restent secrètes; si vous en connaissez un, vous pouvez découvrir l'autre. Celui que vous devez connaître est la clé, et celui que vous pouvez découvrir avec la clé est le message.

   Pour un hachage, c'est un peu différent. Un hachage ne nécessite pas la conservation d'un secret pour en conserver un autre. Au lieu de cela, les hachages fonctionnent sur la base d'une transformation mathématique irréversible; pour tout H (x) = y, il n'y a pas de H ^-1 (y) = x connu sauf pour essayer H (x) pour tous les x possibles jusqu'à ce que vous obteniez y. Cela est généralement dû au fait que plusieurs résultats intermédiaires de l'équation sont ambigus; par exemple, le calcul de la racine carrée d'un nombre positif produit techniquement à la fois un résultat positif et négatif, puisque l'un ou l'autre des nombres peut être multiplié par lui-même pour produire le résultat. L'inverse d'un module est également ambigu; le nombre 1, produit par x mod 3, aurait pu être produit par n'importe quel x = 3k + 1. Ces types de transformations "à sens unique" sont combinés de telle manière que le fait d'essayer de calculer la fonction de hachage inverse génère des possibilités infinies; le moyen le plus simple (le plus simple) de les résoudre est donc d'essayer simplement toutes les entrées possibles jusqu'à ce qu'une sortie corresponde. Cela prend encore beaucoup de temps.

2. Les hachages ne sont pas aléatoires. Comme je l'ai déjà dit, les hachages sont le résultat d'une opération mathématique irréversible. Cette opération doit encore être déterministe; étant donné une entrée constante, la sortie est constante quel que soit le nombre de fois que vous effectuez l'opération. Il n'y a pas de composante aléatoire.

   Là où vous pourriez avoir été confus, c'est dans le terme de ce qu'un hachage simule, qui est un oracle aléatoire . Imaginez une boîte noire dans laquelle se trouve un petit homme avec une mémoire photographique et une méthode mystique pour générer des nombres parfaitement aléatoires. Vous écrivez quelque chose sur un morceau de papier et le poussez à travers une fente où l'homme le prend. Il le lit et une de deux choses se produit. Soit il ne l'a pas lu auparavant, auquel cas il générera un nouveau nombre aléatoire et vous le donnera, en enregistrant à la fois votre message et le numéro dans sa mémoire. Ou, il a lu ce message exact auparavant, auquel cas il se souvient du numéro qu'il a généré la première fois qu'il l'a lu et vous donne ce numéro. Le générateur de nombres aléatoires ne générera jamais un nombre qu'il a déjà généré, il a une ampleur possible infinie et la mémoire du petit homme est illimitée et infaillible. Par conséquent, le petit homme ne pensera jamais avoir lu un message auparavant s'il ne l'a pas fait, n'oublie jamais qu'il a déjà lu un message, et ne produira donc jamais, jamais, deux nombres différents pour le même message exact, ni le même nombre pour deux différents. messages.

   C'est ce que les fonctions de hachage essaient de simuler. Ils ne peuvent pas modéliser ce petit homme avec la mémoire photographique, car cela exigerait un espace de stockage infini et une disponibilité universelle illimitée, même pour les appareils qui ne sont connectés à aucun autre appareil d'une autre manière. Au lieu de cela, ils s'appuient sur un calcul déterministe mais aléatoire qui "digère" le message dans sa valeur de hachage. La même fonction de hachage, avec le même message, produira le même condensé; cependant, ces fonctions sont limitées dans le nombre de valeurs de hachage qu'elles sont autorisées à renvoyer. Cela crée la possibilité de ce que nous appelons des collisions de hachage; il y a plus de messages possibles que de valeurs de hachage, donc tôt ou tard (espérons-le plus tard), deux messages différents produiront le même hachage.

3. Les hachages peuvent être craqués pour trois raisons fondamentales. Premièrement, parce qu'ils sont une dérivation mathématique déterministe de leur message, les mathématiciens (et donc les attaquants) finissent par trouver une relation mathématique entre un message et son hachage, ou entre deux messages et leurs hachages résultants. Ce qui était autrefois un aspect aléatoire ne l'est plus. Cela permettrait un certain nombre d'attaques basées sur la nature de la faiblesse trouvée; s'il existe un moyen algorithmique, étant donné un message et son hachage, de générer un message en collision, c'est un problème. S'il existe un moyen de manipuler un message et de prédire le hachage résultant, c'est un problème différent. S'il existe en fait un moyen d'inverser le hachage, en produisant un message à partir du hachage qui, lorsqu'il est re-haché, produit le même hachage, c'est un problème sérieux .

   Deuxième , comme les hachages ont une taille de résumé limitée, tôt ou tard, deux messages produiront le même hachage. Cela signifie qu'un attaquant n'a pas à trouver le message que vous utilisez pour produire un certain hachage; il lui suffit de trouver un message qui produit le même hachage. Les chances sont minces, théoriquement une chance sur le nombre de hachages possibles, mais toujours meilleures qu'une chance à l'infini.

   Enfin, s'il y a beaucoup de messages possibles, le nombre de messages probables est bien plus petit. Les messages que nous donnons généralement aux fonctions de hachage ont généralement une structure (basée sur la langue, le sujet, le formatage électronique et le but), ce qui signifie que, étant donné une partie du message, nous pouvons deviner plus précisément les autres parties du message. Cela signifie, en termes de science de l'information, que les messages qui sont convertis en hachages ont souvent une entropie plus faible que la fonction de hachage elle-même; en clair, une fonction de hachage qui produit des résumés de 256 bits peut théoriquement produire n'importe quelle permutation de ces bits, 2 ^ 256. Cependant, s'il y a, par exemple, seulement 10000 messages possibles qui pourraient être saisis dans cette fonction de hachage par un système étudié pour l'attaque, alors seulement 10000 des 2 ^ 256 valeurs de hachage possibles seront jamais vues, et plus important encore, un Dans le pire des cas, l'attaquant n'aurait qu'à essayer les 10 000 entrées possibles pour trouver celle qui produit la valeur de hachage qu'il recherche.