Bruteforce function.

[Mondo]

Hi,

Does anyone know of a fast brute force algorithm they are willing to share? I'm looking for something preferably written in C or x86 assembler.

My aim is to brute force a 40-bit key. I tried using the brute force function given in a tutorial titled "the art of password brute forcing". It counts predictably up to FF FE FE FF 00, it then displays

FF FE FF 00 00 as the next key in the sequence instead of the expected FF FE FE FF 01.

The document I am referring to can be found here :Link

I can't seem to find why it behaves this way. I though I would share it in case someone can see how to fix it.

Thanks for any help,

Mondo.

edit : It would help if I showed snippets from my (modified) code. I hope that you can read it, the formatting

is a little screwed up.

#define MIN_CHAR 0

#define MAX_CHAR 255

#define NUM_KEY_BLOCKS 65535

#define NUM_KEYS_PER_BLOCK 16777215

int KeyLength = 5;

static BYTE testkey_new[5] ={0xFF,0xFE,0xFE,0xFF,0x00}; //Last correct key before error.

for(block_count = restart_idx; block_count <= NUM_KEY_BLOCKS; block_count++)

{

for(key_count = 0; key_count <= NUM_KEYS_PER_BLOCK; key_count++)

{

found =0;

//RC4_set_key(&key_rc4asm, KeyLength, testkey_x);

//RC4(&key_rc4asm, 15, knownPlainText, obuf);

//test statement

for(j=0;j<KeyLength;j++)

printf(" %02X",testkey_new[j]);

printf("\n");

getch();

//end of test statement

if(memcmp(obuf, knownPlainText,15) == 0 )

{

printf("Key found \n");

ShowFoundKey():

key_found = TRUE;

break;

}

for(position = KeyLength-1; position !=0; position--)

{

if(testkey_new[position] == MAX_CHAR)

{

memset(testkey_new + position, MIN_CHAR, KeyLength - position);

testkey_new[position-1]++;

found = 1;

break;

}

}

if(!found)

testkey_new[KeyLength-1]++;

}

Edited December 25, 2011 by Mondo

[-Alex-]

FF FE FE FF 00 isnt a dword, so I assume ur bruteforcer only see the first dword, which is FF FE FE FF, and if u increase it, u get FF FE FF 00, exactly what ur app shows.

[Mondo]

Yes, I agree that it behaves as you describe, but it is an array of 5 char bytes which are indexed to generate the sequential key series.

I'm thinking about using 5 nested for loops to index and increment each array element. Is there a faster/better way to do this?

[metr0]

You mean something like this? A mate wanted to use this to generate some sort of permutation, that's what I sent him. It's not particularly fast, but should be enough to start with. I myself did not use the code anywhere so forgive me if it's plain wrong.

#include <iostream>
using namespace std;
inline void PrintBlock(const unsigned __int8 *Block, const unsigned int Blocks)
{
for(unsigned int i = 0; i < Blocks; i++)
  cout << int(Block[i]) << (i == Blocks - 1 ? '\n' : '.');
}
template <unsigned int UpperBound, unsigned int Blocks>
void Recursive(unsigned __int8 *Block, const unsigned int Index)
{
if(Index == Blocks - 1 && Block[Index] == UpperBound - 1)
  return;
if(++Block[Index] == UpperBound && Index <= Blocks - 1)
{
  Block[Index] = 0;
  Recursive<UpperBound, Blocks>(Block, Index + 1);
}
else
{
  PrintBlock(Block, Blocks);
  Recursive<UpperBound, Blocks>(Block, 0);
}
}
template <unsigned int UpperBound, unsigned int Blocks>
void Iterative(unsigned __int8 *Block, unsigned int Index)
{
while(Index != Blocks - 1 || Block[Blocks - 1] != UpperBound - 1)
{
  if(++Block[Index] != UpperBound || Index > Blocks - 1)
  {
   PrintBlock(Block, Blocks);
   Index = 0;
  }
  else Block[Index++] = 0;
}
}
int main()
{
const unsigned int Blocks = 3, Upper = 5;
unsigned __int8 Block[Blocks] = { 0 };
PrintBlock(Block, Blocks);
Iterative<Upper, Blocks>(Block, 0);
memset(Block, 0, Blocks * sizeof *Block);
Recursive<Upper, Blocks>(Block, 0);
return cin.get();
}

[Mondo]

Thank you for sharing Metro. I don't think that I can use your code, at least not in its current form but I might be able to learn something from it to help me develop what I need.

What I want sounds like it should be easy to code, but the more I think about it the more complicated it seems to get. Maybe this is down to my limited programming experience more than anything.

Using 5 nested for loops would achieve the counting easily enough, things get complicated when I want to be able to save and resume a count.

[metr0]

You're incrementing elements in an array, so this is the state of your function. Supplying it to the bruteforce function (even if it's not in its initial state, like 00 00 00 ...) should work, shouldn't it?

The sample above is overcomplicated, since it should also show tail recursion and integer templates (the recursion is optimized to the iterative approach by VS2010 the last time I tested, just another way to write it down).

But you could try having a look at the loop in the iterative version. UpperBound and Blocks are constants (0xFF and 5, in your case). The latter saves you from re-writing code when you want to bruteforce more/fewer values.

Save and resume works like I said above, just pass the array and it will continue counting. Still, it's just a plain simple implementation and by no means optimized for speed or whatever. There are for sure better alternatives (try splitting the work on multiple threads, assign processes to multiple cores, use your GPU if suitable).

[Mondo]

I've got some code working now and I'm also able to save and resume too. I was clearly over-thinking things. Speed ups with threads or GPUs would be nice, I'll maybe try this when I learn a bit more coding.

Thanks again for your help and advice.