暴力加盐 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)它的有效原像.当然，这在实践中是不可能的，因为没有存储设备可以存储如此大量的数据.这种困境被称为内存时间权衡.由于您只能存储如此多的值，因此典型的彩虹表包括某种形式的带有中间归约函数的哈希链(这在维基百科文章中有详细解释)，以通过放弃一点时间节省来节省空间.

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 并且您只是在一个简单的试错方案中迭代一个大的常用密码字典，那么您可以获得多么成功仍然令人惊讶.自然语言和随机性之间的关系表示为entropy.典型的密码选择通常具有低熵，而完全随机的值将包含最大熵.

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屋！