(ichimunki) Re: Too Convenient Security? (updated)

[ichimunki]

(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*

[Ovid]

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:

1. 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.
2. 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.

[thraxil]

just an aside...

i wonder if locking an account after 7 incorrect passwords is that good an idea. if i could guess someone's username, i could just go type it in with random passwords 7 times and effectively DOS them.

anders pearson

[cforde]

It's a better idea than letting you run your favourite password guesser on the accounts of your choice. Most places I've worked lock the account after 3 failed attempts.

ps. guessing someone's username generally isn't hard.

Have fun,
Carl Forde

[jepri]

We used to do this to people we didn't like. Wait till they went to lunch, then lock them out of their terminal :)

____________________
Jeremy
I didn't believe in evil until I dated it.

[n3dst4]

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 log₂ 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-)

[belg4mit]

MD5 is known to have clashes (duplicate hashes for different input).
• http://www.ssh.com/tech/crypto/algorithms.html
• http://www.tml.hut.fi/Opinnot/Tik-110.501/1995/practical-crypto.html