Question:
Ne pourrions-nous pas créer une chaîne qui produit le même hachage qu'une autre chaîne dans SHA-256?
BOI
2020-08-12 01:23:27 UTC
view on stackexchange narkive permalink

Disons que nous avons un algorithme de hachage séparé appelé s2 et qu'il convertirait Hello en dug84nd8.

Si nous pouvions prendre l'algorithme et juste faire de l'ingénierie inverse pour générer une chaîne comme 8GN492MD qui afficherait également dug84nd8 , ne dirait-il pas que (s2 ("Hello") = s2 ("8GN492MD ")) == true) , et laisser un hacker entrer?

J'ai l'impression de manquer quelque chose, mais je ne sais pas ce que c'est.

Notez que cela n'est pas appelé "décryptage" car vous ne récupérez pas la chaîne d'origine - juste une autre chaîne qui hache à la même valeur.Contrairement au cryptage, les hachages ne peuvent pas être inversés
"J'ai l'impression qu'il me manque quelque chose '... Regardez cette vidéo et vous verrez ce qui vous manque: https://www.youtube.com/watch?v=y3dqhixzGVo
Est-ce que cela répond à votre question?[Pourquoi les fonctions de hachage sont-elles à sens unique?Si je connais l'algorithme, pourquoi ne puis-je pas calculer l'entrée à partir de celui-ci?] (Https://security.stackexchange.com/questions/11717/why-are-hash-functions-one-way-if-i-know-l'algorithme-pourquoi-ne-puis-je-calculer-t)
Notez que pour les algorithmes de hachage de mot de passe plus faibles, il est fréquent qu'un outil de hachage de mot de passe force brutalement un hachage et trouve un mot de passe qui n'était pas le mot de passe d'origine, mais comme il a le même hachage, il sera accepté.Cependant, avec des hachages plus forts / plus longs, cela ne se voit pas car vous ne pouvez pas exécuter une recherche exhaustive et la probabilité de renforcer brutalement une deuxième pré-image est très faible.
@Gilles'SO-stopbeingevil' pas une dupe de celui-là.L'OP n'essaie pas de calculer l'entrée d'origine.
@schroeder L'OP tente de calculer une pré-image, qui est exactement la même que la question précédente.
@Gilles'SO-stopbeingevil' De la dupe proposée: "Ne peut-il pas simplement inverser le processus pour calculer le mot de passe à partir du hachage?"Cela semble être une attaque différente et une question différente.Cette question concerne 2 entrées avec le même hachage, ne calculant pas «Hello» à partir de «dug84nd8»
Oui, tu peux faire ça.As-tu essayé?Si vous essayez, vous pourriez trouver des obstacles étranges sur votre chemin.Considérez maintenant que personne n'a encore réussi à contourner ces obstacles.Ils l'ont fait pour les anciennes fonctions de hachage comme MD5, c'est pourquoi nous n'utilisons plus d'anciennes fonctions de hachage.
Bien sûr que vous pourriez.
La réponse (oui, c'est pourquoi vous devez choisir un bon algorithme) ne serait-elle pas sur la première page de tout tutoriel sur le hachage?
Oui.C'est ce qu'on appelle une collision de hachage.C'est intrinsèque au hachage.De bons algorithmes de hachage rendront extrêmement difficile la cause d'une collision.
Treize réponses:
#1
+73
abligh
2020-08-12 11:00:25 UTC
view on stackexchange narkive permalink

Votre prémisse a un défaut. Vous dites que vous voulez «désosser» la fonction de hachage. Il n'est pas nécessaire de procéder à une ingénierie inverse - son implémentation est publique.

Ce que vous ne pouvez pas faire, c'est l'inverser (c'est peut-être ce que vous vouliez dire), car elle n'est pas inversible. Vous pouvez facilement dire que ce n'est pas une fonction inversible car la taille du domaine (nombre possible d'entrées) est supérieure à la taille de la plage (nombre possible de sorties). La plage est de 2 ^ 256 (états de sortie possibles) et la taille de l'espace d'entrée est infinie (techniquement 2 ^ (2 ^ 64) apparemment, mais beaucoup plus grande que 2 ^ 256). Et c'est précisément ce qui permet les collisions (selon le principe du casier, il doit y avoir plus d'une entrée possible pour chaque sortie - au moins pour l'une des entrées).

L'ensemble de la conception de la fonction de hachage la rend calculatrice difficile de trouver ces collisions. Il y a trois propriétés de hachage (première résistance pré-image, deuxième résistance pré-image et résistance aux collisions) qui décrivent cette propriété plus exactement.

La réponse à votre question est donc que la conception de la fonction rend il est volontairement difficile d'y parvenir même si vous savez exactement comment la fonction fonctionne.

Pour plus de détails (dans un contexte légèrement différent) sur la façon dont les fonctions peuvent fonctionner de manière surprenante (pourquoi, par exemple, il est impossible de "revenir en arrière "pour les inverser), consultez les réponses ici.

La plage est 2 ^ 256 et la taille de l'espace d'entrée est infinie. Si l'espace d'entrée est infini, il y a un nombre infini de collisions.∞ / 2²⁵⁶ = ∞ ...
@d-b oui, mais techniquement, il n'est pas nécessaire qu'il y ait une collision infinie (ou même plus d'une) pour chaque valeur de sortie;il se peut qu'un sous-ensemble de valeurs de sortie n'ait qu'une seule valeur d'entrée possible, voire aucune.Je soupçonne qu'il n'est pas possible de prouver s'il existe un nombre infini de collisions pour chaque valeur de sortie pour SHA-256 bien que je soupçonne que c'est le cas.
La taille de l'espace d'entrée n'est pas tout à fait infinie, elle est de 2 ^ (2 ^ 64) puisque la taille de l'entrée est ajoutée avant de prendre le hachage.Non pas que vous ayez une contribution plus importante que cela.
@d-b et pourtant, [les collisions ne se produisent pas vraiment] (https://crypto.stackexchange.com/a/47810/62225).
@CaptainMan C'est parce que 2 ^ 256 ≈ le nombre d'atomes dans l'univers visible.
_ "ce n'est pas une fonction inversible car la taille du domaine est supérieure à la taille de la plage" _ - Vous parlez de [la ** définition mathématique ** des fonctions à sens unique] (https: //en.wikipedia.org / wiki / Injective_function), mais ce n'est pas ce qui est pertinent ici.La [** définition cryptographique **] (https://en.wikipedia.org/wiki/One-way_function) est _ "une fonction qu'il est impossible d'inverser d'un point de vue informatique" _.Le fait que l'inverse soit une fonction à valeurs multiples n'a pas d'importance.
@rtpax IIRC, c'est le compte _bit_ jusqu'à 2 ^ (2 ^ 64).L'espace d'entrée est donc _only_ 2 ^ (2 ^ 61) _bytes_.Ouf, cela devrait aider un _bit_.
Premièrement, l'espace d'entrée SHA256 est limité en raison du standard de remplissage du NIST.On peut hacher au plus 2 ^ 64 bits donc il y a au plus 2 ^ (2 ^ 64) messages différents.2, vous vous trompez sur le principe du casier.Il dit seulement qu'il y a au moins un casier qui a plus d'un pigeon.Il ne parle pas des autres qui peuvent être vides ou non.Avec cela, nous pouvons dire qu'au moins il doit y avoir une collision.Bien sûr, idéalement, nous nous attendons à ce que SHA256 soit une fonction aléatoire uniforme.
AilifprtakCMT corrigé.
Je ne vois pas que les changements sont faits différemment.De plus, même nous ne savons pas que SHA256 assiste toutes les valeurs si nous découpons la sortie de SHA256 en 64 bits.Ce que nous savons, sa sortie semble aléatoire uniforme.
#2
+20
kelalaka
2020-08-12 03:52:41 UTC
view on stackexchange narkive permalink

Vous mélangez les attaques sur les fonctions de hachage. La définition formelle des attaques génériques contre les fonctions de hachage cryptographique peut être trouvée dans Bases de la fonction de hachage cryptographique: définitions, implications et séparations pour la résistance à la pré-image, la résistance à la seconde pré-image et la résistance à la collision par P. Rogaway et T. Shrimpton. Peut simplement être donné comme;

  • L'attaque pré-image : étant donné une valeur de hachage h , trouvez un message m tel que h = Hash (m) . Pensez à stocker les hachages des mots de passe sur le serveur. Par exemple. un attaquant tentera de trouver un mot de passe valide pour votre compte.

  • La deuxième attaque pré-image (également appelée collision faible) : étant donné un message m1 , recherchez un autre message m2 tel que m1 ≠ m2 et Hash (m1) = Hash (m2) . Un exemple est la production d'une falsification d'un message donné.

  • L'attaque par collision (également appelée collision forte) : trouvez deux entrées qui hachent le même sortie: a et b tels que H (a) = H (b) , a ≠ b .

SHA-256 n'est pas encore cassé pour aucune de ces attaques génériques. Voir: Qu'est-ce qui rend SHA-256 sécurisé? sur crypto.stackexchange.

si nous pouvions prendre l'algorithme et simplement le reverse engineering pour générer une chaîne comme 8GN492MD qui afficherait également dug84nd8

  • Si nous ne considérons que cela, il s'agit d'une attaque pré-image et le coût est O (2 ^ 256) pour SHA-256. Notez que le but de l'attaque pré-image n'est pas de trouver l'entrée d'origine, mais plutôt de trouver une entrée qui a la même valeur de hachage. S'il n'y a pas de test externe pour l'entrée, on ne peut pas décider que la pré-image trouvée est la pré-image. Et, l'espace de recherche réel pour la pré-image peut être beaucoup plus grand que les poignées d'attaque de pré-image.

    Il existe une variante de l'attaque pré-image, qui se produit lorsque l'espace du message est court, comme le hachage des numéros de téléphone. Dans ce cas, il peut être très facile de trouver la pré-image.

Si nous pouvions prendre l'algorithme et le désosser pour générer une chaîne comme 8GN492MD cela afficherait également dug84nd8 , ne dirait-il pas que (s2 ("Hello") = s2 ("8GN492MD")) == true) , et laisser un hacker dans?

  • Si nous considérons ci-dessus en termes plus simples; donné Bonjour et dug84nd8 = SHA256 (Bonjour) et trouvez un autre message avec la même valeur de hachage que vous avez demandé, alors c'est la deuxième attaque de pré-image et le coût est de O (2 ^ 256) pour SHA256.

La deuxième pré-image est ce que vous recherchez. C'est irréalisable et non seulement SHA-256 mais également aucune des fonctions de hachage cryptographique n'est interrompue de cette manière.

  • Le coût d'attaque par collision de SHA-256 est O (2 ^ 128 ) en raison de l ' attaque d'anniversaire avec une probabilité de 50%. Dans l'attaque par collision, les attaquants sont libres de choisir le a et le b . Ce n'est pas votre cas puisque vous commencez avec un message fixe.

Conclusion , aucune de ces attaques n'est possible pour SHA-256 à partir de 2020.


Les erreurs dans la réponse la plus haute

La plage est de 2 ^ 256 (états de sortie possibles ) et la taille de l'espace d'entrée est infinie (techniquement 2 ^ (2 ^ 64) apparemment, mais beaucoup plus grande que 2 ^ 256). Et c'est précisément ce qui permet les collisions (selon le principe du casier, il doit y avoir plus d'une entrée possible pour chaque sortie - au moins pour l'une des entrées).

L'espace d'entrée SHA256 est limité en raison de la norme de rembourrage du NIST. On peut hacher au plus 2 ^ 64 bits donc il y a au plus 2 ^ (2 ^ 64) messages différents puisque la taille du message est encodée à la fin du remplissage en 64 bits.

Le principe du casier dit seulement qu'il y a au moins un casier qui a plus d'un pigeon. Il ne parle pas des autres qui peuvent être vides ou non. Avec cela, nous pouvons dire qu'au moins il doit y avoir une collision. Fait intéressant, nous ne savons pas qu'un SHA256 limité à 64 bits atteint toutes les valeurs 64 bits. Ce que nous attendons de SHA256, c'est qu'il ne peut être distingué de l'uniformément aléatoire.

Vous pouvez facilement dire que ce n'est pas une fonction inversible car la taille du domaine (nombre possible d'entrées) est supérieure à la taille de la plage (nombre possible de sorties).

Ce n'est pas non plus correct. Prenez modulo 2 ^ 256 comme hachage, alors il est non inversible. Cependant, une personne ayant une valeur de hachage peut calculer facilement une pré-image, étant donné x , a ;; x + k 2 ^ 265 sont des pré-images. En d'autres termes, nous avons inversé la carte. La définition correcte est une fonction qu'il est impossible d'inverser d'un point de vue informatique

Je me souviens avoir trouvé un site Web où quelqu'un a pris le sha-256 de "Hello, world!"et en a fait une ficelle
De plus, je ne choisis pas les chaînes au hasard, je rétroconce toutes les portes not et xor et ainsi de suite pour créer une chaîne réalisable.
@BOI faire cela pour les algorithmes de hachage modernes est littéralement impossible.Essayer des chaînes aléatoires jusqu'à ce que vous trouviez une correspondance est la seule option
@BOI: Si vous êtes effectivement capable de faire cela, deux choses vont se passer: 1) Vous deviendrez très célèbre, parce que vous avez réussi à faire quelque chose que toute la communauté crypto essaie et échoue depuis 20 ans.2) Quelqu'un analysera votre attaque et concevra une nouvelle fonction de hachage qui corrigera la faille qui permet votre attaque.Les attaques les plus connues actuellement sur SHA-256 ne concernent que des variantes à round réduit.
@BOI Je vous encourage à l'essayer et à voir ce qui se passe!
SHA256 a attiré beaucoup d'attention grâce à Bitcoin.
@BOI Essentiellement, même _si_ vous parveniez à trouver une valeur hachée à la même valeur que SHA256 ("Hello, world!"), Cela ne donnerait accès qu'aux comptes qui utilisaient "Hello, world!"comme mot de passe - qui si vous saviez de quels comptes il s'agissait, vous pourriez simplement utiliser "Hello, world!"et évitez toute agitation avec les collisions de hachage.Et cela suppose également que le service protégé n'a pas pris d'autres précautions de base comme le salage.Et qu'ils utilisent directement SHA256, non itératifs, d'autres algorithmes, etc.
@JörgWMittag "Quelqu'un analysera votre attaque et concevra une nouvelle fonction de hachage qui corrige la faille" est une croyance optimiste plutôt qu'un fait.Ce n'est pas nécessairement vrai que nous pouvons toujours faire cela.
#3
+10
freakish
2020-08-12 11:32:50 UTC
view on stackexchange narkive permalink

et laisser un hacker entrer?

Bien sûr. Mais le problème est que nous ne savons pas comment trouver une autre chaîne qui produit le même hachage de manière efficace. Au moins pour SHA-256 et d'autres algorithmes de hachage largement utilisés. Notez que ces algorithmes sont publics, aucune rétro-ingénierie n'est nécessaire, ce qui ne change rien. C'est tout simplement trop difficile, et en fait ces algorithmes sont délibérément conçus de cette manière.

Tout le problème se résume à résoudre l'équation f (x) = y pour une fonction f et une autre y. Une possibilité est de balayer tous les x, en supposant que le domaine est énumérable. Mais c'est inefficace et ne fonctionne que si nous savons déjà qu'une solution existe (je ne suis pas sûr que toutes les valeurs de SHA soient atteintes plusieurs fois). D'autres possibilités sont souvent inconnues.

C'est peut-être un problème éducatif. À l'école, on nous dit souvent de résoudre des équations. Linéaire, polynomiale, logarithmique, sinusoïdale, etc. Ce qu'ils ne vous disent pas, c'est qu'ils choisissent ces équations de manière à pouvoir les résoudre et de manière relativement simple. Mais en fait, même maintenant, les esprits les plus brillants ne savent pas comment résoudre la plupart des équations. Et ici, vous êtes tombé sur un tel exemple (extrêmement important).

Notez que la situation peut (et l'a déjà fait pour d'autres fonctions de hachage) changer à l'avenir.

Nous * savons * comment trouver une autre chaîne qui produit le même hachage.Au moins, vous avez la force brute.Nous ne savons tout simplement pas comment faire cela dans une contrainte de temps / énergie réalisable.
@LawnmowerMan J'ai mis à jour la réponse.Cependant, je ne sais pas si le forçage brutal est garanti.C'est à dire.si chaque sortie a plus d'une pré-image.
Peut-être pas, mais la force brute peut le prouver aussi.;)
@LawnmowerMan uniquement sous l'hypothèse que l'univers est fini.:)
@freakish Eh bien, est-ce que nous nous soucions réellement de trouver une entrée _différente_?Nous recherchons une entrée et supposons simplement que nous trouverons une entrée alternative (en collision) plus rapidement que l'entrée d'origine (aussi, supposément que nous n'avons même pas un moyen de la vérifier).Trouver l'entrée d'origine est tout aussi bon, en ce qui concerne le piratage.
@freakish, la question de savoir s'il est garanti de s'arrêter n'est normalement pas une question majeure.Si vous le réglez pour s'arrêter après par ex.$ 2 ^ 260 $ essaie, vous avez presque 100% de chances de trouver au moins une (seconde) pré-image.Mais de toute façon, ce sera après la vie de l'univers, donc cela ne sert à rien.
#4
+5
Nick2253
2020-08-12 19:16:41 UTC
view on stackexchange narkive permalink

Je pense que la réponse de @ kelalaka est la plus précise, mais je voulais ajouter un exemple qui pourrait, espérons-le, éclairer le problème.

Tout d'abord, vous êtes tout à fait exact que vous pourriez suivez toute la logique du circuit et finalement obtenez une collision. Cependant , l'une des caractéristiques d'une bonne fonction de hachage cryptographique est que cet exercice est substantiellement aussi difficile que de simplement deviner au hasard.

Considérez le circuit suivant . M1-M3 sont les bits du message. Étant donné un message 101 et une graine de 1 , nous obtenons une sortie de 1.

Three chained XORs in a circuit.

Maintenant, essayons de trouver un message différent qui entre en collision avec 101 en retraçant le circuit. D'après la sortie, nous savons que M3 pourrait être 1 ou 0 . Prenons 0 ; cela signifie que l'autre jambe doit être 1 ( 1 XOR 0 est 1 ). Nous arrivons maintenant à M2. Nous choisirons également 0 à nouveau. Maintenant, nous regardons M1. Nous choisirons 1 pour M1. Mais, euh-oh. La valeur de départ devrait maintenant être 0 . 100 ne fonctionne comme un message que si la graine est 0.

Évidemment, dans cet exemple très simpliste, nous aurions pu simplement assigner de manière triviale M1 à être 0 , et alors notre graine aurait été 1 comme prévu. Mais le but de cet exemple est de mettre en évidence les éléments de rétroaction et de chaînage qui rendent cette approche simple de «retracer le circuit» beaucoup plus compliquée dans un véritable algorithme de hachage cryptographique. Le «circuit» requis pour implémenter ces algorithmes est extrêmement compliqué, car il consiste en multiplication, exponentiation, arithmétique modulaire, etc. Et le caractère récursif de certains de ces calculs fait du tracé du circuit vers l'arrière un exercice de branchement massif. Encore une fois, ce n'est pas impossible; c'est plutôt aussi difficile que de deviner au hasard.

pourquoi le fait d'avoir la graine 0 est-il un problème?
@BOI Parce que la graine étant «1» fait partie de l'algorithme de hachage tel que je l'ai décrit.Si vous vouliez que la graine soit «0», ce serait bien, mais ce serait une fonction de hachage différente, produisant des hachages différents.
#5
+4
user3067860
2020-08-12 21:48:58 UTC
view on stackexchange narkive permalink

"Essayer au hasard jusqu'à ce que vous trouviez une entrée qui produit le hachage correct." Oui, mais c'est toujours une attaque par force brute. C'est la prémisse d'une attaque rainbow table. Précalculez les valeurs de manière à avoir une entrée pour chaque sortie possible. Ensuite, au lieu d'essayer toutes les entrées possibles, vous ne pouvez essayer qu'un sous-ensemble d'entrées qui produisent des hachages uniques. Peu importe que vous obteniez l'entrée exacte qui était le mot de passe d'origine, car le système ne peut pas faire la différence.

Voici les problèmes:

  1. Vous avez pour trouver l'entrée pour chaque hachage. Comme d'autres réponses l'ont dit, c'est "assez lent" avec les fonctions de hachage modernes puisqu'il ne s'agit que de force brute. (Sauf si vous avez un ordinateur quantique assis.) Le principal avantage d'une table arc-en-ciel est que pour les fonctions où vous POUVEZ calculer cela, vous pouvez les calculer toutes une fois et réutiliser les résultats encore et encore sans recalculer (échanger l'espace de stockage toutes ces valeurs pour le gain de temps de ne pas avoir à les recalculer).
  2. Vous n'obtenez pas le mot de passe réel. Dans de nombreux cas, les gens attaquent des systèmes moins sécurisés non pas parce qu'ils veulent s'introduire dans ces systèmes, mais pour profiter des personnes qui réutilisent les mots de passe / connexions sur d'autres systèmes plus intéressants.
  3. Si l'attaquant ne le fait pas connaître le hachage cible et doit vérifier par rapport au système cible, puis il peut être bloqué en limitant le nombre de tentatives incorrectes. (L'attaquant connaissant le hachage cible peut être bloqué par d'autres pratiques de sécurité de base.)
  4. Salt. Ajout d'une autre chaîne unique à l'utilisateur au mot de passe avant de le hacher. Par exemple, disons que nous ajoutons le nom d'utilisateur à la fin du mot de passe avant de le hacher. Maintenant, nous devons trouver une chaîne qui, lorsque le nom d'utilisateur est ajouté à la fin, se calcule en un hachage. Étant donné que le nom d'utilisateur est unique pour chaque utilisateur, nous ne pouvons pas précalculer cela en masse, nous revenons à le faire un par un ... très inefficace, c'est-à-dire prend énormément de temps.
Je suppose qu'il était beaucoup plus facile de simplement hacher un mot de passe comme hash ("hello123");puis forcez les adresses e-mail ou noms d'utilisateur jusqu'à ce que vous trouviez quelqu'un d'assez stupide pour utiliser "hello123" comme mot de passe
Votre premier paragraphe est la description la plus lisible des tableaux arc-en-ciel que j'ai vue.Grâce à vous, je les comprends enfin.J'ai parcouru Wikipedia et plusieurs longs articles "explicatifs", et aucun d'entre eux n'a été aussi utile que les deux phrases du milieu de ¶1.
@Michael Heureux d'avoir pu aider!
@Michael Bien que tout le reste soit valide, cette réponse n'explique pas correctement les tables arc-en-ciel.Ils ne stockent pas une entrée pour chaque sortie possible (ce serait plus de téraoctets que d'étoiles dans l'univers, même pour MD5.) Les tables arc-en-ciel impliquent de précalculer (disons) un million de hachages et de stocker (disons) 1000 d'entre eux.En utilisant un algorithme intelligent, ces millions peuvent être reconstruits en utilisant beaucoup de travail - mais beaucoup * moins * de travail que la force brute pure.Les tables arc-en-ciel sont simplement un levier pour attaquer des mots de passe un peu plus longs lorsqu'il est impossible de stocker des tables précalculées de cette taille.
@Artelius Phooey.Merci de clarifier.
#6
+3
fraxinus
2020-08-12 12:08:08 UTC
view on stackexchange narkive permalink

Vous mélangez probablement "rétro-ingénierie" et recherche d'une "fonction inverse". Ce sont des concepts différents.

L'ingénierie inverse déduit l'algorithme de son implémentation (fermée). L'algorithme SHA-256 est public et vous pouvez ignorer complètement la partie de rétro-ingénierie. Regardez simplement dans Wikipedia, ou le code source d'une bibliothèque de crypto open source.

Afin de casser la crypto (dans votre cas, pour trouver une "collision de hachage"), vous devez trouver un " fonction inverse "- dans le même sens mathématique que la racine carrée est la fonction inverse du carré.

Les algorithmes de hachage utilisés pour la cryptographie sont spécifiquement conçus pour résister à la recherche de collisions et de fonctions inverses. Si quelqu'un trouve un moyen facile de trouver des collisions, la fonction de hachage correspondante est considérée comme compromise et les gens cessent de l'utiliser. C'est ce qui est arrivé aux fonctions MD5 ou SHA-1.

Il existe d'autres fonctions de hachage (par exemple destinées à être utilisées dans les tables de hachage de la base de données) qui ne sont PAS conçues pour être aussi résistantes aux collisions, mais qui sont moins chères en calcul et / ou présentent d'autres avantages. Ils sont toujours appelés hachages, mais sont utilisés dans leurs champs respectifs et non en cryptographie.

Par une fonction inverse, j'essaierais de trouver chaque fonction que sha-256 a, et par exemple une porte NOT, je choisirais une entrée aléatoire, qui reviendrait en arrière jusqu'à ce qu'il y ait une chaîne de travail
@BOI bonne chance.Si vous réussissez, j'ai quelques idées pour devenir très riche avant de publier vos résultats.
@BOI il y a beaucoup de portes dans SHA-256.Si vous essayez des entrées aléatoires pour toutes, vous essaierez beaucoup d'entrées aléatoires avant de trouver celles qui fonctionnent.N'oubliez pas que plusieurs portes ont toutes la même entrée, donc une entrée qui fonctionne pour une porte peut ne pas fonctionner pour une porte différente.
@BOI la raison pour laquelle cela ne fonctionne pas c'est parce que vous ne pouvez pas le faire bit par bit, comme dans une fonction cryptographique généralement chaque bit de sortie est / peut être influencé par * chaque * bit d'entrée.Cela réduit un "choisir une entrée aléatoire et revenir en arrière si c'est faux" à une recherche de tous les espaces de clés possibles, car "l'entrée aléatoire" doit être l'entrée * entière * et obtenir une bonne par hasard est 1/2 ^ 256= effectivement zéro.
#7
+2
Artelius
2020-08-14 11:18:57 UTC
view on stackexchange narkive permalink

Détruire des informations

Lors du calcul d'une fonction de hachage, les informations sont détruites à certaines étapes de l'algorithme. C'est la raison pour laquelle vous ne pouvez pas «exécuter l'algorithme à l'envers».

Si vous commencez par le hachage ccb92793f8a87a695fa3f2e805779da8 , en travaillant à l'envers, il peut y avoir des milliards de possibilités de comment l'étape précédente vous a amené à cette valeur. Pas de problème - choisissez-en un et passez à l'étape suivante; même affaire. Après plusieurs étapes, vous atteignez un point où vous êtes bloqué et ne pouvez pas aller plus loin; vous avez atteint un état intermédiaire impossible. Vous devez donc revenir en arrière et faire un choix différent et vos milliards commencent à se multiplier. S'il y a suffisamment d'étapes, cela devient plus difficile que de forcer brutalement les entrées, alors autant faire cela à la place.

La destruction d'informations n'empêche pas l'attaquant de trouver les pré-images plus rapidement que la force brute.Par exemple, prenez [MD5] (https://security.stackexchange.com/a/225227/86735)
#8
+1
rexkogitans
2020-08-12 13:22:47 UTC
view on stackexchange narkive permalink

Toutes les autres réponses sont toutes correctes et couvrent certains aspects, néanmoins je veux montrer une autre approche.

Ce que vous avez découvert - plus ou moins accidentellement - est le lien inévitable entre fonctions de hachage et le principe du casier .

Si vous regardez les définitions, c'est assez évident:

  • Une fonction de hachage est un mappage d'un domaine contenant des données de taille arbitraire sur des données (un tableau de bits) de taille fixe.
  • Le principe du casier dit: s'il y en a plus pigeons que des trous, alors il doit y avoir au moins un trou avec au moins deux pigeons à l'intérieur.

Pour le domaine d'entrée, vous pouvez avoir des mots de passe plus longs et de longueur variable, et le jeu de symboles est généralement plus grand (lettres minuscules et majuscules, chiffres, certains symboles). Ce sont les pigeons.

Le nombre de valeurs de hachage possibles est facile à calculer: si la longueur est n sur b symboles, alors il y a b ^ n hachages possibles (vous pouvez définir b = 2 pour compter morceaux). Ce sont les trous de pigeons.

Donc, vous avez plus de pigeons (données d'entrée possibles) que de trous (valeurs de hachage possibles), et il doit donc y avoir au moins un pigeon ( données d'entrée possibles) placées dans (mappées sur) un trou (une valeur de hachage).

Bien sûr, dans ce cas, la fonction n'est jamais injective, et donc pas bijective, et donc pas inversible.

«Non inversible» ne signifie pas que vous ne pouvez pas trouver * une * entrée avec une sortie donnée.
@user253751 Par "non inversible", j'entends le sens mathématique, strictement formel, comme dans g est la [fonction inverse] (https://en.wikipedia.org/wiki/Inverse_function) de f si et seulement si g (f (x)) = x pour tout x du domaine d'entrée.Une telle fonction g n'existe pas si f n'est pas bijective.Bien sûr, la force brute est toujours possible.
#9
+1
Martijn
2020-08-12 13:38:46 UTC
view on stackexchange narkive permalink

C'est trop pour un commentaire, alors je vais l'ajouter comme réponse:

Une petite astuce qui pourrait aider: disons que votre algorithme est $ a * $ b , si vous avez 3 et 4, vous obtenez 3 * 4 = 12 . Vous avez maintenant le résultat que vous ne pouvez pas inverser (était-ce 1&12, 2&6, 3&4, 4&3, 6&2 ou 12&1?), Mais il a de multiples collisions. Dans ce cas, 6 entrées différentes donneraient le même résultat, donc nous avons 6 collisions.

Une 'astuce' pour minimiser cette chance (qui ne sera jamais nulle si vous avez un nombre fini de caractères du résultat hash) ajoute plus de bits. Cela signifie que le résultat sera par exemple 1862534 pour 3&4 en entrée, et 2&6 pourrait devenir 6793439 .

#10
  0
Martin Rosenau
2020-08-14 23:32:44 UTC
view on stackexchange narkive permalink

Disons que nous avons un algorithme de hachage séparé appelé s2 et qu'il convertirait Hello en dug84nd8.

.. une chaîne comme 8GN492MD qui afficherait également dug84nd8 ...

Ce que vous décrivez est une "collision de hachage".

Et oui: dans ce cas, Hello et 8GN492MD seront acceptés comme mots de passe valides.

J'ai l'impression qu'il me manque quelque chose , mais je ne sais pas ce que c'est.

Premièrement:

Vous n'avez pas écrit que l'attaquant connaît la valeur de hachage ( dug84nd8 ). Cependant, il semble évident que vous vouliez l'écrire.

Deuxièmement:

En théorie, il serait toujours possible de trouver une chaîne comme 8GN492MD qui a dug84nd8 comme sortie si vous aviez assez de puissance de calcul (peut-être un gros ordinateur quantique).

Cependant, les fonctions qui sont utilisées pour calculer la chaîne 8GN492MD à partir de la chaîne dug84nd8 ce sont des «fonctions à sens unique».

Ce sont des fonctions qui peuvent être calculées assez facilement sur un ordinateur «normal»; cependant, on ne sait pas s'il est possible du tout de calculer la fonction inverse (trouver la chaîne 8GN492MD lorsque la chaîne dug84nd8 est connue) dans un temps réaliste (par exemple moins de 10 ans).

Et bien sûr, on ne sait pas non plus comment cela peut être fait si cela devrait être possible.

En effet, il arrive parfois qu'un mathématicien trouve un moyen comment trouver une collision. Cela signifie que le mathématicien trouve un moyen de trouver la chaîne Hello ou 8GN492MD lorsque la chaîne dug84nd8 est donnée.

Si cela se produit, vous ne pouvez plus utiliser la fonction de hachage (la fonction calculant la valeur dug84nd8 à partir de la valeur Bonjour ) et vous devez remplacer la fonction de hachage par une autre . Sinon, vous aurez un problème de sécurité.

#11
-1
clockw0rk
2020-08-13 14:12:27 UTC
view on stackexchange narkive permalink

D'autres ont mentionné l'utilisation des termes «ingénierie inverse» et «attaque», etc., donc je ne répondrai pas à cela. Mais pour votre question:

Considérez hash (a) = x;

Vous connaissez maintenant x . Disons que vous avez accès à une immense puissance de calcul, comme un botnet, ou peut-être une ferme de serveurs géante. Maintenant, en théorie, vous pouvez commencer à produire des hachages, c'est-à-dire hash (b) = y; hash (c) = z et ainsi de suite. Avec suffisamment de temps, vous pourriez probablement trouver une fonction hash (something) = x . Donc, vous compareriez les sorties les unes aux autres jusqu'à ce que vous trouviez une paire correspondante.

Personnellement, je ne sais pas combien de temps cela prendrait, mais je pense que ce serait possible. Mais, je suppose qu'il existe de meilleures façons de voler un mot de passe, comme une tentative d'ingénierie sociale, ou par effraction sur la machine du client plutôt que sur le serveur.

Vous avez expliqué "l'attaque par collision" qui est déjà couverte par d'autres réponses.
je veux dire revenir en arrière dans l'algorithme pour trouver une correspondance
"Revenir en arrière dans l'algorithme" n'est pas une chose qui se produit plus que "juste l'entropie inversée".
#12
-1
Zsolt Szilagy
2020-08-14 22:26:05 UTC
view on stackexchange narkive permalink

Il existe de nombreuses réponses techniques intéressantes. Je vais essayer de fournir quelque chose de plus approchable: un exemple.

Imaginez, mon algorithme secret est le suivant:

  • Je prends un nombre d'entrée,
  • ajoutez tous les chiffres,
  • multipliez la somme par chaque chiffre,
  • puis répétez le processus.

Donc 234 reviendrait à (2 + 3 + 4) + 2 * 3 * 4 = 216. (2 + 1 + 6) * 2 * 1 * 6 = 108. Ce 108 est le hachage. Avec votre compréhension de mon algorithme , pouvez-vous calculer un nombre qui finit par être 108? Si vous ne pouvez pas, vous devez deviner. Cela semble facile ici, mais imaginez que ces nombres comportent des milliers de chiffres ...

Avertissement: je suis nul en maths, vous pouvez probablement le casser. SHA est une autre bête.

#13
-3
slebetman
2020-08-12 10:51:26 UTC
view on stackexchange narkive permalink

La plupart des algorithmes de hachage sont à sens unique car si vous inversez le fonctionnement des algorithmes de hachage, ils agiront également comme un algorithme de hachage (peut-être pas un bon algorithme).

Disons par exemple que vous avez un algorithme appelé SHA256 () . Et vous implémentez ensuite une fonction avec exactement l'opération inverse de celle-ci appelée REVERSE_SHA256().

Ce qui va se passer est que la sortie de REVERSE_SHA256 (SHA256 (INPUT)) ne correspondra pas au INPUT:

  INPUT = "some string" HASH = SHA256 (INPUT); OUTPUT = REVERSE_SHA256 (HASH); OUTPUT! = INPUT  

Non seulement cela, mais pour une fonction de hachage cryptographiquement sécurisée, la OUTPUT ne peut pas être reformulée à la même valeur:

  HASH2 = SHA256 (OUTPUT); HASH2! = HASH  

Le fait qu'un tel algorithme puisse exister est la raison pour laquelle les fonctions de hachage cryptographique existent.

Je ne pense pas que cela réponde à la question, car OP a explicitement posé la question de générer une chaîne qui aboutit au même hachage, donc `HASH2! = HASH` contredit l'hypothèse de l'OP.OP n'a pas non plus mentionné le simple retour de la séquence d'opérations de l'algorithme de hachage.
@RaimundKrämer Il répond à la partie où l'OP veut générer la chaîne en inversant simplement les opérations de la fonction de hachage.Vous et moi comprenons que ce n'est pas possible - que la seule façon de générer une telle chaîne est d'essayer toutes les chaînes possibles jusqu'à ce que vous en trouviez une avec le même hachage.L'OP ne comprend pas qu'il peut y avoir des algorithmes qui ne sont pas réversibles même lorsque vous inversez les opérations de l'algorithme.
SHA256 (REVERSE_SHA256 ("Some hash")) doit être "Some hash" par définition.Vous ne pouvez pas dire que SHA256 (REVERSE_SHA256 (HASH))! = HASH parce que votre fonction REVERSE_SHA256 est *** cassée *** (comme dans, ne fonctionne pas).
Que signifierait-il pour une fonction d'être «à sens unique»?Non injectif?Les fonctions non-injectives ne résolvent pas la question d'OP.
@user253751 C'est tout le but de ma réponse.Que la construction d'une fonction inverse telle que proposée par l'OP ne fonctionnera pas - c'est-à-dire que la fonction inverse est nécessairement interrompue.L'OP suppose qu'il existe un moyen d'inverser le hachage en procédant à une ingénierie inverse des mécanismes derrière la génération du hachage.J'essaie de montrer que pour certains algorithmes - en particulier les algorithmes que nous considérons comme des fonctions de hachage cryptographiques, une telle ingénierie inverse conduit à des résultats absurdes.
@slebetman Vous dites d'abord que `REVERSE_SHA256 (SHA256 (INPUT))! = INPUT` ce qui est assez juste.(Vous ne le montrez pas, en fait, mais vous le * dites *).Ensuite, vous dites que `SHA256 (REVERSE_SHA256 (HASH))! = HASH`, ce qui est clairement incorrect.Une chaîne n'a pas plus d'un hachage SHA256.
Premièrement: "Si je trouve une chaîne dont le hachage est le même hachage que bonjour, il se peut que ce ne soit pas bonjour" - vrai.Deuxième: "Si je trouve une chaîne dont le hachage est abcdef012345, alors son hachage n'est pas abcdef012345."- faux.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 4.0 sous laquelle il est distribué.
Loading...