BestInternetSecurity.net

Some of my students have asked why we always use XOR (Exclusive OR) in encrypting plaintext into ciphertext. To answer this question, please take a look first at the output of the various combinations of inputs for XOR function.

Suppose we have a plaintext of 1100001111100 and a key of any arbitrary binary number 0001111001000 of the same length. If we XOR them together to give a ciphertext, the ciphertext is:

The XOR output is the ciphertext.

If we now apply the XOR function to the ciphertext with the same key:

The XOR output becomes the original plaintext.

So you can see, the XOR function serves exactly what a symmetric encryption does.

We encrypt (XOR) the original message into the cipher message with any chosen key. Then we can decrypt (XOR) the cipher message back to the original one with the same key.

If you study a lot of symmetric encryption algorithms like DES, you will note that XOR functions play a very important role in the encryption process.

Perhaps the safest encryption system we can now do with symmetric encryption is the so called “One-Time Pad.” This refers to using an infinite long key to XOR with your original message to give a cipher message. If you do not repeat the bit sequence of the encryption key used in your subsequent encryptions, then there is no way a hacker can uncover the original message from ciphertext unless s/he has the same set of one-time pad (the encryption key) that you have. Claude Shannon proved, using information theory considerations, that the one-time pad has the property he termed perfect secrecy.

But of course, practically, it’s not feasible if not impossible to use one-time pad. This is because the receiver needs to process the same identical one-time pad as what you have in order to decrypt the message. You may have a hard time transmitting the one-time pad to the receiver beforehand, considering that it has to be of a length that is long enough to fulfill your present and all future communication needs with the receiver.

The most interesting example of one-time pad I can think of is in the movie “Crimson Tide” with Denzel Washington. This movie is about a US Navy submarine. In the Navy, whenever a submarine is set out for a mission, it has to carry a pre-arranged decoding key (the one-time pad) for decoding the commander’s message sent to it during the mission’s journey. The one-time pad has to be long enough to cover the needs to decrypt all urgent messages of command within that journey. In this movie, the decoded message is about whether the submarine will launch the missile attack on its enemy which will provoke war! So you can see the decoding system is a crucial setup within the navy’s submarine operations.

Of course, whenever the submarine comes back to its base station, it has another chance to “refresh” the one-time pad stock to allow the decoding to be carried out in the next journey.

The one-time pad can never be reused. Otherwise, it will defeat its prime protection feature of being unbreakable by hackers because the keys used appear to be totally random in nature (as there is no repeating sequence). So there is no way the hacker can guess what it is.

And the random generator that generates each one-time pad has to be carefully designed. If somehow, it fails to produce a one-time pad with truly random combinations of 0s and 1s, the encryption key generated from it could be broken. Although I cannot locate the source anymore, I once came across some literature describing an instance during World War II, when the German’s one-time pad encryption system was broken because of an inherent weakness in its one-time pad generator that perhaps was generating one-time pads with statistical bias towards the bit sequence, allowing the allies to finally break the system.

Tags: pseudo-random number generator