How long to go over the SHA-512 salty hash? (salt provided)

Question

Here is the 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); } 

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

Answer 1

In your case, breaking a hash algorithm is equivalent to detecting a collision in a hash algorithm. This means that you do not need to search for the password itself (which would be a preimage attack ), you just need to find the hash output of the function equal to the hash of the real password (thus, “collision”). A collision search using a birthday attack takes O (2 ^ n / 2), where n is the length of the output of the hash function in bits.

SHA-2 has an output size of 512 bits, so O (2 ^ 256) will be required to find a collision. Given that there are no smart attacks on the algorithm itself (currently, none of them are known for the SHA-2 hash family), this is what it takes to break the algorithm.

To understand what 2 ^ 256 actually means: it is currently estimated that the number of atoms in the (whole !!!) universe is about 10 ^ 80, which is about 2 ^ 266. Assuming an input of 32 bytes (which reasonable for your case - 20 bytes of salt + 12 bytes), my machine takes ~ 0.22 s (~ 2 ^ -2 s) for 65536 (= 2 ^ 16) calculations. Thus, 2 ^ 256 calculations would be performed in calculations 2 ^ 240 * 2 ^ 16, which would take

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

Even calling these millions of years is ridiculous. And it's not much better with fast hardware on the planet that computes thousands of hashes in parallel. No human technology can crunch this number into something acceptable.

So forget about the coarse coercion of SHA-256. Your next question was about vocabulary words. Rainbow tables have traditionally been used to extract such weak passwords. The rainbow table, as a rule, is a table of pre-computed hash values, the idea is that if you were able to recompute and save all possible hashes along with your input, then you need O (1) to find the given hash and get a valid prototype for him. Of course, this is impossible in practice, since there is no storage device that could store such a huge amount of data. This dilemma is known as memory-time compilation . Since you can store so many values ​​that regular rainbow tables include some form of hash chain with intermediate reduction functions (this is explained in detail in the Wikipedia article) in order to save space by refusing to save time.

Salts were a countermeasure to make such rainbow tables impracticable. To prevent cybercriminals from pre-calculating the table for a particular salt, it is recommended that you apply salt values ​​for each user. However, since users do not use secure, completely random passwords, it is still amazing how successful you can get if the salt is known, and you simply iterate over a large dictionary of shared passwords in a simple trial and error scheme. The connection between natural language and chance is expressed as entropy . Typical password choices usually have low entropy, while completely random values ​​will contain a maximum of entropy.

The low entropy of typical passwords provides a relatively high probability that one of your users will use a password from a relatively small database of shared passwords. If you are Google for them, you will eventually find torrent links for such password databases, often in the gigabyte size category. The success of such a tool is usually from a few minutes to several days, if the attacker is not limited in any way.

Therefore, as a rule, hashing and salting are not enough, you also need to install other security mechanisms. You must use an artificially slowed-down entropy method such as PBKDF2, described in PKCS # 5 , and you must ensure that the waiting period for this user is respected before they can re-enter the password. A good scheme is to start at 0.5 s and then double that time for each failed attempt. In most cases, users do not notice this and do not fail much more often than three times on average. But this will significantly slow down any malicious outsider trying to attack your application.

Answer 2

I want to know the time for brute force when a password is a dictionary, and also when this word is not a dictionary.

Dictionary

Ball exponent: there are about 1,000,000 English words, and if a hacker can calculate about 10,000 SHA-512 hashes of the second ( update: see CodesInChaos comment, this estimate is very low), 1,000,000 / 10,000 = 100 seconds . So it would take a little more than a minute to crack the password of a word with one word for one user. If the user combines two dictionaries, you are in the area for several days, but it is still very possible if the attacker cares enough. Moreover, and he begins to become tough.

Random password

If the password is a truly random sequence of alphanumeric characters, upper and lower case, then the number of possible passwords of length N is 60 ^ N (there are 60 possible characters). This time we will do the calculation in a different direction; we will ask:. How long can a password be cracked for a given period of time? Just use this formula:

N = Log60(t * 10,000) where t is the time taken to calculate the hashes in seconds (again, assuming 10,000 hashes per second).

 1 minute: 3.2 5 minute: 3.6 30 minutes: 4.1 2 hours: 4.4 3 days: 5.2 

So, given 3 days, we can crack the password if it lasts 5 characters.

This is all a very ball park, but you get the idea. Update: see the comment below, you can actually crack much longer passwords than this.

What is going on here?

Let me clarify some misconceptions:

• Salt does not slow down the calculation of hashes , it just means that they have to crack each user password separately and the previously computed hash tables (buzz-word: rainbow tables) are made completely useless. Unless you have a pre-computed hash table, and you only crack one password hash, salting does not matter.

• SHA-512 is not intended for brute force . More efficient hashing algorithms, such as BCrypt, PBKDF2, or SCrypt , can be configured to take much longer, and the average computer can only calculate 10-20 hashes per second. Read this great answer about password hashing if you haven't already.

• update: as written in CodesInChaos comment, even high entropy passwords (about 10 characters) can be rude if you use the right hardware to calculate SHA-512 hashes.

---

Notes on accepted answer:

The accepted answer as of September 2014 is incorrect and dangerous incorrectly:

In your case, breaking a hash algorithm is equivalent to detecting a collision in a hash algorithm. This means that you do not need to search for the password itself (which would be a prototype attack). A collision search using a birthday attack takes time O (2 ^ n / 2), where n is the length of the output of the hash function in bits.

An attack on a birthday has nothing to do with breaking a given hash. And this is actually a great example of an attack on a prototype. This formula and the following couple of paragraphs lead to dangerously high and completely meaningless values ​​for attack time. As demonstrated above , it is entirely possible to crack salty dictionary passwords in minutes .

The low entropy of typical passwords allows for a relatively high probability that one of your users uses a password from a relatively small database with shared passwords ...

Therefore, as a rule, hashing and salting are not enough, you also need to install other security mechanisms. You should use an artificially slowed-down entropy method like PBKDF2 described in PKCS # 5 ...

Yes, please use an algorithm that is slow to compute, but what is entropy? Entering a password with low entropy through a hash does not increase entropy. It should keep entropy, but you cannot make the garbage password better with a hash, it does not work like that. A weak password set through PBKDF2 is still a weak password.

Answer 3

There is no answer to this question, since there are too many variables, but SHA2 has not yet been hacked (see: The lifetime of cryptographic hash functions ), therefore, it is still a good algorithm for storing passwords. Using salt is good because it prevents an attack from attacks on a dictionary or rainbow tables. The importance of salt is that it must be unique to each password. You can use a format such as [128-bit salt] [512-bit hash password] when storing hashed passwords.

The only viable attack method is to actually calculate the hashes for the different password options and ultimately find the right one by matching the hashes.

To give an idea of ​​how many hashes can be made per second, I think Bitcoin is a good example. Bitcoin uses SHA256 and reduces it, the more hashes you generate, the more bitcoins you get (which you can trade for real money), and since such people are motivated to use the GPU for this purpose. You can see in the hardware review that the average graphics card, which costs only $ 150, can calculate more than 200 million hashes / s. The longer and harder your password is, the longer it will take. Computing at 200 M / s, it takes about 300 hours to try all the possibilities for an alphanumeric character with 8 characters (capital, below, numbers). In real time, it is most likely less if the password is something suitable or a common English word.

As such with any security you need to look in context. What is the motivation of the attacker? What is an app? Having a random salt hash for each gives pretty good protection against cases where something like thousands of passwords is compromised.

One thing you can do is also add extra brute force protection by slowing down the hashing process. Since you only haveh the password once, and the attacker has to do it many times, this works in your favor. A typical way to do this is to take a value, hash it, output it, hash again and so on for a fixed number of iterations. For example, you can try something like 1000 or 10000 iterations. This will force an attacker to find each password several times.