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.
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.
Series Information
"More fun with XOR" is 25th in a larger sequence of 47 posts