Brute force password cracking algorithm challenge

[megatron 0]

Let us celebrate Christmas with friendly rivalry.

The Rules -

1) Must be written in C++
2) Program must compile, run and work before posting your solution
3) Program must be documented, not excessively, but why you went for that approach
4) Program cannot use threads
5) No external libraries may be used, no boost or the like.

6) Program must be run as:

time ./Cracker | ./Target

7) Program must be able to work at variable length:

LENGTH = 2

a, b, c, ..., z, aa, ab, ac, ..., zz

LENGTH = 5

a, b, c, ..., zzzzz

Of course, you may try to randomize it instead.


Here is the target source code:

Target.cpp

#include <iostream>
#include <string>

int main()
{
        const std::string password;
        std::string entered;
        while(std::getline(std::cin,entered))
	{
		if(entered == password)
		{
			std::cerr << "\n\nCorrect password! - " << entered << "\n";
			return 0;
		}
	}
	return 0;
}

Your program should send the generated passwords through std::cout and display any of your program output on std::cerr.

For windows users I don't know how you would pipe program IO so I'm hoping someone can clear that up.

There is no real winner, just something for us to do before the new year kicks in.

Oh, and merry christmas everybody.

[megatron 0]

My approach:

Recursive technique, very CPU intensive on my 2Ghz dual core laptop. I tried setting the password as "megatron" it ran for 18 minutes before I got bored. So I went for a simple test.

#include <iostream>
#include <string>

// Create some alphabet tables

const char AlphabetUpper[26] =
{
	'A', 'B', 'C', 'D', 'E', 'F', 'G',
	'H', 'I', 'J', 'K', 'L', 'M', 'N',
	'O', 'P', 'Q', 'R', 'S', 'T', 'U',
	'V', 'W', 'X', 'Y', 'Z'
};

const char AlphabetLower[26] =
{
	'a', 'b', 'c', 'd', 'e', 'f', 'g',
	'h', 'i', 'j', 'k', 'l', 'm', 'n',
	'o', 'p', 'q', 'r', 's', 't', 'u',
	'v', 'w', 'x', 'y', 'z'
};

// Recursive function, keeps clocking characters
// until length is reached

void Generate(unsigned int length, std::string s)
{
	if(length == 0) // when length has been reached
	{
		std::cout << s << "\n"; // print it out
		return;
	}

	for(unsigned int i = 0; i < 26; i++) // iterate through alphabet
	{
		// Create new string with next character
		// Call generate again until string has reached it's length
		std::string appended = s + AlphabetLower[i];
		Generate(length-1, appended);
	}
}

void Crack()
{
	while(1)
	{
		// Keep growing till I get it right
		static unsigned int stringlength = 1;
		Generate(stringlength, "");
		stringlength++;
	}
}

int main()
{
	std::cerr << "Attempting to crack...";
	Crack();
	return 0;
}

Output:

Attempting to crack...

Correct password! - pound

real	0m4.857s
user	0m7.316s
sys	0m0.056s

EDIT - Test 2 - 6 letters

Attempting to crack...

Correct password! - dollar

real	0m39.247s
user	0m57.548s
sys	0m0.520s

[giblit]

So what happens if it is upper case, if it has numbers, if it has other symbols?

Most passwords will require at least 1 uppercase, at least 1 lower case, at least 1 number, and be at least 8 characters long.

That means the worst case scenario to brute force an average password it will take:

26 * 26 * 10 * 62⁵ = 6193057944320 iterations.

Keep in mind that my math could be off and also that passwords could be more than 8 digits or less than 8 digits.


Also, you didn't say what type of password we were trying to "crack" and you seem to have only done lower case so is that what other people are supposed to be doing as well? Or what kind of passwords are allowed?




Edit oh and your program never ends :P Might want to break out of your crack function.

[megatron 0]

So what happens if it is upper case, if it has numbers, if it has other symbols?

Add them to it if you like, the password doesn't matter as long as it works with the target problem. :)

Keep in mind that my math could be off and also that passwords could be more than 8 digits or less than 8 digits.

Yeah I originally added all characters but my computer is so shit I wouldn't have saw any results.

Also, you didn't say what type of password we were trying to "crack" and you seem to have only done lower case so is that what other people are supposed to be doing as well? Or what kind of passwords are allowed?

The password can be anything you like really as long as it works with the target program, let your imagination take flight, I'm really interested in seeing ideas.

Edit oh and your program never ends :P Might want to break out of your crack function.

Yeah I wasn't sure how to realise if the target program stopped receiving :( I had to keep it in a while loop so it can iterate through unlimited length strings.