Matasano Crypto Challenges Set 1

Lets take a concrete example from the Vigenere cipher. Let our plain text be:

Speak softly and carry a big stick; you will go far.

Which after removing spaces and punctuation and up-casing is:

SPEAKSOFTLYANDCARRYABIGSTICKYOUWILLGOFAR

Let our key be \(k\) = "SECRET", then our cipher text is:

KTGROLGJVCCTFHERVKQEDZKLLMEBCHMAKCPZGJCI

Now we put ourselves in the shoes of the cryptanalyst. Lets say he knows the length of the key, but not the word. If we break up the cipher text in columns with rows the same length of the key (6 in this example) we get:

SECRET
------
KTGROL
GJVCCT
FHERVK
QEDZKL
LMEBCH
MAKCPZ
GJCI

Now notice that All the letters that line up in the first column correspond to a Caesar cipher with key "S":

K G F Q L M G

Everything in the second column is a Caesar cipher with key "E":

T J H E M A J

And so on. Once we solve the Caesar cipher for each column (choosing the key that gives a frequency distribution that looks most like English), we have the set of Caesar keys that give the total Vigenere key \(k\) = "SECRET".

Now that we know how to figure out the key given its length, we have to figure out its length. As usual, there are a number of different approaches, but the one suggested by the challenge works well.

It requires that we calculate the Hamming distance between two strings. The first reason this works so well, is that in a binary alphabet we have just two letters (0 and 1). The Hamming distance measures the numbers of substitutions to transform one sequence to another. If you play with a few binary sequences you will find that the bits which must change in string \(A\) and string \(B\) is: \(C = A \oplus B\). To compute the Hamming distance we just sum the number of 1's in the resulting binary string \(C\).

The second reason that this works is the property that if \(A \equiv B\), then \(A \oplus B = 0\). Now if we look at the repeating key XOR cipher again, we have (using binary XOR instead of adding mod 26):

    535045414b534f46544c59414e44434152525941424947535449434b594f5557494c4c474f464152
(+) 53454352455453454352455453454352455453454352455453454352455453454352455453454352
    --------------------------------------------------------------------------------
    001506130e071c03171e1c151d01001317060a04011b0207070c00191c1b06120a1e09131c030200

If we guess the key length to be three (\(L=3\)), then we would find the hamming distance between:

\begin{equation} H('\text{001506}','\text{130e07}')=8 \end{equation}

Symbolically we would have (\(C[x:y]\) denotes the substring starting at \(x\) and ending at \(y\)):

\begin{align} H(C[0:3] &,C[3:6]) =8 \\ H(P[0:3]\oplus K[0:3] &,P[3:6] \oplus K[3:6]) =8 \end{align}

If we let our plaintext for the first 6 letters be the same for the moment (say "AAAAAA"), then it becomes clear that we are finding the hamming distance between the first three letters of the key, and the second three letters of the key:

\begin{equation} H(K[0:3],K[3:6])=5 \end{equation}

But, \(L=3\) was just a guess, we have to try different key lengths. Something special happens when we guess \(L=6\) in our example (remember K="SECRETSECRETSECRET…"):

\begin{equation} H(K[0:6],K[6:12])=0 \end{equation}

but we don't have the key yet, all we have is the cipher text:

\begin{equation} H(C[0:6],C[6:12])=15 \end{equation}

Notice however, that this is just the hamming distance between the first 12 characters of our plaintext:

\begin{equation} H(P[0:6],P[6:12])=15 \end{equation}

It should hopefully be clear that when we find the hamming distance between parts of our cipher text using the correct key length, we are only finding the hamming distance between parts of the plain text. If we guess the wrong key length, the cancellation doesn't occur and it will result in a larger hamming distance. This leads to the procedure: guess multiple key lengths and choose the key length with the smallest hamming distance.