37

为什么不能像反转数学函数一样反转算法？怎么可能制作一个不可逆的算法？

如果你使用彩虹桌，是什么让使用盐无法破解它？如果您正在使用蛮力制作彩虹表来生成它，那么它会发明每个可能的明文值（到一定长度），最终将包括每个可能密码和每个可能盐的盐（盐和密码/文本将只是作为一个单一的文本组合在一起）。

4

5 回答 5

72

MD5 被设计为加密不可逆。在这种情况下，最重要的属性是在计算上找到哈希的反向是不可行的，但是很容易找到任何数据的哈希。例如，让我们考虑只对数字进行操作（毕竟二进制文件可以解释为一个很长的数字）。

假设我们有数字“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 吗？嗯，在一般情况下，实际上很难计算这个函数的倒数。比我聪明得多的人已经证明，在某些情况下，反转这个函数比向前计算要困难得多。（编辑：尼莫指出，这实际上并没有被“证明”；事实上，你得到的唯一保证是很多聪明人已经尝试了很长时间来找到一种简单的方法，但没有一个他们成功了。） 反转这个操作的问题被称为“离散对数问题”。查找它以获得更深入的报道。这至少是一个好的散列函数的开始。

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

现在，您可能更早地想到了：“计算倒数很容易！我只需对每个数字进行哈希处理，直到找到匹配的那个！” 现在，对于数字都小于十二的情况，这将是可行的。但是对于现实世界的哈希函数的模拟，想象所有涉及的数字都是巨大的. 这个想法是，计算这些大数字的散列函数仍然相对容易，但是搜索所有可能的输入变得更快更难。但是您偶然发现的仍然是一个非常重要的想法：在输入空间中搜索将提供匹配输出的输入。彩虹表是这个想法的一个更复杂的变体，它以智能的方式使用预先计算的输入-输出对表，以便可以快速搜索大量可能的输入。

现在假设您正在使用哈希函数在您的计算机上存储密码。这个想法是这样的：计算机只存储正确密码的哈希值。当用户尝试登录时，您将输入密码的哈希值与正确密码的哈希值进行比较。如果它们匹配，则假定用户具有正确的密码。这是有利的原因是因为如果有人窃取了您的计算机，他们仍然无法访问您的密码，只能访问它的哈希值。因为哈希函数是聪明人设计的，很难反其道而行之，所以他们不能轻易地从中取回您的密码。

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

现在，至于盐，想法是这样的：如果两个用户有相同的密码怎么办？它们将具有相同的哈希值。如果您考虑一下，攻击者实际上并不需要单独破解每个用户的密码。他只是简单地检查所有可能的输入密码，并将哈希值与所有哈希值进行比较。如果它与其中一个匹配，那么他已经找到了一个新密码。我们真正想强迫他做的是为每个他要检查的用户+密码组合。这就是盐的想法，就是你让每个用户的哈希函数略有不同，所以他不能为所有用户重用一组预先计算的值。最直接的方法是在获取哈希之前为每个用户的密码添加一些随机字符串，其中每个用户的随机字符串不同。因此，例如，如果我的密码是“shittypassword”，我的哈希可能会显示为 MD5（“6n93nshittypassword”），如果您的密码是“shittypassword”，那么您的哈希可能会显示为 MD5（“fa9elshittypassword”）。这一点“fa9el”被称为“盐”，每个用户都不同。例如，我的盐是“6n93n”。现在，附加在您密码上的这一点也只是存储在您的计算机上。当您尝试使用密码 X 登录时，计算机可以计算 MD5("fa9el"+X) 并查看它是否与存储的哈希匹配。

所以登录的基本机制保持不变，但对于攻击者来说，他们现在面临着更艰巨的挑战：他们面临的不是 MD5 哈希列表，而是 MD5 和和盐的列表。他们基本上有两种选择：

  1. 他们可以忽略哈希被加盐的事实，并尝试使用他们的查找表来破解密码。但是，他们实际破解密码的可能性大大降低。例如，即使“shittypassword”在他们要检查的输入列表中，很可能“fa9elshittypassword”不在。为了获得破解密码的可能性的一小部分，他们需要测试更多可能的密码数量级。

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

所以基本上，如果他们尝试使用预先计算的表格，使用盐有效地增加了他们为了破解密码而必须测试的可能输入，即使他们没有使用预先计算的表格，它仍然会减慢他们的速度N 的因子，其中 N 是您存储的密码数量。

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

于 2011-07-06T23:35:44.587 回答
28

想想从 1 到 9999 的 2 个数字。将它们相加。现在告诉我最后一个数字。

我无法从这些信息中推断出您最初想到的数字。这是一个非常简单的单向哈希示例。

现在，我可以想到两个给出相同结果的数字，这就是这个简单示例与 MD5 或 SHA1 等“正确”加密散列不同的地方。使用这些算法，想出一个产生特定散列的输入在计算上应该是困难的。

于 2011-07-06T22:46:23.500 回答
4

无法反转散列函数的一个重要原因是数据丢失。

考虑一个简单的示例函数：'OR'。如果将其应用于 1 和 0 的输入数据，它会产生 1。但是现在，如果您知道答案是“1”，那么如何回退原始数据？你不能。它可能是 1,1，也可能是 0,1，或者可能是 1,0。

至于盐渍和彩虹桌。是的，理论上，您可以拥有一个包含所有可能的盐和密码的彩虹表，但实际上，这太大了。如果您尝试了小写字母、大写字母、数字和 12 个标点符号的所有可能组合，最多 50 个字符，则有 (26+26+10+12)^50 = 2.9 x 10^93 种不同的可能性。这比可见宇宙中的原子数量还要多。

彩虹表背后的想法是提前计算一堆可能的密码的哈希值，而密码比 50 个字符短得多，所以这样做是可能的。这就是为什么要在前面添加盐的原因：如果在密码前面添加“57sjflk43380h4ljs9flj4ay”。虽然有人可能已经计算出“pa55w0rd”的哈希值，但没有人会计算出“57sjflk43380h4ljs9flj4aypa55w0rd”的哈希值。

于 2011-07-06T22:47:20.923 回答
1

我不认为 md5 给你完整的结果 - 所以你不能向后工作来找到 md5-ed 的原始东西

于 2011-07-06T22:35:18.327 回答
1

md5 是 128 位，即 3.4*10^38 组合。

八个字符长度密码的总数：

  • 只有小写字符和数字：36^8 = 2.8*10^12
  • 小写和大写和数字：62^8 = 2.18*10^14

您必须为密码存储 8 个字节，为 md5 值存储 16 个字节，即每个条目总共 24 个字节。

所以你的彩虹桌需要大约 67000G 或 5200000G 的存储空间。实际上可以找出密码的唯一原因是人们使用明显的密码。

于 2011-07-06T22:47:29.570 回答