Why is XOR used in cryptography?

Why is only XOR used in cryptographic algorithms, and other logic gates like OR, AND, and NOR are not used?

It isn't exactly true to say that the logical operation XOR is the only one used throughout all cryptography, however it is the only two way encryption where it is used exclusively.

Here is that explained:

Imagine you have a string of binary digits 10101 and you XOR the string 10111 with it you get 00010

now your original string is encoded and the second string becomes your key if you XOR your key with your encoded string you get your original string back.

XOR allows you to easily encrypt and decrypt a string, the other logic operations don't.

If you have a longer string you can repeat your key until its long enough for example if your string was 1010010011 then you'd simple write your key twice and it would become 1011110111 and XOR it with the new string

Here's a wikipedia link on the XOR cipher.

---

I can see 2 reasons:

1. (Main reason) XOR does not leak information about the original plaintext.

2. (Nice-to-have reason) XOR is an involutory function, i.e., if you apply XOR twice, you get the original plaintext back (i.e, XOR(k, XOR(k, x)) = x, where x is your plaintext and k is your key). The inner XOR is the encryption and the outer XOR is the decryption, i.e., the exact same XOR function can be used for both encryption and decryption.

To exemplify the first point, consider the truth-tables of AND, OR and XOR:

And

0 AND 0 = 0

0 AND 1 = 0

1 AND 0 = 0

1 AND 1 = 1 (Leak!)

Or

0 OR 0 = 0 (Leak!)

0 OR 1 = 1

1 OR 0 = 1

1 OR 1 = 1

XOR

0 XOR 0 = 0

0 XOR 1 = 1

1 XOR 0 = 1

1 XOR 1 = 0

Everything on the first column is our input (ie, the plain text). The second column is our key and the last column is the result of your input "mixed" (encrypted) with the key using the specific operation (ie, the ciphertext).

Now, imagine an attacker got access to some encrypted byte, say: 10010111, and he wants to get the original plaintext byte.

Let's say the AND operator was used in order to generate this encrypted byte from the original plaintext byte. If AND was used, then we know for certain that every time we see the bit '1' in the encrypted byte then the input (ie, the first column, the plain text) MUST also be '1' as per the truth table of AND. If the encrypted bit is a '0' instead, we do not know if the input (ie, the plain text) is a '0' or a '1'. Therefore, we can conclude that the original plain text is: 1 _ _ 1 _ 111. So 5 bits of the original plain text were leaked (ie, could be accessed without the key).

Applying the same idea to OR, we see that every time we find a '0' in the encrypted byte, we know that the input (ie, the plain text) must also be a '0'. If we find a '1' then we do not know if the input is a '0' or a '1'. Therefore, we can conclude that the input plain text is: _ 00 _ 0 _ _ _. This time we were able to leak 3 bits of the original plain text byte without knowing anything about the key.

Finally, with XOR, we cannot get any bit of the original plaintext byte. Every time we see a '1' in the encrypted byte, that '1' could have been generated from a '0' or from a '1'. Same thing with a '0' (it could come from both '0' or '1'). Therefore, not a single bit is leaked from the original plaintext byte.

Main reason is that if a random variable with unknown distribution R1 is XORed with a random variable R2 with uniform distribution the result is a random variable with uniform distribution, so basically you can randomize a biased input easily which is not possible with other binary operators.

The output of XOR always depends on both inputs. This is not the case for the other operations you mention.

I think because XOR is reversible. If you want to create hash, then you'll want to avoid XOR.

XOR is the only gate that's used directly because, no matter what one input is, the other input always has an effect on the output.

However, it is not the only gate used in cryptographic algorithms. That might be true of old-school cryptography, the type involving tons of bit shuffles and XORs and rotating buffers, but for prime-number-based crypto you need all kinds of mathematics that is not implemented through XOR.

XOR acts like a toggle switch where you can flip specific bits on and off. If you want to "scramble" a number (a pattern of bits), you XOR it with a number. If you take that scrambled number and XOR it again with the same number, you get your original number back.

210 XOR 145 gives you  67  <-- Your "scrambled" result
 67 XOR 145 gives you 210  <-- ...and back to your original number

When you "scramble" a number (or text or any pattern of bits) with XOR, you have the basis of much of cryptography.

XOR uses fewer transistors (4 NAND gates) than more complicated operations (e.g. ADD, MUL) which makes it good to implement in hardware when gate count is important. Furthermore, an XOR is its own inverse which makes it good for applying key material (the same code can be used for encryption and decryption) The beautifully simple AddRoundKey operation of AES is an example of this.

For symmetric crypto, the only real choices operations that mix bits with the cipher and do not increase length are operations add with carry, add without carry (XOR) and compare (XNOR). Any other operation either loses bits, expands, or is not available on CPUs.

Let's consider the three common bitwise logical operators

Let's say we can choose some number (let's call it the mask) and combine it with an unknown value

• AND is about forcing some bits to zero (those that are set to zero in the mask)
• OR is about forcing some bits to one (those that are set to one in the mask)

XOR is more subtle you can't know for sure the value of any bit of the result, whatever the mask you choose. But if you apply your mask two times you get back your initial value.

In other words the purpose of AND and OR is to remove some information, and that's definitely not what you want in cryptographic algorithms (symmetric or asymmetric cipher, or digital signature). If you lose information you won't be able to get it back (decrypt) or signature would tolerate some minute changes in message, thus defeating it's purpose.

All that said, that is true of cryptographic algorithms, not of their implementations. Most implementations of cryptographic algorithms also use many ANDs, usually to extract individual bytes from 32 or 64 internal registers.

You typically get code like that (this is some nearly random extract of aes_core.c)

rk[ 6] = rk[ 0] ^
 (Te2[(temp >> 16) & 0xff] & 0xff000000) ^
 (Te3[(temp >>  8) & 0xff] & 0x00ff0000) ^
 (Te0[(temp      ) & 0xff] & 0x0000ff00) ^
 (Te1[(temp >> 24)       ] & 0x000000ff) ^
 rcon[i];
rk[ 7] = rk[ 1] ^ rk[ 6];
rk[ 8] = rk[ 2] ^ rk[ 7];
rk[ 9] = rk[ 3] ^ rk[ 8];

8 XORs and 7 ANDs if I count right

The XOR property (a xor b) xor b = a comes in handy for stream ciphers: to encrypt a n bit wide data, a pseudo-random sequence of n bits is generated using the crypto key and crypto algorithm.

Sender:
Data:                    0100 1010 (0x4A)
pseudo random sequence:  1011 1001 (0xB9)
------------------
ciphered data            1111 0011 (0xF3)
------------------

Receiver:
ciphered data            1111 0011 (0xF3)
pseudo random sequence:  1011 1001 (0xB9)  (receiver has key and computes same sequence)
------------------
0100 1010 (0x4A)  Data after decryption
------------------

XOR is a mathematical calculation in cryptography. It is a logical operation. There are other logical operations: AND, OR, NOT, Modulo Function etc. XOR is the most important and the most used.

If it's the same, it's 0.

If it's different, it's 1.

Example:

Message : Hello

Binary Version of Hello : 01001000 01100101 01101100 01101100 01101111

Key-stream : 110001101010001101011010110011010010010111

Cipher text using XOR : 10001110 11000110 00110110 10100001 01001010

Applications : The one-time pad/Vern-am Cipher uses the Exclusive or function in which the receiver has the same key-stream and receives the ciphertext over a covert transport channel. The receiver then Xor the ciphertext with the key-stream in order to reveal the plaintext of Hello. In One Time Pad, the key-stream should be at-least as long as the message.

Fact : The One Time Pad is the only truly unbreakable encryption.

Exclusive Or used in Feistel structure which is used in the block cipher DES algo.

Note : XOR operation has a 50% chance of outputting 0 or 1.

I think its simply because a given some random set of binary numbers a large number of 'OR' operations would tend towards all '1's, likewise a large number of 'AND' operations would tend towards all zeroes. Wheres a large number of 'XOR's produces a random-ish selection of ones and zeroes.

This is not to say that AND and OR are not useful - just that XOR is more useful.

The prevalence of OR/AND and XOR in cryptography is for two reasons:-

One these are lightning fast instructions.

Two they are difficult to model using conventional mathematical formulas