# Faster brute force algorithm

I have this brute force code, where you input a password and runs through combinations of numbers, lowercase and uppercase letters, and special characters until it match the password given.

The problem with it, is that it took about 2 days just to crack the password "password".

What is a way that I can speed up this process and get the passwords faster? Is there a way I can implement multi-threading to speed up the process?

All I'm really asking is, is there a better way for the program to run through all of the characters and match the password faster?

//This program is used for a school project, where I have to create a list of commonly used passwords and run them through the program and see how long it take for the program to crack them. *I would like to get the best result possible and speed up the process*

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices.ComTypes;
using System.Text;

namespace Bruteforce
{
class Program
{
static char[] Match =            {'0','1','2','3','4','5','6','7','8','9','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','A','B','C','D','E','F','G','H','I','J','C','L','M','N','O','P',
'Q','R','S','T','U','V','X','Y','Z','!','?',' ','*','-','+'};
static int Combi;
static string space;
static int Characters;

static void Main(string[] args)
{
Console.Title = "Brute Force";

Console.ForegroundColor = ConsoleColor.Green;
Console.ForegroundColor = ConsoleColor.White;

space = " ";
int Count;

Console.WriteLine("Welcome to BRUTE FORCE");
Console.WriteLine("This program was crated by Nick");
Console.WriteLine(space);

Console.Clear();

DateTime today = DateTime.Now;
today.ToString("yyyy-MM-dd_HH:mm:ss");
Console.WriteLine(space);
Console.WriteLine("START:\t{0}", today);

for (Count = 0; Count <= 15; Count++)
{
Recurse(Count, 0, "");
}
}

static void Recurse(int Lenght, int Position, string BaseString)
{
int Count = 0;

for (Count = 0; Count < Match.Length ; Count++)
{
Combi++;
if (Position < Lenght - 1)
{
Recurse(Lenght, Position + 1, BaseString + Match[Count]);
}
if (BaseString + Match[Count] == FindPassword)
{
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Blue;
Console.ForegroundColor = ConsoleColor.White;
DateTime today = DateTime.Now;
today.ToString("yyyy-MM-dd_HH:mm:ss");
Console.WriteLine(space);
Console.WriteLine("END:\t{0}\nCombi:\t{1}", today, Combi);
Environment.Exit(0);
}
}
}
}
}

• What are you brute forcing exactly? – Ave Nov 22 '16 at 23:50
• I have a school project were I need to get a list of common passwords used and run them through this program and see how long it takes for the programm to get the. So I am trying to get the best result possible and speed the program up – Nick Nov 22 '16 at 23:53
• You mean other that just "guessing" FindPassword to begin with? – Nathan Davis Nov 23 '16 at 1:14
• I still want it to find the password meaning typing the password in and then the program running through characters until it matches ... I just want to find a better algorithm to make it run through the characters a little faster – Nick Nov 23 '16 at 1:16
• So, you are basically trying to generate all possible passwords, then your system will check if any of the password matches to the password user has entered, and if it has been found, your application says "Password Found..."! Something like that?? – Nisarg Nov 23 '16 at 3:23

Do what a real cracker would do.

Cheat.

Here's a list of the most common passwords. Load the list and cycle through them until you have a match, or have exhausted the list. If you don't find a match, then you can fall back to the brute force approach.

This is called a dictionary attack, by the way.

Another approach would be to make your program "learn" each time you use it. Instead of generating each combination of characters every time the program is run, cache the calculated strings to disk along with the data that allows you to start where you stopped. Then you can check your known list of possible passwords before generating more. Essentially, this is a dictionary attack too, but you're building the password dictionary incrementally each time you run your program.

• Do you know how I can implement that? How will I fix the code to get it to cache the data? – Nick Nov 23 '16 at 11:50
• Being its homework, I think you should figure that out yourself @Nick. – RubberDuck Nov 23 '16 at 12:34
• This doesn't really answer the question that was asked. "All I'm really asking is, is there a better way for the program to run through all of the characters and match the password faster?" – Nathan Davis Nov 23 '16 at 19:26
• Yup. Exactly @NathanDavis, the better way is "don't". That's not an uncommon answer during a Code Review. – RubberDuck Nov 23 '16 at 19:28
• @RubberDuck, but if the requirement is to brute force the password, then that's the requirement. Anything else is, as you say, cheating. – Nathan Davis Nov 23 '16 at 19:30

Algorithmically speaking, there is no better way to find a matching password without considering characteristics of the password itself. For instance, if you take into account the length, you could restrict the generated passwords to be only of that length. If you consider the actual characters, then well, you already have the password, so you're done. But neither of these seem to be true to the exercise, do they?

But what about parallelization? After all, this task is trivial to parallelize. Surely if we harness the processing power of all our cores, we will be able to chew through those passwords in lightning speed, right?

Ok, let's talk about that. Suppose you have a machine with 24 cores. If we parellelize, should get a speedup of 24, right? Well, not quite, because there's always some overhead when you parallelize something, due to things like task coordination and so on. So the actual speedup will be something less than 24. But, for the sake of argument, let's assume we have an ideal system and we actually do see a speedup of 24.

Now, you said it took 2 days to find the password "password", right? So with 24 cores, it now takes 2 hours. "password" is 8 charaters. So let's just say that we can find any 8 character password in 2 hours. That's pretty good compared to 2 days!

But what about 9 character passwords. If I counted correctly, there are 68 characters you use to generate passwords. So the set of all 9 character passwords will be 68 times larger than the set of all 8 character passwords. So generating all 9 character passwords will take 68*2 hours = 136 hours = 5 days + 16 hours. Ouch!

So what now, purchase more machines?

By the way, the maximum password length you examine is 15. There are 68^15 passwords of that length. 8^15 is 3,073,503,348,387,795,563,479,826,432. To examine this number of passwords will take 6,722,988,818,432 times longer than it takes to examine all 8 character passwords. And yes, that's 6.7 Trillion. It would about 1.5 Billion years to examine all those passwords on our 24-core machine. I don't know how old you are, but suffice it to say that if you plan on obtaining the results before you expire, you're going to need a lot more machines. If you do plan on doing this, please let me know what server provider you'll be using ... I'd love to invest in them!

So, the bottom line is, the only way to brute force something is through brute force. Parallelization can help, but only if the problem is tractable to begin with. The power of exponentiation will win every time.

• I get what you are saying and that makes sense but is there also a way to maybe insert threading into the program to make it run for faster and efficient – Nick Nov 23 '16 at 4:02
• Sure, this task is trivial to parallelize. The runtime complexity will remain unchanged, though (exponential). – Nathan Davis Nov 23 '16 at 4:05
• Okay, so do you have any idea though on how I can implement threading – Nick Nov 23 '16 at 4:07
• I don't do enough work with C# / .NET to offer any specifics, but there's really no point. Any gain you see from using multiple cores will be fleeting. I've updated the answer to explain why. – Nathan Davis Nov 23 '16 at 5:20
• There are 68 characters in the password array, so it will be 68 times longer. – Der Kommissar Nov 23 '16 at 5:48