This is the third crypto challenge in set 1 from cryptopals, 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, and create a lookup table for the letter frequency.

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.

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).

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.

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.

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.

Blog

Single-byte XOR cipher

Stefan Alfbo

Problem description

Solution

Conclusion

References

Join Our Newsletter. No Spam, Only the good stuff.

Related