# repeating-key xor and hamming distance

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?

-
Could you cite where you read this claim? If the key $K$ is indeed of length $n$ bits and $X$ and $Y$ respectively bits $1$ through $n$ and bits $n+1$ through $2n$ of the plaintext, then the encrypted strings available to you are $X\oplus K$ and $Y\oplus K$, and the Hamming distance between them is the same as the Hamming distance between $X$ and $Y$. I don't see offhand why $X$ and $Y$ should be differing in only a few positions. – Dilip Sarwate Apr 25 '13 at 2:29
My best guess is that one is hoping that the plaintext is sparse. $\:$ – Ricky Demer Apr 25 '13 at 5:38

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.

-
All of this makes sense to me (thanks, @D.W.), but I'm stuck on one issue: If the plaintext consists of only ASCII letters, and the key consists of only ASCII letters, then will comparing the bitwise Hamming distance of ciphertext bites still help? All ASCII letters share the same last two bits (01), so I don't understand how we'll end up with an average bitwise Hamming distance of 4 when doing these comparisons. I'm sure I'm missing something, I just don't know what it is. Can you point me in the right direction? – Gabe Hollombe Nov 10 '14 at 1:49
Hi @GabeHollombe, for new questions, I recommend you post a new question. But the short answer is: yes. If you guessed the key length correctly, you're looking at $\text{wt}(X \oplus K \oplus Y \oplus K) = \text{wt}(X \oplus Y)$, which is 2-3 bits. If you guessed it incorrectly, you're looking at $\text{wt}(X \oplus K \oplus Y \oplus K')$, which is about 3 bits (here all of $X,Y,K,K'$ are independently distributed English ASCII letters). ASCII lowercase letters are 0x61 to 0x7A, so the xor of four of those is close to uniform on its low 6 bits, and thus has 3 bits set on average. – D.W. Nov 10 '14 at 4:41