Comment faire un moyen de fonctions de hachage de travail? (Édité)

J'ai lu l'article de Wikipedia sur le hachage md5, mais je n'arrive toujours pas à comprendre comment un hachage ne peut pas être "reconstitué" retour vers le texte original.

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

  • "reconstituer" et "texte original" peut être le mal des mots et de la raison pour laquelle tout le monde insiste sur le fait de donner la définition d'une fonction de hachage ordinaire. C'est peut-être mieux de penser en terme de "élaboration d'une entrée quelconque que les hachages de la donnée de hachage". Il ne doit pas être l'original.
  • J'ai dû modifier le titre de modifier les étiquettes. :\
InformationsquelleAutor user94154 | 2010-01-21
  1. 49

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

    Une fonction n'est pas seulement une fonction de hachage-une fonction qui perd de l'information-mais une fonction f pour qui, étant donné une image y ("SE" ou 294 dans les réponses existantes), il est difficile de trouver une pré-image de x telle que f(x)=y.

    C'est pourquoi ils sont appelés d'une manière: vous pouvez calculer une image, mais vous ne pouvez pas trouver une pré-image pour une image donnée.

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

    Il n'y a pas de "simple" one-way fonctions. Ils ont pour mélanger leurs entrées si bien que non seulement vous ne reconnaissez pas l'entrée à la sortie, mais vous ne reconnaissez pas une autre entrée.

    SHA-1 et MD5 utilisé pour être populaire d'une manière fonctions, mais ils sont tous les deux près de cassé (spécialiste savez comment créer des pré-images pour les images, ou sont en passe 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 seule fonction serait de calculer beaucoup d'images et de les garder dans un tableau associant à chaque image de la pré-image qui l'a produite. À cela s'avère impossible, dans la pratique, tous d'une sorte de fonction ont une grande sortie, au moins 64 bits, mais peut-être beaucoup plus grande (jusqu'à, disons, 512 bits).

    EDIT: Comment la plupart des fonctions de hachage cryptographiques travail?

    Habituellement, ils ont à leur base une seule fonction qui n'compliqué transformations sur un bloc de bits (un algorithme de chiffrement par bloc). La fonction doit être près de bijective (il ne devrait pas carte de trop nombreuses séquences de la même image, parce que ce serait la cause des faiblesses plus tard), mais il n'a pas à être exactement bijective. Et cette fonction est répété un nombre fixe de fois, assez pour faire l'entrée (ou d'entrée) impossible à reconnaître.

    Prendre l'exemple de L'écheveau, l'un des bons candidats pour le SHA-3 contexte. Sa fonction principale est itéré 72 fois. Le seul nombre d'itérations pour laquelle les créateurs de la fonction savent parfois se rapportent les sorties de certains intrants est de 25. Ils disent qu'il a un "facteur de sécurité" de 2,9.

    • +1 pour le "vous ne devriez pas reconnaître l'entrée à la sortie"
    • c'est donc d'abord une fonction qui n'ont pas l'inverse (pas une fonction bijective). Cela fonctionne lorsque l'entrée est plus grande que la sortie. Mais qu'en est-il, c'est de la même taille, ou lorsque l'entrée est plus petite que la sortie?
    • Il devrait être impossible de reconnaître en voyant la sortie qu'il a été généré à partir d'un bref de saisie. En supposant que l'on vous dit que la sortie a été généré à partir d'un n-bits d'entrée, n plus petit que la taille de la sortie, vous devriez vous attendre à avoir besoin d'essayer sur (2^n)/2 entrées avant d'en trouver un dont la sortie est celui que vous recherchez. Il doit avoir une forte probabilité d'être effectivement le seul à n bits d'entrée de la sortie.
    InformationsquelleAutor Pascal Cuoq
  2. 43

    Penser à une base de hachage pour la chaîne d'entrée, de retour à la somme des valeurs ASCII de chaque caractère. 

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

    Maintenant, compte tenu de la valeur de hachage de 294, pouvez-vous dire ce que la chaîne d'origine a été? A l'évidence non, car " abc " et " abc " (et d'innombrables autres) donnent la même valeur de hachage.

    Fonctions de hachage cryptographiques fonctionnent de la même façon, sauf que, évidemment, l'algorithme est beaucoup plus complexe. Il y a toujours des collisions, mais si vous savez chaîne s hachages pour h, alors il devrait être très difficile ("mathématiquement impossible") à construire une autre chaîne que aussi hachages pour h.

    • il semble donc que toutes les fonctions de hachage aura certains "collisions"...l'objectif dans la conception d'un bon algorithme est de garder les collisions aussi bas que possible?
    • C'est vrai
    • Oui. J'ai mis à jour ma réponse.
    • Non, le but est pour les collisions à être uniformément répartie et imprévisible. Par exemple, pour la base de hachage donné dans cette réponse, vous pouvez facilement prédire que hash('acb') (et beaucoup d'autres) vont avoir le même résultat que hash('abc'). Pour un solide de hachage, il n'y a aucun moyen de le faire (convertir une entrée dans un autre qui a le même hash) qui est plus rapide que juste le hachage des entrées aléatoires jusqu'à ce que vous trouver un avec le droit de hachage (bruteforce).
    • Donc, ce que Graeme a fourni est ce qu'on appelle une somme de contrôle de hachage est une somme de contrôle avec beaucoup d'exigences plus strictes (en.wikipedia.org/wiki/Cryptographic_hash_function). Fondamentalement, ils atteindre cet objectif en faisant l'algorithme écrasez ensemble l'entrée dans le complexe et déroutant que possible (tout en restant très rapide à calculer)
    • enfin, cela fait sens! super réponse!

    InformationsquelleAutor Graeme Perrow
  3. 31

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

    Pour commencer avec, examinons le sujet en deux parties, l'une-des opérations et de hachage. Qu'est-ce que une opération et pourquoi vous en voulez un?

    L'une des opérations sont appelées parce qu'elles ne sont pas réversibles. Le plus typique des opérations comme l'addition et de multiplication peut être inversé alors que modulo division ne peut pas être inversée. Pourquoi est-ce important? Parce que vous souhaitez fournir une valeur de sortie qui 1) est difficile à dupliquer sans l'original entrées et 2) ne fournit aucun moyen pour comprendre les apports de la sortie.

    Réversible

    Plus: 

    4 + 3 = 7

    Cela peut être inversés en prenant la somme et la soustraction de l'un des addends

    7 - 3 = 4

    Multiplication:

    4 * 5 = 20

    Cela peut être renversée par la prise du produit et en divisant par l'un des facteurs

    20 /4 = 5

    Pas Réversible

    Modulo division:

    22 % 7 = 1

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

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

    1  ?  7 = 22  
1  ?  22 = 7

    Avec cela étant dit, un moyen de fonctions de hachage ont les mêmes qualités mathématiques comme modulo division.

    Pourquoi est-ce important?

    Permet de dire 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 livrer à mon banquier. Être le gars intelligent que vous êtes, pour ne pas mentionner suspect, vous chercher immédiatement sur la touche pour voir ce casier numéro est écrit sur la clé. Sachant cela, j'ai fait un peu sournois choses; d'abord, j'ai trouvé deux numéros que lorsqu'il est divisé à l'aide de division modulo me donne un nombre dans la plage comprise entre 1 et 1000, la deuxième j'ai effacé le numéro d'origine et écrit sur le diviseur de la paire de nombres, deuxième, j'ai choisi un terminal de bus qui a un garde de la protection de l'casiers de mécréants que de laisser les gens essayer un casier à jour, avec leur clé, troisième le banquier connaît déjà le dividende ainsi, lorsqu'il reçoit la clé, il peut faire le calcul et de comprendre le reste et casier à ouvrir.

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

    Alors, maintenant, je peux la "confiance" de vous livrer les clés de son propriétaire légitime, sans se soucier que vous pouvez facilement le deviner à qui locker il appartient. Bien sûr, vous pourriez force brute de recherche tous les casiers, mais ce serait prendre près de 3 ans, beaucoup de temps pour mon banquier pour l'utilisation de la touche et de vider le casier.

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

    • Sans commentaire, je n'ai aucune idée de pourquoi c'était downvoted.
    • Bonne explication, merci.
    InformationsquelleAutor Kelly S. French
  4. 10

    Voici un exemple très simple. Supposons que je suis un début cryptographe et j'ai créer 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;
}

    , Voici maintenant le test. SimpleHash(specialFile) est de 0. Ce qui a été mon fichier d'origine?

    Évidemment, 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 "reconstituer" mon fichier basé sur le hachage parce que le hachage ne contient pas tout ce que mon fichier n'.

    • Vous avez défini une fonction de hachage. Une fonction de hachage cryptographique est un hachage avec de fortes propriétés que votre réponse ne mentionne pas. Il ne suffit pas que le fichier ne peut pas être reconstitué; il doit être difficile pour quelqu'un la connaissance de la fonction pour élaborer un fichier de hachages pour 0. En fait, si votre fonction retourne un booléen, il ne peut pas être un-chemin-il seulement besoin d'être essayé sur un couple d'entrées à "craquer".
    • Eh bien, il peut être à sens unique mais force est de seulement 1 bit. Qui est clairement bruteforceable avec du papier et un crayon 🙂
    • Vous êtes très correcte sur de bonnes propriétés d'une fonction de hachage cryptographique. Je vise uniquement à fournir un exemple de ce qui était tout à fait évident qu'il n'y avait aucun moyen pour revenir à l'original ou même deviner ce qu'il pourrait avoir été. J'espère que j'ai répondu à l'OP de la question.
    • qui répond à la question d'origine, exactement et simplement, ce qui ne peut pas être dit pour la plupart compliqué (mais intéressant) réponses ici
    • L ' “original” la question est à propos de d'UNE MANIÈRE fonctions de hachage. Cette réponse, ainsi que la plupart des premières réponses qui ont été écrits, ne pas y répondre (même si je vous accorde qu'ils sont simples). Si vous pensez que la réponse ci-dessus a une quelconque pertinence à l ' “original” à la question, vous devriez lire à propos d'un moyen de fonctions de hachage—à partir de toutes les sources que vous aimez si vous trouvez les réponses ici trop compliqué ou inexactes.
    InformationsquelleAutor Kaleb Pederson
  5. 8

    Un hachage est une (très) codage avec perte.

    Pour vous donner un exemple simple, imaginons un fictif 2-lettre de l'encodage d'un 5-letter word, appelée X-encodage. L'algorithme pour le X-codage est simple: prenez la première et la dernière lettre du mot.

    Donc,

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

    Clairement, vous ne pouvez pas reconstruire la SAUCE à partir de son codage SE (en supposant que notre gamme d'entrées possibles est l'ensemble des 5-lettre des mots). Le mot pourrait tout aussi bien être ESPACE.

    Comme une part, le fait que la SAUCE et de l'ESPACE à la fois SE produire comme un codage est appelé un collision, et vous pouvez voir que le X-ecoding ne ferait pas un très bon hash. 🙂

    • s/codage/un-moyen-de chiffrement
    • Ainsi, le chiffrement est juste un type de codage...
    • La partie importante d'une fonction de hachage cryptographique n'est pas le "lossyness", mais il n'est pas possible de revenir à tout preimage (ou toute collisions).
    • De loin, la meilleure réponse de tous, c'est surtout au point de
    InformationsquelleAutor ezod
  6. 8

    En termes simples, une fonction de hachage fonctionne en faisant un gros emmêlés de l'entrée de données.

    Voir MD5 par exemple. Il traite les données en entrée par 512 bits des blocs. Chaque bloc est divisé en 16 32-bits. Il y a 64 étapes, chaque étape à l'aide de l'une des 16 mots. De sorte que chaque mot est utilisé à quatre reprises au cours de l'algorithme. C'est là un wayness vient de: aucune bits d'entrée est entrée à plusieurs endroits, et entre les deux entrées de la fonction de mélange toutes les données actuelles, ensemble, de sorte que chaque entrée peu impacts plus de la 128 bits de l'état en cours d'exécution. Cela vous empêche d'inverser la fonction, ou le calcul d'une collision, en regardant seulement une partie des données. Vous avez à regarder l'ensemble de 128 bits et l'espace des blocs de 128 bits est trop large pour être efficace traversé.

    Maintenant MD5 ne pas faire un bon travail, comme les collisions pour que la fonction ne peut être trouvée. À partir d'un cryptographe point de vue, MD5 est une rotation fonction de cryptage. Le traitement d'un bloc de message M (512 bits) utilise une entrée de l'état V (une valeur 128 bits) et calcule le nouvel état V' V' = V + E(M, V) où '+' est un mot-wise plus, et le " E "se trouve être un chiffrement symétrique de la fonction (aka un "algorithme de chiffrement par bloc") qui utilise les M comme la clé et V que le message à chiffrer. De regarder de plus près, E est une sorte de "extension de Feistel réseau", similaire à l'algorithme de chiffrement par bloc, avec quatre trimestres au lieu de deux moitiés. Les détails ne sont pas importants ici, de mon point est que ce qui fait une "bonne" fonction de hachage, parmi les fonctions de hachage qui utilisent cette structure (appelée "Merkle-Damgård"), est similaire à ce qui fait un algorithme de chiffrement par bloc "sécurisé". Le succès des attaques par collision MD5 utilisation différentielle de la cryptographie, un outil qui a été conçu pour attaquer les algorithmes de chiffrement par bloc, en premier lieu.

    D'un bon algorithme de chiffrement par bloc pour une bonne fonction de hachage, il y a une étape qui est de ne pas être rejeté. Avec le Merkle-Damgård de la structure, de la fonction de hachage est sécurisé si le sous-jacent de chiffrement par bloc est résistant à l' "les attaques", une obscure des biens contre lequel les algorithmes de chiffrement par bloc sont rarement renforcée parce que, pour le chiffrement symétrique, les attaques n'ont aucun effet dans la pratique. Par exemple, le chiffrement AES s'est avéré ne pas être aussi résistant à la les attaques, comme on pourrait le souhaiter, et cela ne déclenche pas de panique générale. Que la résistance n'était pas partie des propriétés qui ont été recherchés pour quand AES a été conçu. Il empêche de tourner l'AES dans une fonction de hachage. Il y a une fonction de hachage appelé à Remous, qui s'appuie sur un dérivé de Rijndael, "Rijndael" étant le nom initial de ce qui est devenu l'AES; mais à Remous prend soin de modifier les pièces de Rijndael qui sont faibles pour les attaques.

    Aussi, il y a d'autres structures qui peuvent être utilisées pour la construction d'une fonction de hachage. La norme actuelle des fonctions (MD5, SHA-1, et le "SHA-2" de la famille, en l'occurence, SHA-224, SHA-256, SHA-384 et SHA-512) sont Merkle-Damgård fonctions, mais de nombreux successeurs ne le sont pas. Il y a un concours en cours, organisée par le NIST (états-unis organisation fédérale qui traite de ce genre de choses), sélectionnez une nouvelle norme en fonction de hachage, surnommé "SHA-3". Voir cette page pour plus de détails. Maintenant, ils sont en baisse de 14 candidats à partir d'une première 51 (sans compter une douzaine d'appoint qui n'a pas l'administration du test de l'envoi d'une soumission complète avec le code qui compile et s'exécute correctement).

    Nous allons maintenant avoir un niveau plus conceptuel look. Une fonction de hachage sûre devrait ressembler à un aléatoire oracle: un oracle est une boîte noire qui, lors d'un message M comme entrée, de sortie une réponse h(M) qui est choisi au hasard, de manière uniforme, en l'espace de sortie (c'est à dire tous n-des chaînes de bits si la fonction de hachage longueur de sortie est n). Si le même message M de nouveau comme entrée, l'oracle sorties de la même valeur que précédemment. En dehors de cette restriction, la sortie de l'oracle sur un non utilisés précédemment entrée M est imprévisible. On peut imaginer l'oracle comme un conteneur pour un gnome qui jette les dés, et soigneusement enregistre les messages d'entrée et de sorties correspondantes dans un grand livre, de sorte qu'il sera à l'honneur de son oracle contrat. Il n'y a aucun moyen de prédire ce que la prochaine sortie sera depuis le gnome lui-même ne sait pas qu'.

    Si un oracle aléatoire existe, puis en inversant la fonction de hachage a coûté 2^n: afin d'avoir une production donnée, il n'y a pas de meilleure stratégie que de l'aide distinctes messages d'entrée jusqu'à ce que l'on donne de la valeur attendue. Grâce à la répartition homogène de la sélection aléatoire, la probabilité de succès est 1/(2^n) à chacun d'essayer, et le nombre moyen de demandes pour le dé-lancer 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)* les sorties, on peut assembler sur 2^n paires de sortie, chacun ayant une probabilité de 1/(2^n) de correspondance, c'est à dire d'avoir deux entrées distinctes qui ont le même résultat). 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 bon comme un oracle aléatoire: ils doivent se mélanger les données d'entrée de telle façon que nous ne pouvons pas trouver une collision de manière plus efficace que ce qu'il en coûterait pour simplement appeler la fonction 2^(n/2) fois. Le fléau de la fonction de hachage est mathématique de la structure, c'est à dire des raccourcis qui permettent à l'attaquant de vue de la fonction de hachage interne de l'état (qui est grand, au moins n bits) comme une variation sur un objet mathématique qui vit dans une période beaucoup plus courte de l'espace. 30 années de recherche sur le chiffrement symétrique systèmes ont produit de tout un attirail de notions et d'outils (diffusion, les avalanches, les écarts de linéarité,...) qui peuvent être appliquées. Ligne de fond, cependant, est que nous n'avons pas de preuve qu'un oracle aléatoire peut réellement exister. Nous voulez une fonction de hachage qui ne peut pas être attaqué. Ce que nous ont sont fonction de hachage candidats, pour lesquels aucune attaque est actuellement connu, et, un peu mieux, nous avons quelques fonctions pour lesquelles certains genre d'attaque peut être prouvé de ne pas travailler.

    Il y a encore quelques recherches à faire.

    InformationsquelleAutor Thomas Pornin
  7. 3

    tableau

    Avec quelques strabisme, des tableaux associatifs ressemblent beaucoup à des tables de hachage. Les principales différences sont le manque de le symbole % sur le hachage des noms, et que l'on ne pouvait attribuer une touche à la fois. Ainsi, on pourrait dire $foo{'key'} = 1;, mais seulement @keys = keys(foo);. Familier, comme les fonctions de chacun, les clés et les valeurs travaillé comme ils le font maintenant (et de supprimer a été ajouté en Perl 2).

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

    Perl 5 a pris le pas de géant de référence pour les tableaux associatifs comme les tables de hachage. (Pour autant que je sais, c'est le premier langage ont fait référence à la structure de données ainsi, plutôt que de "table de hachage" ou quelque chose de similaire). Ironiquement, il a également pris le code de hachage.c dans l'hv.c.

    Nomenclature

    Les dictionnaires, comme expliqué précédemment, sont non ordonnée des collections de valeurs indexées par des clés uniques. Ils sont parfois appelés tableaux associatifs ou de cartes. Ils peuvent être mis en œuvre dans plusieurs façons, dont l'une est d'utiliser une structure de données appelée une table de hachage (et c'est ce que Perl fait référence à un hachage).

    Perl de l'utilisation du terme "hash" est la source d'un risque de confusion, parce que la sortie d'une fonction de hachage est également parfois appelé une table de hachage (en particulier le chiffrement des contextes), et parce que les tables de hachage ne sont pas habituellement appelé les hachages de n'importe où ailleurs.

    Pour être sur le côté sécuritaire, reportez-vous à la structure de données comme une table de hachage, et utiliser le terme de "hachage" seulement évident, Perl-contextes spécifiques.

    InformationsquelleAutor Albert