More fun with XOR

In order to discuss how the 'Spruchnummer' mistake lead the the Lorenz being broken, and why we must never reuse a one time pad key, we must first understand a little more about the nature of the XOR operation. XOR is essentially a 'bitwise' operation, i.e. it operates on signal bits at a time. I've already discussed some of these ideas in the 'One Time Pad' article, this article presents things in a slightly different way, and takes things a little further.

Suppose we had two bits, A and B which are XORed. The bits can only have one of two values, 0 or 1. XOR simply says 'If the bits are the same, the result is zero, if different the result is 1'. Throughout this entry I'll use ⊕ as the symbol for 'XOR'.

Thus, XOR is also 'commutative' (the order it's done in doesn't matter) as 0⊕1 gives the same result as 1⊕0.

Also, if we XOR anything with 0, the result is the same as whatever we put in (1⊕0=1 and 0⊕0=0).

Now, imagine that we have a set of plaintext bits, P, that we wish to combine with a set of key bits, K.

The result is ciphertext, C, where C=P⊕K.

To get to P, we just do C⊕K, i.e. XOR undoes itself. You should see that K⊕K=0, this is because each bit is being XORed with an identical copy of itself.

To see this, we'll start by saying that C = P⊕K, as above. Suppose we do the operation C⊕K, this is like doing (P⊕K)⊕K. As the order we do things doesn't matter, this is the same as P⊕(K⊕K). As K⊕K = 0, we find that this is P⊕0, which is P!

If you don't believe me, work it through for yourself with some of the previous examples that I used in earlier articles.

Now, suppose that we had two messages, P1 and P2, which are both XORed with the same key, K.

These produce C1 and C2, where C1=P1⊕K and C2=P2⊕K.

We, as cryptanalysts could compute A new message, C1⊕C2. This effectively removes the random key.

This is because C1⊕C2 is equal to (P1⊕K)⊕(P2⊕K).

Rearranging shows this is P1⊕P2⊕K⊕K, and as K⊕K is 0, we get P1⊕P2⊕0, which is just the same as P1⊕P2.

What we are left with is still unintelligable, but we know know that it is one real message XORed with another real message - we have sucked out the randomness, because the same randomness was used twice.

In the second world war, Tiltman used this 'removal of randomness' as a first step in cracking Lorenz.