为什么不能将哈希值反转为可能的输入？

#1 楼

您缺少的是多个逻辑门可以共享同一输入的事实。因此，您不能单独查看每个逻辑门并以这种方式“反转”整个电路，因为选择逻辑门的输入可能会约束其他逻辑门的输出（因此，并非任何逻辑门的所有可能输入选择都会因此，您仍然需要以某种方式“搜索”一组令人满意的输入，您不能仅仅局部地反转每个逻辑门，因为它们都是互连的。而且此搜索空间成倍增长。

#2 楼

正确的是，加密中使用的任何哈希函数（限于固定（或有界）输入大小）都可以实现为有限数量的NOT和OR门。更重要的是：可以为门提供索引，以便任何门的输入都可以由哈希函数的输入或具有较低索引的门的输出组成；这确保了门的构造是一种功能，而不是取决于某些内部状态。而且门的数量是可管理的（对于SHA家族和单个块消息，可能按$ n = 10 ^ {5 \ pm1} $或门的顺序）。

这样可行。但至关重要的是：新的假设依赖于较早的假设，因此当我们遇到一个输出为1的或门时，它将乘以我们的假设数量3以进行跟踪（采用广度优先方法），或者在失败时进行后续探索（以深度优先的方式）。如果我们根据或门的数量$ n $检验要检验的最大假设数，则对于某个常数$ c $，其增长为$ \ mathcal O（c ^ n）$，该常数可能大大高于1。使用一个可以用3个OR门（和一些NOT）构建的XOR，我们有一个论点是$ c \ ge \ sqrt [3] 2 \ approx1.26 $用于某些可能电路的大部分（添加XOR门

因此问题中的论据证明，可以通过足够的努力反转哈希，但是没有给出相应努力的下限；我们知道得出的最佳界限是指数w.r.t.门的复杂性。事实证明，对于密码学中使用的哈希构造（例如具有160位输出和176位输入的SHA-1），此方法的成本比尝试所有可能的哈希输入（例如$ 2 ^ {176} $）高得多。 。

#3 楼

因为哈希函数实质上破坏了输入或信息。例如，哈希中的常见操作是模块化数学，基本上是除法后的余数。 9 mod 2 = 1（9/2 = 4，余数1）。 1在哈希函数中继续前进。但是模块化操作是不可逆的-剩下的就是输出1，但是潜在输入的无限数导致输出1。即使您有一个输入，在本示例中，假设9， mod 2 = 1仍然具有x的无限可能值（基本上是每个奇数）。这不同于许多其他操作（+，-，*，/等），在这些操作中，如果有输出和一个输入，则可以计算另一个输入。

#4 楼

无论采用哪种编程方式，数学单向函数都是不可逆的。
由于没有数学函数的逆函数，因此无法对其进行编程。因此答案是否定的。

当然，除了输出哈希值之外，还可能引起副作用。例如。时序信息可用于检索一些中间功能。由于散列函数通常对旁通道攻击具有相当的抵抗力，因此您可能必须对它进行编程。但是在那种情况下，您最好在应用算法之前打印出哈希函数的输入。

任何哈希函数始终可能发生的一件事就是尝试所有可能的输入，直到找到匹配。使用具有足够强度和输出的加密哈希（例如RIPEMD-160或SHA-256），如果找到匹配项，则可以确保找到原始输入。

您使用两个连续使用不同的哈希函数根本没有任何区别。

#5 楼

您的错误在这里：


OR门无法反转，因为它从根本上丢失了信息。但是，可以从任何给定的输出派生可能的输入。


可以从任何给定的输出派生一组可能的输入。对于1的每个输出，有三种可能的输入组合（01，10和11）。如果您依次添加足够的门，则输入的组合将变得巨大。例如，对于100个门或输出值为1的门，您将要查看515377520732011331036461129765621272702107522001组合（即$ 3 ^ {100} $）。或数千次，我们可以假设在任何阶段，一半的比特将是1。因此，可能的输入值数量将是组合爆炸式增长，并且可能不会少于输入域的组合总数（例如，如果您对1000字节序列进行哈希处理，即8000位，即$ 2 ^ {8000} $的可能性）。我们可以看到，哈希实际上对每个输入位至少采样了一次。

此外，我们不知道要反转的“电路”的布局。我们不知道有多少个输入位，所以我们也不知道电路中有多少个“门”来计算哈希值。

所以，是的，在感觉您可以反转哈希。但是，与遍历输入数据的每种组合相比，这将需要更多的操作，并且需要了解有关输入数据的各种知识。

#6 楼

为什么不能将哈希值反转为可能的输入呢？


实际上，取决于单个哈希值，并且明确地忽略了所有计算可行性问题，可以这样做。只是不要期望反转的结果与“原始输入”相同。

此外，您应该意识到以下事实：取决于哈希的类型和取决于密码的安全性，逆转哈希函数可能与蛮力攻击一样不切实际和/或不切实际。而不是散列秘密”，则您的散列逆转不会像破解密码那样产生任何魔力。也就是说，除非有人真的搞砸了应用程序和/或网站的安全性，并且（无论出于何种原因）忽略了经过良好审查的建议，例如可以在OWASP密码存储备忘单上找到的建议。 >我在这里出了什么问题？


没什么……好吧，除了–正如我已经指出的–好像您忘记了（或只是忽略了）所有哈希的99.9％其中的函数包括一个压缩步骤，该压缩步骤会丢失信息，因此无法逆转（除非有人真的把哈希函数设计弄得很糟）。这会阻止重构原始输入。如前所述：您可能只能获得“某些可能的输入，肯定会与原始输入有所不同”。

例如：MD5的压缩功能可以使用中间相遇攻击仅进行$ 2 ^ {100} $函数评估[1]，但这无助于重现大多数潜在的原始输入。 （尽管，这可能有助于创建原像。）

实际上，您的尝试将仅限于查找不大于哈希输出大小的“可能是”输入（读取：某些可能的输入），但是无法证明这些输入确实是原始输入，也不安全。假设哈希输入没有上限。因此，最后，您的“证明”归结为以下发现：-如果您能够反转整个哈希函数-则可以找到在应用哈希函数时会产生某些预期输出的输入。这既不是魔术，也不是真正的突破……而是简单逻辑的结果……有点像一种通过散列函数（通过构建使这一方面变得困难）返回的方式来创建一对一映射的困难方法。

打包：您的“证明”仅是有意义的，并且应用于不大于相关散列函数的输出的输入–思考：映像前攻击。由于建立了安全加密的哈希（我们倾向于在Crypto.SE上处理的哈希）是为了提供图像前抵抗力，因此提出了一个问题，即您的方法是否足够可行以至于实用–这在很大程度上取决于具体情况。实际上，您将捷径化为“秘密”的机会很少。

另一方面，您可能有一些正当的理由使您想要反转任何数据的哈希字符串，以便（例如）能够伪造该数据的输入。最后，由您决定是否真的要根据时间和资源来扭转“非秘密”哈希。在最坏的情况下，您将花费更多的时间和精力，而花费在优化的蛮力攻击的应用上……当然，这取决于所涉及的单个方案和/或单个哈希函数。 （我只添加后面的内容，因为存在更简单，类似校验和的非加密安全哈希，这些哈希可能为更可行的方案提供了基础。）


[1]加密领域：第15届年度国际研讨会，SAC 2008 –第121页

#7 楼

您尝试反驳不是哈希函数功能的东西。您始终可以通过尝试所有给定长度的所有可能的输入，直到找到给定哈希的原像，来蛮力执行哈希函数。

密码哈希函数的主张是，计算上难以实现找到这样的原像。实际上，对于任何哈希函数在实际使用中都没有证明这一主张（取决于猜想，复杂度等级P和NP不相同。

#8 楼

解决该问题的另一种方法是从通信角度。 。这可能意味着您可以通过通道发送哈希，然后在另一端将其还原。那将几乎是通过通道的无限传输和无限的压缩。该定理也适用于压缩，它限制了可以达到的最大压缩率。超出此限制，将无法传输或压缩更多数据。

#9 楼

想象一个简单的哈希函数。就像我在构建字典时曾经见过的用于对字符串进行哈希处理的“取一个”一样：将所有字符的ASCII或Unicode值相加，然后将余数取一些相当大的n取模，通常是适合整数的最大值。 />
我可以轻松地编写一个函数来生成ASCII字符串，该字符串对于任何给定的输出都是“可能的输入”：选择任何字符，例如“ z”。将哈希值除以ASCII的“ z”。使用商来生成那么多的z。使用其余的产生一个字符。如果我们想要可打印的ASCII，则如果该字符小于32，则删除一个z，将z的ASCII值相加，除以2，然后将该字符加两个。如果还有余数，请在第二个中加一个。我将其旋转到头顶上，因此，如果我错过了一个细节，很好，我敢肯定，可以解决。

是的，哈希函数的本质是不可能最终找到原始输入。在我刚刚讨论过的字符串哈希的示例中，取模算术步骤意味着存在无限数量的可能字符串映射到相同的值。如果哈希值是16位，并且我们的输入字符串可以超过16位，则可能有比输入更多的输入，因此显然多个输入必须映射到同一输出，因此不能确定地反转。但是，如果您是试图查找密码的黑客，则不必担心您是否拥有“真实”密码。哈希值正确的任何字符串都可以帮助您，这就是您所需要的。因此是“可能的输入”。

显然，更复杂的哈希函数将需要更复杂的逆转方法。但是问题是：构造一个散列函数是否如此复杂，以至于任何反向函数都比强力方法固有地需要更多的计算，即尝试所有可能的输入，直到找到能提供所需输出的哈希函数？ />
据我了解，用于密码的哈希函数确实符合这种条件。但是我从未见过这种证明。是真的在数学上证明了这是不可能的，还是只是没有人找到解决方法？

#10 楼

您可以找到一个与原始输入具有相同哈希值的输入。但是取决于所讨论的哈希值和运气，它可能需要整个宇宙数万亿甚至更多年的计算能力。如果输入确实是随机的并且足够大，则散列没有已知的漏洞，并且很难计算，您将必须对所有可能的输入进行散列，直到找到给出相同输出的输入为止。除非您非常幸运，或者拥有一台无限高速的计算机，或者使用一些技巧，例如在0.99999999999c上行驶数年，而相对于您静止的行星上的计算机正在猜测（几年（或任何时间））您的时间将接近无穷大当您接近光速时，就不能（就我们所知，达到光速也没有无限的时间流动，但是您可以任意接近和任意接近无穷大，对于大多数意图和目的，无穷大都是相同的）

如果哈希容易受到更快的攻击，或者输入/输出非常小，或者恰好您拥有无限的计算资源，则可以比1秒内更快地完成。 。

然而，不可能的是（至少一般而言...哈希可能很糟糕，并且可以保证一个输入值具有相同的输出，如果原始值是那个输入值，则可以。有关于输入的额外信息...您知道输入是4让ter英语单词对所有4个字母的英语单词进行哈希处理，如果只有一个与您的未知输入具有相同的哈希，则为输入），证明您计算的输入与原始输入相同。

您如果您希望使用一些过时的哈希值，这些哈希值实际上很容易在普通PC上受到蛮力攻击，则可以在家中尝试此操作。下载MDcrack之类的内容并尝试。

#11 楼

这是证明您的“证明”的非常简单的方法。

我有一个2输入或门。输出为“ 1”。告诉我如何反转输入A和B的确切输入组合。是01、10还是11？仅当门的输出为'0'时才具有确定性。

您可以使用此方法消除一些可能的位条件，但是复杂度很快变得太大，以至于不值得。 br />