security - 散列和加密算法之间的根本区别

Question

我看到散列和加密算法之间有很多混淆，我想听听更多专家的建议:

何时使用散列与加密

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

以下是一些类似的 SO 问题，但没有像我所寻找的那样详细:

What is the difference between Obfuscation, Hashing, and Encryption?
Difference between encryption and hashing

Answer 1

嗯，你可以在 Wikipedia 中查找。 ......但既然你想要一个解释，我会在这里尽力:

哈希函数

它们提供任意长度输入和(通常)固定长度(或更短长度)输出之间的映射。它可以是任何东西，从简单的 crc32 到完整的加密哈希函数，例如 MD5 或 SHA1/2/256/512。关键是正在进行单向映射。它总是一个多:1 映射(意味着总是会有冲突)，因为每个函数产生的输出都比它能够输入的要小(如果你将每个可能的 1mb 文件输入 MD5，你会得到大量的冲突)。

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

现在，如果您想解码散列，您首先需要弄清楚如何将给定的散列拆分为其迭代状态(对于小于数据块大小的输入，有 1 种可能性，对于较大的输入则有多种可能性)。然后你需要反转每个状态的迭代。现在，要解释为什么这非常困难，想象一下试图推论 a和 b来自以下公式:10 = a + b . a有10个正组合和 b那可以工作。现在循环多次:tmp = a + b; a = b; b = tmp .对于 64 次迭代，您将有超过 10^64 种可能性可以尝试。这只是一个简单的添加，其中从迭代到迭代保留了一些状态。真正的哈希函数执行的操作远不止 1 次(MD5 对 4 个状态变量执行大约 15 次操作)。并且由于下一次迭代取决于前一次的状态，而前一次在创建当前状态时被破坏，因此几乎不可能确定导致给定输出状态的输入状态(每次迭代不少于)。结合所涉及的大量可能性，即使解码 MD5 也将占用近乎无限(但不是无限)数量的资源。如此多的资源，如果您知道输入的大小(对于较小的输入)，那么暴力破解哈希实际上比尝试解码哈希要便宜得多。

加密功能

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

用例

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

在检查输入数据的有效性时使用哈希函数。这就是它们的设计目的。如果您有 2 个输入，并且想检查它们是否相同，请通过哈希函数运行它们。对于小输入大小(假设一个好的散列函数)，碰撞的概率是天文数字。这就是为什么建议使用密码的原因。对于最多 32 个字符的密码，md5 有 4 倍的输出空间。 SHA1 有 6 倍的输出空间(大约)。 SHA512 大约有 16 倍的输出空间。您并不真正关心密码是什么，您关心它是否与存储的密码相同。这就是为什么你应该使用哈希作为密码的原因。

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

哈希函数也非常适合签署数据。例如，如果您使用 HMAC，您可以通过将数据与已知但未传输的值( secret 值)连接在一起的哈希值来签署数据。因此，您发送纯文本和 HMAC 哈希。然后，接收器简单地使用已知值散列提交的数据，并检查它是否与传输的 HMAC 匹配。如果相同，您就知道它没有被没有 secret 值的一方篡改。这通常用于 HTTP 框架的安全 cookie 系统中，以及通过 HTTP 传输数据的消息中，您需要在某些情况下保证数据的完整性。

关于密码散列的说明:

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

添加盐会有所帮助，因为它会向哈希添加一些未知数据。所以，而不是找到任何匹配 md5(foo) ，他们需要找到一些东西，当添加到已知的盐中时会产生 md5(foo.salt) (这很难做到)。但它仍然没有解决速度问题，因为如果他们知道盐，那只是运行字典的问题。

所以，有办法处理这个问题。一种流行的方法称为 key strengthening (或键拉伸(stretch))。基本上，您多次迭代哈希(通常为数千次)。这有两件事。首先，它显着减慢了散列算法的运行时间。其次，如果正确实现(在每次迭代中将输入和盐传递回)实际上会增加输出的熵(可用空间)，从而减少碰撞的机会。一个简单的实现是:

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

还有其他更标准的实现，例如 PBKDF2 , BCrypt .但是这种技术被相当多的安全相关系统(如 PGP、WPA、Apache 和 OpenSSL)使用。

底线， hash(password)不够好。 hash(password + salt)更好，但仍然不够好......使用拉伸(stretch)散列机制来生成您的密码散列......

关于琐碎拉伸(stretch)的另一个注意事项

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

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/(2128) 或 1/(3x1038)。虽然这看起来很小，但多亏了 the birthday attack，它并不是真的看起来很小)。

相反，通过每次重新附加盐和密码，您将数据重新引入哈希函数。因此，任何特定回合的任何碰撞都不再是下一轮的碰撞。所以:

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

与原生碰撞几率相同 sha512功能。这就是你想要的。改用那个。