Skip to content

XOR

Table of contents

Open Table of contents

What it is

“Exclusive Or”, or XOR for short is a logical operator that can be found in a lot of cryptographic constructions.

This is due to XOR’s invertibility (the inverse of XOR is XOR itself) and its perfect balance of potential output values given their input values.

When used in a mathematical context, XOR is usually represented as the symbol \oplus. In programming languages you’ll often see the symbol ^ being used for bitwise XOR.

Truth table

To get a better understanding of the benefits the aforementioned properties provide we should start by looking at XOR’s truth table.

aabbaba \oplus b
000
011
101
110

The first two columns of the table show that we’re dealing with two variables aa and bb. The last column displays the result of computing aba \oplus b.

Each row shows one distinct combination of potential values aa and bb can assume. Given that we’re dealing with binary data, those values are either 00 or 11.

In total we have 22=42^2 = 4 rows that show all valid combinations (2 variables, each of which can assume 2 different values).

Translating the meaning of XOR into plain English, we can see that it means ”either this, or that is true, but not both at the same time”.

Properties

Invertibility

The first useful property is invertibility. The inverse of XOR is XOR itself.

This means that to undo an XOR operation that was computed on two values aa and bb we can XOR the result with aa to recover the value of bb or we can XOR the result with bb to recover the value of aa.

To get a better understanding as to why this is useful in Cryptography, let’s assume that we have a plaintext pp and a key kk.

Our ciphertext cc is the result of computing pkp \oplus k.

c=pkc = p \oplus k

Looking closer, we can see that the encryption algorithm is \oplus.

Given our ciphertext cc and the key kk how do we recover the plaintext pp? We just XOR the ciphertext cc with the key kk again.

p=ckp=pkkp=pkkp=p\begin{aligned} p &= c \oplus k \\ p &= p \oplus k \oplus k \\ p &= p \oplus \cancel{k} \oplus \cancel{k} \\ p &= p \end{aligned}

So the decryption algorithm is XOR as well.

This beneficial property is often used in symmetric ciphers such as the stream cipher ChaCha20 which uses \oplus during the encryption and decryption phase.

Perfectly Balanced

Another, very useful property of XOR is that it’s perfectly balanced.

Let’s take a look at the truth table from above to see what it means for XOR to be perfectly balanced.

Here we’ve modified the table slightly and renamed aa to pp and bb to kk. The reason being that we assume that pp is a plaintext bit and kk is a key bit. pkp \oplus k is therefore the resulting ciphertext bit.

ppkkpkp \oplus k
000
011
101
110

If we work under the assumption that the key generation algorithm produces a perfectly random value for kk (i.e. there’s a 50% chance that kk is either 00 or 11), we can see that this randomness is carried through to the ciphertext as its bit value is also either 00 or 11 with exactly 50% probability (again, depending on the key bit value kk).

ppkkpkp \oplus k
000
011
101
110

The exact same is true for when the plaintext bit pp is 11.

ppkkpkp \oplus k
000
011
101
110

So in conclusion we can see that if we get access to a ciphertext bit then there’s an exactly 50% chance that the input bit was either 00 or 11.

Therefore XOR is perfectly balanced.

Additional Resources