24
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Apr 25 '13 at 2:29
  • 1
    $\begingroup$ My best guess is that one is hoping that the plaintext is sparse. $\:$ $\endgroup$ – user991 Apr 25 '13 at 5:38
23
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Gabe Hollombe Nov 10 '14 at 1:49
  • 4
    $\begingroup$ 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. $\endgroup$ – D.W. Nov 10 '14 at 4:41
2
$\begingroup$

I recently started the Matasano Crypto Challenges (aka Cryptopals), which proposes essentially the same principle in this exercise. Specifically, if you want to break a repeating-key xor cipher, try to find the value of n that minimizes the Hamming distance between any two n-length blocks of cipher text, and n will generally correspond to the size of the cipher key.

While this strategy worked in that particular case, it wasn't obvious to me why it should work. I've reasoned through it from first principles and come to a few conclusions. Note: I am by no means an expert in cryptography, and it's entirely possible that this argument is specious, or I'm using incorrect terminology.

At a high level... I believe this essentially works in this case because you are encoding an English cipher text using 8-bit bytes, and the entropy of the English language is much lower than the entropy of all possible combinations of 8 bits. i.e. English only has 26 letters, but there are 256 possible combinations of 8 bits. Entropy seems to be preserved via repeating-key xor, and so you are essentially looking for the block size that minimizes it.

This implies that if you found some way implement a repeating-key xor that transformed alphanumeric plain text into alphanumeric cipher text, this method wouldn't work.

More specifically... I reason that the Hamming distance is a metric that survives transformation of the underlying text by repeating-key xor, given that it is applied to blocks of text that match the length of the cipher key. This is fairly easy to show for small block and key sizes. For instance, assume the plain text is 001010, the key is 010, and the cipher is therefore 011000. The Hamming distance between the two halves of the plain text is 2, and the Hamming distance between the two halves of the cipher text is also 2. I'm fairly certain that this scales to any text and key length, again assuming that you are taking the distance between blocks of the same size as the key.

Now consider what I said above, that the entropy of the English language is fairly low compared to the entropy of the entire possible byte space. This implies that the Hamming distance between two blocks of English text will in general be less than the Hamming distance between two blocks of random bytes.

Combine these principles, and it becomes clear that at least in theory, if you pick the correct block size / key size, the Hamming distance will be minimized for the cipher text (because it was already minimized for the plain text and survives the xor transformation). If you don't pick the correct key size, then you are taking the Hamming distance of essentially random bytes, which will in general be much higher.

$\endgroup$
  • $\begingroup$ "I'm fairly certain that this scales to any text and key length, again assuming that you are taking the distance between blocks of the same size as the key." Well yes, this is because when you're guessing the correct size nof the key, XOR'ing chunks of size n of the ciphertext is the same as XOR'ing their corresponding plaintexts as the key cancels out when XOR'ed with itself. $\endgroup$ – balu Jul 17 '17 at 0:08
1
$\begingroup$

Following D.W.'s answer, here's an actual proof that $\text{wt}(X \oplus K \oplus Y \oplus K') \geqslant \text{wt}(X \oplus K)$.

We'll assume that the plaintext (resp. the key)'s characters have been generated with an alphabet $A$ (resp. $A'$) and a probability distribution over this alphabet $D_A$ (resp. $D_{A'}$).
(e.g. lower case letters and english letter distribution).

This allows us to write the expected normalized Hamming distance as:

$H_R = E[\text{wt}(X_1 \oplus X_2)]$ if the key length is correctly guessed.

$H_W = E[\text{wt}(X_1 \oplus X_2 \oplus X'_1 \oplus X'_2)]$ otherwise.

where $X_i$ (resp. $X'_i$) are independent random variables with distribution $D_A$ (resp. $D_{A'}$).

Now, let's zoom in on bits.

Fact 1:
The probability $p_k$ that the kth bit $b_{i,k}$ of random variable $X_i$ is set to 1 is the probability of drawing a character from $D_A$ whose kth bit is 1, so the sum of the probability of all such characters.
(e.g. letters [q-z] have the 5th bit set to 1, so $p_5$ is $10/26$ for a uniform distribution).

Fact 2:
The XOR of n bits will have value 1 if bit 1 appears an odd number of times, and value 0 otherwise.

From these 2 facts, we can compute the expected Hamming distance for the kth bit:

  • when we XOR $X_1$ and $X_2$:

$$h_{R,k} = h_{2,k} = E[\text{wt}(b_{1,k} \oplus b_{2,k})] = E[b_{1,k} \oplus b_{2,k}] = p(\text{1 bit set}) = 2p_k(1-p_k)$$

  • similarly, when we XOR $X'_1$ and $X'_2$:

$$h'_{2,k} = E[b'_{1,k} \oplus b'_{2,k}] = 2p'_k(1-p'_k)$$

  • when we XOR $X_1$, $X_2$, $X'_1$ and $X'_2$, noticing that to have an odd number of bits set to 1, you must have (an odd number of 1 in the first 2 bits AND an even number in the last 2 bits) OR (an even number in the first 2 bits AND an odd number in the last 2 bits):

$$h_{W,k} = E[b_{1,k} \oplus b_{2,k} \oplus b'_{1,k} \oplus b'_{2,k}] = h_{2,k}(1-h'_{2,k}) + h'_{2,k}(1-h_{2,k}) = h_{2,k} + h'_{2,k}(1-2h_{2,k})$$

If you plot $h_{2,k}$, you can see that it does not exceed 0.5, so $(1-2h_{2,k})$ is positive, and thus $h_{W,k} \geqslant h_{R,k}$.

Since the expected normalized Hamming distance $H_R$ (resp. $H_W$) is just the sum of the expected distances $h_{R,k}$ (resp. $h_{W,k}$) for each bit, we have proven why it is lower when the key length is guessed correctly =)


Note 1. You can now compute the expected Hamming distance, when key length is correctly guessed or not, for any ($A$, $D_A$) and ($A'$, $D_{A'}$).

For example:
- if plaintext and key are random lower case letters, $H_R \approx 2.47 bits$ and $H_W \approx 2.50 bits$.
- if we use english letter frequency instead, $H_R \approx 2.36 bits$ and $H_W \approx 2.49 bits$.
- if we add in spaces (that could be useful) with ~19% frequency, $H_R \approx 2.54 bits$ and $H_W \approx 2.88 bits$.

Note 2. $h_{W,k}$ cannot exceed 0.5 either, so if $h_{R,k}$ (i.e. $p_k$) is close to 0.5 for all bits, key length detection won't work well. And the good thing is that "$p_k$ is close to 0.5 for all bits" does NOT mean there is no statistical information in the text. For a given ($A$, $D_A$), one can maybe devise a set of distinct bytes for each charcater such that $p_k$ is close to 0.5 for every k, in order to make key length guessing more difficult =)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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