php - 有没有办法在没有彩虹表的情况下反转哈希？

Question

这个问题在这里已经有了答案:




9年前关闭。

Possible Duplicate:
md5 decoding. How they do it?

this page建议像 md5() 和 sha1() 这样的哈希算法可以颠倒，因为我们现在拥有巨大的处理能力。在这一点上，我认为只有使用 Rainbow Tables 才有可能。我错了吗？

如果 Rainbow Tables 是唯一的出路，那么有人如何反转用盐制成的哈希呢？

Answer 1

嗯，这个问题一般是 This Question 的重复。 .但是，要回答您的确切问题:

At this point i tought it was only possible with Rainbow Tables. Was i wrong?

从技术上讲，是的，你错了。如果有足够的处理能力，没有哈希函数是不可恢复的。关键在于它需要多少处理能力，在大多数情况下，这远远超出您的想象。原因是可能值的数量在哈希周期的每个阶段呈指数增长。对于 MD5，每个阶段(有 64 个)会将可能性的数量乘以 10^77(很多零)。因此，要成功反转 MD5，您必须尝试使用​​ 真的大量可能的排列(粗略计算显示大约 10^4932 次尝试)。使用当今最快的 super 计算机(大约 8 petaflops，或每秒 8x10^15 次浮点运算)，您将看到大约 10^4908 年 扭转它。顺便说一下，这是现在宇宙年龄的 2.5x10^4898 倍。真的，这是一个巨大的数字，超出了我们人类的理解能力……

这绝对是最好的情况。

所以技术上 可以逆转。但实际上，不是的。

In case Rainbow Tables is the only way to go, how someone could reverse a hash that was made with a salt?

问题是没有人需要扭转它。他们只需要找到一个碰撞。基本上，碰撞是导致相同输出的两个输入。所以如果 hash(a) = x和 hash(b) = x , a和 b是彼此的碰撞。所以，我们需要做的就是找到一个碰撞(不管你信不信，这比找到确切的输入更容易，因为从技术上讲，有无数个输入可以给出特定的输出)。随着输入密码的大小，通常冲突的是原始密码。

找到这种冲突的最简单方法是使用预先计算的哈希列表(通常称为彩虹表)。基本上所有你需要做的就是在表中查找哈希值，看看原始值是否在那里。如果是这样，你就完成了(就这么简单)。

通常添加盐来对抗彩虹表。这是因为如果用户输入 1234作为他们的密码，您使用 abcdefghijklmnop作为盐，原来是1234abcdefgjhijklmnop ，这在彩虹表中出现的可能性要小得多。因此，添加强盐可以防止预先计算彩虹 table 。

蛮力

但是，如果您只是执行 hash(pass + salt)，则有一个重大问题。 .它不容易受到预先计算的彩虹表的影响，但容易受到蛮力的影响。原因是加密散列函数(例如 sha1、md5、sha256 等)被设计得很快。他们的传统角色是在 Signing ，因此它们需要快速才能有用。然而，在密码存储中，这是弱点。使用现代 GPU，攻击者可以在几个小时内用盐暴力破解(只需尝试所有可能的密码排列)一个简单的哈希值(有关更多详细信息，请参阅我的 blog post 关于它)...

最好的预防

最好的预防有两个特点:

预先计算值表(彩虹表)并不容易

散列单个值并不快(不容易蛮力)。

事实证明，有一种使用哈希函数的简单方法。简单地迭代它并使输出依赖于大量的散列函数:

var result = password + salt;
for (var i = 0; i < 10000000; i++) {
    result = hash(result + salt);
}

关键是，通过人为地使其变慢并使用盐，您可以使其抵抗预计算和蛮力。

事实证明，有两种标准算法可以做到这一点(好吧，使用原理)。

最好的一种是 Blowfish 散列 (bcrypt)，它并没有真正使用散列原始函数，而是使用 Blowfish 密码的 key 推导循环。它可以通过 crypt() 在 PHP 中获得.要使用它:

$hash = crypt($password, '$2a$07$' . $salt . '$');

并验证它

$hash == crypt($password, $hash);

另一种方法(不太受欢迎)是 PBKDF2 .用 PHP 编程:

function pbkdf2($hashFunc, $password, $salt, $iterations, $length = 32) {
    $size   = strlen(hash($hashFunc, '', true));
    $len    = ceil($length / $size);
    $result = '';
    for ($i = 1; $i <= $len; $i++) {
        $tmp = hash_hmac($hashFunc, $salt . pack('N', $i), $password, true);
        $res = $tmp;
        for ($j = 1; $j < $iterations; $j++) {
            $tmp  = hash_hmac($hashFunc, $tmp, $password, true);
            $res ^= $tmp;
        }
        $result .= $res;
    }
    return substr($result, 0, $length);
}

注:

这些都不能保护用户免受非常弱的密码的影响。如果他们输入字典单词或通用密码，攻击者仍有可能破解它。然而，它们将增加对中等强度密码的防御......

更多阅读:

Many hash iterations, append salt every time?

Fundimental difference between hashing and encryption

MD5 decoding, how they do it

The Rainbow Table Is Dead

You're storing your password incorrectly

Password storage, salt vs multiple hashes