repeating-key xor and hamming distance

Question

I read that to break repeating-key xor you can do the following: try a keysize $n$ and compute the hamming distance between the first $n$ bits of the encrypted string and the bits $n+1$ to $2n$ of the encrypted string and normalize by keysize.

The true keysize probably minimizes this. Why?

It also suggests to average a couple of the near minimal values computed in this way. But why should keysizes that are not correct help compute the true keysize?

Answer 1

Yes, you are remembering correctly. Yes, this is a reasonable method to find the key length.

The reason why this works is because, typically, the plaintext is not uniformly random. For instance, rather than a random bit-string, the plaintext might be some English text, encoded in ASCII. If $X,Y$ represent two random English letters, encoded in ASCII, then the expected value of the Hamming distance $\text{wt}(X \oplus Y)$ is maybe 2-3 bits. In contrast, if $U,V$ are two random 8-bit bytes, then the expected value of the Hamming distance $\text{wt}(U \oplus V)$ is 4 bits, significantly larger. If you look at sequences of multiple characters, rather than a single letter at a time, the difference becomes even larger.

How does this apply to your situation?

• Well, if you have correctly guessed the key length, then your ciphertext consists of $X\oplus K$ and $Y\oplus K$ (as Dilip Sarwate explains), where $X,Y$ come from the plaintext distribution. Now notice that the Hamming distance between these two is the same as the Hamming distance between $X$ and $Y$, namely, it is $\text{wt}(X \oplus Y)$. As we explained before, you can expect this might be maybe 2-3 bits times the length of $X$ measured in bytes.

• In contrast, if you guessed the key length incorrectly, then you're looking at ciphertexts of the form $X \oplus K$ and $Y \oplus K'$. The Hamming distance between the two basically boils down to the Hamming distance between $U$ and $V$, where $U$ and $V$ are uniformly randomly distributed (since $K,K'$ are uniformly randomly distributed), and thus is $\text{wt}(U \oplus V)$. As explained before, you can expect this should be approximately 4 bits times the length of $X$ measured in bytes.

So, as you can see, the Hamming distance is significantly less when you've guessed the key length correctly.

For a vaguely similar method, read about the Index of coincidence; you can expect it to be more effective in some cases, and less effective in others.

Answer 2

Following D.W.'s answer, here's an actual proof that $\text{wt}(X \oplus K \oplus Y \oplus K') \geqslant \text{wt}(X \oplus Y)$.

We'll assume that the plaintext (resp. the key)'s characters have been generated with an alphabet $A$ (resp. $A'$) and a probability distribution over this alphabet $D_A$ (resp. $D_{A'}$).
(e.g. lower case letters and english letter distribution).

This allows us to write the expected normalized Hamming distance as:

$H_R = E[\text{wt}(X_1 \oplus X_2)]$ if the key length is correctly guessed.

$H_W = E[\text{wt}(X_1 \oplus X_2 \oplus X'_1 \oplus X'_2)]$ otherwise.

where $X_i$ (resp. $X'_i$) are independent random variables with distribution $D_A$ (resp. $D_{A'}$).

Now, let's zoom in on bits.

Fact 1:
The probability $p_k$ that the k^th bit $b_{i,k}$ of random variable $X_i$ is set to 1 is the probability of drawing a character from $D_A$ whose k^th bit is 1, so the sum of the probability of all such characters.
(e.g. letters [q-z] have the 5th bit set to 1, so $p_5$ is $10/26$ for a uniform distribution).

Fact 2:
The XOR of n bits will have value 1 if bit 1 appears an odd number of times, and value 0 otherwise.

From these 2 facts, we can compute the expected Hamming distance for the k^th bit:

• when we XOR $X_1$ and $X_2$:

$$h_{R,k} = h_{2,k} = E[\text{wt}(b_{1,k} \oplus b_{2,k})] = E[b_{1,k} \oplus b_{2,k}] = p(\text{1 bit set}) = 2p_k(1-p_k)$$

• similarly, when we XOR $X'_1$ and $X'_2$:

$$h'_{2,k} = E[b'_{1,k} \oplus b'_{2,k}] = 2p'_k(1-p'_k)$$

• when we XOR $X_1$, $X_2$, $X'_1$ and $X'_2$, noticing that to have an odd number of bits set to 1, you must have (an odd number of 1 in the first 2 bits AND an even number in the last 2 bits) OR (an even number in the first 2 bits AND an odd number in the last 2 bits):

$$h_{W,k} = E[b_{1,k} \oplus b_{2,k} \oplus b'_{1,k} \oplus b'_{2,k}] = h_{2,k}(1-h'_{2,k}) + h'_{2,k}(1-h_{2,k}) = h_{2,k} + h'_{2,k}(1-2h_{2,k})$$

If you plot $h_{2,k}$, you can see that it does not exceed 0.5, so $(1-2h_{2,k})$ is positive, and thus $h_{W,k} \geqslant h_{R,k}$.

Since the expected normalized Hamming distance $H_R$ (resp. $H_W$) is just the sum of the expected distances $h_{R,k}$ (resp. $h_{W,k}$) for each bit, we have proven why it is lower when the key length is guessed correctly =)

---

Note 1. You can now compute the expected Hamming distance, when key length is correctly guessed or not, for any ($A$, $D_A$) and ($A'$, $D_{A'}$).

For example:

• if plaintext and key are random lower case letters, $H_R \approx 2.47 bits$ and $H_W \approx 2.50 bits$.
• if we use english letter frequency instead, $H_R \approx 2.36 bits$ and $H_W \approx 2.49 bits$.
• if we add in spaces (that could be useful) with ~19% frequency, $H_R \approx 2.54 bits$ and $H_W \approx 2.88 bits$.

Note 2. $h_{W,k}$ cannot exceed 0.5 either, so if $h_{R,k}$ (i.e. $p_k$) is close to 0.5 for all bits, key length detection won't work well. And the good thing is that "$p_k$ is close to 0.5 for all bits" does NOT mean there is no statistical information in the text. For a given ($A$, $D_A$), one can maybe devise a set of distinct bytes for each charcater such that $p_k$ is close to 0.5 for every k, in order to make key length guessing more difficult =)

Answer 3

I recently started the Matasano Crypto Challenges (aka Cryptopals), which proposes essentially the same principle in this exercise. Specifically, if you want to break a repeating-key xor cipher, try to find the value of n that minimizes the Hamming distance between any two n-length blocks of cipher text, and n will generally correspond to the size of the cipher key.

While this strategy worked in that particular case, it wasn't obvious to me why it should work. I've reasoned through it from first principles and come to a few conclusions. Note: I am by no means an expert in cryptography, and it's entirely possible that this argument is specious, or I'm using incorrect terminology.

At a high level... I believe this essentially works in this case because you are encoding an English cipher text using 8-bit bytes, and the entropy of the English language is much lower than the entropy of all possible combinations of 8 bits. i.e. English only has 26 letters, but there are 256 possible combinations of 8 bits. Entropy seems to be preserved via repeating-key xor, and so you are essentially looking for the block size that minimizes it.

This implies that if you found some way implement a repeating-key xor that transformed alphanumeric plain text into alphanumeric cipher text, this method wouldn't work.

More specifically... I reason that the Hamming distance is a metric that survives transformation of the underlying text by repeating-key xor, given that it is applied to blocks of text that match the length of the cipher key. This is fairly easy to show for small block and key sizes. For instance, assume the plain text is 001010, the key is 010, and the cipher is therefore 011000. The Hamming distance between the two halves of the plain text is 2, and the Hamming distance between the two halves of the cipher text is also 2. I'm fairly certain that this scales to any text and key length, again assuming that you are taking the distance between blocks of the same size as the key.

Now consider what I said above, that the entropy of the English language is fairly low compared to the entropy of the entire possible byte space. This implies that the Hamming distance between two blocks of English text will in general be less than the Hamming distance between two blocks of random bytes.

Combine these principles, and it becomes clear that at least in theory, if you pick the correct block size / key size, the Hamming distance will be minimized for the cipher text (because it was already minimized for the plain text and survives the xor transformation). If you don't pick the correct key size, then you are taking the Hamming distance of essentially random bytes, which will in general be much higher.