# Hamming Distance vs. Index of Coincidence

When analyzing a repeating-key xor cipher to find the key length, I've read about two key methods (assuming there aren't just repeating chunks of ciphertext for Kasiski's method), for some assumed key length $l$, checking the Hamming distance of nearby chunks of ciphertext of length $l$, and checking the IoC for columns of text when the text is split into $l$ columns.

When are Hamming distances more effective, and when is the IoC more effective? Is there any way to know based on the ciphertext which technique will be more helpful, or is this a "try them both and now it's more an art than a science" sort of thing?

## 1 Answer

The Hamming distance is more effective when you suspect that the plaintext has been XORed with some repeating keystream. That's because XOR works at a bit level, as does the Hamming distance.

The Index of Coincidence is more effective when you suspect that the plaintext has been combined with some repeating keystream, where the combiner works character-by-character instead of bit-by-bit. For instance, the IoC will be more effective for a Vigenere cipher, or for a repeating-key polyalphabetic cipher. This is because those ciphers transform individual characters of the plaintext as a unit (not individual bits), and the IoC works at the character level.

If you like, you can think of the Hamming distance technique as effectively applying the Index of Coincidence at the bit level: the Hamming distance is effectively a variant of the IoC that works at the bit level, and that is especially effective when the combiner is the bitwise XOR operation. Therefore, if you know that the plaintext is combined with some repeating keystream using some bitwise operation (such as XOR), then you might use the Hamming distance (effective, applying the IoC at the bit level instead of the character level).

Of course, you can always apply both and see which works better on your particular cipher -- but the above discussion tells you which method you should expect will work better in any given circumstance, and why.

• Is length of CT another factor? Would Hamming distance perform better on shorter CTs, since you may not have enough columns to get a reliable IoC? – Brownbat Aug 29 '13 at 0:19
• I mean, given a single XOR, of course. Hamming's wouldn't work at all on a Vignere, because the CT would be all letters, the keys wouldn't affect the Hamming weights... – Brownbat Aug 29 '13 at 1:31