散列如何真正确保唯一性？

#1 楼

简单的答案是，哈希不能确保唯一性。从广义上讲，散列的行为类似于``确定性随机数''-从某种意义上说，确定性是指对相同数据进行散列总是给出相同的答案;从某种意义上说，如果不实际计算哈希值，哈希值基本上是不可预测的，那么它将是随机的。而且完全不可预测，对于一个好的密码散列，除了试错法之外，我们不知道找到带有特定散列的字符串的任何方法。真正随机地适用了生日悖论。也就是说，如果散列可以采用$ k $个不同的值，并且它们都具有相同的可能性，则在找到两个具有相同散列的概率大于半。因此，如果您使用的是256位哈希，则需要查看约$ \ sqrt {2 ^ {256}} = 2 ^ {128} \约3 \乘以10 ^ {38} $个文档甚至有50/50的机会找到具有相同哈希值的两个。相比之下，地球上每纳克质量大约有200个文档。

#2 楼

首先，有一些定义；


抗图像前：给定哈希值$ h $，找到一条消息$ m $，使$ h = Hash（m）$。考虑在服务器上存储密码哈希。例如。攻击者将尝试找到您帐户的有效密码。 $ Hash（m_1）=哈希（m_2）$。对给定的消息进行伪造。
耐碰撞性：如果很难找到两个输入散列到相同的输出$ a $和$ b $，使得$ H（a）= H（b）$，$ a \ neq b。$



0）哈希如何真正确保唯一性？


正如大卫给出的答案，不，他们不能确保唯一性。要查看此内容，请考虑一个简单的哈希（模拟唯一的压缩）；

$$ H'：\ {0,1 \} ^ {20} \ rightarrow \ {0,1 \} ^ {1 } $$
$$ x \ mapsto x \ pmod 2 $$

通过定义；所有的偶数都以$ 0 $作为哈希值，而奇数则以$ 1 $作为哈希值。

另一种查看方式是信鸽原理。输入大小大于散列大小，因此至少存在一个散列值包含多个消息。

因此，没有唯一性。但是找到另一个碰撞（碰撞）必须在计算上是不可行的。



a）据我了解，哈希只是长的字母数字字符串。 />

哈希输出是位，只是位。




b）如果人们一遍又一遍地计算所有文档，密钥，信息，文件等的哈希值再次-只是时间问题，直到针对不同的信息再次出现相同的组合



您所说的称为哈希冲突。根据哈希的定义，这是不可避免的，但是找到一个必须在计算上是不可行的。但是，如果您的哈希函数被认为是弱函数或发生了新的攻击，则必须像MD5或SHA-1一样对其进行更改。

$$ H：\ {0,1 \} ^ * \ rightarrow \ {0,1 \} ^ l $$

如所见，只需$ 2 ^ l $可能的哈希输出存在有限的（因为我们不能无限处理）许多可能的输入。 SHA3​​-512仅具有$ l = 512 $个输出位。如果消息空间仅为1024位，则对于给定的哈希值$ h $，有$ 2 ^ {1024} / 2 ^ {512} $个可能的输入值具有$ h $作为哈希值。

随机选择一个，只要哈希函数随机运行，您就有$ 1/2 ^ {512} $的概率匹配哈希。 e-mule上的MD4上有一个有趣的随机哈希冲突。



c）给定大小和可能性，这可能是不切实际的测试，是的，但这是使散列变得强大，使其几乎不可能重新创建任何可预见的精巧的哈希，或者我缺少某些元素，即使将极低的概率也降低到了零，




在散列函数的设计中，要求查找前图像，第二图像和碰撞必须在计算上不可行。但是，就像MD4案一样，攻击者找到它的机会总是微不足道。




是否存在任何设计约束因素，阻止功能强大的计算机支持从哈希计算原始数据？还是仅仅是因为设计如此复杂，以至于只是梦想着完成这项任务所需的大型计算机而徒劳无功？




哈希函数是设计使然的不是不可逆的排列功能。他们通过2达到了这个目标。位依赖性：输出的每一位都取决于输入的每一位。

雪崩：输入中的单个位更改必须随机更改$ \大约$位的一半。

非线性：防止攻击线性系统求解技术。

攻击者必须找到原像或次要原像。强大的实体可以搜索所有可能的输入以匹配给定的哈希。这些示例Rainbow table，hashcat可能不像您想象的那样强大，但是它们处于计算的边缘。

如果以某种方式找到适合哈希值的图像，则无法确定原来是原始图像。

如果您强大的实体是Quantum Computer，请不要担心。 D.J.伯恩斯坦;


任何担心量子哈希碰撞算法的人都已经对非量子哈希碰撞算法有更多的恐惧。


量子计算机的减少从$ 2 ^ {b / 2} $到$ 2 ^ {b / 3} $的哈希冲突的复杂性。非量子计算机已经在更短的时间内实现了
$ 2 ^ {b / 3} $，Rho Machine.1,2



阻止黑客的原因还是恶意的中间人入侵打开创建此“哈希”的软件程序或库，然后使用该库创建自己的哈希或使用自己指向文件的版本的方式错误地标记了目标公司的哈希？特别是由于许多应用程序，语言和开发人员独立使用哈希。无论哪个安全性最弱，我们都可以用它来承担其余的责任？




除了发现碰撞的难度之外，没有别的。如果攻击者以某种方式能够找到冲突，则可以执行该冲突。最近，用于SHA-1的identical-prefix collision attack在PDF文件中执行，以创建恶意的有效PDF。

#3 楼

...在任何可预见的努力下，几乎不可能重新创建哈希，否则我是否会丢失某些即使将极低的概率也降低到零的元素？

诸如SHA-256之类的实用哈希函数的输入空间通常受到限制。 SHA-256的输入消息大小非常大（$ 2 ^ {64}-1 $位）。这主要是由于该算法包括对散列的位数进行编码的算法。对于SHA-256的每个输出值，平均将导致$$ 2 ^ {2 ^ {64}-1} \超过2 ^ {256} $$个冲突。其他哈希函数（例如SHA-3）没有此限制，并且允许无限的消息空间。在那种情况下，很可能有无数的消息具有针对该特定哈希函数的相同哈希值。
然而，发现冲突在计算上是不可行的：两个消息哈希到同一输出。如果哈希函数被破坏，这通常是第一个掉落的属性：例如，发现MD5和SHA-1都发生了冲突。为现有的哈希查找另一条输入消息要困难得多，这被称为“映像前攻击”。

是否存在任何设计约束，这些约束会阻止功能非常强大的计算机从计算机中反算原始数据。哈希？还是仅仅是设计如此复杂，以至于它只是梦to以求的梦dream以求的任务，需要这么大的计算机？

是的，加密哈希函数在定义和定义上都是单向函数设计。通过各种技术，混合输入数据的方式使得计算难以求逆，但是输出的每一位仍然同样依赖于输入的每一位。是什么阻止了黑客或恶意中间人入侵创建该“哈希”的软件程序或库，然后使用该库创建自己的哈希或使用自己的指向文件的版本的标签错误地标记了目标公司的哈希？特别是由于许多应用程序，语言和开发人员独立使用哈希。不论哪个安全性最弱，我们都可以用它来承担其余的安全性？如果您可以更改用于验证哈希的代码，则可以，您可能会欺骗应用程序。就像您可以更改代码以完全跳过哈希比较或签名验证一样。

#4 楼

您的问题很好。其他答案很好地覆盖了它们，但我想提供一个不太正式的方式来解决您的问题。


据我了解，哈希只是长字母数字字符串。如果要一遍又一遍地计算所有文档，密钥，信息，文件等中的哈希值-这只是时间问题，直到针对不同的信息再次出现相同的组合（将其应用于所有可能的上下文）？


技术上来说，是可能的。但是，当您开始考虑现实世界中的限制时，我们会发现它们的唯一性是合理的。如果您具有256位哈希输出，则意味着可能有$ 2 ^ {256} $个哈希输出。从技术上讲，这意味着可能会发生碰撞。但是，鉴于宇宙中估计有$ 2 ^ {260} $个原子，那么在偶然发生碰撞之前，就需要大量的哈希值。

如果那是您的目标该怎么办？如果您让机器尝试哈希直到遇到冲突该怎么办？好吧，您遇到了有趣的身体限制。根据Landauer原理，在此过程中执行的每个位翻转都消耗了最少的能量。我假设您可以在2.7K的背景辐射温度下进行计算，所以只进行了一次计算。如果您只有一个从$ 1 $到$ 2 ^ {256} $的计数器，那么在这些温度下，您将不得不消耗银河系已知能量的3/4左右！

因此，您不能强行使用它。如果您更聪明呢？这会引出您的下一个问题。


是否有任何设计约束条件阻止功能非常强大的计算机从哈希中反算原始数据？ />散列算法的设计使其很难以这种方式进行反算。该属性是密码哈希的主要设计目标。这不是完美的。我们只能考虑我们知道的算法，但是我们做得很好。考虑一下MD5，它持续了大约十年，直到我们发现使它在安全性应用程序中变得毫无价值的攻击。没有已知攻击的散列算法。这不是一个完美的方法，但实际上可以说是有效的。


是什么阻止了黑客或恶意中间人黑客打开创建该“哈希”的软件程序或库，然后使用该方法库创建自己的散列还是错误地将目标公司的散列标签为错误，而自己指向文件的版本？


没有。没有什么可以阻止这一点的。这是一种完全不同的问题。

在现实世界中，与通过整个软件相比，通常可以更轻松地通过安全通道传递短哈希值。

通常，哈希不是单独使用这种方式。哈希与其他工具配合使用以提供有用的功能。例如，在数字签名中，对大型数据库进行签名在计算上非常昂贵，但是对它进行哈希处理然后对哈希进行签名却是效率更高的过程。

#5 楼

1.
如果要一遍又一遍地计算所有文档，密钥，信息，文件等中的哈希值，这只是时间问题，直到针对不同的信息再次出现相同的组合（将其应用于所有可能的上下文中） ）？

是的，好的哈希函数可以为您提供针对不同文档的随机（很好的“随机”）哈希，但是一旦您对尽可能多的不同文档进行了哈希处理，您肯定会两次都具有相同的哈希值。

我是否缺少一些元素，即使将极低的概率也降低到零？

不是零，而是接近零可能为零。主要因素是有太多不同的哈希，除了随机猜测之外，没有其他更好的方法来破坏（重新创建）哈希。

2.
是否有任何设计是一种约束，它会阻止功能非常强大的计算机从哈希表反向计算原始数据吗？

是的，哈希表中的许多操作都是不可追溯的。例如，如果a+b mod 100 = 65，则在0到99之间有100对可能的值（a，b），它们加起来等于64。现在想象一下，但是具有强大的模数值，这使得很难甚至列出可能的值，即使这样您也不知道它是哪个值，而且如果您猜错了，其他地方的其他计算也不会累加，所有这些都会变成一棵指数级的大树。

3
阻止黑客或恶意中间人入侵软件程序的原因是什么...

您不需要黑客，大多数哈希算法都是开源的，每个人都知道哈希如何生成（这就是重点）。

...或使用自己指向目标文件版本的标签错误地标记了目标公司的哈希

这确实是一个潜在的问题。私钥/公钥用作解决方案，公司使用其私钥对文档的哈希进行编码，然后释放结果（所谓的签名），然后每个人都可以使用公司的公钥针对文档的哈希来验证签名。唯一的弱点是，攻击者可以将伪装成公司公钥的公钥发送给您，然后使用其私钥签署反证明文件，您将是一个明智的选择。除非您使用验证机构并要求有效的公共密钥许可证，否则如果您在URL地址的开头看到https://，浏览器会立即执行此操作。

还请注意，哈希，对称加密和私钥/公钥是3个独立的事物，它们的工作原理不同，但是在现代加密技术中，它们全部一起使用。

#6 楼

除了已经给出的完美答案之外，我将尝试提供一个或多或少的ELI5 *答案，该答案既不太简短也不会太长，并且不会深入到具体细节。


是的，对于每个给定的哈希函数，输出数量是有限的**；有输入（实际上是无限数量的输入）会导致相同的输出。这就是我们所说的“碰撞”。但是，由于散列通常会导致128位（甚至更大）的输出，并且由于算法被设计为难以/不可能反转，因此很难强制执行特定的输出。并非没有可能，但是今天使用的（好的）哈希值是无法实现的（鉴于当前的技术水平；在10、20或50年的时间里，情况可能会大不相同，但届时我们还将拥有更新/更好的哈希值（大概））。对于给定的散列，发生碰撞的机会大约为1英寸。但是由于输出的数量有限，因此可能发生的碰撞的数量就定义而言是无限的。您只需要搜索巨大的输入空间即可找到所需的确切输入。对于某些较弱的哈希，除了强行使用外，可能还有一些捷径。您可以找到一个碰撞。
我在第1点中谈到了这一点。哈希的设计可能很复杂，也可能不复杂，但是在所有情况下，算法都是公开的。那里没有秘密。任何依赖于对实际算法保密的算法最终都会（通常早于晚）失败。请参阅
Kerckhoffs的原则：“即使系统中除密钥之外的所有内容都是公共知识，加密系统也应是安全的”或Shannon的格言。在某些时候，很多哈希都依赖于模运算。这是单向哈希函数的简介，比本文提供的内容更深入（此处为存档版本，以防万一）。
算法，软件程序或库已经（或应该）已经公开。有些哈希过去曾经很好，但后来证明是有缺陷的（例如，MD5被认为是“残破的”）。除了“黑客”，还有一群人叫做Cryptanalysist，他们的工作是（或喜欢）寻找密码算法的弱点或缺陷。可以肯定的是，随着时间的推移，更多算法将沿用MD5。多少，以什么速率，是另一回事。当前，许多算法被广泛认为是完全安全/易于使用的（只要按预期使用即可）。有很多（广为人知的，甚至鲜为人知的哈希）。您可以在此处了解有关攻击的更多信息。

*如果您不熟悉该术语：像我5岁（岁）这样解释。
**有完善的哈希函数，但这些仅适用于“固定大小”输入。

#7 楼

当哈希值足够安全且足够时，哈希值可确保其唯一性。这比关闭水龙头确保水不会流失，水龙头没有破裂且型号合适时要更加确定。

那是因为那时我们不知道找到两个可产生不同输入的可行方法相同的哈希即使我们通过信鸽原理知道有这样的输入。

从业人员应用这种方法，使用诸如SHA-256之类的256位哈希（具有128位安全性）来防止当前攻击或诸如SHA-512之类的512位哈希（具有256位安全性）以防止任何可预见的进展，包括假设的量子计算机。在这样的设置中，不会发生碰撞。我们应该宁可担心计算机的渗透，全球变暖和彗星的影响。



是否存在任何设计约束会阻止功能非常强大的计算机对原始数据进行反计算。


假设有一个如上所述的安全且足够宽的哈希，找到原始数据的唯一已知策略是尝试对该原始数据的可能值进行哈希处理，直到找到一个哈希匹配的。然后，几乎可以肯定地找到了原始数据（证明：如果没有，对原始数据的了解将允许使用相同的散列显示两个不同的值，而我们不能！）。

因此，设计约束可以阻止功能非常强大的计算机从哈希中反算原始数据，这是因为攻击者缺少太多关于原始数据的信息，使得他/她无法计算足够的候选者的哈希用于原始数据。

例如，给定一个16位信用卡号的SHA-256哈希，可以找到具有最多1015个哈希值的数字（最后一位是Luhn校验位）。小于250的哈希值，这是一个微不足道但完全可行的SHA-256哈希值（在撰写本文时，据报道，比特币每秒执行> 267的哈希值，因此，我们正在谈论它们在数千个哈希值中的总和超过一百倍）一秒钟）。

另一方面，如果散列的是16位信用卡号，后跟256位（或43个基数64个字符）一致随机且对于攻击者，她或他的人未知任务是没有希望的。

#8 楼

我将重点关注问题的这一部分：是否存在任何设计约束，这些约束会阻止功能非常强大的计算机从哈希中反算原始数据？还是仅仅是因为设计如此复杂，以至于梦想着完成这项任务所需的大型计算机只是徒劳的练习？从哈希开始，原因很简单，就是输入可以无限地具有相同的哈希。因此，您可以做的就是找到一些具有相同散列输出（冲突）的输入。

正如其他人所解释的那样，用蛮力来完成此操作相当困难，最后，您可能会结束例如，如果原始输入为“ James Kumar同意支付$ 100”而哈希为1f262e0cdd8af3928ed8933b0a2cb2bacf6be1d168130dc11af0fa61f952c8cf，则可能会发现一个“原始”输入与“原始”输入没有任何关系。假设其他输入“ AJIUZEBGIUZEBGIZNOIBZIUFBIB”具有相同的哈希值（当然这里不是这种情况）。但是该输入是没有意义的。

因此，即使您发现了碰撞（同样很困难），该碰撞也没有用。

查找另一个具有相同的哈希值并有意义并为攻击者提供优势要困难得多。当然，除非哈希函数存在缺陷。

#9 楼

对于OP的实际问题，这里有一些很好的答案，所以我不会再赘述了，但是散列的一个方面尚未真正涉及到，这可能会提高OP对散列及其用途的理解。

按照定义，哈希函数将任意大小的数据映射到固定大小的数据。换句话说，哈希值几乎不告诉您用于生成它的输入值，甚至不告诉它的长度，这实际上使反向工程成为不可能。是的，可以产生产生相同散列值的输入数据，但是不可能取散列值并计算出产生散列值的输入数据，这使得散列对密码学家非常有吸引力。

奇偶校验位是一个非常简单但非常常用的哈希的示例。设置为true（1）或false（0）表示输入中设置的位数是偶数还是奇数。更改输入中的一位，您将获得不同的奇偶校验-对于快速检查损坏非常有用！输入的内容是莎士比亚的全集还是1到10之间的数字都没有关系。当然，如果您更改偶数个位数，则奇偶校验不会更改（发生冲突！），但是您仍然可以通过非常简单的检查和仅一个位就可以检测到所有可能的篡改的50％ 。哈希中的每一位给您$ 2 ^ n $可能的结果，并将潜在冲突的次数减少$ {1} / {2 ^ n} $，因此，即使是很小的哈希也可以非常迅速地产生非常有用的结果。例如，一个16位哈希可以检测到$ 1-1 / {2 ^ {16}} = 99.998 \％$的所有可能的篡改。换句话说，$ n $哈希可以将任意输入数据分类为$ 2 ^ n $个不同的信鸽，因此对于高效索引，访问和组织数据非常有用。

#10 楼

一个32字节的摘要（如比特币的摘要）只能有256 ^ 32个可能的值。如果散列1K字节块，则必然会有256 ^ 1024/256 ^ 32（非常多）冲突。但是，仍然很幸运，找到了一个。

#11 楼

正如您所观察到的那样，哈希不能保证每个输入都是唯一的-因为它们的大小有限，所以不能具有潜在的无限输入。它们仅将输入“分组”为输出（在数据结构中使用哈希的情况下，有时称为存储桶）。这仍然有用。

通过示例的方式，一个非常简单的哈希函数可能是“给定非空的单字节字符字符串输入，使用第一个字节作为哈希”。考虑一下此函数的属性：


可用于无限多个任意输入（任意长度的字符串）。
最多有256种不同的输出散列（也就是存储桶） ）。
仅通过查看输出就无法重建输入。无论您的计算机多么强大，它都根本无法完成！


即使是一个非常简单的哈希函数，对于某些用途也可能有用（也许是非常简单的字典数据结构）-两个输入之间的比较可以检查其哈希值，并轻而易举地拒绝它们是256中255倍的可能性。这可以使使用它的数据结构快得多。但是，如果两个输入导致相同的哈希（称为“冲突”），则需要对每个输入的整体进行比较，以查看它们是否真的相同。

当然，这种简单的哈希函数对于哈希诸如密码之类的东西将毫无用处（对于数据结构而言也很差）。一个好的散列函数将具有其他属性：


足够多的输出存储桶可用于手头的任务。 （对于数据结构或文件系统哈希，冲突会稍微减慢速度，但对其他方面无害，这可能是2 ^ 32或更小。对于密码，冲突可能会破坏安全性，这可能更像2 ^ 512或更多！）。
桶之间的分配均匀。 （采用第一个字节可能会将几乎所有字符串都放在相同的几十个存储桶中，例如“ A”，“ B”等，将200个存储桶留空）。
整个输入应该有助于哈希。 （不仅仅是第一个字节！）
平均而言，更改输入中的单个位将更改输出中的一半。

并且取决于将哈希值放入的目的，还有其他注意事项：


执行速度；缓慢的固定时间散列函数可以帮助克服安全应用程序中的定时攻击，但是例如，如果在数据结构中使用散列，则快速散列函数的性能更高。
安全应用程序可能希望添加随机的“盐”在计算哈希值之前，先将其输入到输入，以防止从已知输出的列表中查找输入；

要理解的重要一点是，哈希不能保证唯一性-哈希只能为输入是否相同分配置信度。这可能相当弱（对于具有32位哈希的文件系统或数据结构），或者确实非常强（对于具有512位哈希安全加密的密码）。