17
\$\begingroup\$

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 (
"fmt"
"io/ioutil"
"strings"
"sync"
"log"
"time"
"crypto/md5"
)

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{
                    return
                }
            }
        }
    }else {
        for i := range alfabeto{
            wgFather.Add(1)
            go compute(prefix+1, n, fmt.Sprintf("%s%c", a, alfabeto[i]), wgFather)
        }
    }
}

var passwords []string


func main(){

    if loadPasswords() {
        return
    }
    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
            wg.Add(1)
            go compute(0, cont, "", &wg)
            wg.Wait()
            cont++    
        }

    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{
        log.Fatal(err)
        return true
    }
    readstring := string(stream)

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

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

56cc213a6303180cbab6a3da15108751
b1c9b44a9a0a65615f21834aee53594b
4b855fcca0a7140f60dd8259d1a0f1ad
14db43821fb74030ac6e8bdf662646d5
93eea5a9dfb14219e8e9d51ab1ae2b82
b0804ec967f48520697662a204f5fe72
ab6d50d5a9ecafd6fd429d38877837ca
168908dd3227b8358eababa07fcaf091
3cf4046014cbdfaa7ea8e6904ab04608
02c77002a0c646684b3325959fe147b2
f38fef4c0e4988792723c29a0bd3ca98
f3abb86bd34cf4d52698f14c0da1dc60
e842795b282293fd61bc294c49edb12b
c4fdb9019bcca7e82296952ba3e1895b
8dc01b0de0431cb7eced92277c1f04c7
bbebde933d57f88406bc530e5df0df3a
44fd79ea712293e5b5a7b51aceb6c0a7
56eb473ffd7429b00eb136c80664be30
875a8ec1acd2fa9f02ca152974dfd904
23ba6002aa3583a61db26e957b1fbe43
dcaa9fd4f23aaf0c29f540becf35b46f
98f740d68822f4209674ca9f23c20abe
a079350a0e30d9f293f6acaea80bb015
c44ab68f3a5ef32c8dfbbaa1daa86f98
6057b96acf9d41c1ca26a8923d970404
daa10b9d19015cf1cbf4bb53cf135b61
b29533fb6f81a9dbf8eae44b05ce8f49
22b35da29d5fa740fab4cb83ccb820aa
11cff46e84b6cae9951ea65eb5716d9e
9dd8ecec47e0c96bb189038fdb35bf16
e03a5f28b2349d6735adf6f528a7f18c
6057b96acf9d41c1ca26a8923d970404
\$\endgroup\$
  • 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
8
\$\begingroup\$

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 {
    wgFather.Add(1)
    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.

Alternative

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
            close(ch)
            break
        }
        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
        wg.Add(1)
        go consume(ch)
    }

    // Start producing: we can run this in the main goroutine
    produce(ch)

    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.

\$\endgroup\$

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.