有没有办法在没有彩虹表的情况下颠倒散列？ [英] is there a way to reverse a hash without rainbow tables?
问题描述
这个页面表明像md5（）和sha1（）这样的散列算法可以颠倒因为我们现在拥有巨大的处理能力。在这一点上，我认为只有彩虹表才有可能。我是否错了？
如果Rainbow Tables是唯一的出路，那么人们如何能够反转用盐做的散列？
$ b $那么，这个问题一般是重复的这个问题。但是，要回答您的确切问题：
在这一点上，我只能用Rainbow Tables才能做到这一点。我错了吗？
从技术上讲，是的，你错了。给定足够的处理能力，散列函数不可恢复。关键在于它需要多少处理能力，在大多数情况下，处理能力远远超出您的想象。原因是在散列周期的每个阶段，可能值的数量呈指数增长。对于MD5，每个阶段（其中有64个）会将可能性的数量乘以10 ^ 77（很多零）。因此，要成功逆转MD5，您必须尝试真正的大量可能的排列组合（后包络计算显示的尝试次数为10 ^ 4932次）。有了今天创建的最快的超级计算机（每秒大约8 petaflops或8x10 ^ 15个浮点运算），你只需要大约10 ^ 4908年即可将其逆转。顺便说一句，现在是宇宙年龄的2.5x10 ^ 4898倍。真的，这是一个巨大的数字，超出了我们人类理解的能力......
这绝对是最好的情况。
因此技术上可以反转。但实际上，并非如此。
如果彩虹表是唯一的选择，那么某人可以如何反转所做的散列用盐？
事情是没有人需要来反转它。他们只需要找到一个碰撞。基本上，碰撞是导致相同输出的两个输入。因此，如果 hash（a）= x 并且 hash（b）= x ， a 和 b 是彼此之间的冲突。因此，我们所需要做的就是找到一个碰撞（它相信或不相信比找到确切的输入更容易，因为技术上有无数的输入可以提供特定的输出）。输入密码的大小，通常碰撞是原始密码。
查找这种冲突的最简单方法是预先计算散列列表（通常称为彩虹表）。基本上所有你需要做的就是在表格中查找散列，看看原件是否在那里。如果是这样，你就完成了（这很简单）。
通常会添加盐以对抗彩虹表。这是因为如果用户输入 1234 作为他们的密码，并且使用 abcdefghijklmnop 作为盐，那么原件将是 1234abcdefgjhijklmnop ，这显然不太可能出现在彩虹表中。因此，加入强烈的盐可以防止预先计算的彩虹桌。
暴力强制
然而，如果你只是做散列（传递+盐），那么就有一个重要的问题。它不受预先计算的彩虹表影响，但容易遭受暴力强制。原因是加密哈希函数（如sha1，md5，sha256等）被设计得很快。他们的传统角色在签名，所以他们需要快速才能发挥作用。但是，在密码存储中，这是一个弱点。使用现代GPU，攻击者可以在几小时内使用简单的哈希函数（仅尝试每种可能的密码排列方式）使用简单的哈希函数（有关更多详细信息，请参阅博客文章）...
最好的预防有两个特点： >
预先计算一个值表（一个彩虹表）并不容易。
散列单个值并不容易蛮力）。
事实证明，使用散列函数有一个简单的方法。简单地遍历它，并使输出依赖于大量的散列函数：
var result = password + salt;
for（var i = 0; i <10000000; i ++）{
result = hash（result + salt）;
$ / code> 关键在于，通过人为地减缓和使用盐，重新使它抵抗预计算和暴力强制。
事实证明，有两种标准算法可以做到这一点（也就是说，使用原则）。
最好的是Blowfish hash（bcrypt），它并不真正使用哈希原始函数，而是使用Blowfish密码的密钥衍生周期。它通过 crypt（） 在PHP中可用。要使用它：
$ hash = crypt（$ password，'$ 2a $ 07 $'。$ salt。'$'） ;
然后用
$ hash == crypt（$ password，$ hash）;
另一种方法（稍不优先）是 PBKDF2 。用PHP进行编程：
pre code $函数pbkdf2（$ hashFunc，$ password，$ salt，$ iterations，$ length = 32） {
$ size = strlen（hash（$ hashFunc，''，true））;
$ len = ceil（$ length / $ size）;
$ result ='';
（$ i = 1; $ i <= $ len; $ i ++）{
$ tmp = hash_hmac（$ hashFunc，$ salt。pack（'N'，$ i），$ password ，真）;
$ res = $ tmp; （$ j = 1; $ j <$ iterations; $ j ++）{
$ tmp = hash_hmac（$ hashFunc，$ tmp，$ password，true）;
。
$ res ^ = $ tmp;
}
$ result。= $ res;
}
return substr（$ result，0，$ length）;
}
注意： 这些都不会保护用户免受非常弱密码的侵害。如果他们输入词典单词或通用密码，攻击者可能会破解它。然而，他们会加强对中等强度密码的防御...... 更多阅读：
Possible Duplicate:
md5 decoding. How they do it?
this page suggests that a hash algorithm like md5() and sha1() can be reversed because of the huge processing power that we have nowadays. At this point i tought it was only possible with Rainbow Tables. Was i wrong?
In case Rainbow Tables is the only way to go, how someone could reverse a hash that was made with a salt?
Well, this question in general is a duplicate of This Question. However, to answer your exact questions:
At this point i tought it was only possible with Rainbow Tables. Was i wrong?
Technically, yes you are wrong. No hash function is unrecoverable, given enough processing power. The key point, is how much processing power it takes, which in most cases is far bigger than you can imagine. The reason is that the number of possible values increases exponentially at each stage of the hash cycle. For MD5, each stage (there are 64 of them) would multiply the number of possibilities by 10^77 (a lot of zeros). So to successfully reverse an MD5, you'd have to try a really large number of possible permutations (a back-of-envelope calculation shows somewhere on the order of 10^4932 tries). With the fastest super computer ever created today (about 8 petaflops, or 8x10^15 floating point operations per second), you're looking at approximately 10^4908 years to reverse it. Which incidentally is 2.5x10^4898 times the age of the universe right now. Really, it's an enormous number that's beyond our human ability to comprehend...
And that's an absolute best possible case situation.
So technically it is possible to reverse. But practically, no it is not.
In case Rainbow Tables is the only way to go, how someone could reverse a hash that was made with a salt?
The thing is that nobody needs to reverse it. They just need to find a collision. Basically, a collision is two inputs that lead to the same output. So if hash(a) = x and hash(b) = x, a and b are collisions of each other. So, all we need to do is find a collision (which believe it or not is easier than finding the exact input, since there are technically an infinite number of inputs that can give a particular output). With input the size of passwords, typically the collision is the original password.
The easiest way to find this collision is with a precomputed list of hashes (typically called a rainbow table). Basically all you need to do is then look up the hash in the table to see if the original is there. If so, you're done (that easy).
Salts are typically added to combat rainbow tables. This is because if the user enters 1234 as their password, and you use abcdefghijklmnop as the salt, the original would be 1234abcdefgjhijklmnop, which is significantly less likely to appear in a rainbow table. So adding a strong salt will protect against precomputed rainbow tables.
Brute Forcing
However, there is a significant concern if you just do hash(pass + salt). It's not susceptible to precomputed rainbow tables, but it is susceptible to brute forcing. The reason is that cryptographic hash functions (such as sha1, md5, sha256, etc) are designed to be fast. Their traditional role is in Signing, so they need to be fast to be useful. However, in password storage this is the weakness. With modern GPU's, an attacker could brute force (just try every possible password permutation) a simple hash with salt in a matter of hours (for more details, see my blog post about it)...
The best prevention
The best prevention has two features:
It's not easy to pre-compute a table of values (a rainbow table)
It's not fast to hash a single value (not easy to brute force).
As it turns out, there's a simple way of doing that using a hash function. Simply iterate over it and make the output dependent upon a large number of hash functions:
var result = password + salt;
for (var i = 0; i < 10000000; i++) {
result = hash(result + salt);
}
The key is that by making it artificially slow and using a salt, you're making it resistant to precomputation and brute forcing.
As it turns out, there are 2 standard algorithms that do this (well, use the principles).
The best one is Blowfish hash (bcrypt) which doesn't really use a hash primitive function, but uses the key derivation cycle of the Blowfish cipher. It's available in PHP via crypt(). To use it:
$hash = crypt($password, '$2a$07$' . $salt . '$');
And verify it with
$hash == crypt($password, $hash);
The other method (which is slightly less preferred) is PBKDF2. To program it in 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);
}
Note:
None of these will protect a user against a very weak password. If they enter a dictionary word, or a common password it will still be likely that an attacker will be able to crack it. They will however add to the defense against moderate strength passwords...
Some more reading:
- 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
这篇关于有没有办法在没有彩虹表的情况下颠倒散列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
