# Finding a keylength in a repeating key XOR cipher

In an old cryptography FAQ, I found the following step described for determining a the length of the key a cipher was repeatedly XORed against:

1. Discover the length of the key by counting coincidences. (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of the ciphertext against itself, count those bytes which are equal. If the two ciphertext portions have used the same key, something over 6% of the bytes will be equal. If they have used different keys, then less than 0.4% will be equal (assuming random 8-bit bytes of key covering normal ASCII text). The smallest displacement which indicates an equal key is the length of the repeated key.

The wording of the bolded text is the part I'm confused with. Given that my plaintext equals the string "This is a secret message", would I be comparing the first n number of bytes with a second set of n number of bytes that is offset from the first (e.g. the xor'd version of "Th" with "is", if I was comparing 2-byte chunks of the cipher against itself)?

If not, what's the correct way to interpret this passage? Thank you.

-
of related interest: reverseengineering.stackexchange.com/a/2063/1854 – mikeazo Jun 25 '13 at 0:35
This attack only works if your ciphertext is relatively long compared to the key length, and if the plaintext is some human-language text (with words occuring multiple times). – Paŭlo Ebermann Jun 25 '13 at 15:19
@Paŭlo: Actually, you don't need human-language text; the attack works as long as the plaintext character distribution is sufficiently uneven (and the message sufficiently long) that you can statistically distinguish different key characters by their corresponding ciphertext character distributions. – Ilmari Karonen Jun 25 '13 at 19:17

This looks like a sliding window approach to calculating the index of coincidence. So you would have something like:

ABCDE FGHIJ KLMNO
OACBD EFGHI JKLMN


Given enough cyphertext, you'll discover a length at which the IC is high; this is a candidate keylength for the cyphertext, because you've shifted the two texts by one keylength. Multiples of this size will also return high ICs.

Another way to brute force the key length of a Vigenère cypher by iterating through keysizes of different lengths, computing the Hamming distance of adjacent cyphertext blocks of that length, normalizing the distance to the keylength, and taking the smallest value as your keylength. In this case, given cyphertext:

CYPHERCYPHERCYPHERCYPHER


for a guess of keysize 4 you'd split the text into

CYPH
ERCY
PHER
CYPH
ERCY
PHER


and get the Hamming distances that way. You'd keep going for a few more keysizes and should eventually 'settle' on 6 (in this highly contrived example, at least).

-
Thanks for the explanation. Your last paragraph nails what I'm trying to figure out with this post: to break this type of cipher, I'd need to compare (via hamming distance) adjacent N-length blocks of the ciphertext? So the hypothetical example in my post shows the right idea with how to compare the cipher against itself, and I've understood what the passage meant to convey? – hlh Jun 25 '13 at 13:05
well, you wouldn't be comparing plaintext blocks, but the cyphertext ones; also, as far as the particular chunk of text you posted, my note on the index of coincidence, and @D.W.'s answer, are the appropriate interpretations. I've provided a different way of breaking the cypher for educational purposes =) – xorbyte Jun 25 '13 at 18:51
I corrected that! I upvoted both D.W.'s answer and your answer because they explained the text I was looking at, but I'm marking yours as 'correct' because your bit about comparing adjacent blocks of the cyphertext is what helped me solve the problem I was working on. Thanks to all! – hlh Jun 26 '13 at 13:26

You'd be trying each possible displacement (offset).

Suppose the ciphertext is CXEKCWCOZKUCAYZEKW. Here's displacement 1:

CXEKCWCOZKUCAYZEKW
CXEKCWCOZKUCAYZEKW


At displacement 1, there are no matches (nothing where the a letter in the top line is equal to the letter immediately below it).

Here's displacement 2:

CXEKCWCOZKUCAYZEKW
CXEKCWCOZKUCAYZEKW
^


You can see that, at displacement 2, there is one match.

Here's displacement 3:

CXEKCWCOZKUCAYZEKW
CXEKCWCOZKUCAYZEKW


At displacement 3, there are no matches.

In this way, you can count the number of matches at each displacement.

The idea is that, if you line up the ciphertext with itself displaced by $k$, where $k$ is the period of the keystream (i.e., the length of the key), then you get a match in the ciphertext (offset by $k$ places) if and only if there is a match in the plaintext (offset by $k$ places). Now it's a property of English language that the frequency distribution of English letters is not uniform: some are more likely than others. If you pick two positions at random from an English text, there's about a 6% chance (say) that those two positions have the same letter. Consequently, when you've guessed $k$ correctly, there's about a 6% chance that any particular ciphertext letter matches the one $k$ positions later.

In contrast, when you line up the ciphertext with itself displaced by something displacement that does not match the key length, the chances of a match at any particular position are much smaller (1/256, if ciphertexts are bytes; 1/26, if ciphertexts are letters).

-