Hacker2, Crack: Optimisations

Question

I'm busy with the crack program for the hacker 2 assignment. I wrote a dictionary attack which works well for some of the passwords. I also wrote a brute force attack for the other passwords that the dictionary didn't work on, and by a stroke of luck I managed to crack the passwords while I was testing it.

I don't want to give too much away and spoil it for everyone else, I'll just say that I left out some characters and those that were left were enough to break the passwords. When I included the full search space for a more realistic tool, I noticed the speed dropped drastically, as expected.

The specification for hacker 2 is a bit thin on implementation advice, and I'm left wondering what algorithms are used in industry grade password crackers. There must be tried and tested ways of doing these sorts of things, considering the proliferation of password strength checkers and the like.

What sort of optimisations might be used to keep the algorithm efficient and quickly search simpler passwords, and incrementally expand the search space. The trick seems to be to avoid duplicating effort.

For instance, the brute force search will at some point generate the same character sequences as in the dictionary, but how would the program know to avoid re-checking these same values without searching the dictionary?

Or let's say it starts with a reduced set of alphabetical characters. If no password is found then it needs to expand the set to include punctuation and symbols. When the expanded character set is used, it should check all the permutations of all the characters, but not waste effort re-checking the permutations from the smaller character set.

I'm interested in algorithmic solutions, hardware optimisations such as multithreading are less informative.

Answer 1

For instance, the brute force search will at some point generate the same character sequences as in the dictionary, but how would the program know to avoid re-checking these same values without searching the dictionary?

Maybe you should store the words read from the dictionary and tested in a string array, then when you get to your brute-force algorithm, you search whether each of the generated words is in the array using one of the efficient searching algorithms (e.g., binary search). If it exists in the array, then it was tested and you should skip it and proceed to generating the next word.

If no password is found then it needs to expand the set to include punctuation and symbols. When the expanded character set is used, it should check all the permutations of all the characters, but not waste effort re-checking the permutations from the smaller character set.

This will be a little bit complicated process. You may store these special symbols in a char array and in case there are no passwords found, you generate the left possible permutations.

For simplicity and demonstration purposes I'll consider there's only 1 symbol (i.e., ?) and I'll consider my plaintext words consist are 2 characters long and each of the characters might have a value in [a, b]. My generated words should be like that

aa
ab
ba
bb
// all possible permutations were tested

// now we should use the symbols in the symbols array we created
/* we'll start generating the possible permutations from the beginning'
   but instead if starting with the very first letter (e.g., 'a'), we
   will start with the first element in the symbols array putting it
   in all the possible locations then move to the next symbol and
   repeat the process and so on
*/
a?
b?
?a
?b

Notice that we should use all the values in the symbols array in all the possible locations