Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
My best guess is that one is hoping that the plaintext is sparse. $\:$ –  Ricky Demer Apr 25 '13 at 5:38

1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.