哈希如何工作？

#1 楼

快速，系数1081。

或者，如果您愿意，回答这个问题：47的23倍是多少？执行乘法（仅机械地遵循规则）要比仅给定乘积的操作数恢复要容易。乘法。 （顺便说一下，这是某些加密算法（例如RSA）的基础。）

加密散列函数具有不同的数学基础，但是具有相同的属性：它们很容易向前计算（在给定x的情况下计算H（x）），但实际上不可能进行向后的计算（给定y，计算x使得H（x）= y）。实际上，良好的密码哈希函数的标志之一就是找到x的方法没有比尝试所有x和计算H（x）直到找到匹配项更好的方法。哈希函数的含义是两个不同的输入具有不同的哈希。因此，如果H（x1）= H（x2），我们可以得出x1 = x2的结论。从数学上讲，这是不可能的-如果输入的长度大于哈希的长度，则必须发生冲突。但是具有良好的加密哈希函数，没有找到与世界上所有计算资源冲突的已知方法。

如果您想了解更多有关加密哈希函数的信息，请阅读Thomas的答案色情继续，我等。

请注意，哈希函数不是加密函数。加密意味着您可以解密（如果您知道密钥）。有了哈希，没有神奇的数字可以让您返回。

推荐的主要加密散列函数是SHA-1和SHA-2系列（有几种输出大小，主要是SHA-256和SHA-512）。 MD5是较旧的版本，由于已知冲突而已弃用。最终，没有任何数学证据证明它们确实是很好的加密哈希函数，只是一种普遍的看法，因为许多专业密码学家已经花费了数年的时间尝试并失败以破坏它们。

好，故事的一部分。现在，密码哈希不直接是密码哈希函数。密码哈希函数（PHF）接受两个输入：密码和盐。用户选择密码时，随机生成盐，并将其与哈希密码PHF（密码，盐）一起存储。 （重要的是，两个不同的帐户始终具有不同的盐，并且随机产生足够大的盐是具有压倒性概率拥有此属性的一个好方法。）当用户再次登录时，验证系统将从密码数据库中读取盐，计算PHF（密码，盐），并验证结果是否存储在数据库中。他们必须先了解哈希，然后才能分别攻击每个帐户。盐使得不可能提前进行很多裂解工作，例如

这将回答（2）和（3）—合法验证者和攻击者以相同的方式找出密码（由用户输入还是由攻击者猜测） ） 是正确的。故事的最后一点：好的密码哈希函数还具有其他属性，它必须很慢。合法服务器只需要在每次登录尝试时对其进行一次计算，而攻击者则必须在每次猜测时对其进行一次计算，因此，这种缓慢性会给攻击者带来更大的伤害（这是必要的，因为攻击者通常拥有更多的专用硬件）。 >
如果您需要对密码进行哈希处理，请不要发明自己的方法。使用标准方法之一：scrypt，bcrypt或PBKDF2。

#2 楼

加密哈希函数是数学对象，可以描述为“某些位的大量混合和加扰”。它们将一系列位（可能是一个很长的位）作为输入，并提供固定大小的输出。粗略地讲，它们是如此纠结，以至于尽管它们没有什么秘密（这只是确定性的代码），但是没有人知道如何“反转”它们（为给定的输出找到匹配的输入），除非被称为“运气”的基本方法。 “：尝试随机输入，直到找到匹配项。

从科学上讲，散列函数完全可以存在是怎么一个问题。 。哈希没有秘密，没有密钥。

哈希函数有很多用途；其中之一是“密码存储”。哈希函数对于密码存储来说似乎是一件好事。我们不想直接存储密码（否则，攻击者偶尔会偷看我们的数据库会给他太多信息；请参阅此博客文章进行讨论）；我们要存储密码验证令牌：一种用于验证密码（由用户提供）但不透露密码本身的东西。因此，想法是：让我们存储密码的哈希值。当要验证密码时，我们只计算其哈希值，看看它是否与存储的值匹配。但是仅凭哈希值猜测密码很难，因为哈希函数可以抵御“反转”（请参见上文）。 ），为了确保适当的安全，我们需要一个“增强型”哈希函数：


我们想要一个非常慢的哈希函数。散列函数，以便每个密码将使用其自己的散列函数进行散列；这是关于阻止并行攻击。将单个哈希函数转换为多种变体的过程称为“盐化”。

有关哈希密码主题的详细信息，请参见此答案。

#3 楼

散列是从某个位字符串（通常是可变长度）到另一个位字符串（通常是较小且具有固定长度）的函数。结构称为哈希表。它使我们能够将任意数据（例如字符串或具有许多字段的复杂对象）简化为二进制数，然后可以将其直接用作稀疏数组的索引以获取关联的数据（具有一些用于处理哈希的详细信息冲突）。

以上述方式使用的哈希函数是密码哈希函数的“表亲”。它们针对不同的要求而设计。它们必须快速计算并获得良好的分布。

在安全计算中，加密散列用于将数据摘要成一些有代表性的小比特串。密码功能有不同的要求。它们的设计难以反转（成为“活板门”或“单向”功能）。不仅如此，一个重要的要求是，对于给定的纯文本和哈希值，必须很难找到另一个产生相同哈希的纯文本。

哈希不仅可以用于密码，但作为校验和以验证数据完整性，并且是数字签名实施的一部分。要对大型文档进行数字签名，我们只需要对文档进行哈希处理就可以产生一个“摘要”（当对很长的内容进行哈希处理时，该名称用于哈希函数的输出）。然后，仅将此摘要通过公钥密码系统生成签名。您可以在其中看到缺点：如果攻击者成功生成摘要相同的文档怎么办？然后，看起来好像是在真实文件上产生的原始签名实际上是伪造文件的签名：签名转移伪造已得到有效实施。

密码哈希允许系统不存储密码的纯文本版本，但使系统能够验证试图获得输入的用户是否知道该密码。散列不仅允许系统不存储纯文本密码（必须非常谨慎地加以保护），而且还允许即使散列是公开公开的，密码仍然是安全的（类似于公钥加密方式）系统能够公开公钥）。尽管在实践中，哈希仍然受到公共访问的保护：例如，在类Unix系统上的/etc/shadow文件，补充了世界范围内可读的/etc/passwd文件。但是，可以采用随机方法来阻止攻击者建立大量的密码和哈希字典，使他们能够查找哈希码并检索相应的密码。

要更安全地哈希密码，我们可以简单地向它添加一些随机位，称为“盐”。当然，将不同的盐添加到同一密码中会导致产生不同的哈希值（希望冲突很少或没有冲突）。

如果随机盐的宽度为32位，则从理论上讲，这意味着一个密码可以以40亿种不同的方式进行哈希处理，因此很难预先获得包含所有可能值的预先计算的字典大量密码的哈希值。

当然，在对用户进行身份验证时，她对这种盐一无所知。可以，因为盐与哈希一起存储在用户的配置文件中（通常与哈希一起存储在单个紧凑的位串中）。验证用户的密码输入后，会将盐添加到她输入的任何密码中，以便使用正确的盐进行哈希处理。如果密码正确，则哈希将匹配，因为使用的盐也是正确的，已从用户的配置文件中提取。

这样就可以将随机性合并到密码哈希中，同时仍然允许它起作用。在数学中，有很多这样的例子。例如，简单的加法就是活板门。如果我们将一些整数相加来产生总和，就不可能仅知道总和就无法恢复原始数字。如果攻击者拥有密码的哈希值和盐值，并且碰巧猜出了密码，那么她可以轻松地确认身份，就像登录验证器软件所做的一样：她通过哈希函数运行密码加盐值，然后看到正确的哈希出现了。

#4 楼

散列的关键之一是它会丢弃信息。您无法反转哈希，因为必要的知识已经消失了。这是一些可行（但很不值钱）的哈希函数的示例。如果您给我密码，我可以执行以下操作之一：


计算元音的数量
对每个字母取ASCII码并将它们全部异或
采取密码的二进制表示形式的CRC32校验和（这实际上是一个真实的哈希，而不是一个加密的哈希）。


在每种情况下，我都可以t逆转该过程。相反，当您稍后再次给我输入密码时，我必须重新运行该过程，以查看我运行的计算是否匹配。

例如：如果您最初给我输入密码“ monkey”，我可能会存储数字3（3个元音）。然后，稍后当我尝试对密码“ dragon”进行身份验证时，我再次运行相同的检查并给出不匹配3的2。因此，我知道您给了我错误的密码。但是，如果您给我密码“ melissa”，我会错误地认为您输入了正确的密码。这是哈希冲突。

哈希函数是您用来表示代表给定密码的数字的一组规则。这些功能被认为是“单向”功能，因为您不应将它们反向。高质量的哈希函数旨在限制潜在冲突的次数，因此您不必担心该问题。更进一步，密码散列函数旨在使很难提出可能与给定输出匹配的字符串（并可能有意产生冲突）。它们还旨在限制您可以从哈希输出中收集有关给定输入的信息量。

因此，要知道哪种密码与给定的密码散列相匹配，唯一的方法是尝试所有可能性，直到偶然发现可行的可能性。进一步的对策（盐，BPKDF2等）会使人猜测每次尝试的密码都会越跳越多，这使猜测过程变得更加困难。

请注意，我完全掩盖了加密哈希函数如何使很难拿出有效的密码（即使它不是原始密码）。这称为“原像攻击”。在上面的琐碎示例中，使用“ melissa”作为包含3个元音的候选密码就是这种攻击的示例。

加密哈希函数通常通过在给定进程的多个“回合”中运行输入来完成此操作，其中每个回合的输出都成为下一回合的输入的一部分。要弄清楚第一轮的输入，您必须弄清楚第二轮的输入，这又需要您弄清楚第三轮的输入，依此类推，这意味着每个组件的每个猜测必须通过一系列漫长而复杂的计算进行检查。托马斯·波宁（Thomas Pornin）对这种抵抗是如何工作的做出了详尽的解释。如果您想真正理解它，将会非常有用。

#5 楼

确定满足以下等式的z的常数：xy ^ 7 + yz ^ 5 + x ^ 3z = 0。好，x =32。仍然无法解决吗？然后，您不应该首先知道答案。

y的值将其简化为一个单变量方程，从而使该变量对于任何六年级的学生来说都是微不足道的（可能需要计算器），这是我分享的一个秘密只和我信任的人在一起。没有它，z可能是任何东西；它的值取决于y，因此如果没有已知的y常数就无法令人满意地求解。如果您不知道y的值，那是因为我对您的信任不足，无法私下将其提供给您。

这是密码学的基本原理；数学公式或其他确定性过程已得到充分证明，并且该公式的一个或多个可能变量也被公开披露，允许双方就建立密码的方式达成共识，以便双方可以解密对方加密的内容。然而，两个变量仍然是秘密的。如果您知道一个，就可以发现另一个。您应该知道的一个是密钥，而您可以通过该密钥发现的一个是消息。

对于哈希，则有所不同。散列不需要保留一个秘密即可保留另一个秘密。相反，哈希是基于不可逆的数学转换来进行的；对于任何H（x）= y，除了对所有可能的x尝试H（x）直到得到y之外，没有其他已知的H-1（y）= x。通常，这是因为方程的几个中间结果是模棱两可的。例如，计算一个正数的平方根在技术上会同时产生一个正数和一个负数的结果，因为任何一个数都可以乘以它本身以产生结果。模的倒数类似地是模棱两可的。 x mod 3产生的数字1可以由任何x = 3k + 1产生。这些类型的“单向”转换以这样的方式组合：尝试计算逆哈希函数会产生无限可能。因此，解决这些问题的更简单（最简单）的方法是简单地尝试所有可能的输入，直到一个输出匹配为止。这仍然需要很长时间。


哈希不是随机的。如前所述，哈希是不可逆数学运算的结果。该操作必须仍然是确定性的；在给定恒定输入的情况下，无论执行多少次操作，输出都是恒定的。没有随机成分。

您可能会感到困惑的是哈希模拟的含义，这是一个随机预言。想象一个黑匣子，里面是一个有摄影记忆的小矮人，还有一些产生完全随机数的神秘方法。您在纸上写下一些东西，然后将其推入供男人拿到的插槽中。他读了一下，然后发生两件事之一。要么他以前没有读过，在这种情况下，他将生成一个新的随机数并将其提供给您，同时将您的消息和数字都提交给他。或者，他之前已经阅读了此确切的消息，在这种情况下，他会记住他第一次阅读时生成的电话号码并给您电话号码。随机数生成器将永远不会生成它已经生成的数字，它具有无限可能的大小，并且小矮人的记忆是无限且可靠的。因此，这个小矮人永远不会以为自己以前从未读过一条消息，永远不会忘记他之前曾经读过一条消息，因此永远不会为相同的消息产生两个不同的数字，也不会为两个不同的消息产生相同的数字消息。

这是哈希函数尝试模拟的内容。他们无法用照相存储器为这个小矮人建模，因为这将需要无限的存储空间和无限的通用可用性，即使是没有以任何其他方式连接到任何其他设备的设备。取而代之的是，它们依靠确定性的，但看起来很随机的计算，该计算将消息“消化”为哈希值。给定相同消息的相同哈希函数将产生相同的摘要。但是，这些函数在允许返回的哈希值数量上受到限制。这创造了所谓的哈希冲突的可能性；除了散列值之外，还有更多可能的消息，因此迟早（希望是以后），两条不同的消息将产生相同的散列。


散列可以被破解有三个基本原因。首先，由于它们是消息的确定性，数学推导，因此，数学家（因而是攻击者）最终找到了一条消息与其哈希值之间，或者两条消息与其产生的哈希值之间的数学关系。曾经随机寻找的东西不再如此。根据发现的弱点的性质，这将允许进行多种攻击；如果有给定消息及其散列的算法方法来生成冲突消息，那将是一个问题。如果有一种方法可以处理消息并预测生成的哈希，那就是另一个问题。如果实际上有一种反向散列的方法，则从散列中产生一条消息，当重新散列时会产生相同的散列，这是一个严重的问题。

其次，因为散列的限制摘要大小，迟早两个消息将产生相同的哈希值。这意味着攻击者不必找到用于生成特定哈希值的消息；他要做的就是找到一条产生相同哈希值的消息。从理论上讲，这种可能性很小，尽管存在许多可能的哈希，但仍然比无限远的哈希更好。

最后，虽然有很多可能的消息，但可能的消息数量却少得多。我们通常为哈希函数提供的消息通常具有某种结构（基于语言，主题，电子格式和用途），这意味着，给定消息的某些部分，我们可以更准确地猜测消息的其他部分。用信息科学的术语来说，这意味着转换为哈希的消息通常比哈希函数本身具有更低的熵。简而言之，产生256位摘要的哈希函数理论上可以产生这些位的任何排列2 ^ 256。但是，如果说只有10,000个可能的消息可以被正在研究攻击的系统输入到此哈希函数中，那么在2 ^ 256个可能的哈希值中就只会看到10,000个，更重要的是在最坏的情况下，攻击者只需尝试所有10,000种可能的输入即可找到产生他所寻找的哈希值的输入。