password strength

[oDDity]

I was just wondering (in the general direction of you maths gurus) what the chances are of guessing a password (say you have some sort of program to do the guessing for you)

What you know is that the characters in it could be anything on the standard keyboard and it could be anywhere from 6-64 characters in length.

Say in this case the password is 24 characters long and just random letters, digits and symbols.

Even if it billions to one, surely a dedicated app can run though millions of combinations a minute, so it should eventually be guessed, right?

There's this password cracker app on sourceforge for example

 

"Ophcrack is a Windows password cracker based on a time-memory trade-off using rainbow tables. This is a new variant of Hellman's original trade-off, with better performance. It recovers 99.9% of alphanumeric passwords in seconds."

 

99.9% of passwords in seconds?

[sparhawk]

I once wrote an application that tried to crack a 32 Bit key, encrypted with a 1024 bit encryption algorithm. The application, that I wrote was written in assembly and highly optimized. Ever cycle that I managed to optimize resulted in about one day less runtim in total. On average the program took about 12 days to crack one key. BUT! This was a limited subset of the characters, because they key was in hexadezimal ASCII notation, so it only consisted of 0-9 and A-F, instead of the full keyboard characters.

 

So you can consider how long it would take for a normal characterset as you specify above, and a keylength of 64 characters. Even with a 64 bit key, it would have taken me about 10 years (not sure if I remember it correctly though could be that it was 120 years). A 32 bit key in Hex takes 8 Bytes and a 64 bit Hex representation takes 16 bytes, which is a long shot off the 64 bytes you specified.

 

However, how a passwrod can be cracked, depends on the algorithm. A bruteforce is virtually impossible with such a keylength. I guess that it can crack the password, because of weaknesses in the encryption algorithm.

[Crispy]

They're using rainbow tables, a sophisticated method that uses knowledge of the password hash and the hash method to break a password.

 

In order to use this method, you need to have access to the password hash, which a run-of-the-mill attacker won't. So it's only really useful in limited situations. For example, cracking Windows login passwords when you have physical access to the machine. It won't help you at all if you're trying to brute-force password guesses over a network, for example; that will take a long time, for decent passwords. Times for doing so are typically cited on the order of "it would take longer than the age of the universe", though I've never seen the calculations that form the basis for such claims.

 

Also, many network-accessible systems enforce a delay between password attempts, or lock you out after a small number of incorrect guesses, which makes even dictionary attacks quite infeasible. Linux systems make you wait a few seconds between incorrect attempts, and Windows domain logins will be temporarily locked after ~5 incorrect guesses. (The latter approach makes a petty and limited form of denial-of-service attack possible, so it's not ideal, but it works for its intended purpose.)

[Fidcal]

I don't think Oddity's talking about cracking the encryption of a stored password which the hacker has access to - but just brute guessing at a password input by trying every combination? If so, the combinations of "24 characters long and just random letters, digits and symbols." is so colossal you would not even be close if you had started at the big bang. Let's say all 26 letters in upper or lower plus digits plus common symbols - say a 100 characters. That's 24 x 100 x 99 x 98 x 97 x 96 etc.etc.. Doesn't sound much? Just start in with a calculator and see how far you get before it breaks down. Mine stopped after I reached only 95 and a total over 20 billion. Push it a bit further in your head. The 90's are almost a hundred as a rough... 2000 billion, 200,000 billion, etc.. Furthermore, this presupposes that the input will even allow you to try a million times a second. Ophcrack sounds like it might shorten the time using average human choices to limit its guesses - I mean the way in which we humans tend to create passwords probably has common patterns even when inventing words - but a totally random password is a totally random password and I don't see how any software can shorten the combinations. If it succeeds 99.9% of the time it suggests most of us are not using quality passwords.

[oDDity]

I suppose it's like that idea of putting one coin on the first square of a chessboard, 2 one the next, 4 on the next, etc. It doesn't sound like much, but by square 64 it adds up to more money than there is in the world.

OF course people don't use quality passwords. Never random. They're usually dictionary words, names of pets, birthdays etc.

They want to make it easy to remember, but therefore it is a lot easier to guess.

Still, I just found is surprising that they could get virtually all passwords in a few seconds with that program.

[Crispy]

I don't think Oddity's talking about cracking the encryption of a stored password which the hacker has access to - but just brute guessing at a password input by trying every combination?

Yes. But Ophcrack doesn't do brute-forcing; it's just a way of recovering a stored Windows login password. (Which isn't trivial, since the passwords are put through a one-way hash before being stored, but it's a lot easier than trying every possible password combination.) My explanation above was referring to it, since he brought it up. I probably should have been more specific.

 

The total possibility space for a password of any decent length is so huge because it involves factorials, which have approximately exponential behaviour. So yes, it's rather like the chessboard thing.

 

Still, I just found is surprising that they could get virtually all passwords in a few seconds with that program.

While it's true that most people have unbelievably bad passwords, this isn't why Ophcrack is so fast. It just works backwards from a stored, one-way-hashed password in a specific format (the one Windows uses) to get you the original plaintext password.

 

To reiterate, an attacker couldn't use Ophcrack in just any password-cracking situation. It only works on Windows logins, and only if the attacker has physical access to the machine that stores the login data. If that happens you're pretty screwed anyway - if they just want to trash your computer then a sledgehammer will work pretty well, if they want to steal data off it they can just load up a Linux boot disk of their choice and browse your hard drive to their heart's content, and if they want to implant a virus or reformat your computer for selling on the black market then they can do that with a boot disk too.

 

So the only real threat Ophcrack poses to anyone is if you use the same password to access your Windows computer and, say, your bank account.

[oDDity]

Well then, the question is why does windows uses such sloppy hashes.

Reading up on that link to wikipedia, apparently it's becasue windows doesn't use 'salts', which means that rainbow tables don't work.

[OrbWeaver]

It's not a problem with the strength of the hash, it's a fundamental weakness that arises when an attacker has access to the hash itself: the rainbow table makes it relatively quick to generate the hash of random passwords, compare this hash to the stored value, and identify when you have a password which will work (remembering that many thousands of passwords will hash to the same value).

 

In order to be secure you must not give your attacker access to the hash, but must ask them to give you a password, which you hash yourself and then compare to the stored value. This is how normal login works, but this is obviously completely bypassed when you have physical access to the disk.

[Crispy]

(I edited my post after you probably read it, by the way, so you may want to re-read it.)

 

Well, the algorithm in question works on any hash function, apparently; so as long as the hash function used is known then it can be used. So it's not really Microsoft's fault.

 

That said, Windows's hashing scheme is apparently pretty bad. It's not such a big deal because by the time an attacker gets far enough in to make use of such a weakness, they probably have full run of your system anyway. Most of MS's security works on this principle, with the result that once you're inside the anthill (so to speak), the worker ants assume you're friendly and let you do anything! (Though this is slowly changing with Vista.) It's not a very secure strategy, to be sure. They do it because they're more concerned with user-friendliness than security.

[Crispy]

Reading up on that link to wikipedia, apparently it's becasue windows doesn't use 'salts', which means that rainbow tables don't work.

Not quite. A "salt" is effectively just a slight modification of the hashing algorithm, and any hashing algorithm is vulnerable to the rainbow table scheme.

[Serpentine]

Heh, aside from the RT related talk... LanMan stuff is pretty weak and very silly in most places. A simple hash replacement can easily allow a person to gain entery if they have physical access. If you're on a network with non-hardened security boxes... theres always fgdump/pwdump to get you the hashes. A bit more on topic was cracking the actual hash - a nice cracker that's easy to use an gives you loads of options as to the attack type would be http://www.oxid.it/cain.html (good cracker, faster than anything else I have used in windows/nix), I'd make a few hashes and test out the speed - quite relevant to the OT

 

... and then theres always something like http://nsa.unaligned.org/index.php ... *drool*

[STiFU]

I just peeked around the forum a bit, because I was bored and I found this discussion very interesting. I once tried a bruteforce cracker on a rar file, but after a day I stopped it.

 

Anyway, I'd like to say something to Fidcal's example which wasn't quite correct. If you got a 24-characters-long password, every position of the password can be one of the 100 characters. So on the total, you got 100^24=10^48 combinations of possible passwords, which is still a very big number, but of course not even close to factorial of 100 multiplied by 24. What Fidcal possibly had in mind was the formula for the number of combinations, while assuming that every character may only be used once per password, which would create factorial of 100 devided by factorial of (100 - 24) = 100 * 99 * 98 * ... * 77 = 49,497 * 10^45 possible combinations.

Edited November 30, 2007 by STiFU

[demagogue]

Leave it to the guy with the 'math humor' member-pic to catch something like that.

 

By the way, this thread has completely shattered my faith in the accuracy of the movie War Games.

[Baddcog]

Why is it the smartest guys always overlook the simplest options.

 

The Little Annie Decoder Pin

[Fidcal]

Yeah - you're right of course StiFu. I must have been thinking of lottery numbers or something. Still, I was wrong on the right side and the number is bigger than HUGE.