36

我阅读了有关 md5 哈希的 Wikipedia 文章，但我仍然无法理解如何无法将哈希“重构”回原始文本。

有人可以向对密码学知之甚少的人解释这是如何工作的吗？函数的哪一部分使它成为单向的？

4

7 回答 7

51

由于到目前为止每个人都只是简单地定义了哈希函数是什么，所以我会咬一口。

单向函数不仅仅是一个散列函数——一个丢失信息的函数——而是一个函数f，给定一个图像y（“SE”或现有答案中的 294），很难找到一个原图像 x这样f(x)=y。

这就是它们被称为单向的原因：您可以计算图像，但找不到给定图像的原像。

到目前为止，在现有答案中提出的普通哈希函数都没有这个属性。它们都不是单向加密哈希函数。例如，给定“SE”，您可以轻松选择输入“SXXXE”，该输入具有 X-encode("SXXXE")=SE 的属性。

没有“简单”的单向函数。他们必须很好地混合他们的输入，以至于您不仅在输出中根本无法识别输入，而且您也无法识别另一个输入。

SHA-1 和 MD5 曾经是流行的单向函数，但它们都几乎被破坏（专家知道如何为给定图像创建预映像，或者几乎能够这样做）。正在进行一场竞赛以选择一个新的标准，该标准将被命名为SHA-3。

反转单向函数的一种明显方法是计算许多图像并将它们保存在一个表中，该表与生成它的前图像相关联。为了使这在实践中变得不可能，所有单向函数都有一个大的输出，至少 64 位，但可能更大（例如，512 位）。

编辑：大多数加密哈希函数如何工作？

通常，它们的核心只有一个函数，可以对比特块（块密码）进行复杂的转换。该函数应该几乎是双射的（它不应该将太多的序列映射到同一张图像，因为这会在以后导致弱点），但它不必是完全双射的。并且这个函数被迭代了固定的次数，足以使输入（或任何可能的输入）无法识别。

以Skein为例，它是 SHA-3 上下文的有力候选者之一。它的核心功能被迭代了72次。函数的创建者知道如何有时将输出与某些输入相关联的唯一迭代次数是 25。他们说它的“安全系数”为 2.9。

于 2010-01-21T20:59:40.770 回答
49

考虑一个非常基本的散列 - 对于输入字符串，返回每个字符的 ASCII 值的总和。

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

现在，给定 294 的哈希值，你能分辨出原始字符串是什么吗？显然不是，因为“abc”和“cba”（以及无数其他）给出了相同的哈希值。

加密散列函数的工作方式相同，只是算法显然要复杂得多。总是会有冲突，但如果你知道字符串s散列到，那么构造另一个也散列到 的字符串h应该非常困难（“计算上不可行”）。h

于 2010-01-21T20:43:24.803 回答
34

在这里进行简单的类比而不是复杂的解释。

首先，让我们将主题分为两部分，单向操作和散列。什么是单向操作，您为什么想要一个？

一种方式称为操作，因为它们是不可逆的。大多数典型的运算，如加法和乘法，可以反转，而模除法不能反转。为什么这很重要？因为您想提供一个输出值，1) 没有原始输入就很难复制，2) 无法从输出中找出输入。

可逆

加法： 

4 + 3 = 7

这可以通过求和并减去一个加数来反转

7 - 3 = 4

乘法：

4 * 5 = 20

这可以通过取产品并除以其中一个因素来逆转

20 / 4 = 5

不可逆

模除法：

22 % 7 = 1

这无法逆转，因为您无法对商和被除数执行任何操作来重构除数（反之亦然）。

你能找到一个操作来填写'？是？ 

1  ?  7 = 22  
1  ?  22 = 7

话虽如此，单向哈希函数具有与模除法相同的数学质量。

为什么这很重要？

假设我给了你一把公共汽车总站储物柜的钥匙，那里有 1000 个储物柜，并要求你把它交给我的银行家。作为一个聪明的人，更不用说怀疑了，你会立即查看钥匙，看看钥匙上写着什么储物柜号码。知道了这一点，我做了一些狡猾的事情；首先我找到了两个数字，当使用模除法进行除法时，我得到了一个介于 1 和 1000 之间的数字，其次我删除了原始数字并在上面写下了这对数字中的除数，其次我选择了一个有通过每天只让人们用钥匙尝试一个储物柜来保护储物柜免受不法分子的侵害，第三，银行家已经知道红利，所以当他拿到钥匙时，他可以做数学并找出剩余的并知道要打开哪个储物柜。

如果我明智地选择操作数，我可以接近商和被除数之间的一对一关系，这会迫使你尝试每个储物柜，因为答案会将可能输入的结果分布在所需数字的范围内，储物柜在终端中可用。基本上，这意味着即使您知道其中一个操作数，您也无法获得有关余数的任何知识。

所以，现在我可以“相信”你将钥匙交给它的合法拥有者，而不必担心你很容易猜到它属于哪个储物柜。当然，您可以暴力搜索所有储物柜，但这需要将近 3 年的时间，我的银行家有足够的时间使用钥匙并清空储物柜。

有关不同哈希函数的更多详细信息，请参阅其他答案。

于 2010-01-22T15:46:28.453 回答
12

这是一个非常简单的例子。假设我是一名初学密码学家，并且我创建了一个执行以下操作的哈希函数：

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

现在是测试。 SimpleHash(specialFile)是 0。 我的原始文件是什么？

显然，没有办法知道（尽管您可能很容易发现我的哈希是基于文件长度的）。无法根据散列“重构”我的文件，因为散列不包含我的文件所做的一切。

于 2010-01-21T21:11:49.880 回答
10

简单来说，散列函数的工作原理是把输入数据弄得一团糟。

例如，参见MD5。它按 512 位块处理输入数据。每个块被分成 16 个 32 位字。有 64 个步骤，每个步骤使用 16 个输入字中的一个。因此，每个单词在算法过程中被使用了四次。这就是单向性的来源：任何输入位都在多个位置输入，并且在两个这样的输入之间，该函数将所有当前数据混合在一起，以便每个输入位影响大部分 128 位运行状态。这可以防止您通过仅查看数据的一部分来反转函数或计算冲突。您必须查看整个 128 位，而 128 位块的空间太宽，无法有效地遍历。

现在 MD5 在这方面做得不好，因为可以找到该函数的冲突。从密码学家的角度来看，MD5 是一种旋转加密函数。一个消息块 M（512 位）的处理使用输入状态 V（128 位值）并计算新状态 V' 为 V' = V + E(M, V) 其中'+' 是一个单词-明智的加法，“E”恰好是一个对称加密函数（又名“分组密码”），它使用 M 作为密钥，V 作为要加密的消息。仔细看，E can 是一种“扩展 Feistel 网络”，类似于 DES 分组密码，有四分之四而不是两半。细节在这里并不重要；我的观点是，在使用该结构的散列函数（称为“Merkle-Damgård”）中，是什么构成了“好的”散列函数，类似于使分组密码“安全”的原因。对 MD5 的成功碰撞攻击使用了差分密码分析，这是一种最初设计用于攻击分组密码的工具。

从一个好的分组密码到一个好的散列函数，有一个步骤是不容忽视的。对于 Merkle-Damgård 结构，如果底层分组密码能够抵抗“相关密钥攻击”，则哈希函数是安全的，这是一个相当模糊的属性，分组密码很少针对该属性得到加强，因为对于对称加密，相关密钥攻击几乎没有任何实际意义影响。例如，事实证明 AES 加密对相关密钥攻击的抵抗力不如预期的那么好，这并没有引发普遍的恐慌。这种阻力不是设计 AES 时所寻求的特性的一部分。它只是防止将 AES 转换为哈希函数。有一个名为 Whirlpool 的散列函数，它建立在 Rijndael 的派生词之上，“Rijndael”是后来成为 AES 的初始名称；

此外，还有其他结构可用于构建散列函数。当前的标准函数（MD5、SHA-1 和“SHA-2”系列，即 SHA-224、SHA-256、SHA-384 和 SHA-512）是 Merkle-Damgård 函数，但许多可能后继者不是。NIST（处理此类事情的美国联邦组织）组织了一场正在进行的竞赛，以选择一种新的标准哈希函数，称为“SHA-3”。有关详细信息，请参阅此页面。现在，他们从最初的 51 名候选人减少到了 14 名（不包括额外的 12 名候选人，这些候选人未能通过发送完整提交的代码可以正确编译和运行的管理测试）。

现在让我们有一个更概念化的外观。一个安全的散列函数应该看起来像一个随机预言机：一个预言机是一个黑盒子，当给定消息M作为输入时，它会输出一个答案h(M)，它是在输出空间中随机均匀选择的（即所有n -如果哈希函数输出长度为n的位字符串）。如果再次给定相同的消息M作为输入，则 oracle 输出与以前相同的值。除了这个限制之外，oracle 在以前未使用的输入M上的输出是不可预测的。可以将预言机想象成一个投掷骰子的侏儒的容器，并在一本大书中仔细记录输入消息和相应的输出，以便他履行他的预言机合同。没有办法预测下一个输出将是什么，因为 gnome 自己不知道这一点。

如果存在随机预言机，则反转散列函数的成本为2^n：为了获得给定的输出，没有比使用不同的输入消息更好的策略，直到产生预期值。由于统一的随机选择，每次尝试的成功概率为1/(2^n)，对掷骰子 gnome 的平均请求数为2^n。对于冲突（找到两个产生相同哈希值的不同输入），成本约为1.4 2^(n/2)*（粗略地说，有1.4 2^(n/2)* 输出，我们可以组装大约2^ n对输出，每对的概率为1/(2^n)的匹配，即有两个不同的输入具有相同的输出）。这些是使用随机预言机可以做到的最好的。

因此，我们寻找与随机预言机一样好的哈希函数：它们必须以这样一种方式混合输入数据，使得我们无法比简单调用函数2^(n/2更有效地找到冲突)次。哈希函数的祸根是数学结构，即允许攻击者将哈希函数内部状态（很大，至少n位）视为存在于更短空间中的数学对象的变体的捷径。30 年来对对称加密系统的公共研究已经产生了可以应用的概念和工具（扩散、雪崩、微分、线性......）的完整工具。然而，底线是我们没有证据表明随机预言机可能确实存在。我们想要一个无法被攻击的哈希函数。我们拥有的是哈希函数候选者，目前还没有已知的攻击，而且更好的是，我们有一些函数可以证明某些类型的攻击不起作用。

还有一些研究要做。

于 2010-01-22T15:25:53.430 回答
8

哈希是（非常）有损编码。

举一个更简单的例子，想象一个虚构的 5 字母单词的 2 字母编码，称为 X 编码。X 编码的算法很简单：取单词的第一个和最后一个字母。

所以，

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

显然，您无法从 SAUCE 的编码 SE 中重构 SAUCE（假设我们可能的输入范围都是 5 个字母的单词）。这个词可以很容易地成为空间。

顺便说一句，SAUCE 和 SPACE 都产生 SE 作为编码的事实称为冲突，您可以看到 X-ecoding 不会产生非常好的哈希。:)

于 2010-01-21T20:45:07.603 回答
3

数组
关联数组看起来很像散列。主要区别在于哈希名称上缺少 % 符号，并且一次只能为它们分配一个键。因此，有人会说$foo{'key'} = 1;，但只有@keys = keys(foo);。熟悉的函数，如 each、keys 和 values 就像现在一样工作（并且在 Perl 2 中添加了 delete）。

Perl 3 具有三种完整的数据类型：它在哈希名称上具有 % 符号，允许一次分配整个哈希，并添加了 dbmopen（现在不推荐使用，取而代之的是 tie）。Perl 4 使用逗号分隔的哈希键来模拟多维数组（现在使用数组引用可以更好地处理）。

Perl 5 实现了将关联数组称为散列的巨大飞跃。（据我所知，它是第一种引用数据结构的语言，而不是“哈希表”或类似的东西。）有点讽刺的是，它还将相关代码从 hash.c 移动到 hv.c。


如前所述，命名字典是由唯一键索引的值的无序集合。它们有时被称为关联数组或映射。它们可以通过多种方式实现，其中一种是使用称为哈希表的数据结构（这就是 Perl 所称的哈希）。

Perl 对“散列”一词的使用是一些潜在混淆的根源，因为散列函数的输出有时也称为散列（特别是在加密上下文中），并且因为散列表在其他任何地方通常不称为散列。

为了安全起见，将数据结构称为哈希表，并且仅在明显的、特定于 Perl 的上下文中使用术语“哈希”。

于 2012-07-31T18:37:20.717 回答