There's been some discussion of security related to passwords and I wanted to start a root node to discuss this more thoroughly. mdillon pointed out that Lesson 4, part 2 of my CGI course gets some of the details wrong regarding using an MD5 digest. The main problem with this seems to be that I'm not truly using the crypt capabilities of MD5. Thus, a cracker will find my digests easier to crack than using a proper crypt function such as Crypt::PasswdMD5 (merely because they are faster and easier to crack, if the constant is known).
A proper MD5 crypt string will resemble the following:
$1$1PUXLuZE$P.LfclRO9SKqTf2BQK.yD1
The 1PUXLuZE is the salt, so any cracker grabbing the password file now has the salt for every password. I asked why this is done, since this appears to merely be a convenient way of managing the salts, yet decreases security since with a properly random salt, finding the password will be considerably difficult.
In reply to one of my nodes regarding security, thraxil: wrote:
if the salt were secret, how would you ever check the user's password?
My point is that if the salt is separated from the password, security would be increased because, in theory, you would need both pieces the validate the passwords. Thus, including the salt with the password will decrease security because the cracker then has the salt.
After considering this, I understand the benefit of the salt, particularly in avoiding collisions (and I hadn't understood that until mdillon provided the link -- I love this place :), but I still don't see why it's included. If a cracker can gain access to the digests, he or she can try to crack them at leisure. The downside of separating the salt and passwords is that salt management is considerably more complicated.
I have been using a single, static salt (well, a constant appended to the passwords) for security on some of my work and am wondering if this weaker than the traditional method. The salt is tucked away in a config file and the password digests are in a totally separate database. Thus, gaining access one of these is useless to an attacker.
Are there any security systems that manage the salts separate from the passwords? Are they considered too impractical (e.g., if they're both in a filesystem, they might as well be in the same file - if they're on separate servers, you're at the mercy of your network connections).
Cheers,
Ovid
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.
|
Re: Too Convenient Security?
by derby (Abbot) on Jan 07, 2002 at 21:59 UTC
|
Ovid,
I would argue that having a static salt is bad no matter where it is (with the password or seperated and stored someplace). Just as the salt is useful in avoiding collisions, that same property is useful in preventing dictionary attacks. If a bad guy knows the static salt, he would then need to only one-way hash his dictionary once with the static salt. Then it's just a matter of strcmp'ing the hashed dictionary with the hashed password. With a pseudo-random salt, things become a little more difficult (but not impossible), the bad guy now needs to have X number of hashed dictionaries where X is the range of your pseudo-random salt. Granted, it's still feasible to try and brute force crack a password but given the poor choices most people use for passwords, a dictionary attack is more useful.
So I would conclude storage of the salt is a way secondary issue to having a really good pseudo-random number generator and a salt that provides a large yet feasible domain.
-derby | [reply] |
|
|
I'm seeing now the dangers of a static salt, but I'm still wondering if it's too much trouble to keep the salt and password separate. Also, I should mention that even if a cracker grabs my salt (crackers grabbing salt?), that still doesn't grant them access to the database with the password hashes. Alternatively, getting access to the database doesn't give them access to the salt. That would seem more secure than the random salt.
Of course, since I was using a simple digest, this is much easier to crack than the Crypt::PasswdMD5, so a bruteforce is more feasible, though it's still going to be difficult).
So, are there any systems which have distinct salts for each password and keeps the salts separate? Would this be a good or bad idea?
Cheers,
Ovid
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.
| [reply] |
|
|
It's not that keeping the salt seperate would be so hard, it's that it wouldn't buy you anything. A modern OS will protect the password hashes+salts together, so that even if a cracker gets the list of users, they've got nothing to work on. If you system gets so cornholed that the cracker can read the hashes, it's safe to assume that they can also get the salts.The job of the salt is to prevent dictionary attacks, i.e. a precompiled list of passwords and possible hashes. You can think of the salt, then, as part of the hash itself. What you're suggesting (and it's not a bad idea, just a really awkward one :-) is to effectively split the hash into two seperate pieces. If you did this it would actually make more sense to make each part half salt and half hash. Then store the two fragments independently, such that if one is compromised it doesn't mean doom for the other one. Trouble is, the two halves would have to be really different - different machine, different OS, different database, different admin password - just to be sure that a compromise on one wouldn't affect the other. There's probably more mileage (and less heartache) in using a good, trutworthy crypt algorithm like MD5crypt or (better yet) bcrypt (as used in OpenBSD), whish uses Blowfish. And pick good passwords. The idea here is that the algo itself is such a swine that dictionary attacks are infeasible and brute-forcing a hash (even with the salt) takes too long to be practical.
| [reply] |
|
|
(ichimunki) Re: Too Convenient Security? (updated)
by ichimunki (Priest) on Jan 07, 2002 at 22:47 UTC
|
(First off, if MD5 makes you nervous in any way, switch to SHA1 which was designed to compensate for a perceived weakness of MD5 related to authentication, not to simple hashing)
When I produce an MD5 hash using Digest::MD5->md5*() from an input (salt or no) I don't get a string such as the one you indicate (which Ovid points out below is the output of a crypt command). I simply get a 128 bit number. That's a number between 0 and approximately 340,282,366,900,000,000,000,000,000,000,000,000,000 (or 2**128 to be exact ). I prefer to use the md5_hex method, which gives the number as a 32 character string representing the number in hexadecimal. For those playing the home game, 2**128 = 16**32. If I did get a string like you show, I would remove all but the hash itself. This should be nearly impossible to crack...
There are 60*60*24*365.25 seconds in the average year. That's 31,557,600 seconds. At 1,000,000 operations per second, you will be able to brute force all possible hashes in just over 10**25 years. Unless you know of a better way to go from a 128 bit number back to a matching input, such that I could enter that input into the password field on your CGI and thereby gain access. I'd probably have better luck simply running a high-end dictionary crack-- which even so would hopefully raise some alert (so after a hundred consecutive failed attempts to login you should disable the user).
Now, if the algorithm that produces MD5 hashes is such that there are "blank spots" between 0 and 2**128, where in order to find potential inputs (and these are always potentials, the function is not inversible if two inputs can have the same output) we don't need to test (possibly) all 2**128, then the algorithm is less than perfect. But unless it gets the aforementioned brute force timing down to something closer to a few years rather than eons, it is not that important.
One question for our real experts in the audience, wouldn't it be possible to store both the MD5 and the SHA1 hashes, such that an input matching both outputs has an extremely high chance of being unique? Or does knowing both of these outputs make reversing the algorithm to a valid input that much easier?
I think for your example, you might want to remove the salt as a constant and generate a unique salt for each user. But something simple, like reversing the user ID and doing a simple Caesar cipher on it or something to that effect. That way it is different, but predictable, on a per user basis. But I think anyone who can get your hash file is also likely to have access to your script and/or your "managed salt" file-- so I wouldn't put this much effort into it: if I have either of those two things I can easily determined what salt applies to which users (and as long as the salt is different for each user, then I have to rebuild my dictionary to attack each user separately). If the information is that sensitive take it offline.
Frankly, I think the odds of someone having access to the passwords file (even read only) mitigates the likelihood that they need to crack a password to get on the system at all--provided you properly secure the filesystem of the host to begin with. Is it a shared host? Then that password file should only be readable by the user that the CGI process will run as (*not* nobody as is often the case).
Finally, remember this all comes down to the passwords. Are they computationally inconvenient? If not, I might simply use LWP to keep submitting until I find a match. Your CGI should prevent weak passwords. And as part of defense in depth I would (as I said) limit the number of invalid tries. So once you've secured all this, I (as an attacker) will just switch modes to DoS or something: how about I just get your page posted to Slashdot? *grin* | [reply] |
|
|
ichimunki wrote:
So maybe I don't have the advanced math skillz to comprehend this, but when I produce an MD5 hash from an input (salt or no) I don't get a string such as the one you indicate.
Using Digest::MD5 will not generate a string like that. See the link that mdillon referred to for a better explanation of how that string is created.
ichimunki also wrote:
Finally, remember this all comes down to the passwords. Are they computationally inconvenient? If not, I might simply use LWP to keep submitting until I find a match. Your CGI should prevent weak passwords. And as part of defense in depth I would (as I said) limit the number of invalid tries.
Without going too in-depth into our password policies, let me just say two things:
- Over the objection of the users, we have implemented a moderately strong password policy. It's not as strong as I would like it, but no one is going to get away with using 'password' for a password.
- You get seven tries to get your username/password combination correct. Each failure is logged. If you blow it seven times, you are locked out and the company needs to call us to unlock it. They are not even allowed to unlock failures. Of course, we investigate lockouts before unlocking.
Cheers,
Ovid
Join the Perlmonks Setiathome Group or just click on the the link and check out our stats.
| [reply] |
|
|
| [reply] |
|
|
|
|
|
|
Now we're reaching the limits of my 1337 maths 5killz0rz
<takes a swig of b33r>
You don't need to brute force all possible MD5 output hashes. You just need to brute force all possible passwords. People still, by and large, use passwords like [0-9a-zA-Z]{6,8} even though longer, non-alphanumeric strings are allowed. That gives you a mere 218,340,000,000,000 permutations. I mean, that's definitely one metric buttload of work but a lot less than going the other way. And we want to be protected even when AMD's Palomino core is launched :-) so that's why we still need salts.
(incidentally, I think we can assume that since we're talking about stolen hashes, the cr4x0r doesn't need to keep trying the login prompt - he'll be running the crack on his own machinery and waiting for one good answer).
Storing two hashes. Hmm. That might well open you up to a sort of crib attack. It's possible that the two outputs could be solved simultaneously, I'm not sure. But the thing is, it's like Ovid's idea about storing the salt seperately- it's doesn't actually add anything that just using a stronger algorithm doesn't get you. You need twice as much processing horsepower to create hashes, so why not use a tougher algo in the first place? I'm going to mention bcrypt again. Bcrypt has a scaleable complexity, so that when you create passwords, you specify n, where n is the log2 of the number of rounds to apply the algo. By default OpenBSD uses 2**6 rounds. You can make it twice as complicated by changing one number to '7'.
Round three (sorry to go on). The exact nature of the salt is immaterial. You could use everyone's first name, and post a story about your system on perlmonks*. The important thing is that it's different for each user. Salts make precompiled dictionary attacks hard. The reason for using a good random salt is (1) computers don't care whether the salt is 'HelloWorld' or 'a1dg763/gv'. (2) A random salt system maximises the number of possible hashes, making dictionary attacks hard.
Round four (don't worry, I'll go away soon). A cracker who's simply read your password hashes can't actually hurt you unless he can do something with them - like log in as admin, having cracked the password.
Round five - see the bit in parens above.
* But don't. B-)
| [reply] |
|
|
| [reply] |
Re: Too Convenient Security?
by jepri (Parson) on Jan 08, 2002 at 01:49 UTC
|
There is most definately a system where the salt is kept separate to the hash - secret key crypto(logy|graphy). What you are saying is completely reasonable, since you are forcing an attacker to check every salt rather than supplying him with the right salt.
Even if the secret key is compromised, you have reverted to the usual security level - the attacker knows the salt, just like in a password file.
It is true that using different salts forces the attacker to use a pre-hashed dictionary 255 times larger, but advances in storage will take care of that soon enough. ____________________
Jeremy
I didn't believe in evil until I dated it. | [reply] |
|
|
That'd be a dictionary 281,000,000,000,000 times larger - md5crypt has a 48-bit salt.
| [reply] |
|
|
