为什么无法反向加密哈希？

Question

为什么无法反向加密哈希？

hashcryptographymd5cryptographic-hash-functionreversing

39

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

如果使用彩虹表，使用盐巳经无法破解它，是什么原因呢？如果您在用暴力方式制作彩虹表，那么它会生成每个明文可能的值（到一定长度），这将包括每个可能密码和每个可能盐的盐值（盐和密码/文本只需作为一个单独的文本串出现）。

- Keavon

1

请查看维基百科关于地图哈希的文章。 - Ulrich Dangel

1

@mru：地图哈希？你是指像地理哈希那样的吗？ - Nemo

1

@Nemo，打错字了，我不能再编辑我的评论了。我想说的是加密技术：/至少链接是正确的。 - Ulrich Dangel

1

可能是MD5哈希值为什么不可逆？的重复问题。 - Mr. Bultitude

我听说破解哈希的难度在于CPU的限制。每当有更好的CPU问世，它就能够计算出更高的质数。因此，通过将巨大的质数相乘，生成一个大数，需要一个更快（不存在的）CPU才能解密它。这是一个循环游戏，每当一个CPU足够强大以破解旧哈希时，它同时也足够强大以创建一个无法破解的哈希。 - myself

5个回答

31

从1到9999中选择2个数字进行相加，然后告诉我结果的最后一位数字。

根据这些信息，我无法推出你最初想到的数字。这是单向哈希的一个非常简单的例子。

但是，我可以想到两个数字产生相同的结果，这就是这个简单示例与像MD5或SHA1这样的“适当”的加密哈希不同的地方。对于这些算法，计算上制造出产生特定哈希的输入应该很困难。

- Paul Dixon

3

哇，现在我明白了。这是一个非常好和简单的表述方式。谢谢！ - Keavon

4

由于数据丢失，您不能反转哈希函数。考虑一个简单的示例函数：“OR”。如果将其应用于1和0的输入数据，则会产生1。但是，现在，如果您知道答案是“1”，如何回溯原始数据呢？你不能。它可能是1,1或者0,1，或者1,0。

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

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

- Gabe Durazo

哇，我明白了。我习惯于看到盐（对于一个名为Flyff的MMO，我曾经花时间进行私人服务器工作）非常短，像Flyff的是"kikugalanet"，相对较短。但是感谢您提供制作长且完全随机哈希的提示。我仍然有点困惑于答案的第一部分关于数据如何丢失的问题。如果是两者之一，1或0，它如何匹配哈希？不过还是非常感谢您的好回答！ - Keavon

1

我认为 md5 并没有提供完整的结果，因此您无法通过反向工作来查找原始 md5。

- Steve

2

即使是一对一，反转也不一定容易。例如考虑两个大质数的乘积...MD5难以反转，但这与多对一无关。 - Nemo

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的存储空间来存储彩虹表。唯一能够破解密码的原因是人们使用明显的密码。

- Karoly Horvath

不完全正确。那是你需要预先计算的数据量。彩虹表不是一个简单的查找表。整个重点在于它是时间和空间存储之间的权衡。例如，如果您有长度为1,000,000的链，它将占用您建议的空间的1,000,000分之一，但需要比简单查找长1,000,000倍的时间（仍然相对较快）。对于您上面引用的数字，这只需要67 MB或5.2 GB。不错吧？但是再次提醒，有两个注意事项：1.计算表格的时间仍然非常长2.（续） - Jeremy Salwen

彩虹表实际上是统计学的。所以你不会得到“大小写字母和数字”的任何密码，但根据减法函数碰撞的可能性、给予彩虹表的尺寸填充以及你期望需要多大的概率来获得更好的概率，你会得到一定百分比的密码，如99.8或其他。 - Jeremy Salwen

是的，我指的是链接，但不需要存储每个密码。这个想法是你有一个减少函数，它将哈希输出带回到密码域。所以对于每个链，我存储（初始密码，最终哈希）。现在，如果链的长度为1,000,000，则这意味着在连续1,000,000次进行哈希和减少函数后，最终哈希就是我得到的结果。现在，要检查密码，我取哈希值，将其与每个链的末尾进行比较。如果不匹配，我就取哈希值的减少函数，再次哈希，再次比较等，最多重复1,000,000次。 - Jeremy Salwen

如果在任何时候我在其中一个链上找到了匹配项，那么我将从该链的初始密码开始，并继续进行哈希和减少函数，直到找到与我正在寻找的原始哈希相匹配的哈希。现在，我只需记住我给哈希函数的输入以获得该输出，我就有了正确的密码。关键是我要链式下降1,000,000次，因此如果我在这1,000,000次迭代中的任何地方产生了原始密码，我可以从原始密码向下跟随链以找到值和哈希。 - Jeremy Salwen

谢谢！使用加盐密码的时候该怎么做？在重新应用哈希函数之前，您会对已经哈希化的值进行加盐处理，对吗？ - Karoly Horvath

准确地说，关键是在开始生成彩虹表之前必须知道盐的值，并且您不能重复使用已生成的表，因为每个表都是特定于每个盐的。本质上，这使得彩虹表变得无用。 - Jeremy Salwen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeremy Salwen · Accepted Answer

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

假设我们有数字"7"，我们想获取它的哈希值。也许我们尝试的第一件事是将其乘以二作为我们的哈希函数。正如我们将看到的，这不是一个非常好的哈希函数，但我们将尝试它，以说明一个观点。在这种情况下，数字的哈希值将是"14"。这很容易计算。但现在，如果我们看看它的反向有多难，我们发现它同样容易！给定任何哈希值，我们只需将其除以二即可获取原始数字！这不是一个好的哈希值，因为哈希的整个重点是计算反向比计算哈希更困难（这至少在某些环境中是最重要的属性）。

现在，让我们尝试另一个哈希函数。为此，我将介绍时钟算术的概念。在时钟上，数字并不是无限的。实际上，它只从0到11（请记住，在时钟上，0和12是相同的）。因此，如果你将11加1，则会得到0。你可以将乘法、加法和指数扩展到时钟上。例如，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的数字，这样做是可行的。但对于实际哈希函数的模拟，假设涉及的数字都是巨大的。虽然计算这些大数字的哈希函数仍然相对容易，但搜索所有可能的输入会更快地变得更加困难。但你发现的仍然是一个非常重要的思想：在输入空间中搜索一个可以提供匹配输出的输入。彩虹表是这个思想的一个更复杂的变体，它使用预先计算的输入-输出对的智能表格，以便能够快速搜索大量可能的输入。

现在假设你正在使用哈希函数在计算机上存储密码。思路是这样的：计算机只存储正确密码的哈希值。当用户尝试登录时，将输入密码的哈希值与正确密码的哈希值进行比较。如果它们匹配，您就认为用户有正确的密码。之所以这样做是有优势的，是因为如果有人窃取了您的计算机，他们仍然无法访问您的密码，只能获得它的哈希值。因为哈希函数是由聪明人设计成难以逆转的，所以他们无法轻易地从中检索出您的密码。

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

现在，关于盐的想法是这样的：如果两个用户有相同的密码，那么它们将具有相同的哈希值。如果你仔细想一下，攻击者实际上并不必单独破解每个用户的密码。他只需遍历每个可能的输入密码，并将哈希与所有哈希进行比较。如果其中一个匹配，那么他就找到了一个新的密码。我们真正想要迫使他做的是为他想要检查的每个用户+密码组合计算一个新的哈希值。这就是盐的概念，即让哈希函数对每个用户略微不同，以便他无法为所有用户重用单个预计算值集。最直接的方法是在取哈希之前为每个用户的密码添加一些随机字符串，其中随机字符串对于每个用户都不同。例如，如果我的密码是“shittypassword”，我的哈希值可能显示为MD5（“6n93nshittypassword”），如果你的密码也是“shittypassword”，你的哈希值可能显示为MD5（“fa9elshittypassword”）。这个小位“fa9el”称为“盐”，对于每个用户都不同。例如，我的盐是“6n93n”。现在，这个附加到你的密码上的小位也被存储在你的计算机上。当你尝试使用密码X登录时，计算机只需计算MD5（“fa9el”+X）并查看它是否与存储的哈希匹配。

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

1. 忽略哈希值被加盐的事实，并尝试使用原来的查找表破解密码。然而，他们真正破解密码的几率大大降低了。例如，即使"shittypassword"在他们要检查的输入列表中，很可能"fa9elshittypassword"并不在其中。为了获得与以前相同的破解密码概率，他们需要测试数倍于以前的可能密码。

2. 他们可以按用户重新计算哈希值。因此，对于每个用户X，他们计算MD5（Salt_of_user_X + passwordguess），而不是计算MD5（passwordguess）。这不仅迫使他们为每个要破解的用户计算新的哈希值，而且最重要的是，它防止他们能够使用预先计算的表（例如彩虹表），因为他们无法预先知道Salt_of_user_X是什么，所以他们无法预先计算要测试的哈希值。

因此，基本上，如果他们试图使用预先计算的表，使用盐有效地增加了他们必须测试以破解密码的可能输入，并且即使他们不使用预先计算的表，它仍然使他们减速N倍，其中N是您存储的密码数量。

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