Why do salts make dictionary attacks "impossible"?

Question

Possible duplicate:
Need help understanding salt salt

Update: Please note that I am not asking what salt is, what is a rainbow table, what is dictionary attack, or what is the purpose of salt. I ask: if you know user salts and hash, isn’t it easy to calculate their password?

I understand the process and implement it myself in some of my projects.

s = random salt storedPassword = sha1(password + s) 

In the database you are storing:

 username | hashed_password | salt 

Each salting implementation that I saw adds salt either at the end of the password, or begins:

 hashed_Password = sha1(s + password ) hashed_Password = sha1(password + s) 

Thus, a hacker's vocabulary attack, which is worth its salt (ha ha), simply launches each keyword against stored salts in the common combinations listed above.

Undoubtedly, the implementation described above simply adds another step for the hacker, without solving the main question? What alternatives exist to solve this problem or I do not understand the problem?

The only thing I can do is to have a secret blending algorithm that combines salt and password together in a random pattern or adds other custom fields to the hashing process, i.e. the hacker must have access to the database AND code to string them to attack the dictionary, to prove their fruitfulness. (The update, as stated in the comments, is best to assume that the hacker has access to all your information, so this is probably not the best).

Let me give an example of how I suggest a hacker hack a user database with a list of passwords and hashes:

Data from our hacked database:

 RawPassword (not stored) | Hashed | Salt -------------------------------------------------------- letmein WEFLS... WEFOJFOFO... 

General Password Dictionary:

  Common Password -------------- letmein 12345 ... 

For each user entry, loop common passwords and hash them:

 for each user in hacked_DB salt = users_salt hashed_pw = users_hashed_password for each common_password testhash = sha1(common_password + salt) if testhash = hashed_pw then //Match! Users password = common_password //Lets visit the webpage and login now. end if next next 

Hope this illustrates my point much better.

Given 10,000 shared passwords and 10,000 user records, we will need to calculate 100,000,000 hashes to find as many user passwords as possible. This may take several hours, but this is not a problem.

Crack Theory Update

We will assume that we are a corrupt web host that has access to a database of SHA1 hashes and salts along with your algorithm for mixing them. The database contains 10,000 user records.

This site claims to be able to calculate 2,300,000,000 SHA1 hashes per second using the GPU. (In a real situation, the situation is likely to be slower, but for now we will use this figure).

(((95 ^ 4) / 2300000000) / 2) * 10000 = 177 seconds

Given the full range of 95 printable ASCII characters with a maximum length of 4 characters, divided by the computation speed (variable), divided by 2 (assuming that the average password detection time requires an average of 50% permutations), it would take 177 seconds for 10,000 users, to generate all user passwords whose length is <= 4.

Rather adjust it for realism.

(((36 ^ 7) / 1,000,000,000) / 2) * 10,000 = 2 days

Assuming case insensitivity with a password length <= 7 of only alphanumeric characters, it would take 4 days for 10,000 user records, and I halved the speed of the algorithm to reflect overhead and not ideal circumstances.

It is important to recognize that this is a linear attack using brute force, all calculations are independent of each other, so this is an ideal task for solving several systems. (IE is easy to configure 2 computers running an attack from different ends, which will be half the shutdown time).

Given the case of recursive password hashing 1000 times to make this task more expensive:

(((36 ^ 7) / 1,000,000,000) / 2) * 1000 seconds = 10.8839117 hours

This means a maximum length of 7 alphanumeric characters when performing less than half the speed of the quoted digit for one user.

Recursive hashing 1000 times effectively blocks a full attack, but targeted attacks on user data are still vulnerable.

Answer 1

Yes, you only need 3 days for sha1 (salt | password). That's why good password storage algorithms use hashing 1000 iterations: you will need 8 years.

Answer 2

He does not stop the attack on words.

What he does is stop someone who manages to get a copy of your password file using a rainbow table to find out what passwords from hashes are.

In the end, it can be brutally forced. The answer to this part is to make your users not use dictionary words as passwords (for example, the minimum requirements of at least one number or a special character).

Update

I should have mentioned this before, but some (most?) Password systems use different salts for each password, probably stored with the password itself. This makes a single rainbow table useless. This is how the UNIX crypt library works, and modern UNIX-like operating systems have expanded this library with new hashing algorithms.

I know that support for SHA-256 and SHA-512 has been added to newer versions of GNU cryptography.

Answer 3

More precisely, a dictionary attack , that is, an attack in which all words in an exhaustive list are tried out, does not become "impossible", but it becomes impractical : each bit of salt doubles the amount of storage and computation .

This differs from pre-computed verbal attacks, such as attacks using rainbow tables, where it does not matter whether the salt is secret or not.

Example. Using 64-bit salt (i.e. 8 bytes) you need to check additional combinations of ⁶⁴ passwords in a dictionary attack. With a dictionary containing 200,000 words, you will need to do

200,000 * 2 ⁶⁴ = 3.69 * 10 ²⁴

tests in the worst case - instead of 200,000 tests without salt.

An additional advantage of using salt is that an attacker cannot pre-compute password hashes from his dictionary. It takes too much time and / or space.

Update

Your update assumes that the attacker already knows the salt (or stole it). This, of course, is a different situation. However, an attacker cannot use a pre-computed rainbow table. Hashing speed is important here. To make an attack inappropriate, the hash function must be slow. MD5 or SHA are not good candidates here because they are designed to be fast; the best candidates for hashing algorithms are Blowfish or some of its variants.

Update 2

Read well about protecting password hashes in general (much more than the original question, but still interesting):

Enough with rainbow tables: what you need to know about secure password schemes

Consequence of the article: use salted hashes created using bcrypt (based on Blowfish) or Eksblowfish , which allows you to use custom installation times to slow down hashing.

Answer 4

A dictionary is a structure in which values ​​are indexed by keys. In the case of a pre-computed dictionary attack, each key is a hash, and the corresponding value is a password that leads to a hash. With a pre-computed dictionary in hand, an attacker can “instantly” find a password that will generate the necessary hash for login.

With salt, the space needed to store the dictionary is growing fast & hellip; so fast that trying to pre-compute a password dictionary will soon become meaningless.

The best salts are randomly selected from a cryptographic random number generator. Eight bytes is a practical size, and more than 16 bytes have no purpose.

---

Salt does much more than just "make an attacker’s job more annoying." This eliminates the whole class of attack - the use of pre-computed dictionaries.

Another element is necessary for the complete protection of passwords, and this is "key gain". One round of SHA-1 is not good enough: a secure password hashing algorithm should be very slow in computational mode.

Many people use the PBKDF2 function, a key derivation function that feeds results into a hash function thousands of times. The bcrypt algorithm is similar using a slow iterative key output.

When the hashing operation is very slow, a table becomes more and more preferable for an attacker computer. But suitable saline lesions that are suitable.

---

Comments

Below are the comments I made on this subject.

---

Without the solider, the attacker would not use the method demonstrated in Update 2. He simply searched the pre-computed table and received a password in O (1) or O (log n) time (n is the number of potential passwords). Salt is what prevents it and makes it use the O (n) approach shown in Update 2.

After reducing to an O (n) attack, we must consider how long each attempt takes. Strengthening the key can lead to the fact that each attempt in the cycle will take a full second, which means that the time required to check 10k passwords on 10 thousand users will stretch from 3 days to 3 years & hellip; and with only 10k passwords you are likely to crack zero passwords in that time.

You should keep in mind that an attacker will use the fastest tools that he can, and not PHP, so thousands of iterations, not 100, will be a good parameter to strengthen the key. It takes a significant fraction of a second to calculate the hash for a single password.

Strengthening key is part of the standard key derivation algorithms PBKDF1 and PBKDF2, from PKCS # 5, which make excellent password obfuscation algorithms ("derived key" is a "hash").

Many users at StackOverflow cite this article because it was a response to Jeff Atwood's post about the dangers of rainbow tables. This is not my favorite article, but it discusses these concepts in more detail.

---

Of course, you assume that the attacker has everything: salt, hash, username. Assume that the attacker is a corrupt employee of the hosting company who dumped the user table to the myprettypony.com fan site. He is trying to recover these passwords because he is going to turn around and see if your pony fans used the same password on their citibank.com accounts.

With a well-designed password scheme, this guy will not be able to recover passwords.

Answer 5

The purpose of salting is to prevent cushioning of the attacker's efforts.

Without salt, one table of pre-computed hash password entries (e.g. MD5 of all 5-character alphanumeric strings, easy to find on the Internet) can be used for every user in every database in the world.

Using site-specific salt, the attacker must figure out the table himself and then use it for all users of the site.

When using salt for the user, the attacker must expend this effort for each user separately.

Of course, this does not protect really weak passwords directly from the dictionary, but protects strong enough passwords from this depreciation.

Answer 6

In addition, another important point - the use of salt used by USER, prevents the detection of two users with SAME password - their hashes will match. This is why hash hash many times (salt + username + password)

If you try to keep a secret hash, the attacker will also be unable to verify the hashes.

Edit - just noticed that the main comment was made in the comment above.

Answer 7

Salts are implemented to prevent attacks with a rainbow table. The rainbow table is a list of pre-computed hashes, which makes translating the hash into this phrase much easier. You need to understand that salting is ineffective, like modern prevention of password cracking, if we do not have a modern hashing algorithm.

So, let's say we are working with SHA1 using recent exploits discovered using this algorithm, and suppose we have a computer running 1,000,000 hashes per second, it will take 5.3 million years to search for a collision , so php can run 300 seconds, big woop, really does not matter. The reason we rely on is that if someone bothered to generate all the common vocabulary phrases (2 ^ 160 people, welcome to the exploits of the 2007 era).

So, here is a real database with two users that I use for testing and administration.

 RegistrationTime UserName UserPass 1280185359.365591 briang a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5 1281546174.065087 test 5872548f2abfef8cb729cac14bc979462798d023 

In fact, the salting scheme is your sha1 (registration time + username). Come on, tell me my password, these are real passwords in production. You can even sit and hash a list of words in php. Astonishing.

I'm not crazy, I just know that it is safe. For fun, the test password is test . sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

You will need to create a whole rainbow table perpendicular to 27662aee8eee1cb5ab4917b09bdba31d091ab732 only for this user. This means that I can not allow my passwords to compromise one rainbow table, the hacker needs to create a whole rainbow table for test 27662aee8eee1cb5ab4917b09bdba31d091ab732 for testing, and again f3f7735311217529f2e020468004a2aa5b3dee7f bri. Remember 5.3 million million years for all hashes. Think about the storage size of only 2 ^ 80 hashes (which is more than 20 yottabytes ), this will not happen.

Do not confuse salting as a means of creating a hash that you can never decode, it is a means of preventing the rainbow table from translating your strong all user passwords. It is possible at this level of technology.

Answer 8

The idea of ​​a dictionary attack is that you take a hash and find the password from which this hash was calculated without calculating the hash. Now do the same with a salted password - you cannot.

Not using salt makes finding a password as easy as looking up a database. Adding a solo makes the attacker perform a hash calculation of all possible passwords (even for a dictionary prefix, this significantly increases the attack time).

Answer 9

In simple terms: without salting, each candidate password only needs to be hashed once to check it against each user anywhere in the "known universe" (collecting compromised databases) whose password is hashed using the same algorithm. When using salting, if the number of possible salt values ​​significantly exceeds the number of users in the "known universe", each candidate password must be hashed separately for each user with whom it will be tested.

Answer 10

Simply put, salting does not prevent the hash from attacking (bruteforce or dictionary), it only complicates the work; an attacker will either need to find a salting algorithm (which, if implemented properly, will use a larger number of iterations), or to perform tedious work with an algorithm that, if it is not very simple, is almost impossible. Salt also almost completely discards the ability to search rainbow tables ...

Answer 11

Salt makes the Rainbow table attack much harder, as it makes a single hash password much harder to crack. Imagine you have a terrible password of only 1. An attack on a rainbow table will immediately crack.

Now imagine that each password in db is salty with a long random value of many random characters. Now your lousy password "1" is stored in db as a hash of 1 plus a bunch of random characters (salt), so in this example the rainbow table should have a hash for something like: 1.

So if your salt is something safe and random, say ()% ISLDGHASKLU (% #% #, for the rainbow hacker table there should be an entry for 1 * ()% ISLDGHASKLU (*% #% #. Rainbow table on this a simple password is no longer practical.