暴力破解加盐 SHA-512 哈希需要多长时间?(提供盐) [英] How long to brute force a salted SHA-512 hash? (salt provided)

问题描述

这是一个Java算法:

Here is an algorithm in Java:

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}

假设盐是已知的.我想知道当密码是字典单词以及不是字典单词时暴力破解的时间.

Assume the salt is known. I want to know the time to brute force for when the password is a dictionary word and also when it is not a dictionary word.

推荐答案

在你的情况下，破坏哈希算法相当于发现哈希算法中的冲突.这意味着您不需要找到密码本身(这将是 原像攻击)，您只需要找到与有效密码的哈希值相等的哈希函数的输出(因此是冲突").使用 生日攻击 发现碰撞需要 O(2^(n/2)) 时间，其中n 是散列函数的输出长度(以位为单位).

In your case, breaking the hash algorithm is equivalent to finding a collision in the hash algorithm. That means you don't need to find the password itself (which would be a preimage attack), you just need to find an output of the hash function that is equal to the hash of a valid password (thus "collision"). Finding a collision using a birthday attack takes O(2^(n/2)) time, where n is the output length of the hash function in bits.

SHA-2 的输出大小为 512 位，因此发现冲突需要 O(2^256) 时间.鉴于对算法本身没有巧妙的攻击(目前尚无针对 SHA-2 哈希家族的攻击)，这就是破解算法所需要的.

SHA-2 has an output size of 512 bits, so finding a collision would take O(2^256) time. Given there are no clever attacks on the algorithm itself (currently none are known for the SHA-2 hash family) this is what it takes to break the algorithm.

感受一下 2^256 的实际含义:目前认为(整个！！！)宇宙中的原子数大约是 10^80，也就是大约 2^266.假设输入 32 字节(这对您的情况来说是合理的 - 20 字节盐 + 12 字节密码)我的机器需要 ~0,22s (~2^-2s) 进行 65536 (=2^16) 计算.所以 2^256 计算将在 2^240 * 2^16 计算中完成，这需要

To get a feeling for what 2^256 actually means: currently it is believed that the number of atoms in the (entire!!!) universe is roughly 10^80 which is roughly 2^266. Assuming 32 byte input (which is reasonable for your case - 20 bytes salt + 12 bytes password) my machine takes ~0,22s (~2^-2s) for 65536 (=2^16) computations. So 2^256 computations would be done in 2^240 * 2^16 computations which would take

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

即使称这为数百万年也是荒谬的.使用地球上最快的硬件并行计算数千个哈希值并没有变得更好.没有任何人类技术能够将这个数字处理成可以接受的数字.

Even calling this millions of years is ridiculous. And it doesn't get much better with the fastest hardware on the planet computing thousands of hashes in parallel. No human technology will be able to crunch this number into something acceptable.

所以忘记这里的暴力破解 SHA-256.你的下一个问题是关于字典单词的.传统上使用 彩虹表 来检索这种弱密码.彩虹表通常只是一个预先计算的哈希值的表，其想法是，如果您能够预先计算并存储每个可能的哈希及其输入，那么查找给定哈希并检索一个给定的哈希需要 O(1)它的有效原像.当然这在实践中是不可能的，因为没有存储设备可以存储如此大量的数据.这种困境被称为内存时间权衡.由于您只能存储这么多值，因此典型的彩虹表包括某种形式的哈希链和中间缩减函数(这在 Wikipedia 文章中有详细说明)，通过放弃一些时间节省来节省空间.

So forget brute-forcing SHA-256 here. Your next question was about dictionary words. To retrieve such weak passwords rainbow tables were used traditionally. A rainbow table is generally just a table of precomputed hash values, the idea is if you were able to precompute and store every possible hash along with its input, then it would take you O(1) to look up a given hash and retrieve a valid preimage for it. Of course this is not possible in practice since there's no storage device that could store such enormous amounts of data. This dilemma is known as memory-time tradeoff. As you are only able to store so many values typical rainbow tables include some form of hash chaining with intermediary reduction functions (this is explained in detail in the Wikipedia article) to save on space by giving up a bit of savings in time.

盐是使这种彩虹表不可行的对策.为了阻止攻击者预先计算特定盐的表，建议应用每个用户的盐值.但是，由于用户不使用安全的、完全随机的密码，如果知道 salt 并且您只需在一个简单的试错方案中迭代一个包含常见密码的大型字典，那么您能取得多大的成功仍然令人惊讶.自然语言与随机性之间的关系表示为熵.典型的密码选择通常具有低熵，而完全随机的值将包含最大熵.

Salts were a countermeasure to make such rainbow tables infeasible. To discourage attackers from precomputing a table for a specific salt it is recommended to apply per-user salt values. However, since users do not use secure, completely random passwords, it is still surprising how successful you can get if the salt is known and you just iterate over a large dictionary of common passwords in a simple trial and error scheme. The relationship between natural language and randomness is expressed as entropy. Typical password choices are generally of low entropy, whereas completely random values would contain a maximum of entropy.

典型密码的低熵使得您的用户使用相对较小的常用密码数据库中的密码的可能性相对较高.如果你用谷歌搜索它们，你最终会找到此类密码数据库的种子链接，通常在千兆字节大小的类别中.如果攻击者不受任何限制，使用此类工具通常需要几分钟到几天才能成功.

The low entropy of typical passwords makes it possible that there is a relatively high chance of one of your users using a password from a relatively small database of common passwords. If you google for them, you will end up finding torrent links for such password databases, often in the gigabyte size category. Being successful with such a tool is usually in the range of minutes to days if the attacker is not restricted in any way.

这就是为什么通常单独散列和加盐是不够的，您还需要安装其他安全机制.您应该使用人为减慢熵诱导方法，例如 PKCS#5 中描述的 PBKDF2 并且您应该为给定的用户强制等待一段时间，然后他们才能重新尝试输入密码.一个好的方案是从 0.5 秒开始，然后将每次失败尝试的时间加倍.在大多数情况下，用户不会注意到这一点，并且平均失败的次数不会超过 3 次.但它会显着减慢任何恶意外来者试图攻击您的应用程序的速度.

That's why generally hashing and salting alone is not enough, you need to install other safety mechanisms as well. You should use an artificially slowed down entropy-enducing method such as PBKDF2 described in PKCS#5 and you should enforce a waiting period for a given user before they may retry entering their password. A good scheme is to start with 0.5s and then doubling that time for each failed attempt. In most cases users don't notice this and don't fail much more often than three times on average. But it will significantly slow down any malicious outsider trying to attack your application.

这篇关于暴力破解加盐 SHA-512 哈希需要多长时间?(提供盐)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！