I just started learning Go, and I wanted to created a project to learn more about concurrency in go. I heard about Go's lightweight threads, so I wanted to give them a try.

This program uses backtracking to brute-force a list of passwords loaded from a file. It tries from password of length 2 and go ahead until all passwords are been found.

It works well until password length doesn't come to 6: then my RAM will get full. I've already optimized my code in some ways e.g. in the first iteration of the program I used to create a chan for every thread, and every thread would wait for the spawned thread to terminate. Now it has a barrier.

I would need some suggestion about my code and spatial optimization tips.

package main

import (

var alfabeto = []rune {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6','7','8','9'}

func compute(prefix int, n int, a string, wgFather *sync.WaitGroup){
    defer wgFather.Done()

    if prefix == n-1 {
        for _, d := range alfabeto {
            password := fmt.Sprintf("%s%c", a, d)

            if searchPassword(password) {
                if len(passwords) == 0{
    }else {
        for i := range alfabeto{
            go compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)

var passwords []string

func main(){

    if loadPasswords() {
    fmt.Println("File with passwords loaded. We're gonna crack", len(passwords),"passwords!")
    start := time.Now()
    cont := 2
    for len(passwords) > 0  {
            fmt.Println("Searching for passwords at length: ", cont)

            var wg sync.WaitGroup
            go compute(0, cont, "", &wg)

    elapsed := time.Since(start)
    fmt.Println("Password's file cracked in:", elapsed)


func searchPassword(pass string) bool{
    hash := fmt.Sprintf("%x", md5.Sum([]byte(pass)))
    for i, value := range passwords{
        if strings.Compare(hash, value) == 0{
            // Password found!
            fmt.Println("Find Password:", pass, " with hash:", hash)
            passwords = append(passwords[:i], passwords[i+1:]...)
            return true
    return false

func loadPasswords() bool{
    stream, err := ioutil.ReadFile("file.txt")
    if err != nil{
        return true
    readstring := string(stream)

    passwords= strings.Split(readstring, "\n")
    return false

This is my password's file, file.txt:

  • 3
    \$\begingroup\$ Well I have one for you, instead of specifiying the entire alphabet in an array, use ascii character codes. For lowercase letters a-z thats 97-122. For numbers 0-9 thats 48-57. \$\endgroup\$ – Ashwin Gupta Jan 9 '16 at 17:21
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Please consider posting a new question linking back to this one instead. Thanks! \$\endgroup\$ – Mast May 29 at 11:07
  • \$\begingroup\$ Hi! I haven't "updated" the code, I've just translated some variables in English for enhanced readability. The program has not changed, and I don't see anyone suggesting me to translate the variable name to english. \$\endgroup\$ – Federico Ponzi May 30 at 10:42
  • \$\begingroup\$ Could you please_at least_ reapply my grammar fixes? Thanks. \$\endgroup\$ – Federico Ponzi May 30 at 10:44

First let's mention a bug / issue:

  • Your passwords variable is accessed (read and modified) from multiple goroutines without any syncronization: this is a race condition!

Primary problem

Your memory problem arises from launching a tremendous amount of goroutines. For example when you call compute() with n = 6 (to try passwords with a length of 6), it will create:

36^5 = pow(36, 5) = 60466176

(36 is the length of your alphabet; 5 is the prefix value for the condition prefix == n-1 when compute() stops spawning new goroutines)

60 million goroutines!

Goroutines are lightweight, but not that lightweight! Even if managing 1 goroutine would cost only 1 KB memory (it has its own stack etc.), this would require 60 GB memory! Understandable you run out of it. Your code spawns goroutines at a much quicker rate than they complete. (It should be noted that nothing in your code prevents spawning these new goroutines before any would be completed, so this is kind of worst case but still...)

An easy fix!

But the good news is that there is a really easy fix to this tremendous number of goroutines: simply do not spawn many goroutines.

A trivial way to limit spawning goroutines is that when you would spawn them, bind it to a condition to keep them at bay. For example launch 36 goroutines to process passwords starting with the different letters, but after that let 1 goroutine try all the combinations with that starting letter.

We can test this "first letter" condition by comparing prefix to 0:

for i := range alfabeto {
    if prefix == 0 {
        go compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)
    } else {
        compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)

By inserting this condition and the else branch just calling compute() on the same goroutine, you keep your goroutine number and memory usage at bay! But still, you utilize multiple goroutines and multiple CPU cores.

There is a minor "downside": you have no control how these 36 goroutines finish compared to each other, there may be a "relaxed" period when only 1 or 2 goroutines are running and others are finished, in this relaxed period CPU utilization will not be 100%. More formally CPU utilization will be < 100% if # of goroutines is less than # of CPU cores.

Optimization tips

Here are some optimization tips:

  • You do unnecessary round-trips: you build potential passwords as string, then when your searchPassword() function computes its MD5, it has to convert it to []byte. Best would be to build password in a []byte. Go stores strings as UTF-8 encoded sequences (see blog post Strings, bytes, runes and characters in Go for details), and all your alphabet letters map to bytes one-to-one in UTF-8 encoding, so you could just use their byte value for faster building.

  • In your searchPassword() when you have the MD5 of the potential password, you always iterate over all crackable MD5 strings and you compare to all. This is a waste, you could sort the crackable MD5 values and use binary search to find if the potential is in it (sorting and binary search is implemented in the sort package). Or even better: you could build a map from the crackable MD5 strings, and just check if the candidate is in the map (now this check would be O(1) complexity instead of O(log n) of the binary search).

  • It is also an unnecessary round-trip to convert a calculated MD5 to string in order to check if it is a crackable one. Best would be to convert the crackable MD5 values to a byte array (note: array and not slice), and when you have the MD5 of a potential password as an array, you can check if it is a crackable one without converting it to string. Arrays are comparable in Go (unlike slices!), so you could also build a map from the MD5 arrays to check if a potential MD5 is in the map.

  • Also note that your algorithm generates passwords multiple times. For example if you want to check passwords with a length of 3, these 3-letter passwords are essentially all the 2-letter passwords +1. But you don't make use of this, you always generate all passwords with a given length from "scratch".

Utilizing these tips would speed up your algorithm big time; not just because we got rid of lots of needless computation / conversion, but also because much less "garbage" will be generated for the GC.


An alternative way of implementing this brute-force cracker would be to use the producer-consumer pattern. You could have a designated producer goroutine that would generate the possible passwords, and send them on a channel. You could have a fixed pool of consumer goroutines (e.g. 5 of them) which would loop over the channel on which generated passwords are delivered, and each would do the same: receive passwords, hash them (MD5) and check if it matches a crackable one.

The producer goroutine could simply close the channel when all combinations were generated, properly signalling producers that no more passwords will be coming. The for ... range construct on a channel handles the "close" event and terminates properly.

This would result in a clean design, would result in fixed number of goroutines, and it would always utilize 100% CPU. It also has the advantage that it can be "throttled" with the proper selection of the channel capacity (buffered channel) and the number of consumer goroutines.

Here is how this producer-consumer could look like in Go if someone wants to play with it (also note that I elaborated this with full examples and much deeper explanation in StackOverflow question Is this an idiomatic worker thread pool in Go?):

var wg sync.WaitGroup

func produce(ch chan<- []byte) {
    // Now generate all passwords:
    for {
        if noMore { // If no more passwords
        pass := ...   // Here generate next password
        ch <- pass    // send it for processing

func consume(ch <-chan []byte) {
    defer wg.Done()
    for pass := range ch {
        // Hash, check

func main() {
    ch := make(chan []byte, 100) // Buffered channel

    // Start consumers:
    for i := 0; i < 5; i++ { // 5 consumers
        go consume(ch)

    // Start producing: we can run this in the main goroutine

    wg.Wait() // Wait all consumers to finish processing passwords

This blog post is an excellent introduction to parallel computation in Go using goroutines and channels:

Go Concurrency Patterns: Pipelines and cancellation

Further optimization tip

Now if you go with this producer-consumer goroutine model, another optimization becomes available.

The md5.Sum() function (which takes a []byte and returns the MD5 checksum of its content) always creates a new, internal md5.digest value which is used to do the MD5 hashing. Then it is discarded.

Now if we have a small, fixed pool of consumer goroutines, we can now create and it is profitable to create a designated MD5 hasher for each with the md5.New() function. To what end? We can use the returned hasher (which is of type hash.Hash) to compute MD5 hashes, but what's cool is that we can reuse it to compute hashes of multiple byte slices.

hash.Hash implements io.Writer so we can write any []byte into it of which we want to compute the MD5 hash, and it also has a Hash.Sum() method which returns the MD5 hash, giving the option to not create a new array return value which will hold the calculated MD5, but we can pass our slice to it in which we want the result. We can also create prepared arrays ([16]byte) and slice them to obtain a slice []byte, and do this for all of the consumer goroutines. As a result, we can further suppress "memory-garbage" generation and reduce GC work. Once we queried the MD5 sum of a password, we can simply call Hash.Reset() to re-initiaze the hasher for the next password.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.