Click here to Skip to main content
Click here to Skip to main content

A small and elegant bruteforcing class

, 14 Dec 2006
Rate this:
Please Sign up or sign in to vote.
A class that returns all possible combinations of a given subset, without using recursion.

Introduction

Many programs that do some kind of brute-forcing and that have to calculate all possible combinations of a given subset of characters or objects, resort to recursion or to some dirty kind of looping mechanism with inner-loops etc... A couple of years ago, I issued a contest on a hacking forum to write some code in whatever language to return all possible combinations of alphabetic characters up to the length of 6. Only two people submitted an entree, including myself. The other solution was - again - a method that used recursion. My method used something else, namely the idea that any combination of letters could be represented by a unique number so that a simple counter mechanism could be used. The program worked fine but was somewhat static. This article is the result of putting the initial idea into a reusable class that was small and easy to use. It might be not super-performing (otherwise it should be written in ASM or something), but it will allow you to write, e.g., a simple password brute-forcer with a few lines of code... I hope you enjoy it and that it's useful. Any improvements are more than welcome.

The code will also be part of a forthcoming project. This project will try to bundle useful classes for creating programs that can be used to test security, such as for pentests etc… Hopefully online soon.

Background

The whole idea is that any combination of a subset of chars - an array of chars, or symbols, or whatever - can be translated in a unique number representing that combination. Maybe an example will clarify this:

Let's say we have an array {"a","b","c","d"}, and we want to check all combinations possible with length 3. This would be aaa, aab, aac, aad etc..., in total 4 to the power of 3 combinations. Each combination can be translated in a number as follows:

aaa=  0, aab=1, aac =2 .... more specifically, what we do is: dac = 4*4^2+1*4^1+3*4^0 (the fourth element in the array (d=4) times the length of the array (4 chars=4) to the power of the length of the string minus one (3-1=2) (3 chars + the first element of the array times...etc...). Just like, e.g., 5420 can be written as 5*10^3 + 4*10^2 + 2*10^1 +0*10^0.

So now, we have a way to translate a combination in a number, and we can easily do it the other way around, which is in fact what we need because we will implement a counter and return the corresponding string. This is the corresponding code snippet from the class that handles this translation. I called the method factoradic, because I found out afterwards that a similar technique was used in an MSDN article, where they called it factoradic

private string factoradic(ulong l, int power)
{ 
     StringBuilder sb = new StringBuilder(); 
     //set the maximum capacity of our stringbuilder object 
     sb.Capacity = power +1;
     while (power >=0)
     { 
         int len = this.charset.Length;// 
         ulong q = l / (ulong)Math.Pow((double)len,(double)power); 
         ulong m = l % (ulong)Math.Pow((double)len, (double)power); 
         sb = sb.Append(this.charset[(int)q]); 
         l = m;
         power--; 
     } 
     return sb.ToString(); 
}

We use a StringBuilder instead of a string because it's a bit more memory friendly. l is the number we want to translate, and power is the length of the string we want to return -1 (the -1 is done when the function is called). So basically, what we do is make a StringBuilder object and then enter a loop where we do the rundown of the routine where the number gets translated to the corresponding positions in the char array, by decreasing the powers and using the modulus as a re-entree point. I know it sounds complex, but just keep the example above in mind (the 5420 example). The charset that we use is declared earlier in the class. Unfortunately, we have to cast to double for the Math.Pow stuff.

Now that we can translate a number to a string, we have to think of a way on how we can return all the possible combinations in a nice and simple fashion. This is where enumerations come in very handy. First, we make our implement IEnumerable:

public class Bruteforce : IEnumerable

Then our enum routine looks like this:

 public System.Collections.IEnumerator GetEnumerator()
{ 
     for (int x = min; x <= max;x++ ) 
    { 
        ulong counter =0; 
        while (counter < (ulong)
               Math.Pow((double)charset.Length, (double)x)) 
        { 
            string a = factoradic(counter, x-1); 
            yield return a; 
            counter++; 
        } 
    } 
}

The trick here is to reset the counter to zero in the beginning of the loop, otherwise you will just continue with the value when switching bruteforce lengths. So this loop loops between the min length and the max length we want to bruteforce, and then spawns all possible strings, represented by their numeric counterpart which is just a counter that starts at zero and goes up to (ulong)Math.Pow((double)charset.Length, (double)x), which is the number of all possible combinations.

The rest of the code is just a bunch of declarations.

Optimizing the code (update)

Now this code works fine, but lacks some performance. First of all, we use a lot of casts which are expensive, and we also declare some stuff in loops that we could declare earlier (as was pointed out by some readers). Also, it is possible to change the logic in the factoradic method a bit so Math.Pow is no longer needed. So we move up all declarations as much as possible, and we change the factoradic method. I still use a StringbBuilder though. The side effect of changing the factoradic method is that the returned string is brute-forced in reverse order, but this is no problem, since it doesn't affect what we try to achieve. If we change our example and include a Systems.Diagnostics.StopWatch, we can measure the results, which are dramatic:

As you can see, the new code performs about five times better than the old one. It's even more elegant as well Wink | ;) . Here's the full new code (the download includes comments):

using System; 
using System.Collections; 
using System.Text; 
namespace Hacking 
{ 
    public class Bruteforce : IEnumerable 
    { 
    #region constructors 
        private StringBuilder sb = new StringBuilder();
        //the string we want to permutate 
        public string charset = "abcdefghijklmnopqrstuvwxyz";
        private ulong len;
        private int _max; 
        public int max { get { return _max; } set { _max = value; } }
        private int _min; 
        public int min { get { return _min; } set { _min = value; } } 
        #endregion 
        #region Methods
        public System.Collections.IEnumerator GetEnumerator() 
        { 
            len = (ulong)this.charset.Length;
            for (double x = min; x <= max; x++) 
            { 
                ulong total = (ulong)Math.Pow((double)charset.Length, (double)x); 
                ulong counter = 0; 
                while (counter < total) 
                { 
                    string a = factoradic(counter, x - 1); 
                    yield return a; 
                    counter++; 
                } 
            } 
        }
        private string factoradic(ulong l, double power) 
        { 
            sb.Length = 0; 
            while (power >= 0) 
            { 
                sb = sb.Append(this.charset[(int)(l % len)]); 
                l /= len; 
                power--; 
            } 
            return sb.ToString(); 
        } 
    #endregion 
    } 
} 

Thanks for the suggestions!

Using the code

The code is quite simple to use. Import the C# file or the DLL, and then you just set the min and max value, change the charset if you want (default = alphabet), and then start a foreach loop to loop through the enumeration, and do whatever you want in the loop:

using System;
using System.Collections.Generic; 
using System.Text; 
using Hacking; 
namespace example 
{ 
     class Program 
     { 
         static void Main(string[] args) 
         { 
             Bruteforce b = new Bruteforce(); 
             b.min = 2; 
             b.max = 4; 
             b.charset = "abcdefghijklmnopqrstuvwxyz0123456789"; 
             string target= "abc1"; 
             foreach (string result in b) 
             { 
                  Console.Write(result +"\r"); 
                  if (result == target) 
                  { 
                       Console.WriteLine("target found:" + result); 
                       return; 
                  } 
             } 
         } 
     } 
}

We first initialize a new Bruteforce object. Then we set the min and max values and the charset we wish to use. In this example, we are going to loop over our enum until we hit the "abc1" value. Imagine that the target string is a SHA1 hash and that you process each enum value into a SHA1, then you have a simple SHA1 bruteforcer.

Hope you can use the code... Enjoy. 

References

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Filip Waeytens
CEO WSEC
Belgium Belgium
I am currently working as a freelance penetration tester and have my own company: http://www.wsec.be
Follow on   Twitter

Comments and Discussions

 
Questionis this right class? for best performance... PinmemberPietro_SVK13-Jul-07 7:36 
GeneralDoesn't work for very long strings PinmemberMartin Hinks12-Mar-07 2:24 
QuestionConfused PinmemberHokei4-Jan-07 8:28 
AnswerRe: Confused PinmemberFilip Waeytens6-Jan-07 3:08 
GeneralA small detail PinmemberAndreas Botsikas12-Dec-06 14:55 
Hi,
nice way to solve the brute force enumeration. It reminds me of the chromosomes in genetic algorithms.
 
If I remember well, the power sign is ^ rather than ! (which stands for the Factorial function[^]. The symbol confused me a little bit so I though I could contribute.
 
Other than that, great job.
GeneralEnumeration of items [modified] PinmemberIlíon12-Dec-06 13:50 
GeneralRecursion PinmemberRobert Rohde12-Dec-06 9:38 
GeneralRe: Recursion Pinmembercadi12-Dec-06 10:14 
GeneralRe: Recursion Pinmemberbarbsie12-Dec-06 11:29 
GeneralRe: Recursion Pinmemberpeterchen19-Apr-07 9:06 
Generalwithout Math.Pow PinmemberLuc Pattyn12-Dec-06 6:11 
GeneralRe: without Math.Pow PinmemberFilip Waeytens13-Dec-06 8:53 
GeneralRe: without Math.Pow PinmemberLuc Pattyn13-Dec-06 11:15 
GeneralMore performance [modified] Pinmemberdr4cul412-Dec-06 6:08 
GeneralRe: More performance PinmemberFilip Waeytens13-Dec-06 8:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141220.1 | Last Updated 14 Dec 2006
Article Copyright 2006 by Filip Waeytens
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid