Single Byte XOR Decryption and Detection In Go

Intro

Continuing on my path through Cryptopals, I’m going to break down how I solved Set 1 Challenges 3 and 4.

In Challenge 3 we’re given a hex encoded string that’s been XOR encrypted with a single byte key. We need to figure out which byte and decrypt the string.

In Challenge 4 we’re given a file with a bunch of hex encoded strings. We need to find out which one has been encrypted using a single byte XOR.

Laying the Groundwork

Here we are given the following hex encoded string that we have to decrypt using a single byte key.

1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736

The first part of this problem is hex decoding the input string. We’ve done this before in previous entries, so I’m not going to go into detail on it, but in case you’re just joining us, here is the code I’ve written for hex decoding.

import "encoding/hex"
func decodeHexBytes(hexBytes []byte) ([]byte, error) { 
    ret := make([]byte, hex.DecodedLen(len(hexBytes))) 
    _, err := hex.Decode(ret, hexBytes) 
    return ret, err
}

When running our string through that code, we get the following byte array:

[27 55 55 51 49 54 63 120 21 27 127 43 120 52 49 51 61 120 57 120 40 55 45 54 60 120 55 62 120 58 57 59 55 54]

Now that we have our byte array, we can start to figure out how to decrypt it. If you’re not sure what XOR decrypting is, I go a bit more in depth on it here. For this article, we are going to focus more on finding our key.

Finding the Key to the Castle

To find the correct key, we’re going to have to find a way of scoring the output of a given key(byte). You can find resources online for the frequency in which characters appear in the english language, but I went the easy route and just stuck to the most common characters, and it worked for our purposes here.

func getCharWeight(char byte) int { 
    wm := map[byte]int{  
        byte('U'): 2,  
        byte('u'): 2,  
        byte('L'): 3,  
        byte('l'): 3,  
        byte('D'): 4,  
        byte('d'): 4,  
        byte('R'): 5,  
        byte('r'): 5,  
        byte('H'): 6,  
        byte('h'): 6,  
        byte('S'): 7,  
        byte('s'): 7,  
        byte(' '): 8,  
        byte('N'): 9,  
        byte('n'): 9,  
        byte('I'): 10,  
        byte('i'): 10,  
        byte('O'): 11,  
        byte('o'): 11,  
        byte('A'): 12,  
        byte('a'): 12,  
        byte('T'): 13,  
        byte('t'): 13,  
        byte('E'): 14,  
        byte('e'): 14, 
    } 
    return wm[char]
}

Eaten in a Single Byte

Now that we have a way to score our output, we just need to run our encrypted text against all our possible keys, and see which key gives us the best score. The steps we’re going to take are:

1. Loop through all possible bytes (0–255)
2. XOR the byte against each byte of our encrypted text
3. Give the string a score based on the above map
4. Return the string with the highest score

If we take a look at that in code, we get something like this:

func SingleXorCipher(codedMessage []byte) ([]byte, int, error) { 
    b, err := decodeHexBytes(codedMessage) 
    if err != nil {  
        return nil, 0,  err 
    } 
    var answer []byte
    var score int 
    for i := 0; i < 256; i++ {  
        r := make([]byte, len(b))  
        var s int  
        for j := 0; j < len(b); j++ {   
            c := b[j] ^ byte(i)   
            s += getCharWeight(c)   
            r[j] = c  
        }  
        if s > score {   
            answer = r   
            score = s  
        }   
        s = 0 
    } 
    return answer, score, nil
}

If we run our encrypted text through that function, we get:

Cooking MC's like a pound of bacon

with a score of 204.

We’re done, right?

That finishes up challenge 3, but challenge 4 is very closely related and will implement so much of the code above, that it makes sense to combine the two into one post.

In challenge 4, we are given a file with a bunch of hex encoded strings, and one of them has been encrypted using single byte XOR. We need to find which one.

We’re going to use the exact same logic we used above, but we’re going to run our code on each line of the input file and keep track of the best score. Then, whichever line gives us the best score is the XOR encrypted line. Easy as that. Our code is going to assume that we’re passing in the destination to a file that has our encoded strings.

package cryptopals 
import ( 
    "io/ioutil" 
    "strings"
)
func FindXorCipherString(dest string) ([]byte, error) { 
    f, err := ioutil.ReadFile(dest) 
    if err != nil {  
        return nil, err 
    }  
    lns := strings.Split(string(f), "\n")  
    var res []byte 
    var score int  
    for _, l := range lns {  
        st, sc, err := SingleXorCipher([]byte(l))  
        if err != nil {   
            return nil, err  
        }  
        if sc > score {   
            res = st   
            score = sc  
        } 
    } 
    return res, nil
}

If we input our file into the above code, our XOR encrypted string turns out to be:

Now that the party is jumping

Conclusion

Now we have a way of decrypting single byte XOR encryption, and a way of detecting it. As always you can check out my full solutions with tests and a nifty command line interface at github.com/juggler434/crypto