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 Int
s. 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 digitManipulator
s 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.