2

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.

3

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

5
  • Thanks Kareem. This is some useful advice. Jul 8 '14 at 9:54
  • Seems to be similar to opening a 3 digit combination lock. 000, 001, 002, 003... 009, 010, 011, 012... Only 1000 combinations in this case Nov 28 '14 at 2:15
  • @Kareem: I welcome more advice on an approach to solving the CS50 assignment as stated. I am comfortable writing the code to use dictionary, rainbow book, or brute force attacks. Where I am struggling is that the assignment says that the program must "be designed in such a way that it could crack ALL the passwords." If the goal is ALL possible passwds, then (by definition) we must use a brute force attack to cover possible char combos. The math on it is clear, given 95 printable ASCII chars = (95^8)*4096 = 2.72e19. with 100k tries per second in a high-memory VM, that's 8mill+ years?
    – Disco King
    Feb 15 '15 at 17:44
  • @DiscoKing I believe there it a total of 95 + 95^2 + ... + 95^8 different possibilities for each password as each password will be no longer than 8 characters. This is still quite a lot though. I guess you'll be able to crack the first couple of passwords or so using a dictionary attack. In my case, I ensured that my code did what it was supposed to do when I implemented the various attacks since it would eventually crack all the passwords and that was enough for me :)
    – kzidane
    Feb 15 '15 at 21:32
  • @Kareem ah yes, actually my math assumed passwords were ALWAYS 8 chars... but yes since they can be fewer, i would have to add those in too. i will write the code assuming brute force then... i just wondered if there was some approach or some aspect of the instructions that i was missing! thanks for the response. i will proceed accordingly!
    – Disco King
    Feb 16 '15 at 1:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .