0
Posted June 30, 2012 by Spyros in Cryptography
 
 

How XOR Works and Why

table_xor_nor
table_xor_nor

The exclusive OR(xor) operation is probably one of the most used and misused operations, in terms of security or simple data encoding. It is quite normal for new computer programmers to confuse themselves with this instruction. It’s quite simple to understand what OR, AND are, but XOR seems a bit different. First of all, OR and AND make sense. OR is simply raising a bit if one bit of input OR the other bit of input is set. It’s one OR the other. Simple enough. Same with AND. If a AND b are both 1, then the result is 1, otherwise 0. Simple and straightforward, but why XOR is so weird ?

Well, XOR is actually an operation widely used in digital gates and is, in fact, a simple combination of the basic AND and OR operations. To illustrate, a XOR b is actually (a AND b’) OR (a’ AND b). In simply words, it’s the expression ‘either a or b, but not both of them’. Neither OR or AND can accomodate that by themselves. Therefore, XOR is actually a derivation of the two, in order to create a whole new scenario, the one where we need to get a or b as a result but not both of them. This is why 1 xor 1 = 0. The standard way to write the expression (a AND b’) OR (a’ AND b) is : ab’ + a’b. Let’s break it down to the four possible inputs and verify that it is indeed referring to XOR :

A = 0, B = 0 : A XOR B => AB' + A'B => (0 AND 0') OR (0' AND 0) = (0 AND 1) OR (1 AND 0) = 0 OR 0 = 0
A = 1, B = 0 : A XOR B => AB' + A'B => (1 AND 0') OR (1' AND 0) = (1 AND 1) OR (0 AND 0) = 1 OR 0 = 1
A = 0, B = 1 : A XOR B => AB' + A'B => (0 AND 1') OR (0' AND 1) = (0 AND 0) OR (1 AND 1) = 0 OR 1 = 1
A = 1, B = 1 : A XOR B => AB' + A'B => (1 AND 1') OR (1' AND 1) = (1 AND 0) OR (0 AND 1) = 0 OR 0 = 0

Notice that we actually got the same results we would get by simply using xor as we knew it works. The difference is that we know understand how and why it works like this. Careful when encrypting ! When using XOR to encrypt and secure, you should be careful on correctly evaluating two important properties of the operation, being :

1) When you xor A to B and get back C, you can recover A if you know B or B if you know A. Simply put, xor is an easily reversible function, where if you have the ciphertext and the key, you can easily get to the plaintext. Bear that in mind when you encrypt with XOR.

2) A possible even more important property is that when you XOR something with 0, you always get back the same value. This happens because 0 xor 0 = 0 and 1 xor 0 = 1. Therefore, you should avoid using zeroed bytes in your XOR operations. This is a security element that is strongly depicted in the one time pad cryptogram, where a new XOR pad is generated for each message and having zeroed bytes in it can clearly reveal the plaintext and thus, should be avoided.


Spyros