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. :)

Kickshaw

I guess you already found out one of the cons of a brute-force attack :) – Losing

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.

Idaidae

Your code look very similar to mine... I'll try to do a comparison to seek for some optimization – Splice

@Andrea: The routines are identical in terms of performance long poles. The string concat will take more time than whether the recursive function passes one or two parms. – Idaidae

@Andrea: The main difference between our answers is that I finished mine 10 minutes before you. ;> – Idaidae

I didn't want to be competitive, just trying to investigate the best solution: I found that 1) I didn't reset the stopwatch between calls to start and 2) your code return string 1 char more greater than specified: where you write: if (level <= maxlength) should be if (level < maxlength). Regards – Splice

@Andrea: yours is less flexible, but correct. I changed the <= into a < to make Danny's correct. – Azoic

Is there a way to yield return on every combination? I tried but am only getting the single character values. When I place yield return where the Console.WriteLine is. – Favata

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...

Circumlocution

Is new string(combination.ToArray()) the same as String.Join("", combination) in .Net 4? – Anthology

It's not the same, but it has the same result. I considered using String.Join, but with an empty separator it seemed strange, and I think the performance is better with the String constructor since we already have a sequence of characters – Circumlocution

Before the article is pulled, this answer needs to include the extension method used (there were multiple) and how to add it to a project before this answer is useful. – Wicopy

@Wicopy there's only one non-standard extension method (CartesianProduct, from the article), the rest is included in Linq. And regarding "how to add it to a project"... Well, I'm not going to do a full C# development course in a SO answer. – Circumlocution

Not what I meant. It doesn't take "a full C# development course" to provide the extension method and say create a class and paste "this" in. You wrote this much... take it to the hoop. The answer doesn't work without the method, and the methods they give at the site don't work as written, either. And SO, as you should know, has a policy against link-only answers where the post can't stand apart from the link. – Wicopy

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

Splice

"This look to be faster than the solution of @dthorpe": well, you just forgot to reset the stopwatch between the two tests, so obviously the last method tested will always seem slower ;) – Circumlocution

Answer 4

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});
   }
}

Augend

Did you test it ? I don't think Cast<char>() will work, as explained here – Circumlocution

Didn't test it. If Cast() doesn't work, the byte can be cast in the Aggregate function, or in a Select(b=>(char)b) as the other thread suggests. – Augend

Answer 5

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;
    }

Melanoma