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();
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 ;). 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();
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
