C/C++ Bruteforce, Dictionary Creation... Need a method

Micah · 06-06-2006, 12:30 PM

I've recently had an awesome idea which I don't really want to explain YET. (If this becomes a moral thread I may)

I'm looking for some code to cycle X bytes through all possible combinations...

Code:

// Say I have 4 characters (bytes) 
// '00000000' (looks like this in mem as hex)
// I want to go from this to:
// 'FFFFFFFF'

The big thing is that I will need to make the number of characters dynamic (recursion perhaps)

ATM I am stumped on how to do this dynamically. If it were a set of 4 bytes always it'd be a breeze, but due to bandwidth I'll need this number to be changeable on the fly.

I'd really like to get this code to work properly to find out IF my idea has even a chance at working before I just go around saying "W00t! New Idea for doing XY!"

One Idea I've had so far is to create an unsigned long and just increment this. It works, BUT i need it to be dynamic in length. (Do an array of unsigned longs? Or perhaps treat an unsigned char like one?)

Any assistance would be grand!

95se · 06-06-2006, 12:43 PM

Here is a recursive example. Haven't compiled it, so don't count on my code working right off

Code:

#define SIZE 100

int some_checker_func(unsigned char *, unsigned int);
void combo(int (*)(unsigned char *, unsigned int), unsigned char *, unsigned int, unsigned int);

int main() {
    unsigned char d[SIZE];
    
    combo(some_checker_func, d, 0, SIZE);
}

int some_checker_func(unsigned char *data, unsigned int len) {
    //do something
}

void combo(int (*f)(unsigned char *, unsigned int), unsigned char *data, unsigned int pos, unsigned int len) {
    unsigned short i;
    
    for(i = 0; i < 256; i++) {
        data[pos] = (unsigned char)i;
        if(pos == (len - 1)) {
            f(data, len);
        } else {
            combo(f, data, pos + 1, len);
        }
    }
}

It cycles through all the possible combinations and calls the function passed to the recursive function as the first argument each time a change is made. So, in this example, in some_checker_func you could put, like, a call to crypt then compare it with a hashed password or something. It can't be null terminated, so the length is a must.

graemef · 06-06-2006, 01:29 PM

There's no real need for it to be recursive, just add an outer loop from 0 through SIZE-1 Probably something like:

Code:

unsigned char d[SIZE];
// init array
for(j = 0; j < SIZE; j++)
{
    data[j] = 0;
}
// cycle through array
for(j = 0; j < SIZE; j++)
{
    for(i = 0; i < 256; i++)
    {
        data[j]++;
        // Do something with this particular cycle here...
    }
}

<snip>Just corrected a couple of errors I spotted.

Micah · 06-06-2006, 01:38 PM

Wow, that was quicker than expected.

Thanks! I'll give these both a try and see what happens =D

spooon · 06-06-2006, 03:59 PM

Quote:

Originally Posted by graemef

There's no real need for it to be recursive, just add an outer loop from 0 through SIZE-1 Probably something like:

Code:

unsigned char d[SIZE];
// init array
for(j = 0; j < SIZE; j++)
{
    data[j] = 0;
}
// cycle through array
for(j = 0; j < SIZE; j++)
{
    for(i = 0; i < 256; i++)
    {
        data[j]++;
        // Do something with this particular cycle here...
    }
}

<snip>Just corrected a couple of errors I spotted.

This doesn't work. It just goes from 00000000 to 000000FF to 0000FFFF to 00FFFFFF to FFFFFFFF. You see? Each time it takes a byte from 00 to FF, but it doesn't reset it and carry. It just goes through 4*256 combinations, not what you want.

Because of the exponential nature of the problem, recursion (or something equivalent to it) is necessary.

Micah · 06-06-2006, 04:02 PM

95se - This code works =D
graemef - Doesn't work (Close!, but not yet)
spooon - you beat me by minutes (I think)

Is recursion the only way? If so, so be it...
It has to be dynamic in the length of the array.
(I'll be playing with 95se's code this evening)

spooon · 06-06-2006, 04:18 PM

Quote:

Originally Posted by Micah

Is recursion the only way? If so, so be it...
It has to be dynamic in the length of the array.
(I'll be playing with 95se's code this evening)

Any way of doing it requires the same number of steps (256^SIZE). Recursion is the easiest way to implement it. Otherwise, you can emulate recursion by having a while loop, and then when you make a recursive call, just increment the "pos" variable, and use the data[j] to keep track of where in the 256 you are, and when it reaches the end, decrement the "pos" variable to "return" from the recursive call. But this is more complicated.

graemef · 06-06-2006, 04:19 PM

Ah yes... Not been a good week

It is certainly possible to rewrite a recursive algorithm non recursively but this is an example where a recursive algorithm is more elegant.

Micah · 06-06-2006, 04:32 PM

Quote:

Originally Posted by spooon

Any way of doing it requires the same number of steps (256^SIZE). Recursion is the easiest way to implement it. Otherwise, you can emulate recursion by having a while loop, and then when you make a recursive call, just increment the "pos" variable, and use the data[j] to keep track of where in the 256 you are, and when it reaches the end, decrement the "pos" variable to "return" from the recursive call. But this is more complicated.

I've been thinking about it... I'll leave the recursion =D

Thanks!
(Preliminary info: 4 Byte array takes 1m 17s in a Virtual PC over SSH)

tuxdev · 06-06-2006, 06:27 PM

Danger, Will Robi... Stack overflow, core dumped.

Recursion feels like it will shoot you in the foot if it something that really needs a bignum representation.

graemef · 06-06-2006, 07:14 PM

It should be alright because, as I understand, it will only need SIZE recursive calls, where SIZE is the number of bytes required. But yes, care should be taken.

Micah · 06-07-2006, 08:49 AM

Quote:

Originally Posted by tuxdev

Danger, Will Robi... Stack overflow, core dumped.

Recursion feels like it will shoot you in the foot if it something that really needs a bignum representation.

Thanks for bringing this to my attention; I never thought about that... Would have made for some fun debugging though =P

graemef · 06-07-2006, 10:28 AM

Here is a non recursive algorithm:

Code:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 4
unsigned char data[SIZE];

int main(int argc, char *argv[])
{
  char overflow = 0;
  int posn =1;
  while (overflow == 0)
  {
      data[SIZE-posn]++;
      if (data[SIZE-posn] == 0)
      {
         posn++;
         if (posn > SIZE)
            overflow = -1;
      }    
      else
      {
         posn = 1;
         print();
      }    
  }    
  printf("\n");
  system("PAUSE");	
  return 0;
}

void print()
{
    int cnt;
    for (cnt = 0; cnt < SIZE; cnt++)
    {
        printf("%02X",data[cnt]);
    }
    printf("\t");
}