News for hackers. Stuff that matters.
Re:How To Safely Store A Password by tocomment on Tuesday December 14, 2010 @12:47PM (#2004965)
HN, is this the consensus? I thought certain hashes worked fine when properly salted?
Re:How To Safely Store A Password by sph on Tuesday December 14, 2010 @01:19PM (#2005107)
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.

Re:How To Safely Store A Password by tzs on Tuesday December 14, 2010 @01:31PM (#2005162)
Salting was introduced long before rainbow tables were invented.
Re:How To Safely Store A Password by tptacek on Tuesday December 14, 2010 @01:43PM (#2005207)
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.
Re:How To Safely Store A Password by StavrosK on Wednesday December 15, 2010 @06:15AM (#2007726)
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.
Re:How To Safely Store A Password by oiuytrtyuiuytr on Tuesday December 14, 2010 @01:49PM (#2005232)
And with GPUs rainbow tables are gone - it's now quicker to calculate an MD5 than read it from disk!
Re:How To Safely Store A Password by Xk on Tuesday December 14, 2010 @02:03PM (#2005282)
> 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.

Re:How To Safely Store A Password by frisco on Tuesday December 14, 2010 @12:52PM (#2004990)
Yes, this is consensus. "Salting" isn't actually a real security practice. See: http://chargen.matasano.com/chargen/2007/9/7/enough-with-the...
Re:How To Safely Store A Password by aidenn0 on Tuesday December 14, 2010 @01:07PM (#2005052)
That article actually states that salting is a real security practice, is a necessity, and that it's been in UNIX since 1976,
Re:How To Safely Store A Password by tptacek on Tuesday December 14, 2010 @01:45PM (#2005216)
He may be saying that because I've been making fun of people who use the word "salt" (in most other situations, crypto people would call that a "nonce"); I have in the past made the point that real crypto people never say "salt".

But then Eli Biham used the term extensively in his HAIFA framework and I lost the argument. I'll still make fun of the word (salt! smoked salt! peanut salt! hah!), but I can't say no crypto people use it. I wish they wouldn't, though.

Re:How To Safely Store A Password by eru on Tuesday December 14, 2010 @03:38PM (#2005649)
That argument sounds like the German balloon fliers, who insist that they "fahren" (drive) the balloon and don't "fliegen" (fly) it.
Re:How To Safely Store A Password by frisco on Tuesday December 14, 2010 @01:28PM (#2005146)
I was more talking about bcrypt being consensus with that post. Salting slows down cracking attempts by a factor of N where N is the length of the hash; md5 and sha1 are so fast that you shouldn't be banking on salting to protect you in 2010. Also, you should assume that if an attacker has your database (with salts), they also have your code, which tells them exactly how the salt was applied. In that case, salting doesn't slow you down at all.
Re:How To Safely Store A Password by jhchen on Tuesday December 14, 2010 @01:49PM (#2005235)
But you're talking about defending against brute force attacks? Salting's strength is in defending against rainbow tables. It seems the best policy at this point is to use both as they defend against different things and are not mutually exclusive.
Re:How To Safely Store A Password by bostonvaulter2 on Tuesday December 14, 2010 @01:47PM (#2005225)
I think the point is that you should use bcrypt and salt at the same time.
Re:How To Safely Store A Password by tptacek on Tuesday December 14, 2010 @02:04PM (#2005284)
You don't need to do anything like that; bcrypt does all this stuff for you. Don't salt bcrypt.
Re:How To Safely Store A Password by youngian on Tuesday December 14, 2010 @06:30PM (#2006209)
I think people would be a lot less confused if you said this first. Say "Don't salt bcrypt, bcrypt salts for you" and you'll have to explain yourself less.
Re:How To Safely Store A Password by amalcon on Tuesday December 14, 2010 @03:23PM (#2005586)
The salt does exactly one thing: it makes the attacker pay to get each password, as opposed to making them pay once and get all of them. When the cost is a fraction of a second on a commodity CUDA setup, it's not really that helpful to make an attacker pay it multiple times.
Re:How To Safely Store A Password by ax0n on Tuesday December 14, 2010 @12:53PM (#2004994)
In a case like the Gawker incident, it isn't safe. If the source code to the password hashing algo is compromised (it was) then the salt becomes useless. In short, just use bcrypt.
Re:How To Safely Store A Password by Xk on Tuesday December 14, 2010 @12:55PM (#2005007)
No. No no no.

The source code to the hashing algorithm means nothing. It is already open source!

The reason that the salt is there is to prevent against rainbow tables.

The salting did NOT become useless. If they had not salted passwords, then many many more passwords would have been broken because instead of having to brute force each and every one, you'd just look it up in a massively large hash table.

Re:How To Safely Store A Password by jrockway on Tuesday December 14, 2010 @05:48PM (#2006073)
No, he thinks the salt is stored secretly in the source code. Of course, it's not; you store it right next to the hash so that you don't have to use the same salt for every password.
Re:How To Safely Store A Password by aidenn0 on Tuesday December 14, 2010 @01:02PM (#2005036)
Salting and choice of hashing algorithm are orthogonal. If it takes X amount of time to brute force a password of strength Y and you do salt, then an attacker can crack N passwords of strength Y in time NX. If you don't salt, then an attacker can crack all* passwords of strength Y in time N, which is a huge difference.
Re:How To Safely Store A Password by ax0n on Tuesday December 14, 2010 @01:07PM (#2005053)
Alas, I stand corrected. Thanks. At the same time, the author does have a good point that very slow algorithms are fundamentally better for security, but I'm glad you pointed this difference out. Classic case of me not thinking things all the way through.