多长时间蛮力盐腌SHA-512哈希？ （提供盐） [英] How long to brute force a salted SHA-512 hash? (salt provided)

问题描述

这是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）; 
} 
  

假设盐已知。

解决方案

p>在你的情况下，打破哈希算法等效于在哈希算法中发现冲突。这意味着您不需要找到密码本身（这将是一个 preimage攻击），你只需要找到散列函数的输出等于有效密码的散列（因此冲突）。使用生日攻击查找冲突需要O（2 ^ n / 2）次，其中n是输出长度的散列函数的位。

SHA-2的输出大小为512位，因此发现碰撞需要O（2 ^ 256）的时间。鉴于对算法本身没有聪明的攻击（目前没有人知道用于SHA-2哈希族），这是打破算法所需要的。

为了得到什么2 ^ 256实际意味着：目前相信宇宙中的原子数约为10 ^ 80这大概是2 ^ 266。假设32字节输入（对于你的情况是合理的 - 20字节盐+ 12字节密码）我的机器需要〜0,22s（〜2 ^ -2s）为65536（= 2 ^ 16）计算。因此，将在2 ^ 240 * 2 ^ 16个计算中进行2 ^ 256个计算，这将取得

  2 ^ 240 * -2 = 2 ^ 238〜10 ^ 72s〜3,17 * 10 ^ 64年
  

这几百万年是可笑的。它并没有得到更好的与行星上最快的硬件并行计算成千上万的哈希。没有人类技术能够将这个数字压缩成可接受的数字。

所以，忘记了强制SHA-256。你下一个问题是关于字典词。要检索此类较弱的密码，传统上使用彩虹表。彩虹表通常只是一个预先计算的哈希值表，这个想法是，如果你能够预计算和存储每个可能的哈希及其输入，那么它将需要O（1）查找给定的哈希值并检索有效的preimage为它。当然，这在实践中是不可能的，因为没有可以存储这样大量的数据的存储设备。这种困境被称为记忆时间权衡。因为你只能存储这么多的值，典型的彩虹表包括一些形式的哈希链接与中间减少功能（这在维基百科文章中详细解释），通过放弃一点时间节省，节省空间。

盐是使这种彩虹表不可行的对策。为了阻止攻击者预先计算特定盐的表，建议应用每个用户的salt值。然而，由于用户不使用安全，完全随机的密码，如果盐已知，你只是在一个简单的尝试和错误方案中迭代一个大的常用密码字典，你可以获得成功仍然令人惊讶。自然语言与随机性之间的关系表示为熵。典型的密码选择通常是低熵，而完全随机的值将包含熵的最大值。

典型密码的低熵使得可能存在相对高其中一个用户使用来自相对较小的常用密码数据库的密码的机会。如果你google他们，你会最终找到这样的密码数据库，通常在千兆字节大小类别的洪流链接。如果攻击者不受任何限制，通常使用此类工具获得成功通常在几分钟到几天的范围内。

这就是为什么一般来说哈希和盐化是不够的，您还需要安装其他安全机制。您应该使用人为减慢的熵产生方法，例如 PKCS＃5 中所述的PBKDF2，以及您应该为给定用户强制执行等待期，然后他们可以重试输入其密码。一个好的方案是从0.5s开始，然后将每次失败尝试的时间加倍。在大多数情况下，用户不会注意到这一点，并且不会失败的频率比平均三倍多。但它会显着减慢任何恶意的外人试图攻击你的应用程序。

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.

解决方案

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 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.

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.

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.

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.

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