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

--

--

--

Security engineer at Uber. Musician, gamer, and juggler.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The Increasing Threat of Cyber Attacks, an Introduction

its a computer with a skull on it, dudes got a sick eyepatch too

Why Your Packages Are More Vulnerable Than Ever and What to Do About It

Evolving Data Security and Privacy Policies for GDPR Compliance

The best cryptographic protocol ever!

The Darknet (Deep Web) Explained

Why every organization needs to take identity management seriously.

Controlling Who Wo Gets To Use Your Email Address

Poltergeist Exchange x Satoshi Club AMA Recap from 7th of February

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
William Gallagher

William Gallagher

Security engineer at Uber. Musician, gamer, and juggler.

More from Medium

A First Look into Concurrency in Go

Golang Debugging with Delve — [Step by Step]

Limit Unbound Concurrency in Go (Part 3)

How To Begin With Golang | Part 1

Golang Tutorial