First of all let me say that this is not a "how to crack passwords" thread, so mods please understand that, and if it turns into that then you can shut the thread. I want a true discussion on a problem I was thinking about recently. There will be no mention of how to actually crack windows/unix/linux/any other OS passwords with encryption etc or where they are placed or anything of that nature. This has many other applications than "password cracking" but it was inspired from an article I just read at my internship on computer security and a report that I just submitted. Its been bothering me that there has to be a better way.
From the article I will assume that most passwords these days require characters, numbers, and letters together. The average password required now is between 8-10 letters so lets take a password that must be 8 letters with all combinations of letters, numbers, and characters on a standard US keyboard including uppercase letters. You would have a solution space of about 90^8 number of passwords or about 1.14 x 10^15 number of passwords if my math is correct. 90 is the approximate number of available characters on a keyboard (actually I counted 94 but 90 seems nice and round)
If you wanted to find every password then you would develop a brute force method that could take up to O(n^8) which is bad. That is with 8 nested for loops running such that the last character cycles through all available characters, then the next to last increments and you repeat cycling through the last character. I figured that would take about 3 weeks.
You could also use a dictionary to go through all files and permutations but we're going to assume that our user is a little smarter than that.
A second thought, making the assumption you have intelligent users that want hard passwords (we know this doesn't happen) then you could reduce the solution space by leaving out all words that are all characters or all letters (both uppercase and lowercase) or all numbers. That should, if my math is correct, reduce the solution space to about 500 trillion passwords. The problem would be setting up a program that would create this solution space. I personally think that you would have to do more checks for this solution space and you program would end up being slower.
ex. aaaaaaa. Assuming that b would be the next letter
I personally think that reducing the solution space is the best option but it would trade off performance greatly. The number of characters you could get rid of is incredible but the number of checks to get rid of them may be just as bad if not worse than the original. I'm curious as to what ya'll think. Do ya'll have any thoughts on a better implementation?
It must be all or nothing. The password must be all right or all wrong. You cannot assume that the password that you are currently testing partially matches the password on the system because the system does not match those types of passwords.
edit: i'm assuming that there is no limit on the number of attempts for an account and that there is no time to communicate with the host computer. The only time you are dealing with is the actual "cracking" of the passwords.
[Edited by - doodah2001 on June 16, 2004 1:06:38 PM]