Faster brute force algorithm

Question

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
 {
   //define likely password characters
    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','!','?',' ','*','-','+'};
//your password
static string FindPassword;
static int Combi;
static string space;
static int Characters;

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

    Console.ForegroundColor = ConsoleColor.Green;
    Console.WriteLine("ALL FILES LOADED...");
    Console.ForegroundColor = ConsoleColor.White;

    space = " ";
    int Count;

    //user types in a password

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

    //initialize your password
    FindPassword = (Console.ReadLine());
    Characters = FindPassword.Length;
    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.WriteLine("Your password is: " + FindPassword);
            Console.WriteLine("Your password is: " + Characters + " character(s) long");
            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);
            Console.ReadLine();
            Environment.Exit(0);
        }
    }
  }
 }
 }

Answer 1

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.

Answer 2

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.