hash - 为什么无法逆转加密哈希？

Question

为什么不能像反转数学函数那样仅反转算法？如何使算法不可逆？

而且，如果您使用彩虹桌，是什么使使用盐无法破解它呢？如果要使用蛮力生成彩虹表以生成彩虹表，则它会发明每个可能的明文值(一定长度)，最终将包括每个可能的密码的salt和每个可能的salt(salt和密码/文本会只是作为一个单一的文本在一起)。

Answer 1

MD5被设计为cryptographically irreversible。在这种情况下，最重要的属性是在计算上找不到散列的反向项是不可行的，但是很容易找到任何数据的散列。例如，让我们考虑仅对数字进行运算(毕竟，二进制文件可以解释为非常长的数字)。

假设我们有数字“7”，并且我们想取其哈希值。作为哈希函数，我们尝试的第一件事可能是“乘以2”。正如我们将看到的那样，这不是一个很好的哈希函数，但是我们将尝试一下以说明问题。在这种情况下，数字的哈希将为“14”。那很容易计算。但是现在，如果我们看一下逆转它有多么困难，我们发现它也一样容易!给定任何哈希，我们可以将其除以2得到原始数!这不是一个很好的哈希，因为哈希的全部要点是，与计算哈希相比，计算逆值要困难得多(这至少在某些情况下是最重要的属性)。

现在，让我们尝试另一个哈希。对于这一点，我将不得不介绍时钟算法的思想。在时钟上，没有无数个数字。实际上，它只是从0到11(请记住，时钟上的0和12相同)。因此，如果您将11“加一”，您将得到零。您可以将乘法，加法和求幂的思想扩展到一个时钟。例如，8 + 7 = 15，但时钟上的15实际上只是3!因此，在时钟上，您会说8 + 7 = 3! 6 * 6 = 36，但在时钟上，36 = 0!所以6 * 6 = 0!现在，对于权力的概念，您可以做同样的事情。 2 ^ 4 = 16，但是16只是4。所以2 ^ 4 = 4!现在，这是它与哈希关联的方式。我们如何尝试哈希函数f(x)= 5 ^ x，但采用时钟算法。如您所见，这将导致一些有趣的结果。让我们尝试像以前一样取7的哈希值。

我们看到5 ^ 7 = 78125，但是在时钟上，只有5个(如果进行数学计算，您会发现我们已经将时钟全天包裹了6510次)。因此我们得到f(7)= 5。现在的问题是，如果我告诉您我的号码的哈希值为5，您是否能够确定我的号码为7？好吧，在通常情况下，实际上很难计算此函数的逆函数。比我聪明的人证明，在某些情况下，反转此功能比向前计算要困难得多。 (编辑:Nemo指出，这实际上尚未得到“证明”；实际上，您所获得的唯一保证是，许多聪明的人已经花了很长时间尝试找到一种简便的方法来做到这一点，其中的一个已成功完成。)反转此操作的问题称为“Discrete Logarithm Problem”。查找更多深度覆盖。至少这是一个好的哈希函数的开始。

对于现实世界的哈希函数，其思想基本相同:您发现一些难以逆转的函数。比我聪明得多的人设计了MD5和其他哈希值，以使它们难以逆转。

现在，也许是更早的时候您想到了:“计算逆数会很容易!我只是对每个数字进行哈希处理，直到找到匹配的数字!”现在，对于数字都小于十二的情况，这将是可行的。但是对于真实世界的哈希函数的模拟，可以想象所有涉及的数字都是巨大的。这个想法是，为这些大数字计算散列函数仍然相对容易，但是搜索所有可能的输入变得更加困难。但是，您偶然发现的仍然是一个非常重要的想法:在输入空间中搜索将提供匹配输出的输入。 Rainbow表是该思想的一个更​​复杂的变体，它以灵巧的方式使用输入-输出对的预先计算的表，以便可以快速搜索大量可能的输入。

现在，假设您正在使用哈希函数将密码存储在计算机上。这个想法是这样的:计算机只存储正确密码的哈希值。当用户尝试登录时，您将输入密码的哈希值与正确密码的哈希值进行比较。如果它们匹配，则假定用户具有正确的密码。之所以具有优势，是因为如果有人窃取了您的计算机，他们仍然无权访问您的密码，而仅是密码的哈希值。由于哈希功能是聪明人设计的，很难做到相反，因此他们无法轻松地从中检索密码。

攻击者的最佳选择是蛮力攻击，他们尝试一堆密码。就像您可能在上一个问题中尝试输入小于12的数字一样，攻击者可能会尝试由长度小于7个字符的数字和字母组成的所有密码，或字典中显示的所有单词。这里重要的是他不能尝试所有可能的密码，因为例如，有太多可能的16个字符的密码无法测试。因此，重点在于，攻击者必须限制他测试的可能密码，否则，他甚至不会检查其中的一小部分。

现在，关于盐，这个想法是这样的:如果两个用户使用相同的密码怎么办？它们将具有相同的哈希值。如果您考虑一下，攻击者实际上不必单独破解每个用户的密码。他只需输入所有可能的输入密码，然后将哈希与所有哈希进行比较。如果它与其中之一匹配，则他找到了一个新密码。我们真正想强制他做的是为他要检查的每个用户+密码组合计算一个新的哈希。这就是“撒盐”的想法，即您使每个用户的哈希函数略有不同，因此他不能为所有用户重复使用一组预先计算的值。最简单的方法是在进行哈希处理之前，在每个用户的密码上添加一些随机字符串，其中每个用户的随机字符串都不同。因此，例如，如果我的密码是“shittypassword”，则我的哈希值可能会显示为MD5(“6n93nshittypassword”)，而如果您的密码是“shittypassword”，则您的哈希值可能会显示为MD5(“fa9elshittypassword”)。这一点“fa9el”被称为“盐”，并且对于每个用户而言都是不同的。例如，我的盐是“6n93n”。现在，密码上的这一小部分也将存储在您的计算机上。当您尝试使用密码X登录时，计算机只能计算MD5(“fa9el” + X)并查看其是否与存储的哈希匹配。

因此，登录的基本机制保持不变，但是对于攻击者而言，他们现在面临着更为艰巨的挑战:与其列出MD5哈希值，不如列出MD5哈希值和盐值。它们本质上有两个选择:

他们可以忽略哈希值已加盐的事实，并尝试按原样使用其查找表来破解密码。但是，他们实际破解密码的机会大大减少了。例如，即使“shittypassword”在其要检查的输入列表中，也很可能没有“fa9elshittypassword”。为了获得以前破解密码的可能性的很小百分比，他们需要测试更多数量级的可能密码。

他们可以基于每个用户重新计算哈希值。因此，他们不为每个用户X计算MD5(passwordguess)，而是计算MD5(Salt_of_user_X + passwordguess)。这不仅迫使他们为他们想要破解的每个用户计算一个新的哈希，而且最重要的是，这阻止了他们使用预先计算的表(例如，彩虹表)，因为他们不知道什么。 Salt_of_user_X已经存在，因此他们无法预先计算要测试的哈希。

因此，基本上，如果他们尝试使用预先计算的表，则有效地使用salt可以极大地增加他们为了破解密码而必须测试的可能输入，即使他们未使用预先计算的表，也仍然会使它们变慢因数N，其中N是要存储的密码数。

希望这能回答您的所有问题。