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

Question

可能重复：
md5 解码。他们是怎么做到的？

这个页面表明像 md5() 和 sha1() 这样的哈希算法可以反转，因为我们现在拥有巨大的处理能力。在这一点上，我认为只有 Rainbow Tables 才有可能。我错了吗？

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

score 16 · Accepted Answer

好吧，这个问题通常是This Question的副本。但是，要回答您的确切问题：

在这一点上，我认为只有 Rainbow Tables 才有可能。我错了吗？

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

这绝对是最好的情况。

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

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

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

找到这种冲突的最简单方法是使用预先计算的哈希列表（通常称为彩虹表）。基本上，您需要做的就是查找表中的散列以查看是否存在原始散列。如果是这样，你就完成了（很容易）。

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

蛮力

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

最好的预防

最好的预防有两个特点：

预先计算值表（彩虹表）并不容易
散列单个值并不快（不容易暴力破解）。

事实证明，有一种使用散列函数的简单方法。简单地对其进行迭代并使输出依赖于大量的散列函数：

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

关键是，通过人为地减慢速度并使用盐，您可以使其抵抗预计算和暴力破解。

事实证明，有两种标准算法可以做到这一点（好吧，使用这些原则）。

最好的一个是 Blowfish 散列 (bcrypt)，它并不真正使用散列原语函数，而是使用 Blowfish 密码的密钥派生循环。它在 PHP 中通过crypt(). 要使用它：

$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);
}

笔记：

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

更多阅读：

score 2 · Accepted Answer

彩虹表“只是”一个预先计算的散列值的大表，其中包含一些技巧来仅存储表的一小部分并且仍然能够查找所有值。详细地说，可以“反转” N个可能值（即，有N个哈希输出，该表将产生相应的输入）的彩虹表需要大约1.7*N的时间来构建——因此构建表实际上比“只是”尝试N个输入，看看是否有一个与给定的哈希输出匹配。表的优势是当您有多个哈希输出要为其查找匹配输入时。

score 2 · Accepted Answer

也许您可以使用以下攻击，采用用于制作哈希的技术是一个简单的计算。

例如，如果使用 100 的模散列进行计算，我们有：

示例输入：8379547378 输出哈希：78

哈希值 78 的一般公式是 78 +100*k（k 个属于整数）。因此，可以尝试所有可能的序列。请注意，在本例中，模块 100 将搜索空间从 100% 减少到 1%。如果有可能建立一个预感这个数字是 10 位，我们可以使搜索进一步减少到 78 +100 k (10 ^7<=k< 10^8)。

另一种方法是用大量非常棒的哈希值及其入口填充数据库，然后在该数据库中进行搜索。

我希望我有一点帮助。

score 2 · Accepted Answer

首先，一般来说，不可能“反转”加密散列函数。这是因为这些函数通常需要比输出更多的输入数据。

例如，MD5 采用 512 位输入（64 字节）并产生 128 位输出（16 字节）。因此，输入中根本没有足够的信息来重建输出。事实上，大约有 2^384（一个非常大的数字）不同的输入具有完全相同的输出哈希。

相反，密码学家讨论了三种不同类型的哈希攻击：

第一次原像攻击：给定一个哈希 h，找到任何消息 m 使得 hash(m) = h
第二次原像攻击：给定一条固定消息 m1，找到任何其他消息 m2，使得 hash(m1) = hash(m2)
碰撞攻击：找到任意两条消息 m1 和 m2 使得 hash(m1) = hash(m2)

现在回到这个“倒车”业务。当你想“破解一个 MD5 密码”时，你真正想做的是第一次原像攻击：找到任何“密码”m，使得 hash(m) 与存储的哈希 h 匹配。通常，这需要通过蛮力进行大约 2^128 次猜测（超过地球上所有计算机在一个世纪内所能处理的次数）。MD5 中存在已知的弱点，将其降低到 ~2^123，这仍然太难以实用。

但由于密码一般都是由字母和数字组成的短字符串，因此人们实际可能使用的密码远少于 2^128 个。更像是 2^40（即大约一万亿）。这仍然很多，但如果你有一年左右或很多 PS3，就不可能全部尝试。但是，如果您知道要破解大量密码怎么办？您可以将所有可能密码的哈希值存储在磁盘上以供将来使用，而不是每次进行 2^40 次猜测。这（或多或少）是彩虹表：有人已经完成了所有工作，因此您只需查找答案并跳过大部分工作。

你是对的，使用盐打破了这一点。现在你又回到了 2^40 次猜测和满屋的 PS3。使用更好的哈希函数（如 SHA512 或 SKEIN）并不会真正改变这一点，因为它不会改变您需要尝试的可能密码的数量。教训：你需要使用一个很难猜到的密码！

好的，但是 MD5 和 SHA1 是否仍被视为已损坏？是的，但不是在这里（还）真正重要的方式。该领域令人振奋的消息都是关于碰撞攻击，这与破坏部分 SSL 安全性和数字签名有关，但与破坏存储的密码无关。密码学家预计这项工作不久会导致更好的攻击，因此在新程序中使用 MD5 或 SHA1 可能不是一个好主意，但使用 MD5/SHA1 + 适当的加盐来存储密码的程序仍然可以。

score 1 · Accepted Answer

从技术上讲，任何标准哈希算法都是不可逆的！因此，一旦您获得消息的哈希，就应该无法从其哈希字符串中获取原始消息。人们试图破解它的唯一方法是使用蛮力攻击。暴力破解是你能做的最愚蠢的事情，尝试所有可能的密钥！这就解释了为什么安全密码算法的特征之一是拥有大的密钥空间。但是，如果您在某些情况下使用该过程，它可能是实用的，这正是彩虹表所做的。

彩虹表是一个预先计算的表，用于所有可能的组合，直到一定长度。这意味着您可以创建字符（大写和小写）、数字和特殊字符的所有可能组合，直到一定长度。据我所知，最完整的彩虹表可以破坏最多 10 个字符的字符串散列，其中包括数字、大写和特殊字符，因此，如果您的字符串长于该长度，则不应该担心破坏散列本身的任何安全问题。正如您在此处看到的那样，最多可以破解 8 个字符的 vista 密码的表的大小超过 100GB，并且这个数字呈指数增长，这使得进一步超过 10 或 12 个字符是不可能的。

只要你的字符串不容易猜到，足够长并且包含大写字母、数字和特殊字符，就不用担心:)

score 0 · Accepted Answer

0

该页面正在谈论的暴力破解基本上是动态生成彩虹表。

于 2011-09-23T02:24:34.350 回答

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

6 回答 6

Related

Reference