Tagged: brute force

Brute-Force String Generation in C

Earlier this week, I posted an article about string generation for brute-force attacks and a couple of example solutions. I emphasized, that the key aspect of brute-force is speed. We want to try as many combinations of input data as possible in the minimum amount of time. And part of this is also efficient algorithm that will generate input combinations. But the examples I posted were written in Python, which is kind of a high level scripting language, not nearly as fast as C.

Hence, here is my implementation of the same in C:

/*
 * Basic string generation for brute-force attacks
 * Copyright (C) 2011 Radek Pazdera
 */

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

/* I chose to use an one way linked list data structure
 * to avoid restrictions on the generated string length.
 * The thing is, the list must be converted to string so
 * it could be used. This conversion have to happen in
 * each cycle and causes unnecessary slowdown.
 * 
 * Faster solution would be to implement the generation
 * directly on some staticaly allocated string with fixed
 * size (20 characters are more than enough).
 */
typedef struct charlist charlist_t;
struct charlist
{
    unsigned char character;
    charlist_t* next;
};

/* Return new initialized charlist_t element.
 *
 * Elements are initialized
 * @return charlist_t
 */
charlist_t* new_charlist_element()
{
    charlist_t* element;

    if ((element = malloc(sizeof(charlist_t))) != 0)
    {
        element->character = 0;
        element->next = NULL;
    }
    else
    {
        perror("malloc() failed.");
    }

    return element;
}

/* Free memory allocated by charlist.
 *
 * @param list Pointer at the first element.
 * @return void
 */
void free_charlist(charlist_t* list)
{
    charlist_t* current = list;
    charlist_t* next;

    while (current != NULL)
    {
        next = current->next;
        free(current);
        current = next;
    }
}

/* Print the charlist_t data structure.
 *
 * Iterates through the whole list and prints all characters
 * in the list including any '\0'.
 * 
 * @param list Input list of characters.
 * @return void
 */
void print_charlist(charlist_t* list)
{
    charlist_t* next = list;
    while (next != NULL)
    {
        printf("%d ", next->character);
        next = next->next;
    }
    printf("\n");
}

/* Get next character sequence.
 *
 * It treats characters as numbers (0-255). Function tries to
 * increment character in the first position. If it fails,
 * new character is added to the back of the list.
 *
 * It's basicaly a number with base = 256.
 *
 * @param list A pointer to charlist_t.
 * @return void
 */
void next(charlist_t* list)
{
    list->character++;
    if (list->character == 0)
    {
        if (list->next == NULL)
        {
            list->next = new_charlist_element();
        }
        else
        {
            next(list->next);
        }
    }
}

int main()
{
    charlist_t* sequence;
    sequence = new_charlist_element();

    while (1)
    {
        next(sequence);
        print_charlist(sequence);
    }

    free_charlist(sequence);
}

Download the fully working code from github.

String Generation for Brute-force Attacks

Everyone knows what a brute-force attack is. One of the most trivial (and yet pretty useful) methods of cracking passwords and breaking access keys. The idea is simply trying all possible sequences of input characters, until you guess the right combination. The thing is, that it might take some time. Actually, sometimes it might take literally ages, due to large number of possible outcomes. The faster our machines (and algorithms!) get, the lesser time it takes to break in using brute-force attack.

One of the key components in this technique is an algorithm that generates the input combinations. It’s run every time in the main loop. Well, the loop is pretty much generate a password, try it and try again. This article will present a couple of simple implementations of string sequence generators in various languages.

Python implementation

Here is code for a most basic example in Python. It’s a simple recursive function that is able to generate strings up to infinite length. I use a list instad of string in this example, because strings in python are immutable. You need to convert it to string ("".join(list)).

def next(string):
    if len(string)
        string.append(chr(0))
    else:
        string[0] = chr((ord(string[0]) + 1) % 256)
        if ord(string[0]) is 0:
            return list(string[0]) + next(string[1:])
    return string

Download the whole example from github.

This example is simple. It tries every possible combination which takes it’s success rate up to 100 percent. You just can’t miss anything if you try them all, right? But a lot of the characters from ASCII table are non-printable, weird and people don’t use them for passwords. So you spend a great amount of time by trying out combinations that are extremely unlikely to ever occur. It would be pretty awesome if there was some way of saying what characters can be part of a password string and use only them. The number of possible outcomes lowers a lot by this optimization while the chance to miss is still almost zero. I made a some alternations to the next() function above:

import string
ALLOWED_CHARACTERS = string.printable
NUMBER_OF_CHARACTERS = len(ALLOWED_CHARACTERS)

def characterToIndex(char):
    return ALLOWED_CHARACTERS.index(char)

def indexToCharacter(index):
    if NUMBER_OF_CHARACTERS
        raise ValueError("Index out of range.")
    else:
        return ALLOWED_CHARACTERS[index]

def next(string):
    if len(string)
        string.append(indexToCharacter(0))
    else:
        string[0] = indexToCharacter((characterToIndex(string[0]) + 1) % NUMBER_OF_CHARACTERS)
        if characterToIndex(string[0]) is 0:
            return list(string[0]) + next(string[1:])
    return string

This snippet above works only with printable characters (as specified in python’s string module). You can also change the subset of characters it works with by changing the value of ALLOWED_CHARACTERS constant. The whole source is again available at github.

Next time I’ll look into a C implementation of the technique and a comparison of speed between the two languages.