views:

579

answers:

7

As many will know, one-way encryption is a handy way to encrypt user passwords in databases. That way, even the administrator of the database cannot know a user's password, but will have to take a password guess, encrypt that with the same algorithm and then compare the result with the encrypted password in the database. This means that the process of figuring out the password requires massive amounts of guesses and a lot of processing power.

Seeing that computers just keep getting faster and that mathematicians are still developing these algorithms, I'm wondering which one is the most secure considering modern computing power and encryption techniques.

I've been using MD5 almost exclusively for years now, and I'm wondering if there's something more I should be doing. Should I be contemplating a different algorithm?

Another related question: How long should a field typically be for such an encrypted password? I must admit that I know virtually nothing about encryption, but I'm assuming that an MD5 hash (as an example) can be longer and would presumably take more processing power to crack. Or does the length of the field not matter at all, provided that the encrypted password fits in it in the first place?

+5  A: 

To increase password strength you should use a wider variety of symbols. If you have 8-10 characters in the password it becomes pretty hard to crack. Although making it longer will make it more secure, only if you use numeric/alphabetic/other characters.

SHA1 is another hashing (one way encryption) algorithm, it is slower, but is has a longer digest. (encoded messsage) (160 bit) where MD5 only has 128 bit.

Then SHA2 is even more secure, but it used less.

Tony
I will note that slower is actually a *benefit* when it comes to defending against brute-force attacks.
Anon.
@Anon: You're quite right! Thanks for mentioning it:)
Tony
It's not so much "slower" as "difficult to make fast even with dedicated hardware/precomputed tables/mathematical analysis..." which is important. The rationale behind the NIST SHA-3 contest is that current crypto hash functions, while still as slow as before on general-purpose computers, have been weakened recently for various other reasons. Especially MD5 (see the MD5 Wikipedia page).
Pascal Cuoq
Putting any reliance on the speed with which the computer can create the hash is misplaced. The difference in speed between MD5 and SHA1 calculation will provide no discernible protection against brute force attacks. The only thing that should matter is the quality of the hash and that relates to its ability to protect against deducing the input from the hash and its ability to protect against falsely producing the same hash with different inputs.
Thomas
You can still rainbow table SHA1. I've moved most of my new development up to SHA-256
Xorlev
This is not entirely correct. |a| ^ l is the equation that describes the number of possible values in the password, where a is the password alphabet, and l is the length of the password. It is more effective to increase l instead of |a|.
Paul Nathan
@Xorlev: that's what salt is for. There are good reasons to move from SHA-1 to SHA-256, but rainbow table attacks on hashed passwords aren't among them.
Steve Jessop
@Steve Jessop, I salt all my SHA1, but considering that rainbow tables are really starting to show up, it doesn't really hurt me to use SHA-256. One can also do key hardening to increase time taken for brute-force attacks.
Xorlev
@Xorlev You can construct a rainbow table for _any_ hash algorithm. The practicality of constructing a rainbow table is a function of how many possible inputs there are, not of the robustness of the algorithm.
Nick Johnson
@Nick Johnson, I'm aware, however as more and more tables show up I less and less want to use SHA-1.
Xorlev
@Xorlev: but why does it matter? With 64 bits of salt, how can anyone possibly have a rainbow table for SHA-1 *with the right salt value*? They could start generating it once they know the salt for the password they want to crack, but that's no different from a dictionary attack on SHA-1. The existence of rainbow tables for SHA-1 is not a threat to you. The existence of preimage attacks on SHA-1 might be a growing threat.
Steve Jessop
A: 

salting the password is always an extra level of defense

$salt = 'asfasdfasdf0a8sdflkjasdfapsdufp';
$hashed = md5( $userPassword . $salt );
David Morrow
It is important that a fresh salt be generated each time a password is set, not be a fixed value.
caf
@caf: Wouldn't that still make the calculation take way more time if it were always the same, thus increasing the time it would take to brute force it? - If the salt is different every time, it would have to be stored in the same row as the password for the login mechanism to be able to compare the hashed attempt to the real password.
Helgi Hrafn Gunnarsson
If the salt is always the same, the attacker can a) bruteforce all your passwords in parallel (each test hash can be compared against all your password hashes); and b) compute the hashes in advance of seeing your database. Yes, the salt should be stored alongside the hash - that's exactly what UNIX-style password hashes do.
caf
+5  A: 

Great question! This page is a good read. In particular, the author claims that MD5 is not appropriate for hashing passwords:

The problem is that MD5 is fast. So are its modern competitors, like SHA1 and SHA256. Speed is a design goal of a modern secure hash, because hashes are a building block of almost every cryptosystem, and usually get demand-executed on a per-packet or per-message basis.

Speed is exactly what you don’t want in a password hash function.

The article then goes on to explain some alternatives, and recommends Bcrypt as the "correct choice" (his words, not mine).

Disclaimer: I have not tried Bcrypt at all. Consider this a friendly recommendation but not something I can back up with my own technical experience.

Matt Solnit
The author also recommends the password hashing scheme developed for FreeBSD, which uses MD5 at its core but iterates the hash function thousands of times. There is a similar construction based on SHA-1 available in glibc.
caf
+1 for citing Matasano :)
Matthieu M.
A: 

NIST is currently running a contest to select a new hashing algorith, just as they did to select the AES encryption algorithm. So the answer to this question will likely be different in a couple of years.

You can look up the submissions and study them for yourself to see if there's one that you'd like to use.

Jeffrey L Whitledge
+16  A: 

MD5 was found to be weak back in 1996, and should not be used anymore for cryptographic purposes. SHA-1 is a commonly used replacement, but has similar problems. The SHA-2 family of hash functions are the current replacement of SHA-1. The members of SHA-2 are individually referred to as SHA-224, SHA-256, SHA-384, and SHA-512.

At the moment, several hash functions are competing to become SHA-3, the next standardised cryptographic hashing algorithm. A winner will be chosen in 2012. None of these should be used yet!

For password hashing, you may also consider using something like bcrypt. It is designed to be slow enough to make large scale brute force attacks infeasible. You can tune the slowness yourself, so it can be made slower when computers are becoming faster.

Warning: bcrypt is based on an older two-way encryption algorithm, Blowfish, for which better alternatives exist today. I do not think that the cryptographic hashing properties of bcrypt are completely understood. Someone correct me if I'm wrong; I have never found a reliable source that discusses bcrypt's properties (other than its slowness) from a cryptographic perspective.

It may be somewhat reassuring that the risk of collisions matters less for password hashing than it does for public-key cryptography or digital signatures. Using MD5 today is a terrible idea for SSL, but not equally disastrous for password hashing. But if you have the choice, simply pick a stronger one.

Using a good hash function is not enough to secure your passwords. You should hash the passwords together with salts that are long and cryptographically random. You should also help your users pick stronger passwords or pass phrases if possible. Longer always is better.

molf
"Longer always is better". Not *necessarily* true. I've heard anecdotal claims that forcing users to choose longer passwords sometimes causes them to choose passwords with *less* entropy, so that they can remember them. Personally I can remember an 8-alphanum randomly-generated password if I'm using it daily. Longer than that and I'm going to resort to making up passwords myself, and I don't know what entropy those have.
Steve Jessop
@Steve Attackers don't gradually move from low entropy password attempts to higher ones. They try the dictionary attack and then there's brute force. Thus, "ooGoo!ooooooo876" has lower entropy than "d!NA0sue732bnfuw", but it's no less secure.
Lucas
For password hashing, MD5 should still be considered to be a reasonable option (as you've hinted), provided your passwords are strong and you use a salt (which would apply to any hash). The collision attacks are largely irrelevant for password hashing, in my understanding.
MarkR
@Lucas: neither "ooGoo!ooooooo876" nor "d!NA0sue732bnfuw" has any entropy in the relevant meaning, since they are constants not random variables. To be pedantic I should have said "choose passwords as outputs of a r.v with less entropy", not "choose passwords with less entropy". A low-entropy password generation scheme is more likely to generate passwords which fall in the early part of a dictionary/brute-force attack, assuming (as one should, for safety) that the attacker has some insight into how passwords are chosen and has designed his attack sensibly.
Steve Jessop
@Steve: "that the attacker has some insight..." this is the point about using longer password. There is much difference between a 8-characters password (keyboard) and a 14 to 50 characters password (probably alpha num + punctuation and perhaps a few random chars). The latter has a much higher space. Even if it's likely to be composed of words, as you can tweak them (l33t speak, sms-style, ...), it still gives more entropy.
Matthieu M.
+1 for one word: `salt`. Without salt you're susceptible to rainbow-attacks. And I should point out that you want one salt for each password, not one for the whole lot of them!
Matthieu M.
A longer password has the potential for more entropy, of course. But molf said "longer is always better". This is false: a password consisting of 8 random alphanumeric characters is better than a password consisting of two random dictionary words. *If* you then introduce enough additional randomness to the two-word password generation scheme, then eventually it will be better. Whether or not users will actually do so when forced to choose longer passwords is a question in psychology, not information theory. I'm not confident enough of the answer to impose any but a tiny minimum length limit.
Steve Jessop
Many user passwords are already quite simple. Passphrases are often just as easy to remember, while taking advantage of the additional strength of their length. I maintain that, **all other things equal**, longer always is better. But all things are not always equal, and you are quite right in questioning whether or not a *required minimum length* will weaken the passwords. Be careful in imposing strict minimum limits, and help users decide for themselves.
molf
+1  A: 

Seeing that computers just keep getting faster and that mathematicians are still developing these algorithms

RSA encryption is secure in that it relies on a really big number being hard to factor. Eventually, computers will get fast enough to factor the number in a reasonable amount of time. To stay ahead of the curve, you use a bigger number.

However, for most web sites, the purpose of hashing passwords is to make it inconvenient for someone with access to the database to read the password, not to provide security. For that purpose, MD5 is fine1.

The implication here is that if a malicious user gains access to your entire database, they don't need the password. (The lock on the front door won't stop me from coming in the window.)


1 Just because MD5 is "broken" doesn't mean you can just reverse it whenever you want.

Seth
"However, for most web sites, the purpose of hashing passwords is to make it inconvenient for someone with access to the database to read the password, not to provide security." - this may be all that most sites _achieve_, but the purpose should be to make it impractical to reverse any of your users' stored passwords - and doing so is totally achievable.
Nick Johnson
Agreed, I have strongly tried to explain to my colleagues why the weaknesses in MD5 should not preclude its use for password hashing. Needless to say, using a salt and minimum password strength is still advisable
MarkR
A: 

Besides being a cryptographically secure one-way function, a good hash function for password protection should be hard to brute force - i.e. slow by design. scrypt is one of the best in that area. From the homepage:

We estimate that on modern (2009) hardware, if 5 seconds are spent computing a derived key, the cost of a hardware brute-force attack against scrypt is roughly 4000 times greater than the cost of a similar attack against bcrypt (to find the same password), and 20000 times greater than a similar attack against PBKDF2.

That said, from commonly available hash functions, doing a few thousand of iterations of anything from the SHA family is pretty reasonable protection for non-critical passwords.

Also, always add a salt to make it impossible to share effort for brute forcing many hashes at a time.

Ants Aasma