[andrewcooke]

So this is not the complete set of passwords, only the ones that have been cracked so far, using a dictionary?

a dictionary + rules + time. yes (i assume - i have no inside knowledge).

[...] passwords which were randomly generated are, and are likely to remain, safe?

it depends on the length and range of characters. random passwords are still vulnerable if they are short and/or use a restricted range of characters. they can be found "by accident" when using rules and dictionaries. they can also be found by simply trying all combinations ("a", "b", ..., "aa", ..., "ab"...). length and character range protects against both of these.

it's likely that attackers will use all available approaches, including simple brute force. i focused on dictionaries + rules above because (1) that's generally more efficient and (2) some people don't seem to realize how powerful it is.

[frederickcook]

Thanks. I was under the impression somehow that cracking the first few passwords would make it easier to crack the rest (by figuring out the salting scheme perhaps)?

Also, if there is no restricted range of characters, and a solid, random password is used, how can the attacker know when they have broken it, short of trying them all against the actual server?

Edit: Forget that last bit. I'm confusing myself.

[rakkhi]

No cracking one doesn't help you with the rest at all. Salt and encryption scheme figured out to even start.

You just keep going in bruteforce and build bigger rainbow tables / variant dictionary attacks. Given a large number of GPU's you will get all passwords.. time though could be a number of years to thousands of years.

[andrewcooke]

actually, the last point is interesting, but goes the other way: the attacker doesn't have to find your password, just some text that hashes to the same value that is in the password file. that places an upper limit on how secure you can make passwords for any given hash (although in practice it's usually irrelevant).

[frederickcook]

Ok, this is interesting, so now we're talking about hashing collisions, right? The idea might be that if you just start iterating through all possible alphanumeric combinations, that it's possible you'd stumble on a successful collision before you'd stumble on the actual password. It seems this would only be likely once the number of possible passwords was greater than the number of possible hash outputs (32^66 for MD5, right)? That would occur if the length restriction on the password was greater than the length of the hash output, or a broader charset was allowed for the password than for the hashing output.

I guess if this ever actually became a relevant concern, you'd simply keep adding a few extra chars to the hashing algorithm output to keep it beyond the range of reasonable.