# 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 at 2:29
My best guess is that one is hoping that the plaintext is sparse. $\:$ –  Ricky Demer Apr 25 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.

-