Single-byte XOR cipher
Tags: 100daystooffload, cryptopals, challenge
Published: 2024-04-30 21:20:34

This is the third crypto challenge in set 1 from [cryptopals](cryptopals.com), which is the qualifying set. 

The difficulty level is relatively easy, to solve this problem I have used the programming language Go.

# Problem description

The input is a hex encoded string:

`1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736`

which has been XOR'd against a single character. Find the key, and decrypt the message.

Devise some method for "scoring" a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.

# Solution

We start with defining the character frequency metric by looking at this page on [Wikipedia](https://en.wikipedia.org/wiki/Letter_frequency), and create a lookup table for the letter frequency.

```golang
var letterFrequencies = map[string]float64{
	"A": 8.167,
	"B": 1.492,
	"C": 2.782,
	"D": 4.253,
	"E": 12.702,
	"F": 2.228,
	"G": 2.015,
	"H": 6.094,
	"I": 6.966,
	"J": 0.153,
	"K": 0.772,
	"L": 4.025,
	"M": 2.406,
	"N": 6.749,
	"O": 7.507,
	"P": 1.929,
	"Q": 0.095,
	"R": 5.987,
	"S": 6.327,
	"T": 9.056,
	"U": 2.758,
	"V": 0.978,
	"W": 2.360,
	"X": 0.150,
	"Y": 1.974,
	"Z": 0.074,
}
```

Now we will create a naive implementation to score how "english" the plain text is by using the map above. This could be done by looping through each character and sum up the relative frequency value. If a character is not in the map we will give it a negative score unless it is a space character. Something like this.

```golang
var text = regexp.MustCompile("^[a-zA-Z ]$")

func isAlphabetic(str string) bool {
	return text.MatchString(str)
}

func calculateScore(buffer []byte) float64 {
	score := 0.0
	for _, b := range buffer {
		str := string(b)
		if isAlphabetic(str) {
			score += letterFrequencies[strings.ToUpper(str)]
		} else {
			score -= 10.0
		}
	}

	return score
}
```

With that in place we can start to focus on the decryption function. It should take the cipher text (the hex encoded string) and a key (a single character/byte) and return the plain text (the decrypted message).

```golang
func singleByteXOR(buffer []byte, key byte) []byte {
	result := make([]byte, len(buffer))
	for i := range len(buffer) {
		result[i] = buffer[i] ^ key
	}

	return result
}
```

The final step is to use brute force and try all keys to decrypt the message.

```golang
func DecryptTheMessage(hexString string) ([]byte, error) {
	cipher, err := hex.DecodeString(hexString)
	if err != nil {
		return nil, err
	}

	bestKey := byte(0)
	bestScore := 0.0
	for k := range 256 {
		key := byte(k)
		decrypted := singleByteXOR(cipher, key)

		score := calculateScore(decrypted)

		if score > bestScore {
			bestScore = score
			bestKey = key
		}
	}

	decryptedMessage := singleByteXOR(cipher, bestKey)
	return decryptedMessage, nil
}
```

Here we keep track of the best score and its key so we can return the best candidate as the decrypted message.

By creating a unit test we will be able to verify that the, `DecryptTheMessage`, function work as expected.

```golang
func TestDecryptTheMessage(t *testing.T) {
	hexString := "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"

	result, err := basics.DecryptTheMessage(hexString)
	if err != nil {
		t.Errorf("Unexpected error: %v", err)
	}

	expected := []byte("Cooking MC's like a pound of bacon")
	if !bytes.Equal(result, expected) {
		t.Errorf("Expected message: %s, but got: %s", expected, result)
	}
}
```

There is the complete code needed to solve this challenge.

# Conclusion

This challenge required more code than the previous challenges. The tricky part was to create a good scoring algorithm and the key part of that was to give a negative score for non alpha characters in the decrypted text.
 
# References

* [Set 1 - Challenge 3](https://cryptopals.com/sets/1/challenges/3)
* [Wikipedia - Letter frequency](https://en.wikipedia.org/wiki/Letter_frequency)