为什么不能反转加密哈希？

Question

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

如果你使用彩虹桌,是什么让使用盐不可能破解它？如果你用蛮力制作彩虹表来生成它,那么它就会发明每个明文值(到一个长度),最终会包含每个可能密码的盐和每个可能的盐(盐和密码/文本会只是作为单个文本聚集在一起).

Answer 1

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吗？那么,它实际上是非常难计算在一般情况下,这个函数的反函数.很多人比我聪明证明,在某些情况下,扭转这种功能的方式不是向前计算更难.(编辑:Nemo指出,事实上这并没有"证明";事实上,你得到的唯一保证是很多聪明的人已经尝试了很长时间才能找到一个简单的方法,而且没有一个它们已成功.) 逆转此操作的问题称为" 离散对数问题 ".查找更深入的报道.这至少是良好散列函数的开始.

使用真实世界哈希函数,这个想法基本相同:你发现一些难以逆转的功能.比我聪明的人设计了MD5和其他哈希,使他们难以扭转.

现在,或许早些时候你已经想到了这样的想法:"计算倒数很容易!我只需要拿出每个数字的哈希值,直到找到匹配的数字!" 现在,对于数字都小于12的情况,这是可行的.但是对于真实世界哈希函数的模拟,想象所涉及的所有数字都是巨大的.我们的想法是,计算这些大数字的哈希函数仍然相对容易,但搜索所有可能的输入变得更加困难得多.但是你偶然发现的仍然是一个非常重要的想法:在输入空间中搜索输入,这将提供匹配的输出.彩虹表是这个想法的一个更复杂的变体,它以智能方式使用输入 - 输出对的预先计算表,以便能够快速搜索大量可能的输入.

现在让我们假设您使用哈希函数在您的计算机上存储密码.这个想法是这样的:计算机只存储正确密码的哈希值.当用户尝试登录时,您将输入密码的哈希值与正确密码的哈希值进行比较.如果匹配,则假定用户具有正确的密码.这是有利的原因是因为如果有人窃取了您的计算机,他们仍然无法访问您的密码,只能访问您的密码.由于哈希函数是由聪明人设计的,很难反过来,因此无法从中轻松检索密码.

攻击者最好的选择是暴力攻击,他们会尝试一堆密码.就像你可能会尝试在前一个问题中少于12的数字一样,攻击者可能会尝试所有由长度小于7个字符的数字和字母组成的密码,或者在字典中显示的所有单词.这里重要的是他不能尝试所有可能的密码,因为有太多可能的16个字符密码,例如,要进行测试.所以重点是攻击者必须限制他测试的可能密码,否则他甚至都不会检查它们中的一小部分.

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

因此登录的基本机制保持不变,但对于攻击者来说,他们现在面临着更艰巨的挑战:他们面临的是MD5总和和盐的列表,而不是MD5哈希列表.它们基本上有两种选择:

1. 他们可以忽略散列被腌制的事实,并尝试按原样使用查找表破解密码.但是,他们实际破解密码的可能性大大降低.例如,即使"shittypassword"在他们要检查的输入列表中,很可能"fa9elshittypassword"不是.为了获得他们以前破解密码的可能性的一小部分,他们需要测试更多可能的密码.

2. 他们可以按用户重新计算哈希值.因此,不是为每个用户X计算MD5(passwordguess),而是计算MD5(Salt_of_user_X + passwordguess).这不仅迫使他们为他们想要破解的每个用户计算新的哈希值,而且最重要的是,它阻止他们使用预先计算的表(例如彩虹表),因为他们无法知道什么Salt_of_user_X是预先设定的,因此无法预先计算哈希值以进行测试.

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

希望这能解答您的所有问题.

Answer 2

想想1到9999之间的2个数字.加上它们.现在告诉我最后的数字.

根据这些信息,我无法推断出您最初想到的数字.这是单向散列的一个非常简单的例子.

现在,我可以想到两个给出相同结果的数字,这就是这个简单示例与"正确"加密哈希(如MD5或SHA1)的区别.使用这些算法,在计算上难以提出产生特定散列的输入.