Hacker News new | past | comments | ask | show | jobs | submit login

The problem is that it's relatively easy to brute-force attack even a salted hash today.

On the first day, people stored passwords in plain text. If someone got access to your database, they had all the passwords.

On the second day, people decided to hash the passwords so that people couldn't unencrypt them. Then the attackers created rainbow tables that correlated each hash with its associated password since the password would always hash to the same value (so you have "109BCA" in your database, but they have a table that has that hash and that "12345" hashes to that value).

On the third day, people decided to salt the hashes to render the rainbow tables ineffective. Now, each password would hash to a different value so they couldn't just look up the password for a given hash. However, as computing power increased it became easy to just brute-force the password. You have the hash and you have the salt so you can just try every password with the hash until you get a match.

  hashed_password = "ACBDEF1234567890"
  salt = "12345"
  possible_passwords = ["password1", "ilikesheep", "micro$oft"]
  possible_passwords.each do |pass|
    if Digest::SHA1.hexdigest("#{pass}#{salt}") == hashed_password
      real_password = pass
    end
  end
The problem is that code like that has gotten really cheap to run and it's incredibly parallel (you can have loads of machines each take a piece of the workload - oh, and hopefully no one will make a joke that you'd never write that in Ruby; I just felt that would be easy pseudo-code to demonstrate). You can just try combinations of passwords at random, but there are lists of more common passwords that you can try first making it go even faster. Hashing algorithms are meant to be fast because they're meant to be usable on a large piece of data. As such, it also becomes fast to brute force check all sorts of combinations.

On the fourth day, people started using things like bcrypt because bcrypt was made to be slow. The fact that bcrypt is slow means that if someone wants to brute force it, it will be very slow going for them. If one can check 10,000 SHA1 hashes in a second, but only 10 bcrypt hashes in a second, it will take 1,000x longer to crack the bcrypt stored password (those are just made-up numbers as an example).

Salting is better than not salting because they have to brute force the password. However, as computing power increases it isn't so much better because brute forcing is becoming easy. One needs to use a slow algorithm to make sure that cracking it will also be slow (prohibitively slow). Bcrypt also allows you to specify how much work you want it to have to do. This way, as computing power increases, you can increase the amount of computing power needed to compute the bcrypt. By contrast, hashes are meant to go fast and so every day they're getting less secure.




Salting was introduced long before rainbow tables were invented.


Salting was introduced in the 1970's to combat the underlying class of attacks that rainbow tables optimize. Think of rainbow tables as a compression scheme; the attack is precomputation.


That said, I don't know why, with today's computing power, people don't make rainbow table chains longer (or shorter, it's been a while since I read the paper) to save on disk space.


And with GPUs rainbow tables are gone - it's now quicker to calculate an MD5 than read it from disk!


> And with GPUs rainbow tables are gone

Not exactly. I could have a rainbow table for every possible password eight characters or fewer, and find it in a rainbow table in log(table_size) but to brute force it might take several days. GPUs make it so you can generate bigger rainbow tables faster too.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: