Memory Problems

[leverin4]

I have to write a very simplistic password cracker for a Security Class...Basically, the professor gave us a binary file with five encrypted passwords and a list of 354984 possible words. The first part of the assignment was easy, I can crack the 5 passwords in under a second. But the second part is causing me problems.

For part one the passwords only contained lower case letters, so I only had to check the 354984 words. For part two, for each possible password I have to check every possible combination of upper and lower case letters. So a single 4-letter word becomes 16 possible words, and a 10-letter word becomes 1,024 possible words.

I do this by reading a single word, and then finding it's possible combinations and storing them in a temporary String array. I then take each combination one at a time, encrypt them, and compare them to the encrypted passwords given to me. If no combinations match, I take the next word in the file and find its combinations and overwrite the temporary string array. Rinse. Repeat.

I wrote a small side program that calculated average word length and total possible combinations in the file and came up with an average word length of 9 letters, and a total of 181751808 possible combinations. My program cracks the first 2 passwords, aaRDvARk and ABACUS, and then runs out of memory. The list is alphabetical, so it obviously isn't making it very far. Is there a way to clear the "Java Heap Space" occasionally, or anything like that?

I can give code samples if necessary. Thanks.

[masijade]

Sounds like your "temporary" string array may not be so temporary.

But, seeing as how the "password" file is not large, I would read the file completely and keep it's contents in memory, then start with the first word in the "dictionary", compare it in it's original form to all passwords (removing the password from the "to search" list and adding it to the "found" list as soon as it is cracked), then "mutate" the first word to it's next possible configuration and check it against the passwords.

IOW, create two lists, read the encrypted passwords from the file and add them, in encrypred form, to one list. Then take the first word, encrypt it, compare it to the encrypted words in the list, placing the clear text word in the second list and removing the password from the first list when a match is found. Then mutate that word and encrypt it again, and check again. Rinse, lather, repeat, right down the line of words (for a brute-force check) until the first list is empty. There is no reason to keep all the mutations in memory.

[leverin4]

Sounds like your "temporary" string array may not be so temporary.

But, seeing as how the "password" file is not large, I would read the file completely and keep it's contents in memory, then start with the first word in the "dictionary", compare it in it's original form to all passwords (removing the password from the "to search" list and adding it to the "found" list as soon as it is cracked), then "mutate" the first word to it's next possible configuration and check it against the passwords.

IOW, create two lists, read the encrypted passwords from the file and add them, in encrypred form, to one list. Then take the first word, encrypt it, compare it to the encrypted words in the list, placing the clear text word in the second list and removing the password from the first list when a match is found. Then mutate that word and encrypt it again, and check again. Rinse, lather, repeat, right down the line of words (for a brute-force check) until the first list is empty. There is no reason to keep all the mutations in memory.

That's what I think I'm doing for the most part. I think I run into problems with words like "dichlorodiphenyltrichloroethane". It's the longest word I have, with 31 letters. So it has 2, 147, 483, 648 combinations by itself. Am I allowed to make arrays that large? I have a

public String[] getCombinations(char[] word);

function that would return an array of size 2, 147, 483, 648, with each possible combination of letters stored inside each array slot.

I made an error in my initial calculations. There are a total of 8, 348, 224, 722 possible combinations in the word file, not 181 million...

[masijade]

That's what I think I'm doing for the most part. I think I run into problems with words like "dichlorodiphenyltrichloroethane". It's the longest word I have, with 31 letters. So it has 2, 147, 483, 648 combinations by itself. Am I allowed to make arrays that large? I have a

public String[] getCombinations(char[] word);

function that would return an array of size 2, 147, 483, 648, with each possible combination of letters stored inside each array slot.

I made an error in my initial calculations. There are a total of 8, 348, 224, 722 possible combinations in the word file, not 181 million...

I've made arrays with millions of memebers (I had Gigs of memory available though).

You are going to have to show more code.

[jmaat7]

couldn't you use a vector if you wanted to constantly change the size? i'm kinda confused how you're doing the search though, he's right at least post the full search method.

btw - System.gc() will run the garbage collector, but if you're just reusing the same array it wouldn't really make a difference. it won't clear all the space, but will free up whatever's not in use.

[masijade]

it won't clear all the space, but will free up whatever's not in use.

Just a note, the JVM itself must do this before it throws a Heap Exception. An OOME Heap Space full will never be thrown due to unreclaimed heap space. Only due to all of the heap space being actively used.

[JamesCherrill]

I think I run into problems with words like "dichlorodiphenyltrichloroethane". It's the longest word I have, with 31 letters. So it has 2, 147, 483, 648 combinations by itself.

This suggests that you should not be creating an array with all the combinations if you don't have to; and you don't have to!

You can simply check each UC/LC combination in turn as you generate them, without any need to store them all. Change the method to something like:
public boolean checkCombinations(char[] word, String encryptedPassword)

[masijade]

This suggests that you should not be creating an array with all the combinations if you don't have to; and you don't have to!

You can simply check each UC/LC combination in turn as you generate them, without any need to store them all. Change the method to something like:
public boolean checkCombinations(char[] word, String encryptedPassword)

That is, essentially, my first suggestion, except to pass all the encrypted passwords (assuming there would not be millions of them), so that each "mutation" of the word only need occur once. ;-)

[JamesCherrill]

That is, essentially, my first suggestion, except to pass all the encrypted passwords (assuming there would not be millions of them), so that each "mutation" of the word only need occur once. ;-)

I agree.