散列和加密算法的根本区别

Question

我看到哈希和加密算法之间有很多混淆，我想听听更多关于以下方面的专家意见：

>

何时使用哈希与加密

是什么使散列或加密算法不同（从理论/数学层面），即是什么使散列不可逆（没有彩虹树的帮助）

以下是一些类似的问题，但没有像我想要的那么详细：

模糊处理、哈希和加密之间的区别是什么？
加密和哈希之间的区别

Answer 1

嗯，你可以在维基百科上查一下...但既然你想要一个解释，我就在这里尽力而为：

它们提供了任意长度输入和（通常）固定长度（或较小长度）输出之间的映射。它可以是从一个简单的crc32到一个完整的加密散列函数，如MD5或SHA1/2/256/512。关键是，有一个单向映射正在进行。这总是一个多：1的映射（意味着总是会有冲突），因为每个函数产生的输出都小于它能够输入的输出（如果您将每一个可能的1MB文件输入到MD5，您将得到大量冲突）。

它们很难（或在实际中不可能）逆转的原因是因为它们在内部的工作方式。大多数加密哈希函数对输入集进行多次迭代以产生输出。因此，如果我们查看每个固定长度的输入块（它依赖于算法），散列函数将把它称为当前状态。然后，它将对状态进行迭代，并将其更改为一个新的状态，并将其作为对自身的反馈（对于每一个512bit数据块，MD5会执行此操作64次）。然后，它以某种方式将所有这些迭代的结果状态组合在一起，形成结果散列。

现在，如果您想对哈希进行解码，首先需要弄清楚如何将给定的哈希分解为其迭代状态（对于小于数据块大小的输入，有1个可能性，对于较大的输入，有许多可能性）。那么您需要为每个状态反转迭代。现在，要解释为什么这是非常困难的，想象一下试图从以下公式推导出a和B:10=a+B。A和B有10种正面组合可以起作用。现在循环一堆时间:tmp=a+b；a=B；b=TMP。对于64次迭代，您将有超过10^64个可能性可以尝试。这只是一个简单的相加，在迭代的过程中保留了一些状态。真正的哈希函数所做的操作远远不止1个（MD5对4个状态变量做了大约15个操作）。由于下一次迭代依赖于前一次迭代的状态，而前一次迭代在创建当前状态时被破坏了，所以几乎不可能确定导致给定输出状态的输入状态（对于每次迭代都是如此）。再加上所涉及的大量可能性，即使是解码MD5也会占用几乎无限（但不是无限）的资源。资源如此之多，因此如果您知道输入的大小（对于较小的输入），那么强行执行哈希实际上比尝试解码哈希要便宜得多。

它们在任意长度的输入和输出之间提供1：1的映射。而且它们总是可逆的。需要注意的是，使用某种方法，它是可逆的。对于一个给定的钥匙总是1：1。现在，有多个输入：密钥对可能会生成相同的输出（实际上，通常会生成相同的输出，这取决于加密函数）。好的加密数据与随机噪声是无法区分的。这与良好的散列输出不同，散列输出的格式总是一致的。

当您想要比较一个值但无法存储纯表示（由于各种原因）时，请使用哈希函数。密码应该非常适合这个用例，因为出于安全原因，您不想以纯文本形式存储它们（也不应该）。但如果您想检查文件系统中是否有盗版音乐文件呢？每个音乐文件存储3 mb是不切实际的。因此，取而代之的是，获取文件的哈希值，并将其存储起来(md5将存储16个字节，而不是3MB)。这样，您只需对每个文件进行散列，并与存储的散列数据库进行比较（这在实践中并不是很好地工作，因为需要重新编码、更改文件头等等，但它是一个示例用例）。

在检查输入数据的有效性时使用哈希函数。这就是他们设计的目的。如果您有两个输入，并且希望检查它们是否相同，那么通过哈希函数运行这两个输入。对于较小的输入大小（假设有一个好的哈希函数），冲突的概率极低。这就是为什么它被推荐用于密码。对于最多32个字符的密码，md5有4倍的输出空间。SHA1具有6倍的输出空间（大约）。SHA512约有16倍的输出空间。您并不关心密码是什么，而是关心它是否与存储的密码相同。这就是为什么你应该对密码使用哈希的原因。

每当需要将输入数据取回时，请使用加密。注意need这个词。如果您存储信用卡号码，您需要在某个时候将它们取出来，但不希望存储它们的纯文本。因此，存储加密版本并尽可能保持密钥的安全。

哈希函数也很适合签署数据。例如，如果您使用的是HMAC，则通过对与已知但未传输的值（秘密值）连接的数据进行哈希来对一段数据进行签名。因此，发送纯文本和HMAC散列。然后，接收器简单地用已知值散列提交的数据，并检查它是否与发送的HMAC匹配。如果是一样的，你就知道它不是被没有秘密值的一方篡改的。这通常用于HTTP框架的安全cookie系统中，以及通过HTTP传输数据的消息中，您需要对数据的完整性提供某种保证。

密码哈希函数的一个关键特性是，创建它们的速度非常快，而反向非常困难/缓慢（如此之快以至于几乎不可能）。这就给密码带来了问题。如果您存储sha512(password)，那么您没有做任何事情来防范彩虹表或暴力攻击。请记住，哈希函数是为速度而设计的。因此，攻击者只需通过哈希函数运行字典并测试每个结果就可以了。

添加salt有助于解决问题，因为它会向散列中添加一些未知数据。因此，他们不需要找到任何与MD5(foo)匹配的东西，而是需要找到当添加到已知的salt中时生成MD5(foo.salt)的东西（这很难做到）。但它仍然不能解决速度问题，因为如果他们知道盐，这只是一个查字典的问题。

所以，有办法处理这个问题。一种流行的方法叫做按键强化（或按键拉伸）。基本上，您对一个哈希进行多次迭代（通常为数千次）。这有两件事。首先，它显著地减慢了散列算法的运行时间。其次，如果正确实现（在每次迭代时传递输入和salt）实际上会增加输出的熵（可用空间），从而减少冲突的机会。一个简单的实现是：

var hash = password + salt;
for (var i = 0; i < 5000; i++) {
    hash = sha512(hash + password + salt);
}

还有其他更标准的实现，如PBKDF2、BCRYPT。但是这种技术被相当多的安全相关系统（如PGP、WPA、Apache和OpenSSL）所使用。

最重要的是，散列（密码）不够好。散列（密码+盐）更好，但仍然不够好...使用扩展哈希机制生成密码哈希...

在任何情况下都不要将一个哈希的输出直接反馈回哈希函数：

hash = sha512(password + salt); 
for (i = 0; i < 1000; i++) {
    hash = sha512(hash); // <-- Do NOT do this!
}

其原因与碰撞有关。请记住，所有哈希函数都有冲突，因为可能的输出空间（可能输出的数量）小于输入空间。为了了解原因，让我们看看发生了什么。作为前言，我们假设sha1()发生冲突的几率为0.001%（在实际中这个几率要低得多，只是为了演示目的）。

hash1 = sha1(password + salt);

现在，hash1发生冲突的概率为0.001%。但是当我们执行下一个hash2=sha1(hash1)；时，hash1的所有冲突都自动变成hash2的冲突。现在，Hash1的比率为0.001%，第二个sha1()调用增加了这个比率。所以现在，hash2发生冲突的概率为0.002%。那是两倍的机会！每次迭代都会为结果添加另一个0.001%冲突的几率。所以，经过1000次迭代，碰撞的几率从微不足道的0.001%跃升到1%。现在，退化是线性的，实际的概率要小得多，但影响是一样的（估计与MD5发生一次碰撞的概率大约为1/(2¹²⁸)或1/(3x10³⁸)。虽然这看起来很小，但由于生日攻击，它并不像看起来那么小）。

相反，通过每次重新附加salt和密码，您将数据重新引入哈希函数。所以任何一轮的碰撞都不再是下一轮的碰撞。所以：

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
    hash = sha512(hash + password + salt);
}

与本机sha512函数发生冲突的机会相同。这正是你想要的。用那个代替。