Comment les fonctions de hachage à sens unique fonctionnent-ils? (Édité)

Question

Je lis l'article de Wikipedia à propos de hash md5 mais je ne peux toujours pas comprendre comment un hachage ne peut pas être « reconstitué » retour au texte original.

Quelqu'un pourrait-il expliquer à quelqu'un qui sait très peu de choses sur la cryptographie comment cela fonctionne? Quelle partie de la fonction rend à sens unique?

Answer 1

Puisque tout le monde jusqu'à présent a simplement défini ce qu'est une fonction de hachage est, je mordre.

Une fonction à sens unique est non seulement une fonction de hachage - une fonction qui perd l'information - mais une f de fonction pour laquelle, étant donné une y d'image ( « SE » ou 294 dans les réponses existantes), il est difficile de trouver une pré-image x tel que f(x)=y.

Ceci est la raison pour laquelle ils sont appelés à sens unique. Vous pouvez calculer une image, mais vous ne pouvez pas trouver une pré-image pour une image donnée

Aucune de la fonction de hachage ordinaire proposée jusqu'à présent dans les réponses existantes ont cette propriété. Aucun d'entre eux sont à sens unique les fonctions de hachage cryptographique. Par exemple, étant donné "SE", vous pouvez facilement prendre l'entrée "SXXXE", une entrée avec la propriété que X-encode ( "SXXXE") = SE.

Il n'y a pas de « simples » fonctions à sens unique. Ils doivent mélanger leurs entrées si bien que non seulement vous ne reconnaissez pas l'entrée du tout dans la sortie, mais vous ne reconnaissez pas une autre entrée non plus.

SHA-1 et MD5 utilisés comme des fonctions populaires à sens unique, mais ils sont tous deux presque brisés (spécialiste savent comment créer des pré-images pour les images données, ou sont presque en mesure de le faire). Il y a un concours en cours pour choisir un nouveau standard, qui sera nommé SHA- 3 .

Une approche évidente pour inverser une fonction à sens unique serait de calculer de nombreuses images et les conserver dans une table associant à chaque image pré-image qui l'a produit. Pour que cela soit impossible dans la pratique, toutes les fonctions à sens unique ont une grande sortie, au moins 64 bits, mais peut-être beaucoup plus grande (jusqu'à, disons, 512 bits).

EDIT: Comment fonctionne le plus de hachage ne fonctionnent cryptographiques

Habituellement, ils ont à leur base une fonction unique qui ne transformations complexes sur un bloc de bits (a chiffrement par bloc ). La fonction doit être à peu près bijective (il ne devrait pas la carte trop de séquences à la même image, car cela causerait des faiblesses plus tard), mais il ne doit pas être exactement bijective. Et cette fonction est un itérer nombre de fois, assez pour faire l'entrée (ou toute entrée possible) impossible à reconnaître.

Prenons l'exemple de Skein, l'un des candidats forts pour le contexte SHA-3. Sa fonction essentielle est itéré 72 fois. Le seul nombre d'itérations pour lesquelles les créateurs de la fonction savent comment se rapportent parfois les sorties à des entrées est 25. Ils disent qu'il a un « facteur de sécurité » de 2,9.

Answer 2

Pensez à un hachage vraiment basique - pour la chaîne d'entrée, retourne la somme des valeurs ASCII de chaque caractère.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

, compte tenu de la valeur de hachage de 294, pouvez-vous dire ce que la chaîne d'origine était? Evidemment non, parce que « abc » et « CBA » (et bien d'autres) donnent la même valeur de hachage.

Cryptographic fonctions de hachage fonctionnent de la même manière, sauf que de toute évidence l'algorithme est beaucoup plus complexe. Il y aura toujours des collisions, mais si vous connaissez chaîne s hash à h, alors il devrait être très difficile ( « infaisable ») construire une autre chaîne qui hash aussi h.

Answer 3

prise de vue pour une simple analogie ici au lieu d'une explication complexe.

Pour commencer, nous allons briser le sujet en deux parties, les opérations à sens unique et hachage. Qu'est-ce qu'une opération à sens unique et pourquoi vous en voulez un?

Une des opérations de manière sont appelés parce qu'ils ne sont pas réversibles. La plupart des opérations typiques comme l'addition et la multiplication peuvent être inversées tandis que la division modulo ne peut pas être inversée. Pourquoi est-ce important? Parce que vous souhaitez fournir une valeur de sortie qui 1) est difficile à reproduire sans les entrées originales et 2) ne donne aucun moyen de comprendre les entrées de la sortie.

réversible

Addition :

4 + 3 = 7  

Cela peut être inversé en prenant la somme et en soustrayant l'un des cumulateurs

7 - 3 = 4  

Multiplication :

4 * 5 = 20  

Cela peut être inversé en prenant le produit et en divisant par l'un des facteurs

20 / 4 = 5

Non réversible

Division Modulo :

22 % 7 = 1  

Cela ne peut pas être inversée parce qu'il n'y a pas d'opération que vous pouvez faire au quotient et le dividende pour reconstituer le diviseur (ou vice versa).

Pouvez-vous trouver une opération à remplir où le « ? » est?

1  ?  7 = 22  
1  ?  22 = 7

Cela étant dit, à sens unique les fonctions de hachage ont la même qualité mathématique que la division modulo.

Pourquoi est-ce important?

Disons que je vous ai donné une clé d'un casier dans un terminal de bus qui a un millier de casiers et vous a demandé de remettre à mon banquier. Être le gars intelligent que vous êtes, sans parler de suspect, vous immédiatement regarder la clé pour voir ce numéro casier est écrit sur la clé. Sachant cela, je l'ai fait quelques petites choses sournoises; d'abord j'ai trouvé deux chiffres que lorsqu'ils sont divisés en utilisant la division modulo me donne un nombre compris entre 1 et 1000, seconde j'ai effacé le numéro original et écrit sur elle le diviseur de la paire de chiffres, deuxième j'ai choisi un terminal de bus qui a garde protégeant les casiers de scélérats que de laisser les gens essayer un casier par jour avec leur clé, le banquier tiers connaît déjà le dividende alors quand il obtient la clé, il peut faire le calcul et comprendre le reste et le savoir qui casier pour ouvrir.

Si je choisis les opérandes à bon escient que je peux obtenir près d'un one-to-one relation entre le quotient et le dividende qui vous oblige à essayer chaque casier parce que la réponse se propage les résultats des entrées possibles sur la plage de nombres souhaités , les casiers disponibles dans le terminal. En gros, cela signifie que vous ne pouvez pas acquérir des connaissances sur le reste, même si vous connaissez l'un des opérandes.

Alors, maintenant, je peux « confiance » vous livrer la clé à son propriétaire légitime sans se soucier que vous pouvez facilement deviner à qui il appartient LOCKER. Bien sûr, vous pourriez recherche exhaustive tous les casiers, mais qui prendrait presque 3 ans, beaucoup de temps pour mon banquier d'utiliser la clé et vider le casier.

Voir les autres réponses pour plus de détails sur les différentes fonctions de hachage.

Answer 4

Voici un exemple très simple. On suppose que je suis un début cryptographe et je crée une fonction de hachage qui effectue les opérations suivantes:

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

Maintenant, voici le test. SimpleHash(specialFile) est 0. Quel était mon fichier original?

De toute évidence, il n'y a aucun moyen de savoir (bien que vous pourriez probablement découvrir assez facilement que mon hachage est basé sur la longueur du fichier). Il n'y a aucun moyen de mon dossier « reconstituer » basé sur le hachage car le hachage ne contient pas tout ce que mon dossier a fait.

Answer 5

Un hachage est un (très) codage avec pertes.

Pour vous donner un exemple plus simple, imaginez une 2 lettres fictive de codage d'un mot de 5 lettres appelé le codage X. L'algorithme pour le X-encodage est simple:. Prendre les premières et dernières lettres du mot

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

De toute évidence, vous ne pouvez pas reconstruire SAUCE de son encodage SE (en supposant que notre gamme d'entrées possibles est tous les mots de 5 lettres). Le mot pourrait tout aussi bien être SPACE.

En aparté, le fait que SAUCE et SPACE SE produisent tous les deux comme un codage est appelé collision , et vous pouvez voir que le X-ecoding ne ferait pas un très bon hachage. :)

Answer 6

En termes simples, une fonction de hachage fonctionne en faisant un grand fouillis des données d'entrée.

Voir MD5 par exemple. Il traite les données d'entrée par blocs de 512 bits. Chaque bloc est divisé en 16 mots de 32 bits. Il y a 64 étapes, chaque étape en utilisant l'un des 16 mots d'entrée. Donc, chaque mot est utilisé quatre fois dans le cours de l'algorithme. C'est là un Wayness provient de: un bit d'entrée est entrée à plusieurs endroits, et entre deux de ces entrées la fonction mixe toutes les données actuelles ensemble afin que l'impact de chaque bit d'entrée la plupart de l'état de fonctionnement de 128 bits. Cela vous empêche d'inverser la fonction ou le calcul d'une collision, en regardant seulement une partie des données. Vous devez regarder l'ensemble 128 bits, et l'espace est trop large de blocs de 128 bits pour être efficace par marché.

MD5 ne fait pas un bon travail, puisque les collisions pour cette fonction peuvent être trouvés. D'un point de vue cryptographe, MD5 est une fonction de cryptage pivotée. Le traitement d'une M de bloc de message (512 bits) utilise un état d'entrée V (valeur de 128 bits) et calcule le nouvel état V « en tant que V » = V + E (M, V) où « + » est un mot: plus sage, et « E » se trouve être une fonction de chiffrement symétrique (aka un « de chiffrement par bloc »), qui utilise comme clé M et V en tant que message à chiffrer. De plus près, E peut est une sorte de « réseau étendu Feistel », similaire au chiffrement par bloc DES, avec quatre trimestres au lieu de deux moitiés. Détails ne sont pas importants ici; mon point est que ce qui fait une « bonne » fonction de hachage, entre les fonctions de hachage qui utilisent cette structure (appelée « Merkle-Damgard »), est similaire à ce qui fait un chiffrement par bloc « sécurisé ». Les attaques de collision avec succès sur MD5 utilisent cryptanalyse différentiel, un outil qui a été conçu pour attaquer chiffrements par bloc en premier lieu.

D'un chiffrement par bloc à une bonne fonction de hachage, il y a une étape qui ne doit pas être rejeté. Avec la structure Merkle-Damgard, la fonction de hachage est sécurisée si le chiffrement par bloc sous-jacent est résistant aux « attaques clés connexes », une propriété plutôt obscure contre laquelle chiffrements par bloc sont rarement renforcées parce que, pour le chiffrement symétrique, les attaques clés liées ont à peine une pratique impact. Par exemple, le cryptage AES est avéré ne pas être aussi résistant aux attaques clés connexes pourraient être souhaité, et cela n'a pas déclenché la panique générale. Cette résistance ne faisait pas partie des propriétés qui ont été recherchées quand AES a été conçu. Il empêche simplement tourner l'AES dans une fonction de hachage. Il y a une fonction de hachage appelé Whirlpool, qui repose sur un dérivé de Rijndael, « Rijndael » étant le nom initial de ce qui est devenu l'AES; mais Whirlpool prend soin de modifier les parties de Rijndael qui sont faibles à des attaques clés connexes.

En outre, il existe d'autres structures qui peuvent être utilisées pour la construction d'une fonction de hachage. Les fonctions standard actuelles fonctions (MD5, SHA-1, et la famille "SHA-2", alias SHA-224, SHA-256, SHA-384 et SHA-512) sont Merkle-Damgard, mais beaucoup de soi- successeurs ne sont pas. Il y a une compétition permanente, organisée par le NIST (l'organisme fédéral américain qui traite de ce genre de choses), pour sélectionner une nouvelle fonction de hachage standard, baptisée « SHA-3 ». Voir cette page pour plus de détails. En ce moment, ils sont en baisse à 14 candidats d'un premier 51 (sans compter une douzaine supplémentaire qui a échoué le test administratif d'envoyer une soumission complète avec le code qui compile et fonctionne correctement).

Jetons maintenant un coup d'oeil plus conceptuelle. Une fonction de hachage sécurisée doit ressembler à une oracle aléatoire : un oracle est une boîte noire qui, quand donné un message M en entrée, sorties une réponse h (M ) qui est choisi au hasard, de façon uniforme, dans l'espace de sortie (à savoir tous n chaînes de -bit si la longueur de sortie de la fonction de hachage est N ). Si on leur donne le même message M à nouveau en entrée, l'oracle délivre en sortie la même valeur que précédemment. En dehors de cette restriction, la sortie de l'oracle sur une entrée non utilisée précédemment M est imprévisible. On peut imaginer l'oracle comme un conteneur pour un gnome qui jette les dés, et enregistre attentivement les messages d'entrée et de sorties correspondantes dans un grand livre, afin qu'il honorera son contrat d'oracle. Il n'y a aucun moyen de prédire ce que la prochaine sortie sera depuis le gnome lui-même ne le sait pas.

Si un oracle aléatoire existe, l'inversion de la fonction de hachage a coûté 2 ^ n : afin d'avoir une sortie donnée, il n'y a pas de meilleure stratégie que l'utilisation des messages d'entrée distincts jusqu'à ce qu'un donne le prévu valeur. En raison de la sélection aléatoire uniforme, la probabilité de réussite est 1 / (2 ^ n) à chaque essai, et le nombre moyen de demandes au lancement de dés gnome sera 2 ^ n . Pour les collisions (trouver deux entrées distinctes qui donne la même valeur de hachage), le coût est d'environ * 1.4 * 2 ^ (n / 2) * (grosso modo, avec * 1.4 * 2 ^ (n / 2) * sorties, nous pouvons assembler environ 2 ^ n paires de sortie, ayant chacun une probabilité de 1 / (2 ^ n) de correspondance, soit à deux entrées distinctes, qui ont la même sortie). Ce sont les meilleurs qui peut être fait avec un oracle aléatoire.

Par conséquent, nous recherchons des fonctions de hachage qui sont aussi bons comme oracle au hasard: ils doivent mélanger les données d'entrée de telle manière que nous ne pouvons pas trouver une collision plus efficace que ce qu'il en coûterait pour appeler simplement la fonction 2 ^ (n / 2) fois. Le fléau de la fonction de hachage est une structure mathématique, à savoir des raccourcis qui permettent à l'attaquant de visualiser la fonction de hachage état interne (qui est grande, au moins n bits) comme une variation sur un objet mathématique qui vit dans une espace beaucoup plus court. 30 ans de la recherche publique sur les systèmes de chiffrement symétrique ont produit un ensemble de notions accessoires et outils (diffusion, avalanche, différentiels, linéarité ...) qui peuvent être appliquées. Ligne de fond, cependant, est que nous avons aucune preuve qu'un oracle au hasard peut réellement exister. Nous veulent une fonction de hachage qui ne peut pas être attaqué. Ce que nous Vous sont candidats fonction de hachage, pour lesquels aucune attaque est actuellement connu , et, un peu mieux, nous avons des fonctions pour lesquelles certains types d'attaque peut être prouvé de ne pas travailler.

Il y a encore des recherches à faire.

Answer 7

array
 Avec un peu de strabisme, les tableaux associatifs ressemblent beaucoup hash. Les principales différences sont l'absence du symbole% sur les noms de hachage, et que l'on ne pouvait leur assigner une touche à la fois. Ainsi, on dirait $foo{'key'} = 1;, mais seulement @keys = keys(foo);. fonctions familières comme chacun, les clés et les valeurs ont travaillé comme ils le font maintenant (et supprimer a été ajouté en Perl 2).

Perl 3 avait trois entiers types de données: il avait le symbole% sur les noms de hachage, a permis à un hachage entier à être affecté à à la fois, et a ajouté dbmopen (maintenant dépréciée en faveur de la cravate). Perl 4 utilisées clés de hachage séparés par des virgules pour émuler des tableaux multidimensionnels (qui sont maintenant mieux traitées avec des références de tableau).

Perl 5 a pris le pas de géant de se référer à des tableaux associatifs comme hash. (Pour autant que je sache, il est la première langue avoir renvoyé à la structure de données ainsi, plutôt que « table de hachage » ou quelque chose de semblable.) Un peu ironiquement, il a également déplacé le code correspondant de hash.c en hv.c.

Nomenclature
Dictionnaires, comme expliqué plus haut, sont des collections non ordonnées de valeurs indexées par des clés uniques. Ils sont parfois appelés tableaux associatifs ou des cartes. Ils peuvent être mis en œuvre de plusieurs façons, dont l'un est à l'aide d'une structure de données connue sous le nom d'une table de hachage (ce qui est ce que Perl fait référence à un hachage).

L'utilisation de Perl du terme « hachage » est la source d'une certaine confusion potentielle, car la sortie d'une fonction de hachage est aussi parfois appelé un hachage (en particulier dans des contextes de chiffrement), et parce que les tables de hachage ne sont généralement pas appelé hash partout d'autre.

Pour être du bon côté, reportez-vous à la structure de données comme une table de hachage, et d'utiliser le terme « hachage » que dans des contextes spécifiques évidents, Perl.