Comment fonctionne le hachage?

Rapide, facteur 1081.

Ou si vous préférez, répondez à ceci: quest-ce que 23 fois 47?

Lequel est le plus facile? 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. (Cest dailleurs le fondement de certains algorithmes cryptographiques tels que RSA .)

Les fonctions de hachage cryptographique ont des bases mathématiques différentes, mais elles ont la même propriété: elles « re facile à calculer à lavenir (calculer H (x) étant donné x), mais pratiquement impossible de calculer en arrière (étant donné y, calculer x tel que H (x) = y). En fait, lun des signes dun bon hachage cryptographique est quil ny 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 des fonctions de hachage est que deux entrées différentes ont des hachages différents. si H (x ₁ ) = H (x ₂ ), nous pouvons conclure que x ₁ = x ₂ Mathématiquement parlant, cest 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 ny a aucun moyen connu de trouver une collision avec toutes les ressources informatiques dans le monde.

Si vous voulez en savoir plus sur fonctions de hachage cryptographique , lisez cette réponse de Thomas Pornin . Allez, jattendrai.

Notez quune fonction de hachage nest pas une fonction de chiffrement. Le chiffrement implique que vous pouvez déchiffrer (si vous connaissez la clé). Avec un hachage, il ny 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 SHA-2 (disponible en plusieurs tailles de sortie, principalement SHA-256 et SHA-512). MD5 est une version plus ancienne, désormais obsolète car elle a connu des collisions. En fin de compte, il ny a aucune preuve mathématique quil sagit en fait 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 briser.

Ok, que  » est une partie de lhistoire. Désormais, un hachage de mot de passe nest 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 salt est généré aléatoirement lorsque lutilisateur choisit son mot de passe, et il est stocké avec le mot de passe haché PHF (mot de passe, sel). (Ce qui compte, cest que deux comptes différents ont toujours des sels différents, et générer au hasard un sel suffisamment grand est un bon moyen davoir cette propriété avec une probabilité écrasante.) là encore, le système de vérification lit le sel dans la base de données de mots de passe, calcule PHF (mot de passe, sel) et vérifie que le le résultat est ce qui est stocké dans la base de données.

Le point du sel est que si quelquun veut déchiffrer un mot de passe, il « devra connaître le hachage avant de pouvoir démarrer , et ils doivent attaquer chaque compte séparément. Le sel rend impossible deffectuer de nombreux travaux de craquage à lavance, par ex. en générant une table arc-en-ciel .

Cela répond (2) et (3) – le vérificateur légitime et lattaquant découvrent dans le même façon si le mot de passe (entré par lutilisateur, ou deviné par lattaquant) est correct. Un dernier point dans lhistoire: une bonne fonction de hachage de mot de passe a une propriété supplémentaire, elle doit être lente. Le serveur légitime na besoin de le calculer quune fois par tentative de connexion, alors quun attaquant doit le calculer une fois par estimation, donc la lenteur nuit davantage à lattaquant (ce qui est nécessaire, car lattaquant a généralement plus de matériel spécialisé).

Si jamais vous avez besoin de hacher des mots de passe, ninventez pas votre propre méthode . Utilisez-en une des méthodes standard : scrypt , bcrypt ou PBKDF2 .  

Commentaires

• Damn I venez sur le site de sécurité de tous les autres et la seule chose qui est très claire est que vous avez mis un travail insensé à répondre. Non seulement correctement, mais extrêmement minutieux. Jaurais aimé pouvoir sélectionner deux réponses, mais la vôtre ressemblait beaucoup plus à quoi Je cherchais.
• @Griffin – Vous pouvez cependant voter pour les deux. Ou bien – quand il y a ‘ plus de t deux réponses – votez pour tout ce que vous pensez quelles ont été utiles, même si vous ne pouvez en accepter quune. Beaucoup de questions ici ont plus dune bonne réponse, et parfois il ‘ est même recommandé de lire la plupart des réponses pour mieux comprendre le sujet en question. Oui, parfois même les moins votés. En votant (de toute façon), vous aidez également les futurs lecteurs à décider de la validité des réponses, en particulier les lecteurs qui sont encore en train dapprendre sur un certain sujet. 😉
• Jai voté les deux! Elles ont été extrêmement utiles.
• +1: Toutes les réponses sont bonnes, mais celle-ci est à peu près aussi proche d’une réponse parfaite que moi ‘ jamais vu sur Stack Exchange. Jaurais +10 si je pouvais.
• @IlmariKaronen Cest ‘ pourquoi jaime venir ici.

Les fonctions de hachage cryptographique sont des objets mathématiques qui peuvent être décrits comme « un grand mélange et brouillage de quelques 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 quil ny ait rien de secret à leur sujet (cest 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 quune correspondance soit trouvée.

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

Le hachage nest pas un chiffrement . Il ny a pas de secret, pas de clé dans le hachage.

Les fonctions de hachage ont de nombreuses utilisations; lun deux 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 lattaquant lui donnerait trop dinformations; consultez 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 dun mot de passe (que lutilisateur présente) mais ne révèle pas le mot de passe lui-même. Lidée est donc la suivante: stockons le hachage du mot de passe. Lorsquun mot de passe doit être vérifié, nous calculons simplement son hachage et voyons sil 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ésiliente contre « linversion » (voir ci-dessus).

Puisque les mots de passe sont un type spécial de données (ce sont des données dont les humains peuvent se souvenir), pour une sécurité adéquate, nous avons besoin dun « renforcé » fonction de hachage:

• Nous voulons une fonction de hachage très lente .
• Nous ne voulons pas une fonction de hachage, mais beaucoup de fonctions de hachage distinctes, de sorte que chaque mot de passe sera haché avec sa propre fonction de hachage; il sagit de dissuader les attaques parallèles. Ce processus consistant à transformer une seule fonction de hachage en plusieurs variantes est appelé salage .

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

Commentaires

• Désolé mais alors que votre réponse était extrêmement complète et bien préparée, jai trouvé lautre réponse ressemble plus à ce que je cherchais.

Le hachage est une fonction de certains 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 les structures de données en mémoire appelées tables de hachage. Cela nous permet de réduire des données arbitraires, telles quune 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 la gestion du 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 linformatique 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 de «trappe» ou «à sens unique»). Non seulement cela, mais une condition importante est quil 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 lintégrité des données et dans le cadre de la mise en œuvre de signatures numériques. Pour signer numériquement un gros document, nous devons simplement hacher le document pour produire un « digest » (un nom utilisé pour la sortie dune 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 dun 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 de un mot de passe, mais leur permet de vérifier si lutilisateur essayant dentrer 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 quen pratique, les hachages soient néanmoins protégés de laccès public: par exemple les fichiers /etc/shadow sur des systèmes de type Unix, en complément des 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 quen 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 davoir un dictionnaire précalculé de tous les hachages possibles dun grand nombre de mots de passe.

Bien sûr, lorsque lutilisateur est authentifié, il ne sait rien de ce sel. Ce nest pas grave car le sel est stocké avec le hachage dans le profil de lutilisateur (souvent, combiné avec le hachage en une seule chaîne de bits compacte). Lorsque lentrée du mot de passe de lutilisateur est en cours de validation, le sel est ajouté à nimporte quel mot de passe elle est entrée, pour que le hachage soit 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 lutilisateur.

Cest ainsi que le caractère aléatoire est incorporé dans le hachage du mot de passe, tout en lui permettant de fonctionner.

Ce qui rend les hachages difficiles à déchiffrer, cest quils sont construits à partir de fonctions «trappe» ou «à sens unique». En mathématiques, il existe de nombreux exemples de ce genre de choses. Par exemple , laddition simple est une trappe. Si nous ajoutons des nombres entiers pour produire une somme, il est impossible de récupérer les nombres dorigine, en 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 dun mot de passe, et arrive à deviner le mot de passe, alors elle peut facilement le confirmer, exactement de la même manière que le logiciel dauthentification de connexion le fait: elle exécute le mot de passe plus le sel via la fonction de hachage et voit que le bon hachage émerge.

Commentaires

• Excellentes compétences en écriture et une y pour comprendre une réponse qui est tout à fait correcte, tout en abordant tous les points et en conservant un flux naturel qui la rend beaucoup plus complète. Ce ‘ nest pas une tâche facile, merci beaucoup pour votre réponse!
• très informatif.vous avez couvert tous les aspects.

Lune des clés du hachage est quil 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 lun 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 redonnerez le mot de passe plus tard pour voir si le calcul que jai effectué correspond.

Pour exemple: Si vous me donnez initialement le mot de passe «singe», je pourrais stocker le numéro 3 (3 voyelles). Ensuite, plus tard, lorsque jessayerai dauthentifier le mot de passe «dragon», je lance à nouveau la même vérification et jen trouve 2, ce qui ne correspond pas à 3. Je sais donc que vous mavez 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. Il sagit dun hash collision .

Lensemble 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 être en mesure de les inverser. Les fonctions de hachage de haute qualité sont conçues pour limiter le nombre de collisions potentielles, de sorte que vous navez 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 dune 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é dinformations que vous pouvez glaner sur une entrée donnée uniquement à partir de la sortie de hachage.

Par conséquent, la seule façon de savoir quel mot de passe correspond à un hachage cryptographique donné est dessayer toutes les possibilités jusquà ce que vous tombiez sur une qui fonctionne. Dautres contre-mesures (sel, BPKDF2, etc.) rendent ce processus de devinettes encore plus difficile en obligeant la personne qui devine le mot de passe à sauter à travers plus de cerceaux à chaque essai.

Notez que jai complètement passé sous silence la façon dont une fonction de hachage cryptographique le rend difficile de trouver un mot de passe fonctionnel (même si ce nest pas loriginal). Ceci est appelé une attaque de pré-image «  « . Dans lexemple trivial ci-dessus, proposer » melissa « comme mot de passe candidat contenant 3 voyelles est un exemple dune telle attaque.

Les fonctions de hachage cryptographique le font généralement en exécutant lentrée sur plusieurs » rounds « dun processus donné, où la sortie de chaque cycle devient une partie de lentrée au suivant.Pour déterminer lentrée du premier tour, vous « d devez comprendre lentrée du deuxième tour, qui à son tour vous oblige à comprendre lentrée du troisième tour, etc., ce qui signifie que chaque estimation de chaque composant doit être vérifié à travers un ensemble long et complexe de calculs. Thomas Pornin a une jolie explication exhaustive du fonctionnement de cette résistance; lecture assez utile si vous voulez vraiment Comprenez-le.

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

   La valeur de y, qui réduira cela à une seule équation de variable, ce qui rend la résolution de cette variable simple triviale pour tout élève de 6e (éventuellement besoin dune calculatrice), est un secret que je nai partagé quavec des personnes en qui jai confiance. Sans lui, z pourrait être nimporte 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 le faites pas  » t connais la valeur de y « s, cest parce que je ne vous ai pas fait assez confiance pour vous la donner en privé.

   Cest le principe de base de la cryptographie; la formule mathématique ou autre processus déterministe est bien -documentées, et une ou plusieurs des variables possibles de la formule sont également autorisées à être connues du public, ce qui permet aux deux parties de se mettre daccord sur un moyen de configurer leurs chiffrements afin que chacune puisse déchiffrer ce que lautre chiffre. Cependant, deux variables restez secret; si vous en connaissez un, vous pouvez découvrir l’autre. Celui que vous devez connaître est la clé, et celui que vous peut découvrir avec la clé est le message.

   Pour un hachage, cest un peu différent. Un hachage ne nécessite pas la conservation dun secret pour en conserver un autre. Au lieu de cela, les hachages fonctionnent sur la base dune transformation mathématique irréversible; pour tout H (x) = y, il ny a pas de H ^-1 (y) = x sauf pour essayer H (x) pour tous les x possibles jusquà ce que vous obteniez y. Habituellement, cest parce que plusieurs résultats intermédiaires de léquation sont ambigus; par exemple, le calcul de la racine carrée dun nombre positif produit techniquement les deux un résultat positif et négatif, puisque lun ou lautre des nombres peut être multiplié par lui-même pour produire le résultat. Linverse dun module est également ambigu; le nombre 1, produit par x mod 3, aurait pu être produit par nimporte quel x = 3k + 1. Ces types de transformations « à sens unique » sont combinés de telle manière que le fait dessayer 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 dessayer simplement toutes les entrées possibles jusquà ce quune sortie corresponde. prend encore beaucoup de temps.

2. Les hachages ne sont pas aléatoires. Comme je lai déjà dit, les hachages sont le résultat dune 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 lopération. Il ny a pas de composant aléatoire.

   Là où vous pourriez avoir été confus, cest dans le terme pour ce quun 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 dans une fente où lhomme 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 exactement message avant, auquel cas il se souvient du nombre quil a généré la première fois quil la lu et vous donne ce nombre. Le générateur de nombres aléatoires ne générera jamais un nombre quil a déjà généré, il a une magnitude possible infinie, et le petit homme la mémoire est illimitée et infaillible. Par conséquent, le petit homme ne pensera jamais avoir lu un message avant sil ne la pas fait, noubliera jamais quil 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 messages différents.

   Cest ce que les fonctions de hachage tentent de simuler. Elles ne peuvent pas modéliser ce petit homme avec la mémoire photographique, car cela nécessiterait un espace de stockage infini et une disponibilité universelle illimitée, même pour appareils qui ne sont connectés à aucun autre appareil d’une autre manière. Au lieu de cela, ils reposent sur un calcul déterministe mais aléatoire regardant qui «digère» le message dans sa valeur de hachage. La même fonction de hachage, donné le même message, produira le même condensé; cependant, ces fonctions sont limitées dans le nombre de valeurs de hachage quelles 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 (jespère plus tard), deux moi différents ssages produira le même hachage.

3. Les hachages peuvent être craqués pour trois raisons fondamentales.Premièrement, parce quils 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 lest plus. Cela permettrait un certain nombre dattaques basées sur la nature de la faiblesse trouvée; sil existe un moyen algorithmique, étant donné un message et son hachage, de générer un message en collision, cest un problème. Sil existe un moyen de manipuler un message et de prédire le hachage résultant, cest un problème différent. Sil existe en fait un moyen dinverser le hachage, produire un message à partir du hachage qui, lorsquil est re-haché, produit le même hachage, cela « est un problème sérieux .

   Deuxièmement, comme les hachages ont une taille de condensé limitée, tôt ou tard, deux messages produiront le même hachage. Cela signifie quun attaquant na 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 que celles à linfini.

   Enfin, bien quil y ait beaucoup de messages possibles, il y en a beaucoup plus petit nombre de messages probables . 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 linformation, que les messages qui sont convertis en hachages ont souvent une entropie inférieure à 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 nimporte quelle permutation de ces bits, 2 ^ 256. Cependant, sil y a, disons, seulement 10000 messages possibles qui pourraient être entrés dans cette fonction de hachage par un système étudié pour lattaque, alors seulement 10000 des 2 ^ 256 valeurs de hachage possibles seront jamais vues, et plus important encore, un Dans le pire des cas, lattaquant naurait quà essayer les 10 000 entrées possibles pour trouver celle qui produit la valeur de hachage quil recherche.

Commentaires

• Et ceci …. cest pourquoi jaime la sécurité informatique ‘ sur le site déchange de piles.
• Aussi votre explication du n ° 1 est exactement ce dont javais besoin. Cependant, jai une question. Il semble que les  » hachages  » sont comme des versions numériques pour une chose donnée (mots de passe dans ce cas). Donc, si jai un site Web et que 100 000 personnes sinscrivent. Ensuite, 50% utilisent le mot de passe  » password  » Je peux économiser une tonne despace en stockant simplement la valeur hachée de  » mot de passe  » au lieu dun mot de passe des tonnes de fois?
• Eh bien, si vous ‘ re en utilisant un hachage sécurisé (> = taille de résumé de 256 bits) puis en stockant la valeur hachée de  » mot de passe  » va augmenter la taille de votre stockage. De plus, si un attaquant voyait un jour que 50% des comptes utilisateurs avaient le même hachage de mot de passe, il ‘ saurait que tout ce quil ‘ d doit faire est de craquer un mot de passe et il a accès à 50% des comptes utilisateurs. Vous devriez  » saler  » vos hachages de mot de passe; il existe une variété de méthodes, mais le résultat final est que le même mot de passe haché par le même algorithme produit un résumé différent, en raison dune valeur de sel unique supplémentaire pour chaque compte.