2

Disclaimer: there are many similar questions on SO, but I am looking for a practical suggestion instead of just general principles. Also, feel free to point out implementations of the "ideal" algorithm (PHP would be nice ;), but please provide specifics (how it works).

What is the best way to calculate hash string of a password for storing in a database? I know I should:

  • use salt
  • iterate hashing process multiple times (hash chaining for key stretching)

I was thinking of using such algorithm:

x = md5( salt + password);
repeat N-times:
    x = md5( salt + password + x );

I am sure this is quite safe, but there are a few questions that come to mind:

  1. would it be beneficial to include username in salt?

  2. I have decided to use a common salt for all users, any downside in this?

  3. what is the recommended minimum salt length, if any?

  4. should I use md5, sha or something else?

  5. is there anything wrong with the above algorithm / any suggestions?

  6. ... (feel free to provide more :)

I know the decisions necessarily depend on the situation, but I am looking for a solution that would:

  • provide as much security as possible
  • be fast enough ( < 0.5 second on a decent machine )

So, what would the ideal algorithm look like, preferably in pseudo-code?

johndodo
  • 17,247
  • 15
  • 96
  • 113
  • For [key stretching](http://en.wikipedia.org/wiki/Key_stretching) - I have updated the question to reflect that. – johndodo Oct 28 '11 at 09:57

2 Answers2

6

The "ideal" password hashing function, right now, is bcrypt. It includes salt processing and a configurable number of iterations. There is a free opensource PHP implementation.

Second best would be PBKDF2, which relies on an underlying hash function and is somewhat similar to what you suggest. There are technical reasons why bcrypt is "better" than PBKDF2.

As for your specific questions:

1. would it be beneficial to include username in salt?

Not really.

2. I have decided to use a common salt for all users, any downside in this?

Yes: it removes the benefits of having a salt. The salt sole reason to exist is to be unique for each hashed password. This prevents an attacker from attacking two hashed passwords with less effort than twice that of attacking one hashed password. Salts must be unique. Even having a per-user salt is bad: the salt must also be changed when a user changes his password. The kind of optimization that an attacker may apply when a salt is reused / shared includes (but is not limited to) tables of precomputed hashes, such as rainbow tables.

3. what is the recommended minimum salt length, if any?

A salt must be unique. Uniqueness is a hard property to maintain. But by using long enough random salts (generated with a good random number generator, preferably a cryptographically strong one), you get uniqueness with a high enough probability. 128-bit salts are long enough.

4. should I use md5, sha or something else?

MD5 is bad for public relations. It has known weaknesses, which may or may not apply to a given usage, and it is very hard to "prove" with any kind of reliability that these weaknesses do not apply to a specific situation. SHA-1 is better, but not "good", because it also has weaknesses, albeit much less serious ones than MD5's. SHA-256 is a reasonable choice. As was pointed out above, for password hashing, you want a function which does not scale well on parallel architectures such as GPU, and SHA-256 scales well, which is why the Blowfish-derivative used in bcrypt is preferable.

5. is there anything wrong with the above algorithm / any suggestions?

It is homemade. That's bad. The trouble is that there is no known test for security of a cryptographic algorithm. The best we can hope for is to let a few hundreds professional cryptographer try to break an algorithm for a few years -- if they cannot, then we can say that although the algorithm is not really "proven" to be secure, at least weaknesses must not be obvious. Bcrypt has been around, widely deployed, and analyzed for 12 years. You cannot beat that by yourself, even with the help of StackOverflow.

As a professional cryptographer myself, I would raise a suspicious eyebrow at the use of simple concatenation in MD5 or even SHA-256: these are Merkle–Damgård hash functions, which is fine for collision resistance but does not provide a random oracle (there is the so-called "length extension attack"). In PBKDF2, the hash function is not used directly, but through HMAC.

Community
  • 1
  • 1
Thomas Pornin
  • 72,986
  • 14
  • 147
  • 189
  • Thanks, that's exactly what I was hoping for - I must admit I was unaware of bcrypt. Now that I've searched around the net for information about it I know why... This must be one of the best kept secrets... ;) I agree with your post, the concerns you raise are exactly those that made me post the question. Any suggestion on how to properly use bcrypt? Through [phpass](http://www.openwall.com/phpass/) or [some](https://gist.github.com/1070401) [other](http://stackoverflow.com/questions/4795385/how-do-you-use-bcrypt-for-hashing-passwords-in-php) [class](https://gist.github.com/1053158)? – johndodo Oct 28 '11 at 21:37
  • 1
    [This answer](http://stackoverflow.com/questions/1581610/how-can-i-store-my-users-passwords-safely/1581919#1581919) recommends phpass and seems to give details on how to use it. I do not develop in PHP myself. – Thomas Pornin Oct 28 '11 at 22:01
1

I tend to use a fixed application salt, the username and the password

Example...

string prehash = "mysaltvalue" + "myusername" + "mypassword";

The benefit here is that people using the same password don't end up with the same hash value, and it prevents people with access to the database copying their password over another users - of course, if you can access the DB you don't really need to hack a login to get the data ;)

IMO, salt length doesn't matter too much, the hashed value length is always going to be 32 anyway (using MD5 - which again is what I would use)

I would say in terms of security, this password encryption is enough, the most important thing is to make sure your application/database has no security leaks in it!

Also, I wouldn't bother with repeated hashing, no point in my opinion. Somebody would have to know you algorithm to try to hack it that way and then it doesn't matter if it is hashed once or many times, if they know it, they know it

musefan
  • 47,875
  • 21
  • 135
  • 185
  • 1
    Multiple rounds of hashing increases the calculation required. It's cheap for one-off authentication, but rapidly becomes more expensive for the attacker. – Roger Lipscombe Oct 28 '11 at 09:55
  • Exactly. :) @musefan: I am looking for "best practice" solution instead of "good enough". There is no damage in doing things right - there are just too many poor security solutions out there (not saying yours is one of them). Salt key length is important because it lengthens the hashed string - requiring bigger rainbow tables (I think). I do agree about other holes though, but that's a whole new subject. :) – johndodo Oct 28 '11 at 10:05
  • @johndodo: If they know the salt key then the length is not important, if they are using rainbow tables then they are likely hacking either the hash directly, or your login function (in which case they don't need to care about the salt) – musefan Oct 28 '11 at 10:11