2
\$\begingroup\$

For a puzzle I had to brute force a password. I've never used goroutines before, and I don't have much experience in concurrency.

This is the cksum function, which takes an array of the ASCII code for each letter in a string (a is 97, b is 98...etc):

func cksum(bytes []int) int{
    a := 0
    b := 0
    for i := 0; i < len(bytes); i++ {
        a = (a + bytes[i]) % 255
        b = (b + a) % 255
    }
    return (b << 8) | a;
}

The password was a-zA-z of even length, and greater than a length of 10. The left and right halves had to output a certain value when run through cksum, and when put together, the even letters of the password had to output a certain value when run through cksum.

The left half would have to output: 53358

The right half would have to output: 61453

And together, the even letters would output: 0

I came up with the following code that assumed the password was 12 characters (it could be more characters).

  1. Launches a goroutine for each of the 52 possible letters.

  2. Each goroutine generates every single possible combination for a 6 letter string where the first letter is the one the goroutine was started with.

  3. If that six letter string matches the left hand side it is pushed into an array.

  4. If it matches the right hand side, a new goroutine is launched that concatenates that right hand match with every single match in the left hand side array and checks if the even checksum is 0.

package main

import "fmt"
import "bytes"

var leftAnswers = []string{}

func everyEven(bytes []int) []int {
    arr := []int{}
    for i := 0; i < len(bytes); i++ {
        if i % 2 == 0 {
            arr = append(arr, bytes[i])
        }
    }
    return arr
}

func toBytes(str string) []int{
    arr := []int{}
    for _,code := range str {
        arr = append(arr, int(code))
    }
    return arr
}

func cksum(bytes []int) int{
    a := 0
    b := 0
    for i := 0; i < len(bytes); i++ {
        a = (a + bytes[i]) % 255
        b = (b + a) % 255
    }
    return (b << 8) | a;
}

func brute(start int) {
    counter := 0
    alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    fmt.Println("Started", start)

    for a := start; a < len(alphabet); a++ {
        letter1 := string(alphabet[a]);
        for b := 0; b < len(alphabet); b++ {
            letter2 := string(alphabet[b]);
            for c := 0; c < len(alphabet); c++ {
                letter3 := string(alphabet[c]);
                for d := 0; d < len(alphabet); d++ {
                    letter4 := string(alphabet[d]);
                    for e := 0; e < len(alphabet); e++ {
                        letter5 := string(alphabet[e]);
                        for f := 0; f < len(alphabet); f++ {
                            letter6 := string(alphabet[f]);
                            counter += 1
                            var buffer bytes.Buffer
                            buffer.WriteString(letter1)
                            buffer.WriteString(letter2)
                            buffer.WriteString(letter3)
                            buffer.WriteString(letter4)
                            buffer.WriteString(letter5)
                            buffer.WriteString(letter6)
                            pw := buffer.String()
                            checksum := cksum(toBytes(pw))
                            go lhs(pw, checksum)
                            go rhs(pw, checksum)
                            if (counter % 1000000 == 0) {
                                fmt.Println(start, counter, " processed")
                            }
                        }
                    }
                }
            }
        }
    }
}

func lhs(pw string, checksum int) {
    if checksum == 53358 {
        leftAnswers = append(leftAnswers, pw)
    }
}

func rhs(pw string, checksum int) {
    if checksum == 61453 {
        go findPassword(pw)
    }
}

func findPassword(pw string) {
    for i := 0; i < len(leftAnswers); i++ {
        fullpw := leftAnswers[i] + pw
        bytes := toBytes(fullpw)
        evens := everyEven(bytes)
        if cksum(evens) == 0 {
            fmt.Println("THE PASSWORD IS:", fullpw)
        }
    }
}

func main() {
    for i := 0; i < 52; i++ {
        go brute(i)
    }
    select {}
}

It eventually did the job in ~15 minutes, but I don't know if I used concurrency correctly at all. I just spawned a goroutine as frequently as possible to be honest because I assumed more concurrency = faster code. Could someone help me out?

\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

This is not purely efficient:

for i := 0; i < 52; i++ {
    go brute(i)
}
counter := 0
alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
fmt.Println("Started", start)

for a := start; a < len(alphabet); a++ {
    // stuff

I don't know enough about the specifics of Go to talk about what I would call a static variable or in other languages, or constants... but it seems like counter should be static probably? Maybe not. I might be completely unnecessary. And alphabet should be both static and constant (many languages automatically treat constants as static).

Anyway, let's talk about efficiency. From my understanding of Go, your for loop in main is spawning 52 subroutines (that's what the go keyword does, right?). That's pretty smart, one subroutine for each letter, upper & lower case, of the alphabet, to break an alphabetic-only code.

Here's the problem. Your subroutines don't stop until they've reached the end of the alphabet, and you're not running this on a machine that can handle 52 different threads at once.

So, what that means, is that depending on your machine, by the time you get to "e" or "i" or "q" or some letter down the line, your machine has run out of the capability to simultaneously work on any more threads. You can create as many as you want, and your machine will do its best to make you think it's working on all of the threads at once, but it can only do so much.

This isn't to imply that you shouldn't make more threads than your computer can work on simultaneously. No, not at all.

But it's important that when we're spawning off so many threads, that we be certain that we're not duplicating work between the threads.

If the thread we started for "A" can't really get any work done because the thread we started for "a", "b", "c", "d" are still running, that's fine. But if the thread we started for "a", "b", "c", and "d" are all four going to check everything that the thread we started for "A" is going to check, then starting the thread for "A" is a waste of time.

So... let's fix that.

All we have to do is unwrap a layer of nested for loops.

counter := 0
alphabet := "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
fmt.Println("Started", start)

letter1 = alphabet[start]

for b := 0; b < len(alphabet); b++ {
    // stuff
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Disclaimer: I wrote this answer knowing absolutely nothing about Go. None of what I talked about has to deal with Go specifics really though, so the answer should be fine in terms of the general concept. \$\endgroup\$
    – nhgrif
    Jul 5, 2015 at 13:55
  • \$\begingroup\$ One question I have is that you say I should make counter and alphabet static. Originally I had that, but when I was reading a few articles about concurrency it said having variables that all the routines share isn't a good idea because the variables get locked and unlocked constantly. I thought that making the variables local to the routine would then be a better idea because there would be no locking down of variables. Is that flawed reasoning? \$\endgroup\$
    – m0meni
    Jul 5, 2015 at 14:06
  • 1
    \$\begingroup\$ Note my disclaimer, but given that alphabet is only being read from, what we should be doing is making it a constant. If it's a constant, it shouldn't be getting locked (but this would require comment from a Go expert) because it can't be modified. It's more important we make it constant than anything else. \$\endgroup\$
    – nhgrif
    Jul 5, 2015 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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