Password cracking in reverse

When passwords start getting long (say 15 characters or longer, just as an example), if the authentication system is relatively secure, so is the password. At 15 characters, as long as the password is not easily guessible (e.g. password, frog, 1234, etc.), the password becauses non-trivial to guess (whether in plain-text or hashed form).

For example, if Windows logon passwords are not stored in their weak LM hash form, if the password is 15 characters or longer and is not a super easy dictionary word, it becomes computationally difficult to brute-force, even with rainbow tables.

But I wonder if anyone has done any research on the security keyspace given by long passwords if the unlikelly passwords are automatically ruled out? By that I mean, if you have a password keyspace of 15 characters, it usually means that the number of potential passwords is 15 times the number of possible different characters in the password. In Microsoft Windows, user’s can use up to 65K different characters (the fully Unicode character set) in their passwords. If the keyspace was really 15^65K, it would be impossible to hack Windows logon passwords.

But in reality, we know that most users may only use 40 characters (i.e. lowercase alphabet, but not a lot of z’s or q’s, a few uppercase characters, a few numbers (i.e. 1 or 2), and a few symbols (i.e. !#@,), and they use dictionary words.

Even if forced to use symbols or numbers in their passwords, they will use a bastardized version of a dictionary word, and modify it slightly to contain the enforced constraints. Further, history shows us that if users are forced to use numbers, they usually put them at the end (e.g. frog1, frog2…frog32). If forced to use symbols, they will often substitute @ for the letter a, or zero for the letter O, or the number 5 for an s, or ! or 1 for the letter l. If forced to use a number, that number will be the number 1 or 2.

Understanding human behavior means that even though the total keyspace of all the possible 15 character passwords is “uncrackable”, in theory, we can make “guesses” and rule in or out likely password combinations.

Using 40 characters, a few symbols and numbers, and a dictionary approach, many Windows logon passwords can be cracked in a lot less time than initially mathematically computed.

I wonder if anyone has taken that argument even further? For example, it is highly unlikely that end-users will use password combinations using a lot of random letters that make no sense, or lots of non-vowels in a row. Hence, a password of wqutxv or vxckdt is a lot more unlikely than a password of wabtus. It’s just human nature.

If I was a professional password cracker, I would spend a little time computing all the unlikely password combinations and rule them out before beginning my password crack.

So, hence, even if an end-user uses a 15-chracter password, by paring down the likely potential password keyspace, I wonder what the effective password keyspace becomes? I bet it’s a lot less than what we would normally think.

I wonder if anyone has done any probability studies to rule out the unlikely password combinations and removed them from their password guessing dictionaries? Something like this would be highly useful to any professionals whose job it is to brute force passwords.