3
$\begingroup$

While solving a (easy...) Project Euler cipher problem this week I repeatedly saw instructions for breaking ciphers after identifying the keylength as:

'shift the ciphertext by that key length and XOR it with itself. This removes the key and leaves you with plaintext XORed with the plaintext shifted the length of the key'

So I can understand how this drops the key out the equation, but I don't see how plaintext XORd with plaintext shifted by keylength is any more tractable. In the many references I saw about this, no one followed up with how to solve the plaintext^shiftedPlaintext piece. It doesn't seem that different than plaintext^keyPhrase really.

What am I missing about why this makes the problem easier to solve? What approaches deal with this part of the problem?

$\endgroup$

1 Answer 1

6
$\begingroup$

Well, if we have plaintext^shiftedPlaintext, what we have is the values $P_i \oplus P_{i+k}$, where $k$ is the length of the shift.

What does this imply? Well, if we consider the values $P_i \oplus P_{i+k}$, $P_{i+k} \oplus P_{i+2k}$, $P_{i+2k} \oplus P_{i+3k}$, ... we get a chain where, if we guess one of the values $P_{i+nk}$ for some $n$, we can immediately reconstruct all other plaintext bytes in the chain; thus giving us the correct value for every $k$th plaintext byte.

That can be exploited in several ways. One approach is crib dragging; we guess that a common word (the canonical crib for English is "the") occurs at a specific location, and see what that implies for other places in the plaintext; if it makes sense, then it is likely correct (and we have a large amount of plaintext; that gives useful context for other cribs); if it doesn't make sense, we try our crib elsewhere.

In addition, if the plaintext includes spaces, then a useful fact of ASCII can be useful; alphabetical letters have bit 6 set, spaces have bit 6 clear (and while numbers and punctuation also have bit 6 clear, those are comparatively rare). So, if we see that the value of $P_i \oplus P_{i+k}$ has bit 6 set, then a good guess is that either $P_i$ or $P_{i+k}$ is a space; that acts as a 1 character crib.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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