Challenges 2-6: Caesar and Vigenère Ciphers

The next few challenges cover implementing and then breaking the Caesar and Vigenère ciphers. These ciphers usually serve as the introduction to most cryptography books, as a history lesson of what we used to use and how easy they are to break. However, with cryptopals, we take this academic knowledge and turn it into practice.

Challenge 2: Fixed XOR

The next few challenges are based on XOR functionality, with challenge 2 simply requiring the XORing of two values of equal length.

XOR (eXclusive OR) involves flipping bits based on the following pattern:

Basically, it will only return true if either bit is true, but not both.

We can XOR two bytes using the ^ operator, something I’ve surprisingly never had to use in anger before this challenge. The following code to solve this challenge assumes byte arrays of equal length.

public static class Xor
{
    public static byte[] ByteArrays(byte[] x, byte[] y)
    {
        var xorData = new byte[x.Length];
    
        for (var i = 0; i < x.Length; i++)
            xorData[i] = (byte) (x[i] ^ y[i]);
        
        return xorData;
    }
}

Challenge 3: Single-byte XOR cipher

For challenge 3, we’re given a value that has been XOR’d using a single byte, with our objective being to find the key that was used. So, let’s try brute forcing it using the byte value of every single ASCII character (0 – 127).

I like to think of this as the XOR version of the Caesar cipher, where the plaintext has been encrypted by performing the same operation on each value. Traditionally this would shift the values using a key of 3. So, let’s say the key is 3 and the plaintext is C, this would mean the ciphertext would be F:

In order to use our existing XOR functionality, I expanded the single-byte key so that it is at least the same length as the ciphertext.

public static string ExpandKey(string hex, string key) {
    var expandedKey = string.Empty;

    while (expandedKey.Length < hex.Length) {
        expandedKey += key;
    }

    return expandedKey;
}

We can then try each byte as the key using methods from the previous two challenges, returning a dictionary of each key and the result:

public static Dictionary<string, string> BruteForceSingleByte(string cipherText) {
    var outputs = new Dictionary<string, string>();
    foreach (var key in Enumerable.Range(0, 127))
    {
        var keyAsHex = Convert.ToString(key, 16);
        var expandedKey = ExpandKey(cipherText, keyAsHex);

        var outputHex = Xor.HexStrings(cipherText, expandedKey);
        var outputBytes = Hex.StringToBytes(outputHex);
        outputs.Add(keyAsHex, Encoding.ASCII.GetString(outputBytes));
    }

    return outputs;
}

The next part of the challenge is to programmatically figure out which key was the correct one. It’s hinted that we can score English text with the phrase “ETAOIN SHRDLU” being quoted.

My initial approach was to take each character and score it against its frequency in English text. This worked for the most part, however, if a value contained a lot of the character “e”, the most common letter in English text, it would get scored as the most likely. Even though the rest of the text was gibberish.

I managed to stumble upon a Crypto.StackExchange post discussing this very challenge. After reviewing the solutions, my preferred solution involved the use of the “Bhattacharyya coefficient” which is defined as:

“The Bhattacharyya coefficient is an approximate measurement of the amount of overlap between two statistical samples. The coefficient can be used to determine the relative closeness of the two samples being considered.”

My implementation of this looked like so:

public static double EnglishRating(string text) {
    var chars = text.ToUpper().GroupBy(c => c).Select(g => new {g.Key, Count = g.Count()});

    double coefficient = 0;

    foreach (var c in chars)
    {
        if (LetterScore.TryGetValue(c.Key, out var freq))
        {
            coefficient += Math.Sqrt(freq * c.Count / text.Length);
        }
    }

    return coefficient;
}

// http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html (including space character)
private static readonly Dictionary<char, double> LetterScore = new Dictionary<char, double>
{
    {'E', 12.02}, {'T', 9.10}, {'A', 8.12}, {'O', 7.68}, {'I', 7.31}, {'N', 6.95},
    {'S', 6.28}, {'R', 6.02}, {'H', 5.92}, {'D', 4.32}, {'L', 3.98}, {'U', 2.88},
    {'C', 2.71}, {'M', 2.61}, {'F', 2.30}, {'Y', 2.11}, {'W', 2.09}, {'G', 2.03},
    {'P', 1.82}, {'B', 1.49}, {'V', 1.11}, {'K', 0.69}, {'X', 0.17}, {'Q', 0.11},
    {'J', 0.10}, {'Z', 0.07}, {' ', 0.19}
};

I found adding a letter score for a space character helped prevent values such as "tHIS\0IS\aS\0CORRECT" scoring higher than "This is correct".

Challenge 4: Detect single-character XOR

Challenge 4 involves loading in a file and trying each value for a single byte key. We’re brute forcing each line of the file.

I’m not going to dig into this one, as it’s mostly a repeat of challenge 3. It should give your English scoring code a run for its money though.

Challenge 5: Implement repeating-key XOR

Again, a relatively challenge assuming you’ve completed the previous ones. This time we have a key that is larger than a single byte. This is where my approach to expand the key first became a happy little accident.

Similar to how the single byte Xor was our version of the Caesar cipher, this is our version of the Vigenère cipher. This is an improvement over the Caesar cipher, where we have a key and use each character in turn to shift the plaintext. The key is simply repeated until we’ve shifted the all of the plaintext. In effect, it is a repeated Caesar cipher.

To implement this, we can just expand the key to the same size as our plaintext and then run both the plaintext and the expanded key through our Xor functionality.

Challenge 6: Break repeating-key XOR

Now it’s time to break a Vigenère cipher. This is done using a combination of first figuring out the key length, and then some frequency analysis.

Luckily, the cryptopals instructions give us some decent step-by-step instructions for both reliably finding the key length and then using our existing code to brute force the key. But first, we need to implement some new functionality: Hamming distance.

Hamming Distance

The challenge gives us two example strings of “this is a test” and “wokka wokka!!!”, stating that the hamming distance is 37. I found that most implementations get this wrong, but the challenge insists that this is the correct distance. From what I can tell, this was because some solutions only look at character differences, as opposed to the differences in bits.

public static int GetHammingDistance(this byte[] x, byte[] y) {
    if (x.Length != y.Length) throw new ArgumentException("values must be same length");

    var distance = 0;

    for (var i = 0; i < x.Length; i++)
    {
        var value = (int)Xor.Bytes(x[i], y[i]);

        while (value != 0)
        {
            distance++;
            value &= value - 1;
        }
    }

    return distance;
}

Finding the Key Size

To find our key size, we’re going to guess some key lengths (2 to 40), take chunks of the ciphertext equal to that length, and calculate the normalized hamming distance between each pair. The lowest value should be our key length.

var encodedCipherText = File.ReadAllLines("TestData/Set1/6.txt")
    .Aggregate(string.Empty, (s, s1) => s + s1);

byte[] cipherText = Base64.DecodeBytes(encodedCipherText);

var keySizeResults = new Dictionary<int, int>();

// 1. "Let KEYSIZE be the guessed length of the key; try values from 2 to (say) 40."
for (var keySize = 2; keySize <= 40; keySize++)
{
    // 2. For hamming distance tests see Funcationlity\StringExtensionTests.cs
    // 3. "For each KEYSIZE, take the first KEYSIZE worth of bytes, 
    // and the second KEYSIZE worth of bytes, and find the edit distance between them.
    // Normalize this result by dividing by KEYSIZE."

    var hammingDistance = 0;
    var numberOfHams = 0;

    for (int i = 1; i < cipherText.Length / keySize; i++)
    {
        var firstKeySizeBytes = cipherText.Skip(keySize * (i - 1)).Take(keySize);
        var secondKeySizeBytes = cipherText.Skip(keySize * i).Take(keySize);

        hammingDistance += firstKeySizeBytes.GetHammingDistance(secondKeySizeBytes);
        numberOfHams++;
    }

    var normalizedDistance = hammingDistance / numberOfHams / keySize;
    keySizeResults.Add(keySize, normalizedDistance);
}

// 4. "The KEYSIZE with the smallest normalized edit distance is probably the key.
// You could proceed perhaps with the smallest 2-3 KEYSIZE values.
// Or take 4 KEYSIZE blocks instead of 2 and average the distances."
var orderedResults = keySizeResults.OrderBy(x => x.Value);
var bestKeySize = orderedResults.First().Key;

The challenge stated that we can either get the hamming distance of the first two chunks of bytes or take multiple and take the average. I found that getting the average gave me the correct answer with my implementation. It also allowed me to use the variable name numberOfHams.

Brute Forcing the Key

Now that we now the key length, we can creak each byte of the key in turn, using code we already have from previous challenges.

Since we know the key length, we know what bytes of our ciphertext were encrypted by the first byte of the key, the second, etc. So, if we take all of the ciphertext bytes that were encrypted using each part of the key, we can brute force them in turn, as if they were a single-byte key. We’ve effectively broken down our Vigenère cipher, into multiple Caesar ciphers.

First, we need to chunk our ciphertext and then transpose it. I used the following two helper methods:

public static T[][] CreateMatrix<T>(this IEnumerable<T> source, int size)
{
    var taken = 0;
    var output = new List<T[]>();
    var enumeratedSource = source.ToArray();

    while (taken < enumeratedSource.Length)
    {
        output.Add(enumeratedSource.Skip(taken).Take(size).ToArray());
        taken += size;
    }

    return output.ToArray();
}

public static T[][] Transpose<T>(this T[][] source)
{
    var transposedBlocks = new List<List<T>>();

    for (var i = 0; i <= source.Length; i++)
    {
        foreach (var block in source.ToList())
        {
            if (i < block.Length)
            {
                if (transposedBlocks.ElementAtOrDefault(i) == null)
                    transposedBlocks.Add(new List<T>());

                transposedBlocks[i].Add(block[i]);
            }
        }
    }

    return transposedBlocks.Select(x => x.ToArray()).ToArray();
}

I had some real issues with this one. Not only am I not used to dealing with 2-dimensional arrays, but existing solutions out there seemed to completely throw me off (due to lots of index out of range issues).

The way I could implement this that my brain could cope with involved using jagged arrays (array of arrays) over multi-dimensional arrays, and some defensive programming using lists and LINQ. It’s not pretty, but I found it more readable than the alternative. Plus, jagged arrays are apparently “more C#”.

So, let’s brute force each byte, find our key, and complete this challenge:

// 5. "Now that you probably know the KEYSIZE: break the ciphertext into blocks of KEYSIZE length."
var blocksOfKeySize = cipherText.CreateMatrix(bestKeySize);

// 6. "Now transpose the blocks: make a block that is the first byte of every block,
// and a block that is the second byte of every block, and so on."
var transposedBlocks = blocksOfKeySize.Transpose();

// 7. "Solve each block as if it was single-character XOR. You already have code to do this."
var bruteForceResults = transposedBlocks
    .Select(x => Xor.BruteForceSingleByte(Hex.BytesToString(x)))
    .ToList();

// 8. "For each block, the single-byte XOR key that produces the best looking histogram is the repeating-key
// XOR key byte for that block. Put them together and you have the key."
var fullKey = string.Empty;
    
foreach (var result in bruteForceResults)
{
    string key = null;
    double currentHighestScore = 0;

    foreach (var attempt in result)
    {
        var rating = LetterAnalyzer.EnglishRating(attempt.Value);
        if (currentHighestScore < rating)
        {
            key = attempt.Key;
            currentHighestScore = rating;
        }
    }

    fullKey += key;
}

// Use key!
var expandedKey = Xor.ExpandKey(Hex.BytesToString(cipherText), fullKey);
var plainTextAsBytes = Xor.ByteArrays(cipherText, Hex.StringToBytes(expandedKey));
var plaintext = Encoding.UTF8.GetString(plainTextAsBytes);