Generating every character combination up to a certain word length

Question

I am doing a security presentation for my Computer and Information Security course in a few weeks time, and in this presentation I will be demonstrating the pros and cons of different attacks (dictionary, rainbow and bruteforce). I am do the dictionary and rainbow attacks fine but I need to generate the bruteforce attack on the fly. I need to find an algorithm that will let me cycle though every combination of letter, symbol and number up to a certain character length.

So as an example, for a character length of 12, the first and last few generations will be:

a
ab
abc
abcd
...
...
zzzzzzzzzzzx
zzzzzzzzzzzy
zzzzzzzzzzzz

But it will also use numbers and symbols, so it's quite hard for me to explain... but I think you get the idea. Using only symbols from the ASCII table is fine.

I can kind of picture using an ASCII function to do this with a counter, but I just can't work it out in my head. If anyone could provide some source code (I'll probably be using C#) or even some pseudo code that I can program a function from that'd be great.

Thank you in advance. :)

Answer 1

A recursive function will let you run through all combinations of ValidChars:

    int maxlength = 12;
    string ValidChars;
    private void Dive(string prefix, int level)
    {
        level += 1;
        foreach (char c in ValidChars)
        {
            Console.WriteLine(prefix + c);
            if (level < maxlength)
            {
                Dive(prefix + c, level);
            }
        }
    }

Assign the set of valid characters to ValidChars, the maximum length of string you want to maxlength, then call Dive("", 0); and away you go.

Answer 2

You need to generate all combinations of characters from a set of valid characters ; let's call this set validChars. Basically, each set of combinations of length N is a cartesian product of validChars with itself, N times. That's pretty easy to do using Linq:

char[] validChars = ...;

var combinationsOfLength1 =
    from c1 in validChars
    select new[] { c1 };

var combinationsOfLength2 =
    from c1 in validChars
    from c2 in validChars
    select new[] { c1, c2 };

...

var combinationsOfLength12 =
    from c1 in validChars
    from c2 in validChars
    ...
    from c12 in validChars
    select new[] { c1, c2 ... c12 };

var allCombinations =
    combinationsOfLength1
    .Concat(combinationsOfLength2)
    ...
    .Concat(combinationsOfLength12);

Obviously, you don't want to manually write the code for each length, especially if you don't know in advance the maximum length...

Eric Lippert has an article about generating the cartesian product of an arbitrary number of sequences. Using the CartesianProduct extension method provided by the article, you can generate all combinations of length N as follows:

var combinationsOfLengthN = Enumerable.Repeat(validChars, N).CartesianProduct();

Since you want all combinations from length 1 to MAX, you can do something like that:

var allCombinations = 
    Enumerable
        .Range(1, MAX)
        .SelectMany(N => Enumerable.Repeat(validChars, N).CartesianProduct());

allCombinations is an IEnumerable<IEnumerable<char>>, if you want to get the results as a sequence of strings, you just need to add a projection:

var allCombinations = 
    Enumerable
        .Range(1, MAX)
        .SelectMany(N => Enumerable.Repeat(validChars, N).CartesianProduct())
        .Select(combination => new string(combination.ToArray()));

Note that it's certainly not the most efficient solution, but at least it's short and readable...

Answer 3

You can try this code, that use recursion to print all possible strings of 0 to stringsLenght chars lenght, composed by all combination of chars from firstRangeChar to lastRangeChar.

class BruteWriter
{
    static void Main(string[] args)
    {
        var bw = new BruteWriter();
        bw.WriteBruteStrings("");
    }

    private void WriteBruteStrings(string prefix)
    {
        Console.WriteLine(prefix);
        if (prefix.Length == stringsLenght)
            return;

        for (char c = firstRangeChar; c <= lastRangeChar; c++)
            WriteBruteStrings(prefix + c);

    }

    char firstRangeChar='A';
    char lastRangeChar='z';
    int stringsLenght=10;


}

This look to be faster than the solution of @dthorpe.I've compared the algorthms using this code:

class BruteWriter
    {
        static void Main(string[] args)
        {
            var st = new Stopwatch();
            var bw = new BruteWriter();
            st.Start();
            bw.WriteBruteStrings("");
            Console.WriteLine("First method: " + st.ElapsedMilliseconds);

            for (char c = bw.firstRangeChar; c <= bw.lastRangeChar; c++)
                bw.ValidChars += c;

            st.Start();
            bw.Dive("", 0);
            Console.WriteLine("Second method: " + st.ElapsedMilliseconds);

            Console.ReadLine();


        }

        private void WriteBruteStrings(string prefix)
        {
            if (prefix.Length == stringsLenght)
                return;

            for (char c = firstRangeChar; c <= lastRangeChar; c++)
                WriteBruteStrings(prefix + c);

        }

        char firstRangeChar='A';
        char lastRangeChar='R';
        int stringsLenght=5;



        int maxlength = 5;
        string ValidChars;
        private void Dive(string prefix, int level)
        {
            level += 1;
            foreach (char c in ValidChars)
            {
                if (level <= maxlength)
                {
                    Dive(prefix + c, level);
                }
            }
        }
    }

and, on my pc, I get these results:

First method: 247
Second method: 910

Answer 4

Another alternative i did, that return a string.

I did not care about the performance of the thing since it was not for a real world scenario.

private void BruteForcePass(int maxLength)
    {
        var tempPass = "";
        while (tempPass.Length <= maxLength)
        {
            tempPass = GetNextString(tempPass);//Use char from 32 to 256
            //Do what you want
        }
    }

    private string GetNextString(string initialString, int minChar= 32, int maxChar = 256)
    {
        char nextChar;
        if (initialString.Length == 0)
        {
            nextChar = (char)minChar;//the initialString Length will increase
        }
        else if (initialString.Last() == (char)maxChar)
        {
            nextChar = (char)minChar;
            var tempString = initialString.Substring(0, initialString.Length -1);//we need to increment the char just before the last one
            initialString = GetNextString(tempString, minChar, maxChar); 
        }
        else
        {
            nextChar = (char)(initialString.Last() + 1);//Get the lash Char and increment it;
            initialString= initialString.Remove(initialString.Length - 1);//Remove the last char.
        }
        return initialString + nextChar;
    }

Answer 5

public void BruteStrings(int maxlength)
{
   for(var i=1;i<i<=maxlength;i++)
      BruteStrings(Enumerable.Repeat((byte)0,i));

}

public void BruteStrings(byte[] bytes)
{
   Console.WriteLine(bytes
                       .Cast<char>()
                       .Aggregate(new StringBuilder(), 
                          (sb,c) => sb.Append(c))
                       .ToString());

   if(bytes.All(b=>b.MaxValue)) return;

   bytes.Increment();

   BruteStrings(bytes);
}

public static void Increment(this byte[] bytes)
{
   bytes.Last() += 1;

   if(bytes.Last == byte.MinValue)
   {
      var lastByte = bytes.Last()
      bytes = bytes.Take(bytes.Count() - 1).ToArray().Increment();
      bytes = bytes.Concat(new[]{lastByte});
   }
}