89

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

9
  • 7
    What makes you think this is the case?
    – skaffman
    Commented Sep 4, 2009 at 15:31
  • 2
    Are you trying to ask "why do cryptographic algorithms only use XOR?" I've used XOR elsewhere... Commented Sep 4, 2009 at 15:33
  • 3
    Austin, he is not saying XOR isn't used elsewhere but XOR is the only one that is used as a method of encryption
    – Stephen Lacy
    Commented Sep 4, 2009 at 15:43
  • 1
    Keccak(now SHA-2) uses XOR, NOT, AND and ROT. Commented Nov 15, 2012 at 10:46
  • 1
    @Xz_awan It's not an encryption algorithm. It's a cryptographic hash function and thus a cryptographic algorithm. The SHA-2 compression function is built from a block cipher. | But I made a mistake in the above comment, I wanted to say "Keccak(now SHA-3) ...". Unlike Keccak, SHA-2 uses ADD in addition the the above operations. Commented Apr 17, 2014 at 7:15

13 Answers 13

80

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.


2
  • "If you have a longer string you can repeat your key until its long enough" - Could you please elaborate on that? I think simply repeating the key to encrypt a larger text is a really bad idea as patterns start to emerge. Commented Dec 16, 2015 at 23:23
  • 1
    @Tiago: certainly if this is supposed to be secure in any real sense repeating the key is a terrible idea. The classical way to do secure communication with XOR is with a "one time pad". You and the person you're communicating with have identical copies of an arbitrarily long notebook with random bits. You XOR as many bits as needed to send one message, and burn that part of the pad immediately after, never to be used again. This is logistically not feasible most of the time, so cleverer methods are needed in practice. XOR ciphers can be building blocks for better techniques. Commented Feb 9, 2016 at 1:35
68

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.

40

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.

4
  • 1
    This point is really important - as it holds for any distribution of bits in the message. The bits in the ciphertext will always be uniformly distributed, ensuring that statistical cryptanalysis techniques such as frequency analysis cannot be used to break the cipher.
    – mistertim
    Commented Jul 2, 2013 at 21:30
  • 1
    You need R1 and R2 to be independent for the result to be uniform (easy counter-example: R1 = R2).
    – rlandster
    Commented Mar 29, 2014 at 19:10
  • @rlandster correct, but I never mentioned they being dependent? they are random + R1 could be biased but R2 is pure random theoritically Commented Apr 1, 2014 at 5:17
  • 4
    This is the best answer here. R1 does not need to be random at all, and R1 could equal R2. As long as R2 is random, the result is indistinguishable from random. That's why XOR is the darling.
    – Jim Flood
    Commented May 13, 2015 at 21:54
31

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

0
6

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.

5

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

1
  • There is no reason why hashes should avoid reversible operations. Typically the main part of a hash function is reversible, and only in the end an irreversible operation is applied. Often that irreversible operation consists entirely out of XORs. Commented Nov 15, 2012 at 10:48
4

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.

3

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.

2

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.

2
  • 3
    There are more invertible instructions available on common CPUs: Rotation is one, integer multiplication by an odd integer is another one. All are used in some modern block ciphers. Commented Sep 5, 2009 at 16:58
  • I omitted rotation because it's not really suitable for crypto by itself. I never would have guessed that odd integer multiply was invertible.
    – Joshua
    Commented Sep 5, 2009 at 18:47
2

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
                        ------------------
2

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

2

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.

enter image description here

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.

enter image description here

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.