Framework for Writing Flexible Bruteforcers

When writing a bruteforcer, it’s easiest to think of it as mapping some kind of output to a monotonically-increasing number.

Like for one of the solved PlaidCTF question, the answer string was composed from the eight letters “plaidctf”, which conveniently is a power of 2, meaning each output character can be represented with 3 bits. To write a bruteforcer for a string composed of these characters, you might imagine generating a 3-bit number (i.e. from 0 to 7) then mapping it to the character set for one output character, or a 30-bit number if the output string was 10 characters. Unsurprisingly, this was exactly what I did for my solver script. The output string was generated from a BitVector of 171 * 3 bits.

But what if the output was composed of several different pieces that cannot be represented uniformly as a set of bits?

One solution might be to emulate such a behaviour using an array of integers, like how I modified my solver script in version 2 to handle a character set of arbitrary length.

In this post, I will walk-through writing a basic, but flexible, bruteforcer with accompanying code snippets in Go.

Keeping State

Continuing on the CTF puzzle, the BitVector was replaced with an array of Ints. Each Int will represent one character of the output string. We can thus represent the state like so (for simplicity, let’s limit the output string to 2 characters):

type state struct {
    digit [2]int
}

In order to increment each digit, we can write a function that increments state.digit until a certain number, then resets it to zero.

To make it generic, we will write a function that returns another function that manipulates a digit position, so we don’t have to copy & paste the code for each digit position:

// returns a function that manipulates the digit at given pos
func digitManipulator(pos int) func(*state) bool {
    return func(s *state) bool {
        s.digit[pos]++
        if s.digit[pos] == MAX_NUMBER {
            s.digit[pos] = 0
            return true
        }
        return false
    }
}

We will talk more about the boolean return value later.

Arithmetic Carry

When implemented as separate integers, we do not have the convenience of arithmetic carry as a monotonically-increasing number does.

Re-visiting our “plaidctf” example above, a 2 letter output string will be represented using 2 * 3 bits. In its initial state when all the binary digits are zero, both output characters will be mapped to “p” (the first character).

000 000 -> pp
000 001 -> pl
000 010 -> pa
.
.
.
000 111 -> pf
001 000 -> lp
001 001 -> ll

When the state reaches 000 111 (or 7 in decimal), a subsequent increment will cause the first output character to transition from “p” to “l“. Therefore, when the number runs from 000 000 to 111 111, all 64 possible permutations of the 2 character string would have been produced.

This arithmetic carry behaviour is thus desirable when implementing a bruteforcer. We can emulate this behaviour by chaining digitManipulators like so:

// controls the order in which state is manipulated
var stateManipulators = []func(*state) bool{
    digitManipulator(1), // 2nd digit
    digitManipulator(0), // 1st digit
}

// manipulates the state
func nextState(s *state) bool {
    i := 0
    for ; i < len(stateManipulators); i++ {
        if !stateManipulators[i](s) {
            break
        }
    }

    return i == len(stateManipulators)
}

Each manipulator function returns a boolean, indicating whether it has reached its maximum and should carry over into the next output “digit”. At the same time, it also resets itself to the initial value.

The manipulators are stored in a stateManipulators array that will determine the order in which each digit is manipulated. Having manipulator functions will allow for flexibility, meaning you can modify other data types like booleans.

Putting it Together

We can see how our bruteforcer is looking by adding a main function:

func main() {
    s := &state{} // initial state

    for {
        fmt.Printf("%v\n", s)
        if nextState(s) { break }
    }

    fmt.Println("finished.")
}

You can play around with this example on the Go Playground. When MAX_NUMBER is set to 2, the output forms a 2-bit binary counter:

&{[0 0]}
&{[0 1]}
&{[1 0]}
&{[1 1]}
finished.

Changing MAX_NUMBER to 10 will transform it into a 2 digit decimal counter, counting from 00 to 99.

State Formatting

This bruteforcer is not very useful until you can transform the state into an output that you want.

Let’s add a function that formats the state into a string. This function takes each state.digit and maps it into an character, just like the “plaidctf” example discussed:

func stateFormatter(s *state) string {
    const c = "0123456789abcdef"
    return string(c[s.digit[0]]) + string(c[s.digit[1]])
}

We also expand MAX_NUMBER to 16, and modify the fmt.Printf call to run the state through stateFormatter first:

func main() {
    s := &state{} // initial state

    for {
        fmt.Println(stateFormatter(s)) // <-- format state here
        if nextState(s) { break }
    }

    fmt.Println("finished.")
}

With these simple changes, we now have a bruteforcer that esentially counts in hexadecimal, from 00 to ff.

You can easily imagine variations of this to generate all kinds of weird strings. If you have separate MAX_NUMBER limits for each state digit, you can output hex on the first digit, but decimal numbers on the second, for example.

You could also add a boolean to the state that perhaps determines if a dash or special character should be appended or prepended.

Complete Example

Here’s a completed example of the hexadecimal bruteforcer that outputs both positive and negative hex numbers from 00 to ff, then -00 to -ff.

It adds a boolean for the state of the negative sign, and a modified stateFormatter to prepend the sign character.

By adopting this generic framework, you can write a bruteforcer for almost anything.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s